滑动窗口
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
滑动窗口模板题，有点类似于快慢指针？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 N = len (A) res = 0 left, right = 0 , 0 zeros = 0 while right < N: if A[right] == 0 : zeros += 1 while zeros > K: if A[left] == 0 : zeros -= 1 left += 1 res = max (res, right - left + 1 ) right += 1 return res
给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
简单题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 def findShortestSubArray (nums: List [int ] ) -> int : freq = {} s_e = {} for i, num in enumerate (nums): if freq.get(num): freq[num] += 1 s_e[num][1 ] = i else : freq[num] = 1 s_e[num] = [i, i] freq = sorted (freq.items(), key=lambda x:x[1 ]) max_freq = freq[-1 ][1 ] max_freq_list = [] i = -1 while True : if len (freq) >= abs (i) and freq[i][1 ] == max_freq: max_freq_list.append(freq[i][0 ]) i -= 1 else : break min_len = s_e[max_freq_list[0 ]][1 ] - s_e[max_freq_list[0 ]][0 ] for i in max_freq_list: min_len = min (min_len, s_e[i][1 ] - s_e[i][0 ]) return min_len + 1
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
这个方法很妙，维护了两个极值的双向队列，这样能够快速判断当前极值，核心思想还是滑动窗口。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution : def longestSubarray (self, nums, limit ): r = l = res = 0 min_q = collections.deque() max_q = collections.deque() for num in nums: while len (min_q) and num < min_q[-1 ]: min_q.pop() while len (max_q) and num > max_q[-1 ]: max_q.pop() min_q.append(num) max_q.append(num) r += 1 ; while max_q[0 ] - min_q[0 ] > limit: if min_q[0 ] == nums[l]: min_q.popleft() if max_q[0 ] == nums[l]: max_q.popleft() l += 1 res = max (res, r - l) return res
给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。
如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。
简单题
1 2 3 4 5 6 7 8 9 10 class Solution : def isToeplitzMatrix (self, matrix: List [List [int ]] ) -> bool : from collections import deque dq = deque(matrix[0 ]) for i in range (1 , len (matrix)): dq.pop() if list (dq) != matrix[i][1 :]: return False dq.appendleft(matrix[i][0 ]) return True
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
还算比较简单
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution : def maxSatisfied (self, customers: List [int ], grumpy: List [int ], X: int ) -> int : plain_customer = 0 N = len (customers) for i in range (N): if not grumpy[i]: plain_customer += customers[i] max_add = 0 for i in range (X): if grumpy[i]: max_add += customers[i] l = 1 tmp_add = max_add while l <= N-X: tmp_add = tmp_add - grumpy[l-1 ]*customers[l-1 ] + grumpy[l+X-1 ] * customers[l+X-1 ] max_add = max (max_add, tmp_add) l += 1 return max_add + plain_customer
模拟
给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。
反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。
找规律就可以
1 2 3 4 5 6 7 8 9 10 11 12 class Solution : def flipAndInvertImage (self, A: List [List [int ]] ) -> List [List [int ]]: for line in A: l, r = 0 , len (line) - 1 while l < r: if line[l] == line[r]: line[l] = line[r] = (1 ^ line[l]) l += 1 r -= 1 if l == r: line[l] ^= 1 return A
外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：
单词 word 中包含谜面 puzzle 的第一个字母。
单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。
写了一个位运算的，但是看到n2的时间复杂度心里就觉得过不了了，结果确实没有，官方解给出了子集的做法、
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def findNumOfValidWords (self, words: List [str ], puzzles: List [str ] ) -> List [int ]: for i in range (len (puzzles)): tmp = 0 for ch in puzzles[i]: tmp |= (1 << ord (ch) - ord ('a' )) puzzles[i] = (tmp, puzzles[i][0 ]) for i in range (len (words)): tmp = 0 for ch in words[i]: tmp |= (1 << ord (ch) - ord ('a' )) words[i] = tmp for i in range (len (puzzles)): p = puzzles[i] match = 0 for w in words: if (w >> (ord (p[1 ]) - ord ('a' ))) & 1 and w == (w & p[0 ]): match += 1 puzzles[i] = match return puzzles
正解：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution : def findNumOfValidWords (self, words: List [str ], puzzles: List [str ] ) -> List [int ]: frequency = collections.Counter() for word in words: mask = 0 for ch in word: mask |= (1 << (ord (ch) - ord ("a" ))) if str (mask).count("1" ) <= 7 : frequency[mask] += 1 ans = list () for puzzle in puzzles: total = 0 mask = 0 for i in range (1 , 7 ): mask |= (1 << (ord (puzzle[i]) - ord ("a" ))) subset = mask while subset: s = subset | (1 << (ord (puzzle[0 ]) - ord ("a" ))) if s in frequency: total += frequency[s] subset = (subset - 1 ) & mask if (1 << (ord (puzzle[0 ]) - ord ("a" ))) in frequency: total += frequency[1 << (ord (puzzle[0 ]) - ord ("a" ))] ans.append(total) return ans
递归
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
1 2 3 4 5 6 7 8 class Solution (object ): def longestSubstring (self, s, k ): if len (s) < k: return 0 for c in set (s): if s.count(c) < k: return max (self.longestSubstring(t, k) for t in s.split(c)) return len (s)
前缀和
给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（ i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class NumArray : def __init__ (self, nums: List [int ] ): self.sum = [0 ] for num in nums: self.sum .append(num + self.sum [-1 ]) def sumRange (self, i: int , j: int ) -> int : return self.sum [j+1 ] - self.sum [i]
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
(2, 1) ，右下角(row2, col2) = **(4, 3)，**该子矩形内元素的总和为 8。
跟上题思路类似，不过需要多一点想法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class NumMatrix : def __init__ (self, matrix: List [List [int ]] ): m, n = len (matrix), (len (matrix[0 ]) if matrix else 0 ) self.sums = [[0 ] * (n + 1 ) for _ in range (m + 1 )] _sums = self.sums for i in range (m): for j in range (n): _sums[i + 1 ][j + 1 ] = _sums[i][j + 1 ] + _sums[i + 1 ][j] - _sums[i][j] + matrix[i][j] def sumRegion (self, row1: int , col1: int , row2: int , col2: int ) -> int : _sums = self.sums return _sums[row2 + 1 ][col2 + 1 ] - _sums[row1][col2 + 1 ] - _sums[row2 + 1 ][col1] + _sums[row1][col1]
动态规划
给定一个非负整数 num 。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
由于对于一个二进制数i，其结果必为i >> 1再加上i是否为奇数，所以可以使用动态规划
1 2 3 4 5 6 class Solution : def countBits (self, num ): res = [0 ] * (num + 1 ) for i in range (1 , num + 1 ): res[i] = res[i >> 1 ] + (i & 1 ) return res
给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution : def maxEnvelopes (self, envelopes: List [List [int ]] ) -> int : if not envelopes: return 0 n = len (envelopes) envelopes.sort(key=lambda x: (x[0 ], -x[1 ])) f = [1 ] * n for i in range (n): for j in range (i): if envelopes[j][1 ] < envelopes[i][1 ]: f[i] = max (f[i], f[j] + 1 ) return max (f)
当然，可以使用二分查找优化算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution : def maxEnvelopes (self, envelopes: List [List [int ]] ) -> int : if not envelopes: return 0 n = len (envelopes) envelopes.sort(key=lambda x: (x[0 ], -x[1 ])) f = [envelopes[0 ][1 ]] for i in range (1 , n): if (num := envelopes[i][1 ]) > f[-1 ]: f.append(num) else : index = bisect.bisect_left(f, num) f[index] = num return len (f)
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
瞟了一眼题解，发现是可以用dp做，返回到文档来想想dp怎么做。
如果我们用dp[i]表示前缀s[0…<i]中能够切分为回文串的最小次数。那么我们最后返回dp[len(s)]即可，即需要定义一个长度为len(s) + 1的dp数组。
接下来得思考如何构造状态转移方程
由于dp[i]是最小分割次数，所以肯定要从dp[0]到dp[i-1]中枚举，由于我们加入了一个新的字母，所以源字符串s[0…<i]中，存在一个下标j，使s[j…<i]也能是一个回文串。
这样的话就是dp[j] + 1（dp[j]就是s[0…<j]的分割为回文串的最小次数。
得到状态转移方程为d p [ i ] = m i n 0.. i ( d p [ j ] ) + 1 dp[i] = min_{0..i}(dp[j]) + 1 d p [ i ] = mi n 0.. i ( d p [ j ]) + 1
此外，如果s[0…<i]为回文串的话，dp[i] = 0
至于判断是否为回文串，可以使用本文中回溯里的判断回文串 的题目中的函数
1 2 3 4 5 @cache def isPalindrome (i: int , j: int ) -> int : if i >= j: return 1 return isPalindrome(i + 1 , j - 1 ) if s[i] == s[j] else -1
所以完整题解为
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution : def minCut (self, s: str ) -> int : dp = [0 ] * (len (s) + 1 ) @cache def isPalindrome (i: int , j: int ) -> int : if i >= j: return 1 return isPalindrome(i + 1 , j - 1 ) if s[i] == s[j] else -1 for i in range (1 , len (s) + 1 ): if isPalindrome(0 , i-1 ) == 1 : dp[i] = 0 else : minCnt = len (s) for j in range (1 , i): if isPalindrome(j, i-1 ) == 1 : minCnt = min (minCnt, dp[j] + 1 ) dp[i] = minCnt return dp[len (s)]
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
这道题可以建立一个len(s) * len(t)的dp数组，其中dp[i][j]表示在t的前i个字符里，有s的前j个字符的组数。
因此如果s[i] == t[j], dp[i][j] = dp[i-1][j - 1]
栈
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
1 2 3 4 5 6 7 8 9 10 11 class Solution : def nextGreaterElements (self, nums: List [int ] ) -> List [int ]: length = len (nums) ret = [-1 ] * length stack = [] for i in range (length * 2 ): while stack and nums[stack[-1 ]] < nums[i % length]: ret[stack.pop()] = nums[i % length] stack.append(i % length) return ret
给出由小写字母组成的字符串 S，重复项删除操作 会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
这不就是消消乐么，可以发现栈非常容易做这个啊。
1 2 3 4 5 6 7 8 9 class Solution : def removeDuplicates (self, S: str ) -> str : stack = [] for i in list (S): if stack and stack[-1 ] == i: stack.pop() else : stack.append(i) return '' .join(stack)
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution : def calculate (self, s: str ) -> int : ops = [] nums = [] for i in list (s): if i == ' ' : continue elif i == '(' or i == '+' or i == '-' : ops.append(i) elif i == ')' : while ops[-1 ] != '(' : op = ops.pop() n1, n2 = nums.pop(), nums.pop() nums.append(n1 + n2 if op == '+' else n2 - n1) ops.pop() else : nums.append(int (i)) n1, n2 = nums.pop(), nums.pop() ret = n1 + n2 if ops[0 ] else n2 - n1 return ret
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
1 2 3 4 5 6 7 _9_ / \ 3 2 / \ / \ 4 1 # 6 / \ / \ / \ # # # # # #
例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
可以把一个叶子结点转为空节点
1 2 3 4 5 6 7 8 9 class Solution (object ): def isValidSerialization (self, preorder ): stack = [] for node in preorder.split(',' ): stack.append(node) while len (stack) >= 3 and stack[-1 ] == stack[-2 ] == '#' and stack[-3 ] != '#' : stack.pop(), stack.pop(), stack.pop() stack.append('#' ) return len (stack) == 1 and stack.pop() == '#'
回溯
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
可以使用记忆化搜索寻找回文串，然后就是dfs回溯即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution : def partition (self, s: str ) -> List [List [str ]]: n = len (s) ret = list () ans = list () @cache def isPalindrome (i: int , j: int ) -> int : if i >= j: return 1 return isPalindrome(i + 1 , j - 1 ) if s[i] == s[j] else -1 def dfs (i: int ): if i == n: ret.append(ans[:]) return for j in range (i, n): if isPalindrome(i, j) == 1 : ans.append(s[i:j+1 ]) dfs(j + 1 ) ans.pop() dfs(0 ) isPalindrome.cache_clear() return ret
