知识补充
- python赋值的执行顺序：
在41中，对于测试案例[-1,4,3,1] 当i=1时，以下两条语句的执行结果不一致：
“nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]”
“nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]”
解析：① 先计算右侧，nums[i] = 4, nums[nums[i]-1] = nums[4-1] = nums[3]
再执行从左到右的赋值：nums[nums[i]-1] = nums[i] = 4 导致nums[3] = 4
nums[i] = nums[3] = 1 导致nums[1] = 1
得到 [-1,1,3,4] 的交换结果
② 先计算右侧，nums[nums[i]-1] = nums[4-1] = nums[3]，nums[i] = 4
再执行从左到右的赋值：nums[i] = nums[3] = 1 导致nums[1] = 1
nums[nums[i]-1] = nums[1-1] = nums[i] = 4 导致nums[0] = 4
得到 [4,1,3,1] 的交换结果
问题出在语句②左侧的计算顺序在nums[i]重新赋值之后
15 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
1.i/j/k不等：只往i后取j，只往j后取k
2.三元组组合不重复：hashmap/set去重（要求排序）
方法一：回溯 枚举每种组合可能，看是否同时满足len=3，sum=0
方法二：固定nums[i]转为在[i:-1]里查找两数之和为-nums[i]的组合可能
方法三：双指针 排序后固定nums[i]，用一头一尾双指针来控制sum大小，需要保证元素不重复；
class Solution(object): def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ # 固定一个数然后在排列好的数组中一头一尾取 nums.sort() n = len(nums) res = [] for i in range(n): if i and nums[i]==nums[i-1]: continue j,k = i+1,n-1 while j<k: tmp = nums[i]+nums[j]+nums[k] if tmp==0: res.append([nums[i],nums[j],nums[k]]) while j<n and nums[j] == tmp-(nums[i]+nums[k]): # 跳到下一个不同的nums[j] j += 1 elif tmp<0: j += 1 else: k -= 1 # 实际上只有tmp=0是需要跳到下一个不相同的数，避免有效答案不重复即可 return res
560 和为K的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。
连续非空序列求和=区间和=前缀和
知识补充：
前缀和：sum[i]=num[1]+num[2]+……+num[i] 实现区间和的O(1)查询
核心操作：sum(num[i:j]) = sum[j-1] - sum[i-1]
差分数组：cf[i]=num[i]-num[i-1] 实现区间修改的O(1)操作
核心操作：对num[i:j]全+1 等价于 cf[i]+=1 cf[j+1]-=1
b[1] = a[1]
b[2] = a[2] - a[1]
...
b[n] = a[n] - a[n-1]
两者关系：b[i] 是 a[i] 的差分数组，a[i] 是 b[i] 的前缀和，某种程度上的逆运算；对差分数组进行前缀和操作可以得到原数组；
为了不特殊处理，perSum[i]表示sum(num[:i-1])
一维前缀和：sum[i:j] = perSum[j+1] - perSum[i]
二维前缀和：sum[i:j][m:n] = perSum[j+1][n+1] - perSum[j][m] - perSum[i][n] + perSum[i][m]
相关题目：leetcode：1480/303/304/
方法：构造前缀和后，转为找两个数的差值为K（两数之和也是先判断再插入字典）
class Solution(object): def subarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ tmp = {0:1} summ, res = 0, 0 for num in nums: summ += num if summ-k in tmp: # 这俩if不能交换位置！！！ res += tmp[summ-k] if summ not in tmp: tmp[summ] = 1 else: tmp[summ] += 1 return res
239 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
方法：在窗口中只保留能用到的元素（即>=nums[i]）的排序；
class Solution(object): def maxSlidingWindow(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ n = len(nums) if k>=n: return [max(nums)] stack, res = sorted(nums[:k], reverse=True), [] res.append(max(stack)) for i in range(k, n): while stack and nums[i] > stack[-1]: #只留下比nums[i]大的值 stack.pop() stack.append(nums[i]) # 插入当前值 if nums[i-k] in stack: # 移出仍在stack中超过窗口长度的值 stack.remove(nums[i-k]) res.append(stack[0]) return res案例[-6,-10,-7,-1,-9,9,-8,-4,10,-5,2,9,0,-7,7,4,-2,-10,8,7] k=7 无法通过
原因：窗口[-7,-1,-9,9,-8,-4,10]对应的stack是[10]
而窗口[-8,-4,10,-5,2,9,0]对应的stack是[10,9,0] 但此时nums[i-k]=9 就把第12位的9当成第6位的9移出stack
解决：利用不重复的值（下标）来表示每个元素
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) if k>=n: return [max(nums)] stack, res = [], [] for i in range(n): while stack and nums[i] > nums[stack[-1]]: #只留下比nums[i]大的下标值 stack.pop() stack.append(i) # 插入当前下标值 if i>=k-1: if (i-k) in stack: # 移出仍在stack中超过窗口长度的值 stack.remove(i-k) res.append(nums[stack[0]]) return res
76 最小覆盖字串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
方法：先右侧扩展至找齐t的所有字符，再左侧缩减至缺少t的一个字符，记录长度；
class Solution: def minWindow(self, s: str, t: str) -> str: m, n = len(s), len(t) left, right = 0, 0 tmp, cnt, res = {}, n, s while left<=right and right<m: if cnt: # 未找齐全部字符， 右侧扩展 if right<n: if t[right] in tmp: tmp[t[right]] += 1 else: tmp[t[right]] = 1 if s[right] in tmp: tmp[s[right]] -= 1 if not tmp[s[right]]: cnt -= 1 # 要确保是tmp[s[right]]还差 right += 1 else: # 找齐全部字符，左侧收缩 if right-left < len(res): res = s[left:right] if s[left] in tmp: tmp[s[left]] += 1 if tmp[s[left]]: cnt += 1 left += 1 while left<m and not cnt: # 最后处理 if right-left < len(res): res = s[left:right] if s[left] in tmp: tmp[s[left]] += 1 if tmp[s[left]]: cnt += 1 left += 1 return '' if res==s else res案例s = 'abc' t = 'cba' 无法通过
原因：同步计数使遍历s的'a'时被认为不在t中
解决：先对t计数
案例s = 'aa' t = 'aa' 无法通过
原因：判断 tmp[s[right]] 条件错误；初始化和最终结果相同，无法具体判断
解决：初始化res=2*s 有效字符判断条件改成 if tmp[s[right]]>=0
from collections import Counter class Solution: def minWindow(self, s: str, t: str) -> str: m, n = len(s), len(t) left, right = 0, 0 cnt, res = n, 2*s tmp = Counter(t) while left<=right and right<m: if cnt: # 未找齐全部字符， 右侧扩展 if s[right] in tmp: tmp[s[right]] -= 1 if tmp[s[right]]>=0: cnt -= 1 # 要确保是tmp[s[right]]还差 right += 1 else: # 找齐全部字符，左侧收缩 if right-left < len(res): res = s[left:right] if s[left] in tmp: tmp[s[left]] += 1 if tmp[s[left]]>0: cnt += 1 left += 1 while left<m and not cnt: # 最后处理 if right-left < len(res): res = s[left:right] if s[left] in tmp: tmp[s[left]] += 1 if tmp[s[left]]>0: cnt += 1 left += 1 return '' if res==2*s else res
53 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
方法一：区间和—构造前缀和找（后-前）的最大值 O(n^2)
方法二：动态规划
dp[i]表示以i结尾的连续子数组的最大值
dp[i] = dp[i-1]+nums[i] if dp[i-1]>=0 else nums[i]
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ n = len(nums) dp, res = [0]*n, float('-inf') for i,num in enumerate(nums): if i==0:dp[i] = num else: if dp[i-1]<0: dp[i] = num else: dp[i] = dp[i-1]+num res = max(res, dp[i]) return res # 完成如上代码后发现可以优化空间 class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ n = len(nums) dp, res = 0, float('-inf') for i,num in enumerate(nums): if i==0:dp = num else: if dp<0: dp = num else: dp = dp + num res = max(res, dp) return res
41 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
方法：原地哈希， 越界值不处理；
class Solution: def firstMissingPositive(self, nums: List[int]) -> int: i, n = 0, len(nums) while i<n: if 0<nums[i]<=n and nums[i] != i+1 and nums[nums[i]-1] != nums[i]: # 注意交换条件:当前值在处理范围且不在正确位置！！同时需要被交换的值也不在正确位置！！ # 注意交换顺序 # nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i] nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1] else: i+=1 # 越界值不处理 for i in range(n): if nums[i] != i+1: return i+1 return n+1
142 环形列表II
检测链表是否有环：快慢指针判断是否会再次相遇；
求链表环入口：假设入环前长度x，环长度y，当快慢指针相遇时fast比slow多在环内绕n圈，则slow=ny，即slow再走x步即可到达环入口；
class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: if head == None: return None slow, fast = head, head.next while fast and fast.next and fast != slow: fast, slow = fast.next.next, slow.next if not fast or not fast.next: return None # 无环 fast, slow = head, slow.next while fast != slow: fast, slow = fast.next, slow.next return fast
437 路径总和III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
相当于求区间和为目标值的所有区间——前缀和
class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int: global res tmp, res, hashmap = 0, 0, {0:1} def backtrack(node, tmp): if not node: return global res tmp += node.val # 当前前缀和 if tmp-targetSum in hashmap: # 能找到区间和为targetSum的区间 res += hashmap[tmp-targetSum] if tmp in hashmap: hashmap[tmp] += 1 # 更新前缀和 else: hashmap[tmp] = 1 backtrack(node.left, tmp) backtrack(node.right, tmp) hashmap[tmp] -= 1 tmp -= node.val return backtrack(root, tmp) return res
994 腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
方法：一次遍历统计新鲜橘子个数和腐烂橘子位置，模拟腐烂后统计腐烂时间（需要多点同时腐烂才能得到最小分钟数）
class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) stack, cnt, res = [], 0, 0 for i in range(m): for j in range(n): if grid[i][j] == 1: cnt += 1 elif grid[i][j] == 2: stack.append([i,j]) if cnt==0: return 0 if not stack: return -1 while stack: # print(stack) time = len(stack) for _ in range(time): [x, y] = stack.pop(0) # 左出右进 for [i,j] in ([0,-1],[0,1],[-1,0],[1,0]): if 0<=x+i<m and 0<=y+j<n: # print([x+i,y+j]) if grid[x+i][y+j] == 1: grid[x+i][y+j] = 0 # 避免后续重复 stack.append([x+i, y+j]) cnt -= 1 res += 1 if cnt: return -1 else: return res-1
153 寻找旋转排序数组最小数
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
由于题目强调数组中的元素值互不相同，所以增加特殊判断，避免mid和left/right元素值相同的情况；
class Solution: def findMin(self, nums: List[int]) -> int: # 不限制时间复杂度的话一次遍历找到断点即可 left, right = 0, len(nums)-1 while left<=right: mid = (left+right)//2 if nums[left]<nums[mid]: # 左侧有序 if nums[left]<nums[right]: return nums[left] else: left = mid + 1 elif nums[mid]<nums[right]: # 右侧有序 right = mid else: return min(nums[left], nums[right])
416 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
方法一：计算数组总和后转为求数组和为sum//2的子集组合——回溯
方法二：动态规划，dp代表元素和
class Solution: def canPartition(self, nums: List[int]) -> bool: summ = sum(nums) if summ%2: return False else: summ = summ//2 dp = [False]*(summ+1) dp[0] = True for num in nums: for i in range(summ, num-1, -1): # 从后往前，避免加入num后使dp[k*num]都有效 if dp[i-num]: dp[i] = True return dp[-1]
1143 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
思路：动态规划
dp[i][j]表示text1[:i]和text2[:j]的最长公共子序列长度；
状态转移：
当text1[i-1]==text2[j-1]时，dp[i][j] = dp[i-1][j-1]+1
当text1[i-1]!=text2[j-1]时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0]*(n+1) for _ in range(m+1)] for i in range(m+1): for j in range(n+1): if i==0: dp[i][j] = 0 # 和空字符串的最长公共子序列为0 elif j==0: dp[i][j] = 0 else: if text1[i-1]==text2[j-1]: dp[i][j] = dp[i-1][j-1]+1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[-1][-1]
72 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
思路：动态规划
dp[i][j]表示word1[:i]转换成word2[:j]的最少操作数；
状态转移：dp[i][j] = dp[i][j-1]+1 (插入) dp[i][j] = dp[i-1][j]+1 (删除) dp[i][j] = dp[i-1][j-1]+1（替换）
故：dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1
class Solution: def minDistance(self, word1: str, word2: str) -> int: m, n = len(word1), len(word2) dp = [[0]*(n+1) for _ in range(m+1)] for i in range(m+1): for j in range(n+1): if i==0: dp[i][j] = j # 空的word1变成word2，直接插入 elif j==0: dp[i][j] = i # word1变成空的word2，直接删除 else: if word1[i-1]==word2[j-1]: # 不用操作 dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1 # print(dp) return dp[-1][-1]
287 寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
取消数组不修改的限制可以用原地哈希；
本质上是一个环形链表找环入口的问题；
建立下标i和nums[i]的映射关系，若有重复的nums[i]，则代表有多个不同的i能映射到nums[i]，即构成环；解决思路参考142
class Solution: def findDuplicate(self, nums: List[int]) -> int: if len(nums) == 1: return nums[0] fast, slow = nums[nums[0]], nums[0] while fast != slow: fast = nums[nums[fast]] slow = nums[slow] idx1, idx2 = 0, fast while idx1 != idx2: idx1 = nums[idx1] idx2 = nums[idx2] return idx1
