【Leetcode】 top100 round2 需要加强版

知识补充

• 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]: continuej,k = i+1,n-1while 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 += 1elif tmp<0: j += 1else: 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, 0for num in nums:summ += numif summ-k in tmp:            # 这俩if不能交换位置！！！res += tmp[summ-k]if summ not in tmp:tmp[summ] = 1else:tmp[summ] += 1return 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, 0tmp, cnt, res = {}, n, swhile left<=right and right<m:if cnt:             # 未找齐全部字符， 右侧扩展if right<n:if t[right] in tmp: tmp[t[right]] += 1else: tmp[t[right]] = 1if s[right] in tmp:       tmp[s[right]] -= 1if not tmp[s[right]]: cnt -= 1      # 要确保是tmp[s[right]]还差right += 1else:               # 找齐全部字符，左侧收缩if right-left < len(res):res = s[left:right]if s[left] in tmp:tmp[s[left]] += 1if tmp[s[left]]: cnt += 1left += 1while left<m and not cnt:      # 最后处理if right-left < len(res):res = s[left:right]if s[left] in tmp:tmp[s[left]] += 1if tmp[s[left]]: cnt += 1left += 1return '' 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, 0cnt, res = n, 2*stmp = Counter(t)while left<=right and right<m:if cnt:             # 未找齐全部字符， 右侧扩展if s[right] in tmp:       tmp[s[right]] -= 1if tmp[s[right]]>=0: cnt -= 1      # 要确保是tmp[s[right]]还差right += 1else:               # 找齐全部字符，左侧收缩if right-left < len(res):res = s[left:right]if s[left] in tmp:tmp[s[left]] += 1if tmp[s[left]]>0: cnt += 1left += 1while left<m and not cnt:      # 最后处理if right-left < len(res):res = s[left:right]if s[left] in tmp:tmp[s[left]] += 1if tmp[s[left]]>0: cnt += 1left += 1return '' 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] = numelse:if dp[i-1]<0: dp[i] = numelse: dp[i] = dp[i-1]+numres = 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 = numelse:if dp<0: dp = numelse: dp = dp + numres = 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+1return 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 Noneslow, fast = head, head.nextwhile fast and fast.next and fast != slow:fast, slow = fast.next.next, slow.nextif not fast or not fast.next:return None  # 无环fast, slow = head, slow.nextwhile fast != slow:fast, slow = fast.next, slow.nextreturn fast

437 路径总和III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

相当于求区间和为目标值的所有区间——前缀和

class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:global restmp, res, hashmap = 0, 0, {0:1}def backtrack(node, tmp):if not node: returnglobal restmp += node.val                # 当前前缀和if tmp-targetSum in hashmap:   # 能找到区间和为targetSum的区间res += hashmap[tmp-targetSum]if tmp in hashmap: hashmap[tmp] += 1   # 更新前缀和else: hashmap[tmp] = 1backtrack(node.left, tmp)backtrack(node.right, tmp)hashmap[tmp] -= 1tmp -= node.valreturnbacktrack(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, 0for i in range(m):for j in range(n):if grid[i][j] == 1: cnt += 1elif grid[i][j] == 2: stack.append([i,j])if cnt==0: return 0if not stack: return -1while 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 -= 1res += 1if cnt: return -1else: 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)-1while left<=right:mid = (left+right)//2if nums[left]<nums[mid]:        # 左侧有序if nums[left]<nums[right]:  return nums[left]else:left = mid + 1elif nums[mid]<nums[right]:     # 右侧有序right = midelse: 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 Falseelse: summ = summ//2dp = [False]*(summ+1)dp[0] = Truefor num in nums:for i in range(summ, num-1, -1):  # 从后往前，避免加入num后使dp[k*num]都有效if dp[i-num]: dp[i] = Truereturn 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      # 和空字符串的最长公共子序列为0elif j==0: dp[i][j] = 0else:if text1[i-1]==text2[j-1]:dp[i][j] = dp[i-1][j-1]+1else: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, fastwhile idx1 != idx2:idx1 = nums[idx1]idx2 = nums[idx2]return idx1