Skip to content

Commit 9eadc7d

Browse files
daachengdaacheng
committed
更新md
更新md
1 parent df13139 commit 9eadc7d

14 files changed

Lines changed: 419 additions & 0 deletions

‎leetcode_array/main.md‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,16 @@
11
## LeetCode数组
22
1. [两数之和](两数之和.md)
3+
34
2. [删除排序数组中的重复项](删除排序数组中的重复项.md)
45
3. [移除元素](移除元素.md)
6+
4. [搜索插入位置](搜索插入位置.md)
7+
5. [最大子序和](最大子序和.md)
8+
6. [加一](加一.md)
9+
7. [合并两个有序数组](合并两个有序数组.md)
10+
8. [杨辉三角](杨辉三角.md)
11+
9. [杨辉三角 II](杨辉三角II.md)
12+
10. [买卖股票的最佳时机](买卖股票的最佳时机.md)
13+
11. [买卖股票的最佳时机II](买卖股票的最佳时机II.md)
14+
12. [两数之和II-输入有序数组](两数之和II.md)
15+
13. [多数元素](多数元素.md)
16+
14. [旋转数组](旋转数组.md)

‎leetcode_array/两数之和II.md‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
## 两数之和II
2+
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
3+
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
4+
示例：
5+
```python
6+
输入: numbers = [2, 7, 11, 15], target = 9
7+
输出: [1,2]
8+
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
9+
```
10+
#### 方法一：哈希表，时间复杂度O(n),空间复杂度O(n)
11+
```python
12+
def twoSum(numbers, target):
13+
num_dict = {}
14+
for i, item in enumerate(numbers):
15+
other = target - item
16+
if other not in num_dict:
17+
num_dict[item] = i
18+
continue
19+
else:
20+
return [num_dict[other]+1, i+1]
21+
return []
22+
```
23+
24+
#### 方法二：利用两个指针，同时利用数组已经排序的这个特点
25+
* 一个指针指向头部，一个指针指向尾部
26+
* 如果和大于目标值，尾部的指针向前运动
27+
* 如果和小于目标值，头部指针向后运动
28+
29+
```python
30+
def twoSum(numbers, target):
31+
left_index = 0
32+
right_index = len(numbers)-1
33+
while left_index < right_index:
34+
if numbers[left_index] + numbers[right_index] > target:
35+
right_index -= 1
36+
elif numbers[left_index] + numbers[right_index] < target:
37+
left_index += 1
38+
else:
39+
return [left_index+1, right_index+1]
40+
return []
41+
```

‎leetcode_array/买卖股票的最佳时机.md‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
## 买卖股票的最佳时机
2+
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
3+
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
4+
示例：
5+
6+
```python
7+
输入: [7,1,5,3,6,4]
8+
输出: 5
9+
解释: 在第2天（股票价格=1）的时候买入，在第5天（股票价格=6）的时候卖出，最大利润=6-1= 5。
10+
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
11+
```
12+
#### 暴力法 时间复杂度O(n2)，会超出时间限制：
13+
* 找出给定数组中两个数字之间的最大差值（即，最大利润）
14+
* 第二个数字（卖出价格）必须大于第一个数字（买入价格）。
15+
```python
16+
def maxProfit(prices):
17+
max_profit = 0
18+
for i in range(0, len(prices)):
19+
for j in range(i+1, len(prices)):
20+
max_profit = max(prices[j]-prices[i], max_profit)
21+
return max_profit
22+
```
23+
#### 方法二：一次遍历，同时记录最小值与最大利润
24+
* 记录历史股票最低价格，这个价格是相对于当前遍历而言，遍历没结束，不一定是列表最小值。
25+
* 记录当前天数的股票价格与历史最低价格的差值，来记录最大利润。
26+
27+
```python
28+
def maxProfit(prices):
29+
if not prices:
30+
return 0
31+
min_price = prices[0]
32+
max_profit = 0
33+
for price in prices[1:]:
34+
# 纪录最小价格
35+
if price < min_price:
36+
min_price = price
37+
# 记录最大利润
38+
if price - min_price > max_profit:
39+
max_profit = price - min_price
40+
return max_profit
41+
```

‎leetcode_array/买卖股票的最佳时机II.md‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
## 买卖股票的最佳时机 II
2+
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
3+
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
4+
示例：
5+
```python
6+
输入: [7,1,5,3,6,4]
7+
输出: 7
8+
解释: 在第2天（股票价格=1）的时候买入，在第3天（股票价格=5）的时候卖出,
9+
这笔交易所能获得利润=5-1=4 ，随后，在第 4 天（股票价格 = 3）的时候买入，
10+
在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
11+
```
12+
13+
分析：
14+
15+
如果是[1,2,3,4,5],最大利润=5-1=(2-1)+(3-2)+(4-3)+(5-4)
16+
17+
只要后一天的价格比前一天的价格高，就可以进行交易，盈利，最后计算总利润。
18+
19+
代码：
20+
```python
21+
def maxProfit(prices):
22+
if not prices:
23+
return 0
24+
max_profit = 0
25+
for i in range(0, len(prices)-1):
26+
if prices[i+1] - prices[i] > 0:
27+
max_profit += prices[i+1] - prices[i]
28+
return max_profit
29+
```

‎leetcode_array/加一.md‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
## 加一
2+
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
3+
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
4+
你可以假设除了整数 0 之外，这个整数不会以零开头。
5+
示例：
6+
```python
7+
输入: [4,3,2,1]
8+
输出: [4,3,2,2]
9+
解释: 输入数组表示数字 4321。
10+
```
11+
#### 方法一：类型转换
12+
```python
13+
def plusOne(digits):
14+
num = int(''.join([str(i) for i in digits])) + 1
15+
return [i for i in str(num)]
16+
```
17+
#### 方法二：直接进行数学运算，只有+1=10的情况下才会进位
18+
```python
19+
def plusOne(digits):
20+
# 从个位数开始+1，如果等于10，就取余向前进一位
21+
# 如果不等于10直接返回
22+
for i in range(len(digits)-1, -1, -1):
23+
digits[i] += 1
24+
digits[i] %= 10
25+
if digits[i] != 0:
26+
return digits
27+
digits.insert(0, 1)
28+
return digits
29+
```

‎leetcode_array/合并两个有序数组.md‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
## 合并两个有序数组
2+
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
3+
说明:
4+
5+
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
6+
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
7+
8+
示例：
9+
```python
10+
输入:
11+
nums1 = [1,2,3,0,0,0], m = 3
12+
nums2 = [2,5,6], n = 3
13+
14+
输出: [1,2,2,3,5,6]
15+
```
16+
#### 双指针法，从后往前遍历，哪个元素大就把这个元素放在最后：
17+
18+
```python
19+
def merge(nums1, m, nums2, n):
20+
p1 = m - 1
21+
p2 = n - 1
22+
p = m + n -1
23+
while p1 >= 0 and p2 >= 0:
24+
if nums1[p1] >= nums2[p2]:
25+
nums1[p] = nums1[p1]
26+
p1 -= 1
27+
p -= 1
28+
else:
29+
nums1[p] = nums2[p2]
30+
p2 -= 1
31+
p -= 1
32+
if p1 < 0:
33+
nums1[:p2+1] = nums2[:p2+1]
34+
if p2 < 0:
35+
pass
36+
return nums1
37+
```

‎leetcode_array/多数元素.md‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
## 多数元素
2+
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
3+
示例：
4+
```python
5+
输入: [2,2,1,1,1,2,2]
6+
输出: 2
7+
```
8+
#### 方法一：利用哈希表统计元素个数，时间复杂度O(n)
9+
```python
10+
def majorityElement(nums):
11+
count_dict = {}
12+
for item in nums:
13+
count_dict[item] = count_dict.get(item, 0) + 1
14+
if count_dict[item] > len(nums)/2:
15+
return item
16+
```
17+
18+
#### 方法二：排序
19+
将数组按照从小到大或从大到小排序后，位于len(nums)/2位置上的数一定是多数元素。
20+
* [1, 1, 1, 2, 2, 2, 2, 2]， 7//2 = 3
21+
* [1, 1, 1, 2, 2, 2, 2] 6//2 = 3
22+
23+
```python
24+
def majorityElement(nums):
25+
nums.sort()
26+
return nums[len(nums)//2]
27+
```

‎leetcode_array/搜索插入位置.md‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
## 搜索插入位置
2+
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
3+
你可以假设数组中无重复元素
4+
示例：
5+
```Python
6+
输入: [1,3,5,6], 5
7+
输出: 2
8+
```
9+
#### 方法一：遍历，穷举所有情况
10+
时间复杂度O(n)
11+
```python
12+
def searchInsert(nums, target):
13+
if not nums:
14+
return 0
15+
if target < nums[0]:
16+
return 0
17+
if target > nums[-1]:
18+
return len(nums)
19+
if target == nums[-1]:
20+
return len(nums)-1
21+
for i in range(len(nums)-1):
22+
if target == nums[i]:
23+
return i
24+
if nums[i] < target and target < nums[i+1]:
25+
return i + 1
26+
```
27+
28+
#### 方法二：二分查找
29+
* 时间复杂度O(logn)
30+
* 设定坐下标left和右下标right，计算中间下标mid。
31+
* nums[mid]等于目标值，直接返回mid。
32+
* nums[mid]大于目标值，则right左移。
33+
* nums[mid]小于目标值，则left右移。
34+
* 查找结束没有值相等，返回left。
35+
36+
```python
37+
def searchInsert(nums, target):
38+
left = 0
39+
right = len(nums) - 1
40+
while left <= right: # 循环结束的条件
41+
mid = (left+right)//2
42+
if nums[mid] == target:
43+
return mid
44+
elif target < nums[mid]:
45+
right = mid -1
46+
elif target > nums[mid]:
47+
left = mid + 1
48+
return left
49+
```

‎leetcode_array/旋转数组.md‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
## 旋转数组
2+
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
3+
示例：
4+
```python
5+
输入: [1,2,3,4,5,6,7] 和 k = 3
6+
输出: [5,6,7,1,2,3,4]
7+
解释:
8+
向右旋转 1 步: [7,1,2,3,4,5,6]
9+
向右旋转 2 步: [6,7,1,2,3,4,5]
10+
向右旋转 3 步: [5,6,7,1,2,3,4]
11+
```
12+
13+
解析：
14+
15+
```python
16+
三步反转：
17+
[1,2,3,4,5,6,7]
18+
# 第一步，反转整个数组
19+
[7,6,5,4,3,2,1]
20+
# 第二步，反转nums[:k]
21+
[5,6,7,4,3,2,1]
22+
# 第三步，反转nums[k:]
23+
[5,6,7,1,2,3,4]
24+
```
25+
26+
代码：
27+
28+
```python
29+
def rotate(nums, k):
30+
length = len(nums)
31+
k = k%length
32+
if k == 0:
33+
return nums
34+
nums[:] = nums[::-1]
35+
nums[:k] = nums[:k][::-1]
36+
nums[k:] = nums[k:][::-1]
37+
return nums
38+
```

‎leetcode_array/最大子序和.md‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
## 最大子序和
2+
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
3+
示例：
4+
5+
```python
6+
输入: [-2,1,-3,4,-1,2,1,-5,4],
7+
输出: 6
8+
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
9+
```
10+
如果当前元素的前一个元素大于0，就将当前元素加上前一个元素。例如：
11+
```python
12+
[-2,1,-3,4,-1,2,1,-5,4]
13+
[-2,1,-2,4, 3,5,6, 1,5]
14+
```
15+
代码:
16+
```python
17+
def maxSubArray(nums):
18+
for i in range(1, len(nums)):
19+
if nums[i-1] > 0:
20+
nums[i] += nums[i-1]
21+
return max(nums)
22+
```

0 commit comments

Comments
 (0)