普通数组
动态规划
首先需要知道的是，之所以使用dp是因为当前有两种选择，要么之前的总和拖累了当前，只选择当前。要么之前的总和加当前
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0]*len(nums)
ans = 0
for i in range(len(nums)):
if i == 0:
dp[i] = nums[i]
else:
dp[i] = max(nums[i], nums[i]+dp[i-1])
return max(dp)
|
数组操作
记得先排序
在ans中操作，不要操作完了再传入ans
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals = sorted(intervals)
ans = []
ans.append(intervals[0])
for i in range(1, len(intervals)):
if intervals[i][0] > ans[-1][1]:
ans.append(intervals[i])
else:
ans[-1][1] = max(ans[-1][1], intervals[i][1])
return ans
|
三步反转法！！！
- 反转整个数组
- 反转前k个元素
- 反转后n-k个元素
需要注意k可能比n大的多的多的多，所以需要取余，即k % n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def rotate(self, nums: list[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
k = k % len(nums)
reverse(0, len(nums)-1)
reverse(0, k-1)
reverse(k, len(nums)-1)
|
前缀🐔
注意两个前缀🐔是从左到右和从右到左即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
left_prex, right_prex, ans = [1] * n, [1] * n, [1] * n
for i in range(n):
if i == 0:
left_prex[i] = 1
else:
left_prex[i] = left_prex[i-1] * nums[i-1]
for i in range(n-1, -1, -1):
if i == n-1:
right_prex[i] = 1
else:
right_prex[i] = right_prex[i+1] * nums[i+1]
for i in range(n):
ans[i] = left_prex[i] * right_prex[i]
return ans
|
原地哈希
这题说难难，说简单也简单，将数组下标与值做一个映射（i-1<->nums[i]），不过在判断移位时
- 在判断中需要满足两个条件，第一个是在数组长度之内，第二个如果需要置换，两个不能相同
- 需要一个tmp，一行写不行
- 都满足返回一个n+1不要忘了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[i] != nums[nums[i]-1]:
j = nums[i]-1
nums[i], nums[j] = nums[j], nums[i]
for i in range(n):
if i+1 != nums[i]:
return i+1
return n+1
|
