Skip to content

Commit 9d943c3

Browse files
daachengdaacheng
committed
更新md
更新md
1 parent 44baaf4 commit 9d943c3

11 files changed

Lines changed: 307 additions & 0 deletions

‎leetcode_array/main.md‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,3 +14,13 @@
1414
12. [两数之和II-输入有序数组](两数之和II.md)
1515
13. [多数元素](多数元素.md)
1616
14. [旋转数组](旋转数组.md)
17+
15. [存在重复元素](存在重复元素.md)
18+
16. [存在重复元素II](存在重复元素II.md)
19+
17. [缺失数字](缺失数字.md)
20+
18. [移动零](移动零.md)
21+
19. [第三大的数](第三大的数.md)
22+
20. [找到所有数组中消失的数字](找到所有数组中消失的数字.md)
23+
21. [最大连续1的个数](最大连续1的个数.md)
24+
22. [斐波那契数](斐波那契数.md)
25+
23. [数组中的K-diff数对（逆向思维）](数组中的K-diff数对.md)
26+
24. [数组拆分I](数组拆分I.md)

‎leetcode_array/存在重复元素.md‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
给定一个整数数组，判断是否存在重复元素。
2+
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
3+
示例：
4+
5+
```python
6+
输入: [1,2,3,1]
7+
输出: true
8+
```
9+
代码
10+
```python
11+
class Solution:
12+
def containsDuplicate(self, nums: List[int]) -> bool:
13+
if len(set(nums)) == len(nums):
14+
return False
15+
return True
16+
```

‎leetcode_array/存在重复元素II.md‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
2+
示例：
3+
4+
```python
5+
输入: nums = [1,2,3,1], k = 3
6+
输出: true
7+
8+
输入: nums = [1,0,1,1], k = 1
9+
输出: true
10+
```
11+
12+
利用哈希表：
13+
14+
```python
15+
def containsNearbyDuplicate(nums, k):
16+
hash_ = {}
17+
for index, item in enumerate(nums):
18+
if item not in hash_:
19+
# 元素不存在，就保存元素及索引信息
20+
hash_[item] = index
21+
else:
22+
if index - hash_[item] <= k:
23+
# 遇到重复的且索引差满足条件直接返回True
24+
return True
25+
else:
26+
# 遇到重复的，但索引差不满足条件，更新索引
27+
hash_[item] = index
28+
return False
29+
```

‎leetcode_array/找到所有数组中消失的数字.md‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
2+
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
3+
示例：
4+
```python
5+
输入:
6+
[4,3,2,7,8,2,3,1]
7+
输出:
8+
[5,6]
9+
```
10+
#### 方法一：使用哈希表
11+
* 遍历数组，将元素存入字典中。
12+
* 遍历 1-n，判断哪个元素不存在字典。
13+
14+
```python
15+
def findDisappearedNumbers(nums):
16+
hash_table = {}
17+
dissappear_nums = []
18+
for num in nums:
19+
hash_table[num] = ''
20+
for item in range(1, len(nums)+1):
21+
if item not in hash_table:
22+
dissappear_nums.append(item)
23+
return dissappear_nums
24+
```
25+
26+
#### 方法二：原地遍历标记数组元素
27+
将出现的数字所在的下标的元素变成负数，这样遍历完输入数组之后，剩余的没有变成负数的下标就是缺失的数值。
28+
比如：
29+
```python
30+
[3, 3, 2, 1, 4, 5, 6, 4]
31+
第一个元素值为3，正常情况1~n [1, 2, 3, 4, 5, 6, 7, 8]
32+
3应该出现在索引2=3-1的位置上，所以把这个位置的数字变成负数。
33+
[3, 3, -2, 1, 4, 5, 6, 4]
34+
就表示这个数字已经出现过了。
35+
当遍历到-2时，其实也就是2，就把索引为1=2-1的元素变为负数，
36+
表示2这个数字已经出现过了。
37+
[3, -3, -2, 1, 4, 5, 6, 4],如此下去，
38+
所有出现过的元素，应该在的位置的数字全都变为负数了
39+
[-3, -3, -2, -1, -4, -5, 6, 4]
40+
所以，元素为正数的最后两位，实际也就是7，和8没有出现。
41+
```
42+
代码
43+
```python
44+
def findDisappearedNumbers(nums):
45+
disappear_nums = []
46+
for num in nums:
47+
num = abs(num)
48+
if nums[num-1] > 0:
49+
nums[num-1] = -nums[num-1]
50+
for index, item in enumerate(nums):
51+
if item > 0:
52+
disappear_nums.append(index+1)
53+
return disappear_nums
54+
```

‎leetcode_array/数组中的K-diff数对.md‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k。
2+
示例：
3+
```python
4+
输入: [3, 1, 4, 1, 5], k = 2
5+
输出: 2
6+
数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
7+
尽管数组中有两个 1，但我们只应返回不同的数对的数量。
8+
```
9+
方法：
10+
1. 遍历数组，两个集合，一个集合(diff)保存diff对中最小的元素，一个集合(saw)保存已经遍历过的元素。
11+
2. 如果x-k in saw,保存x-k到diff中。
12+
3. 如果x+k in saw,保存x到diff中。
13+
4. 返回diff的长度.
14+
```python
15+
def findPairs(nums, k):
16+
if k < 0:
17+
return 0
18+
diff = set()
19+
saw = set()
20+
for item in nums:
21+
if (item-k) in saw:
22+
diff.add(item-k)
23+
if (item+k) in saw:
24+
diff.add(item)
25+
saw.add(item)
26+
return len(diff)
27+
```

‎leetcode_array/数组拆分I.md‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。
2+
示例：
3+
```python
4+
输入: [1,4,3,2]
5+
输出: 4
6+
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
7+
```
8+
#### 方法一：排序 求和
9+
```python
10+
如果是min(a,b)总和最大，那排序后分组一定是相邻的两个一组。
11+
大数跟大数分一起，小数跟小数分一起。
12+
[1,2,3,4,5,6,7,8]
13+
[(1,2),(3,4),(5,6),(7,8)]
14+
```
15+
代码
16+
```python
17+
def arrayPairSum(nums):
18+
nums.sort()
19+
sum_ = 0
20+
for i in range(0, len(nums), 2):
21+
sum_ += nums[i]
22+
return sum_
23+
```

‎leetcode_array/斐波那契数.md‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
2+
```python
3+
F(0) = 0, F(1) = 1
4+
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
5+
```
6+
#### 递归：效率最低
7+
```python
8+
def fib(N):
9+
if N == 0:
10+
return 0
11+
elif N == 1:
12+
return 1
13+
return fib(N-1) + fib(N-2)
14+
```
15+
#### 自底向上计算：
16+
自底向上通过迭代计算，把结果保存在数组中
17+
```python
18+
def fib(N):
19+
res = [0, 1]
20+
for i in range(2, N+1):
21+
res.append(res[i-1] + res[i-2])
22+
return res[N]
23+
```

‎leetcode_array/最大连续1的个数.md‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
给定一个二进制数组， 计算其中最大连续1的个数。
2+
示例：
3+
```python
4+
输入: [1,1,0,1,1,1]
5+
输出: 3
6+
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
7+
```
8+
代码
9+
```python
10+
def findMaxConsecutiveOnes(nums):
11+
max_ones = 0
12+
tmp_max_ones = 0
13+
for item in nums:
14+
if item == 1:
15+
tmp_max_ones += 1
16+
else:
17+
max_ones = max(tmp_max_ones, max_ones)
18+
tmp_max_ones = 0
19+
max_ones = max(tmp_max_ones, max_ones)
20+
return max_ones
21+
```

‎leetcode_array/移动零.md‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
2+
示例：
3+
输入: [0,1,0,3,12]
4+
输出: [1,3,12,0,0]
5+
6+
暴力法：
7+
两个指针，从第一个元素开始遍历数组，如果是0，就与下一个不为0的元素交换位置
8+
```python
9+
def moveZeroes(nums):
10+
for i in range(0, len(nums)-1):
11+
for j in range(i+1, len(nums)):
12+
if nums[i] == 0 and nums[j] == 0:
13+
continue
14+
if nums[i] == 0 and nums[j] != 0:
15+
nums[i], nums[j] = nums[j], nums[i]
16+
if nums[i] != 0:
17+
break
18+
return nums
19+
```
20+
双指针：
21+
```python
22+
def moveZeroes(nums):
23+
i = 0
24+
for j in range(len(nums)):
25+
if nums[j]:
26+
# 不为0，就交换位置
27+
nums[i], nums[j] = nums[j], nums[i]
28+
i += 1
29+
```

‎leetcode_array/第三大的数.md‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
2+
示例：
3+
```python
4+
输入: [2, 2, 3, 1]
5+
输出: 1
6+
解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
7+
存在两个值为2的数，它们都排第二。
8+
9+
输入: [1, 2]
10+
输出: 2
11+
解释: 第三大的数不存在, 所以返回最大的数 2 .
12+
```
13+
#### 方法一：去重，排序
14+
```python
15+
def thirdMax(nums):
16+
nums = list(set(nums))
17+
nums.sort()
18+
if len(nums) >= 3:
19+
return nums[-3]
20+
else:
21+
return nums[-1]
22+
```
23+
#### 方法二：定义三个变量存储最大的三个数
24+
```python
25+
def thirdMax(nums):
26+
max_1 = float('-inf')
27+
max_2 = float('-inf')
28+
max_3 = float('-inf')
29+
for item in nums:
30+
if item > max_1:
31+
# 第一大的数更新后，原来的第一大变为第二大，第二大变为第三大
32+
max_3 = max_2
33+
max_2 = max_1
34+
max_1 = item
35+
elif max_2 < item < max_1:
36+
# 第二大的数更新后，原来的第二大变为第三大
37+
max_3 = max_2
38+
max_2 = item
39+
elif max_3 < item < max_2:
40+
max_3 = item
41+
if max_3 == float('-inf'):
42+
return max_1
43+
return max_3
44+
```

0 commit comments

Comments
 (0)