-
变量定义：nums 数组，target 查找或插入的目标值
-
搜索区间是否为空：
- left = 0，right = len(nums)，此时查找区间为 [left, right] 闭区间，那么while中的终止条件应该是 left >= right，因为当 left == right 时，闭区间 [left, right] 不为空，还可以取;
- left = 0，right = len(nums) - 1，此时查找区间为 [left, right) 左闭右开区间，那么while中的终止条件应该是 left > right，因为当 left == right 时，左闭右开区间 [left, right) 不为空，不能再取了;
-
中间值的取法：
- 为防止内存溢出的情况，中间下标为 mid = left + (right - left) // 2
-
nums[mid] 的值不等于 target 的情况：
- 如果搜索区间是闭区间，当 nums[mid] > target, 或 nums[mid] < target 时，则分别对应 right = mid - 1 和 left = mid + 1。当要使用mid更新left，right时，由于是闭区间，终止条件中已经说明了mid和target下标的关系，也就是说left和right位置的值已经和target比较过了，应该move on了，所以left和right更新时应该考虑+1或者-1；跳出循环时，left指向target插入位置，返回left；
- 如果搜索区间是左闭右开区间，当 nums[mid] > target, 或 nums[mid] < target 时，则分别对应 right = mid 和 left = mid + 1。当要使用mid更新left，right时，由于是左闭右开区间，并没有比较right位置的值和target谁大谁小，应该令right=mid，left不变；跳出循环时，left指向target插入位置，返回left
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if len(nums) < 1: return 0
left = 0
right = len(nums) - 1 # 这里使用闭区间
while(left <= right): # left <= right 闭区间
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1 # 闭区间
else:
left = mid + 1
return right + 1- 题目输入的是一个数组和移除值，返回的是遍历完成后数组的长度（移除完成后的长度）
- 因为字符在内存中以连续空间存储，如果移除值在数组中出现，则需要将后面的值往前移，覆盖这个值，不能直接删除
- 使用快慢指针，两指针同时移动，
- 当数组中遍历到的值等于移除值时，需要将快指针+1；
- 当数组中遍历到的值不等于移除值时，将快指针对应的值赋值给慢指针对应的值（这可以看作是连续赋值）
- 当快指针走到头时，说明一遍就遍历完了，那么慢指针所在的位置，即是遍历移除后这个数组的长度
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# 使用快慢指针，可以在O(n)下完成循环
slow, fast = 0, 0
while (fast < len(nums)):
if val != nums[fast]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slowclass Solution:
def pivotIndex(self, nums: List[int]) -> int:
if len(nums) == 0: return -1
s = sum(nums)
for i in range(len(nums)):
if sum(nums[:i])*2 + nums[i] == s:
return i
return -1- 注意sort的排序用法
- 每次更新的对象其实是上一个区间，也就是说每次遍历的对象是当前区间，根据当前区间的左边界是否大于上一个区间的右边界来判断
- 如果小于，则两个区间有重合，更新上一个区间时，其左边界取【上一个右边界】和【当前区间右边界】的最大值
- 如果大于，则两个区间没有重合，上一个区间就是独立区间（添加到结果中），将当前区间变为上一个区间
- 最后别忘了，要把最后一个区间添加到结果中
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# 首先是有序，判断区间内的第二个数是否在下一个区间内，如果在则可以合并；
intervals.sort(key=lambda x:x[0]) # 对左边区间进行排序
last = intervals[0].copy()
res = []
for i in range(1, len(intervals)):
if intervals[i][0] <= last[1]:
# 包含重叠的情况，值更新last，下次备用
last[1] = max(last[1], intervals[i][1])
else:
# 不包含重叠的情况，将当前last加入结果，然后再更新last
res.append(last)
last = intervals[i].copy()
# 对于intervals只有一个数组的情况下，这里可以将last添加进结果中
res.append(last)
return res- 数组排序的目的是使得数组有序，并简化步骤。由于要求三数之和为0，根据左右指针的定义，如果当前值nums[i] > 0，后面的就不必计算了，一定和是大于0的。
- 双指针的目的：1. 固定 i 的情况下遍历剩下的数组，2.避免重复计算。
- 指定左指针为 i+1, 右指针为 n-1 ，只要满足 L < R 的条件，且三数之和为0，此时需要判断当前 nums[i] 是否等于下一个 nums[i]（L 往右遍历，R 向左遍历），如果是，则需要更新 L 和 R 的位置
- 如果三数之和大于0，则说明 R 大了，更新 R 的位置
- 如果三数之和小于0，则说明 L 小了，更新 L 的位置
- 避免重复计算时，会比较 【i，i-1】，【L，L+1】，【R，R-1】的大小，此时需要给出边界条件，避免出现溢出的情况
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) <= 2 or not nums: return []
res = []
n = len(nums)
nums.sort()
for i in range(n):
if nums[i] > 0:
return res
if (i > 0 and nums[i] == nums[i-1]):
# 注意这种情况，排序过后先处理 i-1 位置的，然后才处理 i
# 如果nums[i-1]和nums[i]相等，直接让 i-1 变为 i+1，即跳过i，下面对L和R的处理相同
continue
L = i + 1
R = n - 1
while(L < R):
if nums[i] + nums[L] + nums[R] == 0:
res.append([nums[i], nums[L], nums[R]])
# while 条件 L<R 给出了一个边界，使得 L+1 没有超出边界
while(L<R and nums[L] == nums[L+1]):
L += 1
while(L<R and nums[R] == nums[R-1]):
R -= 1
L += 1
R -= 1
elif nums[i] + nums[L] + nums[R] > 0:
R -= 1
else:
L += 1
return res- 状态：随着新加入的一个数，连续数组的和为变量
- 选择：新加入的数 nums[i] 与前面的和合并？还是自己作为一个新的序列
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 使用动态规划
if len(nums) < 2: return nums[0]
# 状态：（变量）子序和
# 选择：当前元素（1）与前面的数组进行结合（2）自己开始一个新数组
# 席间dp数组，定义dp[i] 表示前i个数组成的数组中的最大子序和
dp = nums
for i in range(1, len(nums)):
dp[i] = max(dp[i-1] + nums[i], nums[i])
return max(dp)- 两个指针p1，p2分别从两数组的末尾开始遍历，p为nums1的空间末尾指针，比较p1，p2对应的值，谁大，谁就赋值给p对应的值，直到p1或p2小于0
- 注意最后，p2需要将剩余没遍历的数替换掉nums1中没遍历的值
- 复杂度分析：
- 空间复杂度：O（1）
- 时间复杂度：O（m+n）
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
# two get pointers for nums1 and nums2
p1 = m - 1
p2 = n - 1
# set pointer for nums1
p = m + n - 1
# while there are still elements to compare
while p1 >= 0 and p2 >= 0:
if nums1[p1] < nums2[p2]:
nums1[p] = nums2[p2]
p2 -= 1
else:
nums1[p] = nums1[p1]
p1 -= 1
p -= 1
# add missing elements from nums2
# 注意，这里的nums1括号内的指针是p2而不是p，因为如果走到这一步，p1已经结束了，并且p=p1+p2，所以剩下的就是将[:p2+1]全部赋值过去
nums1[:p2 + 1] = nums2[:p2 + 1]- 复杂度分析：
- 时间复杂度：O(log(m+n))
- 空间复杂度：O(1)
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def getKthElement(k):
"""
- 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
- 这里的 "/" 表示整除
- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
- 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
- 这样 pivot 本身最大也只能是第 k-1 小的元素
- 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部"删除"，剩下的作为新的 nums1 数组
- 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部"删除"，剩下的作为新的 nums2 数组
- 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
- 注意：
- 如果 k = 1，则返回两数组中0位置(即第1小的数)小的那个数，就是中位数
- 如果一个指针走到头，就返回另一数组中第k小的数
"""
# 这里的k就表示中位数的下标+1（因为k是根据m和n（数组长度）算出来的），
# 设定两个指针都是指向两个不断更新的有序数组的头，即每个更新后的数组的0位置
index1, index2 = 0, 0
while True:
# 特殊情况：如果一个数组的指针走到头了，那么就返回另一个数组的第k小的数
if index1 == m:
# idx2 表示删除后的数组，该数组从头开始算的第 idx2+k 个数，-1表示这个数的下标
return nums2[index2 + k - 1]
if index2 == n:
return nums1[index1 + k - 1]
if k == 1:
# 第1小的k对应的数就是中位数了，返回当前指针下，两个数组中较小的数
return min(nums1[index1], nums2[index2])
# 正常情况，分别将指针定位到第k小的数的位置，生成新指针（注意这里的k//2）
newIndex1 = min(index1 + k // 2 - 1, m - 1)
newIndex2 = min(index2 + k // 2 - 1, n - 1)
# 判断两个数组中新指针下的数的大小
pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
if pivot1 <= pivot2:
# 更新k值，需要减去偏移量：newIndex1-index1+1，也就是 k//2
k -= newIndex1 - index1 + 1
# 更新指针位置，因为包括newIndex1在内的右边都不要了，所以要+1
index1 = newIndex1 + 1
else:
k -= newIndex2 - index2 + 1
index2 = newIndex2 + 1
m, n = len(nums1), len(nums2)
totalLength = m + n
# 当两个有序数组的长度确定时，他们组合起来的中位数的index也就确定了，
# 向getKthElement传递的就是这个中位数
if totalLength % 2 == 1:
# 针对组合后数组长度为奇数
return getKthElement((totalLength + 1) // 2)
else:
# 针对组合后数组长度为偶数
return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2核心方法1 ：左右双指针，分别从两头进行遍历，并维护左右两个最大高度；首先判断两个指针谁大，谁小就处理谁，然后判断小的那个和其对应的最大高度谁大，指针对应值大，则更新高度，对应值小，则计算接雨水的大小并类型
- 复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
class Solution:
def trap(self, height: List[int]) -> int:
"""
分别从左右两端开始遍历，思路如下：
对于左边开始移动的指针，只要右指针数比当前数大，且当前数还比左侧的小，则当前数处形成凹陷；
如果当前数没有左侧数小，就将左侧最大数更新为当前数。
对于右边开始移动的指针亦然。
"""
# 边界条件
if not height: return 0
n = len(height)
left, right = 0, n - 1 # 分别位于输入数组的两端
maxleft, maxright = height[0],height[n - 1]
ans = 0
while left <= right:
if height[left] < height[right]:
if height[left] >= maxleft:
maxleft = height[left]
else:
ans += maxleft - height[left]
left += 1
else:
if height[right] >= maxright:
maxright = height[right]
else:
ans += maxright - height[right]
right -= 1
return ans核心方法2: 使用单调递减栈，栈中存储数组索引。从左至右进行遍历，如果当前元素高度小于前一个元素高度，则当前索引入栈；否则，取出栈顶元素（在此处形成低洼），计算所接雨水的量，雨水的宽度是取出栈顶元素的宽度，高度是当前栈顶元素和当前遍历元素的最小高度
- 复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n) 栈
class Solution:
def trap(self, height: List[int]) -> int:
"""
使用一个递减栈来完成，遍历1次，时间复杂度为O（n），空间复杂度也是O（n）
从左至右，如果当前元素的高度【小于等于】前一个元素高度，则进行压栈；
如果当前元素的高度【大于】前一个元素，则栈顶处凹陷，左边为栈顶的前一个元素，右边为当前元素，可计算面积
面积的宽度为 当前元素index - 前一元素index - 1，高度为左右两边低的那个
"""
stack = []
res = 0 # 记录接雨水的量
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
top = stack.pop() # 出栈后，栈顶元素变为下面的一个
if not stack: break # 如果栈为空，说明左边没有柱子接雨水了
width = (i - stack[-1] - 1) # 两个下标的差再减1，表示雨水宽度
lenght = min(height[i], height[stack[-1]]) - height[top] # 取两个边界高度的最小值
res += width * lenght
stack.append(i) # 栈内存储的是元素的下标
return res- 双指针分别从数组的两头开始，移动指针意味着宽度要减小；如果移动对应大数的指针，则有可能水的面积会减小
- 复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
class Solution:
def maxArea(self, height: List[int]) -> int:
# 双指针法
# 两个指针分别从两端进行遍历，每次遍历移动对应数较小的指针，因为小的数（即小的高度）决定了盛水的大小
# 然后计算两指针的区间内的盛水面积，维护一个最大面积
n = len(height)
L = 0
R = n - 1
ans = 0
while (L <= R):
ans = max(ans, min(height[L], height[R]) * (R - L))
if height[L] < height[R]:
L += 1
else:
R -= 1
return ansclass Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 下一个排列一定是比当前排列要大，除非这个排列已经是最大的
# 要让这个排列中「较小数」尽量靠右，而「较大数」尽可能小，这样才能保证下一个排列是我们想要的
# 那么从后向前找到第一个升序的序列，这个序列中的【第一个】数就是可交换的【较小数】，这个数的后面一定是一个降序的序列
# 然后再从后向前找这个降序序列中【第一个】比【较小数】大的数，是为【较大数】
# 交换这两个数，然后对【较小数】后面的降序序列进行升序排序
# 注意：找下来发现并没有较小数，则说明原序列已经是降序序列了，直接进行升序排序就行
i = len(nums) - 2 # 比较的是当前数和后一个数，所以需要这样初始化
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
# 此时i对应的就是较小数
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[i] >= nums[j]:
j -= 1
# 此时j对应的就是较大数
# 互换
nums[i], nums[j] = nums[j], nums[i]
# 对后面的降序序列进行升序排序（双指针法）
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows == 0: return []
if numRows == 1: return [[1]]
if numRows == 2: return [[1],[1,1]]
res = [[1], [1,1]]
# i 表示杨辉三角的第几行
for i in range(2, numRows):
sin = [1] # 给该行初始化，并添加一个1
# j 表示下一行的第几个数，从下标为1开始，
# 这个位置的数等于上一个这个位置和前一个位置的和
for j in range(i-1):
sin.append(res[i-1][j] + res[i-1][j+1])
sin.append(1) # 最后加入 1
res.append(sin)
return res1014，最佳观光组合，中等
核心方法：使用直接遍历的方式，得分公式可以转化为value[i] + i 和 value[j] - j 的和。在遍历过程中，在统计节点j时，由于values[j] - j是固定不变的，因为只要保证 value[i] + i 是最大的，那么最佳的观光组合就有了。遍历过程中，可以同时维护 value[i] + i 的最大值 i_max。这里的复杂度就是能从O(n)降低到O(1)。
时间复杂度：O(n)
空间复杂度：O(1)
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
ans = 0
i_max = values[0] + 0
for j in range(1, len(values)):
ans = max(ans, i_max + values[j] - j)
i_max = max(i_max, values[j]+j)
return ans核心方法：动态规划
class Solution:
def maxScoreSightseeingPair(self, A: List[int]) -> int:
n = len(A)
res = dp = A[1]+A[0]-1
for i in range(2,n):
dp = A[i]+max(-1-A[i-1]+dp,A[i-1]-1)
res = max(dp,res)
return res135，分发糖果，困难
核心方法：遍历两次。
【相邻的孩子中，评分高的孩子必须获得更多的糖果】这句话拆分为两个规则：
- 左规则：当
ratings[i−1] < ratings[i]时，i 号学生的糖果数量将比 i−1 号孩子的糖果数量多。 - 右规则：当
ratings[i] > ratings[i+1]时，i 号学生的糖果数量将比 i+1 号孩子的糖果数量多。
在从左向右遍历的过程中，使用一个数组left来记录每个位置分发的糖果数。对于满足条件的情况，left[i] = left[i-1] + 1。否则left[i] = 1。
在从右向左遍历的过程中，只要使用单个变量right来记录即可。对于不满足的条件，当前位置的right直接赋值为1；满足时，right等于上一步right+1。在遍历的同时将当前right和对应位置的left[i]的最大值加入最终结果。也就是说，不需要再拿一个数组出来每个位置的糖果数了，因为最终求的糖果总数，所以只用当前right，即影响了最终结果，并且在满足右规则的条件下还影响了下一个位置的right，节约了空间。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
left = [0] * n
# 从左向右进行遍历
for i in range(n):
if i > 0 and ratings[i-1] < ratings[i]:
left[i] = left[i-1] + 1
else:
left[i] = 1
# 从右向左进行遍历
# 其中ret为糖果总数，right
right = ret = 0
for i in range(n-1, -1, -1):
if i < n-1 and ratings[i+1] < ratings[i]:
right += 1
else:
right = 1
ret += max(left[i], right)
return ret核心方法：常数空间遍历
对于递增序列：
- 只要还在递增序列中，那么递减序列的长度就为0
- 需要参考前一个同学分得的糖果数，并且直接将这个糖果数加入到结果中
- 因为每次都是只+1，所以在递增序列中，当前遍历位置分到的糖果数就是递增序列的长度
- 递增序列是严格递增的
对于递减序列：
- 只要在递减序列中，递减序列的长度就+1
- 当前递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中。
- 递减序列中的每个同学分得的糖果数，是根据序列长度添加进结果中；当后面又出现一个满足递减序列的同学时，需要将前面所有同学的糖果数+1
- 只要出现递减的情况，那么当前同学分得的糖果数=1，这里并不影响递减序列向结果添加的糖果数的结果，主要是为递增序列做准备的。
时间复杂度：O(n)，其中 n 是孩子的数量。只要遍历一次数组即可。
空间复杂度：O(1)。我们只需要常数的空间保存若干变量。没有额外数组
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
ret = 1 # 最终结果
# 分别初始化，递增序列长度，递减序列长度，前一个同学分得的糖果数
inc, dec, pre = 1, 0, 1
for i in range(1, n):
if ratings[i] >= ratings[i-1]:
# 如果当前得分大于上一个得分
# 那么首先将递减序列的长度置为0
dec = 0
# 记录当前同学分得的糖果
pre = (1 if ratings[i] == ratings[i-1] else pre + 1)
# 将当前同学分得的糖果数加入最终结果
ret += pre
# 当前同学分得的糖果数量恰好就是递增序列的长度，注意这里是严格的递增序列，
# 如果下一个同学分得的糖果和上一个一样，递增序列的长度不增加
inc = pre
else:
# 否则递减序列+1
dec += 1
# 如果递增序列和递减序列长度相等，
# 需要把最近的递增序列的最后一个同学也并进递减序列中。
if dec == inc:
dec += 1
# 当前递减序列有几个，就向结果中添加几，举例来说，如果递减序列为3，2，1
# 遍历到2时，向ret中加入2，因为当前序列为3，2，长度为2
# 遍历到1时，向ret中加入3，因为当前序列为3，2，1，长度为3
# 这种方式能够保证递减序列中每个同学能够被正确的计算分得糖果数
ret += dec
# 经过递减序列后，前一同学的糖果一定是1，需要重置，为下次做准备
pre = 1
return ret54，螺旋矩阵，中等
核心方法：使用转圈遍历法。矩阵的维度乘积等于遍历位置的个数。每遍历完一个位置，这个个数都减一。创建 l, r, t, b 四个变量分别记录遍历的位置，分别是左边界，右边界，上边界，下边界。每次完成一行或者一列的赋值过程后，压缩对应的边界，对于上边界和左边界，使用+=1，对于下边界和右边界，使用-=1。
注意：每行（列）遍历完成后，判断一次是否待遍历个数已经为0，为零则不需要再遍历了；因为这里使用的是for，所以需要单独处理一遍，如果使用的是while，可以直接写进条件中
- 时间复杂度：$O(mn)$
- 空间复杂度：O(1)
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
l, r, t, b = 0, len(matrix[0])-1, 0, len(matrix)-1
total = len(matrix) * len(matrix[0])
res = list()
while total > 0:
for i in range(l, r+1):
res.append(matrix[t][i])
total -= 1
t += 1
if total == 0: break
for i in range(t, b+1):
res.append(matrix[i][r])
total -= 1
r -= 1
if total == 0: break
for i in range(r, l-1, -1):
res.append(matrix[b][i])
total -= 1
b -= 1
if total == 0: break
for i in range(b, t-1, -1):
res.append(matrix[i][l])
total -= 1
l += 1
return res59，螺旋矩阵2，中等
核心方法：按照螺旋的顺序进行赋值。创建 l, r, t, b 四个变量分别记录遍历的位置，分别是左边界，右边界，上边界，下边界。每次完成一行或者一列的赋值过程后，压缩对应的边界，对于上边界和左边界，使用+=1，对于下边界和右边界，使用-=1。每个位置遍历完毕后需要将起始值+=1.
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n^2)$
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
l, r, t, b = 0, n-1, 0, n-1
num, total = 1, n * n
mat = [[0] * n for _ in range(n)]
while num <= total:
for i in range(l, r+1):
mat[t][i] = num
num += 1
t += 1
for i in range(t, b+1):
mat[i][r] = num
num += 1
r -= 1
for i in range(r, l-1, -1):
mat[b][i] = num
num += 1
b -= 1
for i in range(b, t-1, -1):
mat[i][l] = num
num += 1
l += 1
return mat326，3的幂，简单
核心方法，使用这个数对3求余，只要余数为0，那么将这个数除以3，最后的结果一定是1。如果不是1，则返回False。小于0的数一定是不满足的，所以当这个数小于1时，可以直接返回False。
时间复杂度：$O(log_3n)$
空间复杂度：O(1)
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n < 1:
return False
while n % 3 == 0:
n = n / 3
return n == 1238，除自身外数组的乘积，中等
核心方法：分别获取当前遍历位置的左侧的乘积和右侧的乘积。然后再遍历一次时，除自身外每个位置的乘积就等于当前位置对应的左侧乘积值与右侧乘积值的乘积。
时间复杂度：O(n)
空间复杂度：O(n)
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
L, R, res = [0] * n, [0] * n, [0] * n
# 从左至右填充当前i位置左侧的积
L[0] = 1
for i in range(1, n):
L[i] = nums[i-1] * L[i-1]
# 从右至左填充当前i位置右侧的积
R[n-1] = 1
for i in range(n-2, -1, -1):
R[i] = nums[i+1] * R[i+1]
# 每个位置的乘积就等于对应位置左右侧的乘积
for i in range(n):
res[i] = L[i] * R[i]
return res基于上面的方法，直接使用输出数组作为统计每个位置左侧乘积，然后使用一个动态变量计算每个右侧乘积，当前这个位置的就等于索引指示的左侧乘积乘以动态右侧乘积，然后需要更新右侧乘积即可
时间复杂度：O(n)
空间复杂度：O(1)
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n
# 从左至右填充当前i位置左侧的积
res[0] = 1
for i in range(1, n):
res[i] = nums[i-1] * res[i-1]
# 从右至左填充结果，并更新当前i位置右侧的积
R = 1
for i in range(n-1, -1, -1):
res[i] = R * res[i]
R = nums[i] * R
return res33，搜素旋转排序数组，中等
核心方法：对于有序数组，二分查找
虽然这个数组在位置k进行了一次旋转，但是将数组从中间进行分开后，一定有一部分数组是有序的。这里可以提示我们在以mid分割后需要查看[l, mid]，[mid+1, r]哪部分是有序的，并根据有序的那部分确定我们该如何改变二分查找的上下界，因为能够根据有序的那部分判断出target在不在这个部分里。
时间复杂度：O(logn)
空间复杂度：O(1)
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 使用二分查找，首先采用闭区间的方式进行编写
if not nums:
return -1
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]:
if nums[0] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if nums[mid] < target <= nums[len(nums)-1]:
l = mid + 1
else:
r = mid - 1
return -1704，二分查找
此题必须牢记
时间复杂度：O(logn)
空间复杂度：O(1)
# 使用闭区间
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)-1 # 注意
while l <= r: # 注意
mid = l + (r - l) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
r = mid - 1 # 注意
else:
l = mid + 1
return -1
# 使用开区间
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) # 注意
while l < r: # 注意
mid = l + (r - l) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
r = mid # 注意
else:
l = mid + 1
return -134，在排序数组中查找元素的第一个和最后一个位置，中等
核心方法：使用二分搜索
时间复杂度：O(logn)
空间复杂度：O(1)
- 如果左侧边界的搜索和右侧边的搜索都使用两端闭区间
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if len(nums) < 1:
return [-1, -1]
# 二分查找搜索左侧边界（左闭右闭）
l, r = 0, len(nums)-1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] == target:
r = mid - 1
elif nums[mid] > target:
r = mid - 1
else:
l = mid + 1
# 检查是否出现越界的情况
# 当target比所有元素都大，l会被加到len(nums)+1，这种情况下应该直接返回找不到
if l >= len(nums):
return [-1, -1]
left = l
# 二分查找搜索右侧边界（左闭右闭）
l, r = 0, len(nums)-1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] == target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
else:
l = mid + 1
# 当target比所有元素都小，r会被减到-1，会越界
if r < 0 or nums[r] != target:
return [-1, -1]
right = r
return [left, right]- 如果左侧边界的搜索和右侧边的搜索都使用左闭右开区间
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if len(nums) < 1:
return [-1, -1]
# 二分查找搜索左侧边界（左闭右闭）
l, r = 0, len(nums)
while l < r:
mid = l + (r - l) // 2
if nums[mid] == target:
r = mid
elif nums[mid] > target:
r = mid
else:
l = mid + 1
# 检查是否出现越界的情况
if l >= len(nums):
return [-1, -1]
left = l
# 二分查找搜索右侧边界（左闭右闭）
l, r = 0, len(nums)
while l < r:
mid = l + (r - l) // 2
if nums[mid] == target:
l = mid + 1
elif nums[mid] > target:
r = mid
else:
l = mid + 1
# 当target比所有元素都小，right会被减到-1，会越界
if l == 0 or nums[l-1] != target:
return [-1, -1]
right = l-1
return [left, right]总结：
- 在对边界进行初始化时，如果
r = len(nums)表示开区间；如果r = len(nums)-1表示开区间。 while内的终止条件是随着边界初始化来制定的：如果r = len(nums)那么终止条件为l < r；如果r = len(nums)-1那么终止条件为l <= r- 在进行压缩区间时，边界r是随着边界初始化来制定的：如果
r = len(nums)那么在压缩区间时r = mid；如果r = len(nums)-1那么在压缩区间时r = mid-1。但是左边界始终都是l = mid + 1 - 搜索左边界的时候，当
nums[mid] == target时，需要改变r的值，改变方式与压缩空间时改变r的值统一；搜索右边界的时候，当nums[mid] == target时，需要改变l的值，改变方式与压缩空间时改变l的值统一 - 如果
r = len(nums)终止条件就是l = r，也就是说结果返回l或者返回r都是一样的；如果r = len(nums)-1终止条件就是l = r+1，也就是说结果返回l-1或者返回r都是一样的 - 对越界情况的处理
- 搜索左边界时，需要判断左边界
l是否超出了最左端，即l <= 0?，满足的话说明找不到，返回-1 - 搜索右边界时，如果是开区间，那么需要返回
l-1，需要检查l是否等于0，或者l-1位置的值是否不等于target，满足条件则返回-1；如果是闭区间，那么需要返回r，需要检查r是否小于0，或者r位置的值是否不等于target，满足条件则返回-1
- 搜索左边界时，需要判断左边界
371，两整数之和，中等
核心方法：不能使用+和-号，只能使用位运算
位运算中的加法：异或运算，相同为0，不同为1
异或运算和与运算的结合。
- 异或运算特性是无进位加法
a = 5 = 0101
b = 4 = 0100
a ^ b 如下：
0 1 0 1
0 1 0 0
-------
0 0 0 1- 与运算能够提供进位的数
a = 5 = 0101
b = 4 = 0100
a & b 如下：
0 1 0 1
0 1 0 0
-------
0 1 0 0从结果可见，0100 并不是我们想要的进位，1 + 1 所获得的进位应该要放置在它的更高位，即左侧位上，因此我们还要把 0100 左移一位，才是我们所要的进位结果。
算法： 计算(a 和 b 的无进位结果) + (a 和 b 的进位结果)，循环这个过程，直到进位为0
class Solution(object):
# python的主要难点在于, python整数类型为Unifying Long Integers, 即无限长整数类型.
def getSum(self, a, b):
# 转化为32位无符号整数，一个F表示4位
a &= 0xFFFFFFFF
b &= 0xFFFFFFFF
# 无符号整数加法
while b:
carry = a & b
a ^= b
b = ((carry) << 1) & 0xFFFFFFFF
# print((a, b))
# 结果映射为有符号整数，负数相加需要确定符号位
# 采取的方式为：结果与16进制最大值取异或，对异或结果按位取反（符号位不变）
return a if a < 0x80000000 else ~(a^0xFFFFFFFF)287，寻找重复数
核心方法：排序
如何证明nums中至少存在一个重复的数字？
使用哈希表，判断哈希表和原数组的长度；如果不相等，说明存在重复元素
时间复杂度：O(nlogn)
空间复杂度：O(1)
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
nums.sort()
last = nums[0]
for i in range(1, len(nums)):
if nums[i] == last:
return last
else:
last = nums[i]推荐 核心方法：双指针
因为数组中数是从1到n的，并且元素下标也是从0到n的，所以可以假设索引i到nums[i]存在一条边，由于存在的重复的数字 target，因此 target 这个位置一定有起码两条指向它的边，因此整张图一定存在环，且我们要找到的 target 就是这个环的入口。
时间复杂度：O(n)
空间复杂度：O(1)
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow, fast = 0, 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = 0
while True:
slow = nums[slow]
fast = nums[fast]
if slow == fast:
return fast208，实现前缀树，中等
前缀树的优点：利用字符串的公共前缀来节约存储空间。利用词的公共前缀缩小查找范围，通过状态间的映射关系避免了字符的遍历，从而达到高效检索的目的
- 插入操作：如果当前字母没有出现过，则在对应位置往下生成一个Trie；若当前字母出现过，则继续遍历下一个字母，直到字符串遍历结束（结束时要标记end，表示这个单词已经结束了）
- 遍历要查找的字符串word，如果还没有遍历到end，在某字符处出现null，则直接返回false，因为该字符是第一次出现， 一定不会出现这个单词；当前遍历到查找字符串的末尾，若当前这个位置的isEnd = true，表示找到了，否则没有这个单词
- 前缀匹配：遍历需要前缀匹配的字符串prefix，主要在这个位置上出现null，就返回false；否则知道prefix全部遍历完都没有返回false的话，表示当前字典数中有该前缀字符串，返回True
时间复杂度：初始化为 O(1)，其余操作为 O(|S|)，其中 |S|是每次插入或查询的字符串的长度。
空间复杂度：$O(|T|\cdot\Sigma)$，其中
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.children = [None] * 26
self.isEnd = False
def searchPrefix(self, prefix):
node = self
for ch in prefix:
ch = ord(ch) - ord('a')
if not node.children[ch]:
# 如果这个位置没有，直接返回None
return None
node = node.children[ch]
# 全部遍历完
return node
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self
for ch in word:
ch = ord(ch) - ord('a')
if not node.children[ch]:
node.children[ch] = Trie()
node = node.children[ch]
node.isEnd = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.searchPrefix(word)
# 当前词word全部遍历完并且最后位置是end
return node is not None and node.isEnd
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
# 查找前缀，要求前缀全部遍历完，说明前缀存在
return self.searchPrefix(prefix) is not None240，搜索二维矩阵2，中等
核心方法：利用矩阵性质，选择合适的遍历起点。
矩阵的性质是，从上到下，从左至右都是升序排序，所以可以选择左下角作为遍历起点：如果指针指向数大于目标值，则指针向上移动；若指针指向数小于目标值，则指针向右移，直到找到目标并返回True，或者指针指向矩阵维度维度之外的（row， col）为止
对于如何选择出发点的问题：从当前点出发，必须满足朝一个方向走增大，朝另一个方向走减小。
时间复杂度：O(m+n)
空间复杂度：O(1)
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
height, width = len(matrix), len(matrix[0])
start_r = height-1
start_e = 0
while start_e < width and start_r >= 0:
if matrix[start_r][start_e] > target:
start_r -= 1
elif matrix[start_r][start_e] < target:
start_e += 1
else:
return True
return False647，回文子串，中等
核心方法：中心扩展
本代码参考第5题，最长回文子串的做法，选择一个中心，向两边进行扩展，就能够过遍历完所有的子串。需要注意的是中心可以是一个字符，也可以是两个字符。
因为我们只需要考虑回文串的个数，所以只需要一个变量记录个数就行了
时间复杂度：O(n^2) 空间复杂度：O(1)
class Solution:
def countSubstrings(self, s: str) -> int:
def expendAroundCentre(s, l, r):
nonlocal num
while l >= L and r <= R and s[l] == s[r]:
l -= 1
r += 1
num += 1
L, R = 0, len(s)-1
num = 0
for i in range(len(s)):
expendAroundCentre(s, i, i)
expendAroundCentre(s, i, i+1)
return num核心方法：manacher算法
它的处理方式是在所有的相邻字符中间插入 ##，比如 abaa 会被处理成 #a#b#a#a#，这样可以保证所有找到的回文串都是奇数长度的，以任意一个字符为回文中心。我们用 f(i) 来表示以 s 的第 i 位为回文中心，可以拓展出的最大回文半径，那么 f(i) - 1 就是以 i 为中心的最大回文串长度。
-
初始化
现在我们的任务是求解以
$i$ 为回文中心的最大回文半径$f(i)$ ，那么$f(i)$ 可能的结果有哪些呢？为了解决这个问题，我们已知$[1, i-1]$ 这些点作为回文中心时候的最大半径，并且在这些点中我们维护了一个最右端点$r_m$ 和对应的回文中心$i_m$ 。我们选定位置$j$ ，它是$i$ 关于$i_m$ 对称位置的点，也就是说$j$ 到$i_m$ 与$i$ 到$i_m$ 的距离一样，所以 $j+i=2i_m$。那么当 $i < r_m$ 时，说明以 $i$ 中心的最大半径一定没有超过 $r_m-i+1$，因为如果超了，那么 $r_m$ 就不是 $[1, i-1]$ 这些点中的最远端点了，会继续向右移。另一方面由于 $i$ 和 $j$ 是关于 $i_m$ 对称的，且 $i$ 和 $j$ 都包含在以 $i_m$ 为中心的回文串内，所以以 $j$ 为回文中心的最大半径 $f(j)$ 有可能等于 $i$ 为回文中心的最大半径 $f(i)$。综上，当 $i < r_m$ 时，$f(i)$ 应当取 $r_m-i+1$ 和 $f(j)$ 的最小值，因为 $j+i=2i_m$，所以$f(j)$ 可以转化为$f(2*i_m-i)$ . 如果$i > r_m$ , 就先初始化$f(i) = 1$ 题目中提到的为什么
$f(j)$ 有可能大于$r_m-i+1$ ，是由于$f(j)$ 一定小于等于$r_m-i_m+1$ ，但是$i$ 大于$i_m$ ，那么$r_m-i+1$ 就有可能小于$f(j)$ 了。 -
中心拓展
做完初始化之后，我们可以保证此时的
s[i + f(i) - 1] = s[i - f(i) + 1]，要继续拓展这个区间，我们就要继续判断s[i + f(i)]和s[i - f(i)]s[i−f(i)]是否相等，如果相等将f(i)自增；这样循环直到s[i + f(i)] != s[i - f(i)]，以此类推。我们可以看出循环每次结束时都能保证s[i + f(i) - 1] = s[i - f(i) + 1]，而循环继续（即可拓展的条件）一定是s[i + f(i)] = s[i - f(i)]。 这个时候我们需要注意的是不能让下标越界，有一个很简单的办法，就是在开头加一个$，并在结尾加一个!，这样开头和结尾的两个字符一定不相等，循环就可以在这里终止。
时间复杂度：O(n)。即 Manacher 算法的时间复杂度，由于最大回文右端点 r_m 只会增加而不会减少，故中心拓展进行的次数最多为 O(n)，此外我们只会遍历字符串一次，故总复杂度为 O(n)。
空间复杂度：O(n)。
class Solution:
def countSubstrings(self, s: str) -> int:
s = '#'.join(s)
s = '$#' + s + '#!'
n = len(s)-1
f = [1 for _ in range(n)]
i_m, r_m, res = 0, 0, 0
for i in range(1, len(n)):
# 初始化f[i]
f[i] = min(r_m - i + 1, f[2 * i_m - i]) if i <= r_m else 1
# 中心拓展
while s[i + f[i]] == s[i - f[i]]:
f[i] += 1
# 动态维护 i_m 和 r_m
if i + f[i] - 1 > r_m:
i_m = i
r_m = i + f[i] - 1
# 记录结果
res += (f[i] // 2)
return res75，颜色分类，中等 (荷兰国旗问题)
核心方法：统计频率，然后按照颜色个数，按位填颜色
时间复杂度：O(n)
空间复杂度：O(n)
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
d = collections.Counter(nums)
print(d)
c_0, c_1, c_2 = d[0], d[1], d[2]
for i in range(0, c_0):
nums[i] = 0
for i in range(c_0, c_0 + c_1):
nums[i] = 1
for i in range(c_0 + c_1, len(nums)):
nums[i] = 2核心方法：单指针
使用一个指针指向字符串的头部，第一次遍历，将0换到数组头部（指针处），指针每次后移一位；第二次遍历，将1换到指针处，指针每次移动一位。
时间复杂度：O(n)
空间复杂度：O(1)
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
p = 0
for i in range(n):
if nums[i] == 0:
nums[p], nums[i] = nums[i], nums[p]
p += 1
for i in range(p, n):
if nums[i] == 1:
nums[p], nums[i] = nums[i], nums[p]
p += 1核心方法：双指针
使用两个指针，p0用来交换0，p1用来交换1。
- 从左至右遍历数组时，如果找到
1，那么将其与nums[p1]进行交换，并将p1向后移动一位 - 如果找到
2，那么将其与nums[p2]进行交换，但是有可能交换之后，将原本1序列中的第一个1交换到了后面，有可能是2的后面。所以如果p0 < p1还需要再做一步，将nums[i]与nums[p0]进行交换，也就是将2序列中的第一个2换到了后面，这样p1指针前的序列全部都是排好序的。
时间复杂度：O(n)
空间复杂度：O(1)
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
p0 = p1 = 0
for i in range(n):
if nums[i] == 1:
nums[i], nums[p1] = nums[p1], nums[i]
p1 += 1
elif nums[i] == 0:
nums[i], nums[p0] = nums[p0], nums[i]
if p0 < p1:
nums[i], nums[p1] = nums[p1], nums[i]
p0 += 1
p1 += 1