Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6afe9d0

Browse files
author
lixiang.2533
committed
add new answers
Change-Id: Ib413119076014fff9d0bdfbd8dda2b4d83c61adb
1 parentae09862 commit6afe9d0

File tree

83 files changed

+22764
-384
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

83 files changed

+22764
-384
lines changed

‎.DS_Store

0 Bytes
Binary file not shown.

‎merge_md.md

Lines changed: 0 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -1,42 +1,3 @@
1-
```python
2-
import os
3-
from globimport glob
4-
5-
dirs= os.listdir('/Users/lixiang.2533/Desktop/Blogs/Leetcode/')
6-
dir='/Users/lixiang.2533/Desktop/Blogs/Leetcode'
7-
dirs= ['动态规划','栈','回溯']
8-
for ain dirs:
9-
md_list= glob(os.path.join(dir, a,'*.md'))
10-
md_list=sorted(md_list)
11-
contents= []
12-
file_name= [i.split('/')[-1].split('.md')[0]for iin md_list]
13-
file_name=dict([(i.split('.')[0], i)for iin file_name])
14-
## 给总结md加入title
15-
withopen(md_list[0],'r')as f:
16-
lines= f.readlines()
17-
new_lines= []
18-
for iin lines:
19-
if i.strip():
20-
nums= i.split('-')[1]
21-
if nums.isdigit():
22-
new_lines.append(' -'+ file_name.get(nums, nums)+'\n')
23-
else:
24-
new_lines.append('-'+ file_name.get(nums, nums)+'\n')
25-
26-
withopen(md_list[0],'w')as f:
27-
f.writelines(new_lines)
28-
for mdin md_list:
29-
md_name= md.split('/')[-1]
30-
contents.append('###'+ md_name+"\n")
31-
withopen(md,'r')as f:
32-
contents.append(f.read()+"\n")
33-
34-
withopen(os.path.join(dir,"{}总结.md".format(a)),"w")as f:
35-
f.writelines(contents)
36-
```
37-
38-
39-
401
```
412
dirs = os.listdir('/Users/lixiang.2533/Desktop/Blogs/Leetcode/')
423
dir = '/Users/lixiang.2533/Desktop/Blogs/Leetcode'

‎个人项目总结.pdf

162 KB
Binary file not shown.

‎二分法/0.二分法总结.md

Lines changed: 18 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,22 @@
11
- 找target
2-
- 69 x 的平方根：牛顿法
3-
- 74 搜索二维矩阵
4-
- 367 有效的完全平方数：牛顿法
5-
- 374 猜数字大小
6-
- 704 二分查找
2+
-[ ]69 x 的平方根：牛顿法
3+
-[ ]74 搜索二维矩阵
4+
-[ ]367 有效的完全平方数：牛顿法
5+
-[ ]374 猜数字大小
6+
-[ ]704 二分查找
77
- 找边界
8-
- 34 在排序数组中查找元素的第一个和最后一个位置：注意判断是否存在该元素
9-
- 35 搜索插入位置
10-
- 278 第一个错误的版本
11-
- 441 排列硬币
8+
-[ ]34 在排序数组中查找元素的第一个和最后一个位置：注意判断是否存在该元素
9+
-[ ]35 搜索插入位置
10+
-[ ]278 第一个错误的版本
11+
-[ ]441 排列硬币
1212
- 有技巧的二分法
13-
- 29 两数相除
13+
14+
-[ ] 4 寻找两个正序数组的中位数：收缩区间法
15+
-[ ] 29 两数相除
1416
- 旋转数组
15-
- 33 搜索旋转排序数组：左右闭区间，
16-
- 81 搜索旋转排序数组 II：在33的基础上对所有mid=left/right无法判断搜索方向的场景跳过
17-
- 153 寻找旋转排序数组中的最小值：开区间，只能和右边界进行判断，避免从小值跳到大值
18-
- 162 寻找峰值：通过mid左右值大小判断搜索方向
19-
- 240 搜索二维矩阵 II：Z字形搜索（每个点都有唯一的搜索方向）
17+
-[ ] 33 搜索旋转排序数组：左右闭区间，
18+
-[ ] 81 搜索旋转排序数组 II：在33的基础上对所有mid=left/right无法判断搜索方向的场景跳过
19+
-[ ] 153 寻找旋转排序数组中的最小值：开区间，只能和右边界进行判断，避免从小值跳到大值
20+
-[ ] 162 寻找峰值：通过mid左右值大小判断搜索方向
21+
-[ ] 240 搜索二维矩阵 II：Z字形搜索（每个点都有唯一的搜索方向）
22+
-[ ] 287 寻找重复数

‎二分法/287. 寻找重复数.md

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
给定一个包含 n + 1 个整数的数组 nums ，其数字都在[1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
2+
3+
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
4+
5+
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
6+
7+
8+
9+
示例 1：
10+
11+
输入：nums =[1,3,4,2,2]
12+
输出：2
13+
14+
示例 2：
15+
16+
输入：nums =[3,1,3,4,2]
17+
输出：3
18+
19+
20+
21+
提示：
22+
23+
1 <= n <= 105
24+
nums.length == n + 1
25+
1 <= nums[i] <= n
26+
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
27+
28+
29+
30+
31+
进阶：
32+
33+
如何证明 nums 中至少存在一个重复的数字?
34+
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
35+
36+
37+
38+
```python
39+
classSolution:
40+
deffindDuplicate(self,nums: List[int]) ->int:
41+
defcheck(i):
42+
cnt=0
43+
for nin nums:
44+
if n<=i:
45+
cnt+=1
46+
return cnt<=i
47+
left=0
48+
right=len(nums)-1
49+
while left<right:
50+
mid=(left+right)//2
51+
if check(mid):
52+
left= mid+1
53+
else:
54+
right=mid
55+
return right
56+
```
57+
58+
59+
60+
Tips
61+
62+
隐形的二分搜索题，通过判断nums中小于mid的部分是否可能存在重复，来缩小搜索区间，需要使用二分单纯是为了不使用额外的内存空间
Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
2+
3+
算法的时间复杂度应该为 O(log (m+n)) 。
4+
5+
6+
7+
示例 1：
8+
9+
输入：nums1 =[1,3], nums2 =[2]
10+
输出：2.00000
11+
解释：合并数组 =[1,2,3] ，中位数 2
12+
13+
示例 2：
14+
15+
输入：nums1 =[1,2], nums2 =[3,4]
16+
输出：2.50000
17+
解释：合并数组 =[1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
18+
19+
示例 3：
20+
21+
输入：nums1 =[0,0], nums2 =[0,0]
22+
输出：0.00000
23+
24+
示例 4：
25+
26+
输入：nums1 =[], nums2 =[1]
27+
输出：1.00000
28+
29+
示例 5：
30+
31+
输入：nums1 =[2], nums2 =[]
32+
输出：2.00000
33+
34+
35+
36+
提示：
37+
38+
nums1.length == m
39+
nums2.length == n
40+
0 <= m <= 1000
41+
0 <= n <= 1000
42+
1 <= m + n <= 2000
43+
-106 <= nums1[i], nums2[i] <= 106
44+
45+
46+
47+
```python
48+
classSolution:
49+
deffindMedianSortedArrays(self,nums1: List[int],nums2: List[int]) ->float:
50+
defhelper(k):
51+
index1, index2=0,0
52+
whileTrue:
53+
# 其中一个数组已经遍历完
54+
if index1==l1:
55+
return nums2[index2+k-1]
56+
if index2==l2:
57+
return nums1[index1+k-1]
58+
if k==1:
59+
returnmin(nums1[index1], nums2[index2])
60+
61+
newindex1=min(index1+ k//2-1, l1-1)#右边界是闭区间 取min避免指针越界
62+
newindex2=min(index2+ k//2-1, l2-1)
63+
if nums1[newindex1]<=nums2[newindex2]:
64+
k-= newindex1-index1+1#双闭区间，右-左+1
65+
index1= newindex1+1
66+
else:
67+
k-= newindex2- index2+1# 双闭区间，右-左+1
68+
index2= newindex2+1
69+
70+
l1=len(nums1)
71+
l2=len(nums2)
72+
total= l1+l2
73+
if total%2==1:
74+
return helper(total//2+1)# k是第几个元素，是index+1
75+
else:
76+
return (helper(total//2)+ helper(total//2+1))/2
77+
```
78+
79+
80+
81+
Tips
82+
83+
- K=7，中位数就是排名第4的数字（k//2+1）
84+
- 这里的二分搜索通过比较nums1[index1], nums2[index2]的大小，较小的一方如果是nums1[index1]则index1之前的元素都不可能是中位数，可以从搜索范围内剔除，同时K也会跟着缩小。
85+
- 最难处理的部分是边界问题
86+
- Nums1，Nums2任意一个碰到边界，直接返回另一个的对应位置
87+
- 搜索时双闭区间

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp