【MIX】算法题解(20200705)

题目列表

LC 75. 颜色分类LC 76. 最小覆盖字串LC 77. 组合LC 78. 子集LC 79. 单词搜索LC 80. 删除排序数组中的重复项 II

LC 75. 颜色分类

题目链接 使用三路快排的思想求解 定义三根指针i指向表头，k指向表尾，j为游走 当j<=k时循环:

如果nums[j]==0那么将i，j所指向的元素交换，同时将两根指针后移如果nums[j]==1，后移j指针如果nums[j]==2，交换j，k指针所指向的元素，同时将k指针后移

算法时间复杂度$\mathcal{O}(n)$，只需要扫描一遍数组即可

class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ # 三路切分 n=len(nums) if not n: return i, j, k=0, 0, n-1 while j<=k: if nums[j]==0: nums[i], nums[j]=nums[j], nums[i] i+=1 j+=1 elif nums[j]==1: j+=1 elif nums[j]==2: nums[j], nums[k]=nums[k], nums[j] k-=1

LC 76. 最小覆盖字串

题目链接 本题使用双指针算法，建立两个hash表统计指针窗口串和目标串t的分布，对于超过t中的频数的字符，移动j指针，对于不足t中频数的字符，计入已匹配的字符长度cnt，当cnt==t.size()时，更新最小覆盖字串ans. 时间复杂度$\mathcal{O}(n)$(哈希表添加/删除元素时间开销为$\mathcal{O}(1)$)

class Solution: def minWindow(self, s: str, t: str) -> str: dt, ds=defaultdict(int), defaultdict(int) for c in t: dt[c]+=1 ans, cnt="", 0 i, j, n=0, 0, len(s) while i<n: ds[s[i]]+=1 if ds[s[i]]<=dt[s[i]]: cnt+=1 while j<n and ds[s[j]]>dt[s[j]]: ds[s[j]]-=1 j+=1 if cnt==len(t): # update if not len(ans) or len(ans)>i-j+1: ans=s[j:i+1] i+=1 return ans

LC 77. 组合

题目链接 经典递归回溯问题 依次从1,2,…,n开始考虑组合，如果当前集合有k个元素则加入结果集，可以优化循环次数为n+1-len(vec)次.

class Solution: def combine(self, n: int, k: int) -> List[List[int]]: ans=[] def dfs(index, vec): if len(vec)==k: ans.append([*vec]) return for i in range(index, n+2-k+len(vec)): vec.append(i) dfs(i+1, vec) vec.pop(-1) dfs(1, []) return ans

LC 78. 子集

题目链接 本题和第77题类似，可以使用递归回溯/迭代算法求解. 算法时间复杂度为$\mathcal{O}(2^n)$ 方法1： 递归回溯 依次从index开始的元素组合子集，所有组合均加入结果集

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: ans, n=[], len(nums) def dfs(index, vec): ans.append([*vec]) for i in range(index, n): vec.append(nums[i]) dfs(i+1, vec) vec.pop(-1) dfs(0, []) return ans

方法2：迭代&二进制 由于子集的数量是固定的，对于一个长度为$n$的集合，子集的个数为$2^n$， 可以映射到区间$[0,2^{n-1}]$，考虑使用二进制方式计数. 设j=1<<n每一个bit表示对应位置的元素选(1)或不选(0)

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: n, ans =len(nums), [] for j in range(1<<n): vec=[] for i in range(n): if j>>i&0x01: vec.append(nums[i]) ans.append(vec) return ans

LC 79. 单词搜索

题目链接 本题使用递归回溯的方法求解 算法时间复杂度为$\mathcal{O}(n^2{3}^k)$ 对于每一个匹配到单词首位的字符进行dfs搜索，将已经匹配到的字符mask，在回溯时执行umask操作，探测可能的3个方向，如果能完全匹配单词，则返回True.

class Solution: def exist(self, board: List[List[str]], word: str) -> bool: r, c, n=len(board), len(board[0]), len(word) dirs=[[-1, 0], [0, 1], [1, 0], [0, -1]] def dfs(u, x, y): if u==n: return True t=board[x][y] board[x][y]='#' for d in dirs: nx, ny=x+d[0], y+d[1] if nx>=0 and nx<r and ny>=0 and ny<c and board[nx][ny]==word[u]: if dfs(u+1, nx, ny): return True board[x][y]=t return False for i in range(r): for j in range(c): if word[0]==board[i][j]: if dfs(1, i, j): return True return False

LC 80. 删除排序数组中的重复项 II

题目链接 本题使用双指针算法，时间复杂度为$\mathcal{O}(n)$ 定义指针j表示有效集的末尾指针(类似end())，i表示当前正在遍历数组的指针，由于数组有序，所以如果满足nums[i]!=nums[k-1]||nums[i]!=nums[k-2]||k<2可以向有效集中添加元素.

class Solution: def removeDuplicates(self, nums: List[int]) -> int: j=0 for i in range(len(nums)): if j<2 or nums[i]!=nums[j-1] or nums[i]!=nums[j-2]: nums[j]=nums[i] j+=1 return j