438. 找到字符串中所有字母异位词Medium

日常刷题

821. 字符的最短距离（Easy）

4月19号的每日一题。一道简单题。

做法1：遍历每一个位置ｉ，然后在ｉ处定义两个指针 l e f t , r i g h t left, right left,right，两个指针同时向左右移动，当其中一个到头的时候，只移动另一个。直到两个指针中至少有一个指向的字符为目标 c c c。

想法很简单，复杂度很高。为 O ( n 2 ) O(n^2) O(n2)

class Solution:def shortestToChar(self, s: str, c: str) -> List[int]:ans = [0] * len(s)for i in range(len(s)):cur = s[i]left, right = i, i# 左边走到头了或者没走到头但是不是c and 右边走到头了或者没走到头但是不是cwhile  (left == -1 or s[left] != c) and (right == len(s) or s[right] != c):if left >= 0:left -= 1if right < len(s):right += 1# 如果左边没找到，那么left=-1， 如果右边没找到，那么right=nif left == -1: ans[i] = right - ielif right == len(s): ans[i] = i - leftelse: ans[i] = min(i-left, right-i)return ans

为什么每次在位置 i i i上都要向左右两边遍历呢。其实可以想象，位置 i i i左边和右边的 c c c的位置和 i − 1 i-1 i−1是没区别的，只要他们两个都不是 c c c，只是相对位置有变化。那么，每次在位置 i i i，不需要再重新开始向左右两边遍历了。

class Solution:def shortestToChar(self, s: str, c: str) -> List[int]:n = len(s)ans = [1] * n# 左边的c，如果左边没c，就加上一个很大的数，之后取min的时候会直接passidx = -2 * n   # 只要是一个大于n的数即可for i in range(n):if s[i] == c:idx = ians[i] = i - idx # 右边的cidx = 3 * n    # 只要是一个大于n的数即可for i in range(n-1, -1, -1):if s[i] == c:idx = ians[i] = min(ans[i], idx-i)return ans

230. 二叉搜索树中第K小的元素（）

暴力解法，利用二叉搜索树中序遍历是递增序列的特性。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:# 二叉搜索树的中序遍历是递增序列nums = []def dfs(root):if not root: returndfs(root.left)nums.append(root.val)dfs(root.right)dfs(root)return nums[k-1]

使用迭代法的话，可以不需要遍历整棵树，只需要找到K个从最小开始递增的数即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:# 使用迭代法来进行中序遍历，当从小到大找到k个数时就可以停止stack = []while root or stack:while root:# 先暂存根节点，一致往左遍历到空节点stack.append(root)root = root.leftroot = stack.pop()k -= 1if k == 0: return root.valroot = root.right

739. 每日温度

暴力解法，会超时。

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n = len(temperatures)res = [0] * nfor i in range(n-1):if temperatures[i+1] > temperatures[i]:res[i] = 1continuefor j in range(i+1, n):if temperatures[j] > temperatures[i]:res[i] = j - ibreakreturn res

单调栈解法：

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n = len(temperatures)res = [0] * nstack = []for i in range(n):temperature = temperatures[i]while stack and temperature > temperatures[stack[-1]]:prev_index = stack.pop()res[prev_index] = i - prev_indexstack.append(i)return res

438. 找到字符串中所有字母异位词

笨方法，划定一个长度为 m m m的窗口，在字符串 s s s上进行滑动，每次都对窗口内的字串进行排序，和排序后的 p p p进行比较。复杂度很高。为 O ( n m l o g ( m ) ) O(nmlog(m)) O(nmlog(m))。其中 n n n为 s s s的长度， m m m为 p p p的长度。勉强AC。

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:m, n = len(p), len(s)res = []sorted_p = sorted(p)for i in range(n-m+1):if sorted(s[i:i+m]) == sorted_p:res.append(i)return res

那么自然会想到还有一种字典的方法。

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:m, n = len(p), len(s)res = []counter_p = Counter(p)for i in range(n-m+1):if Counter(s[i:i+m]) == counter_p:res.append(i)return res

没想到的是，这个提交上去不仅速度一样慢，空间占用也很多。

那么，还有其他更快的方法吗？肯定是有的。

上面的两种做法有一个问题就是对每一个窗口都需要重新排序或者统计字母的频率，很容易想到这里面有重复计算。因为相邻两个窗口其实后一个只是在前一个窗口的基础上去掉了第一个，追加了之前窗口的后一个，那么每次只需要更新这两个就行了其实。

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:m, n = len(p), len(s)if m > n:return []res = []p_count = [0] * 26s_count = [0] * 26# 先对第一个窗口进行处理for i in range(m):p_count[ord(p[i]) - 97] += 1s_count[ord(s[i]) - 97] += 1if p_count == s_count:res.append(0)# 往后遍历for i in range(1, n-m+1):s_count[ord(s[i-1]) - 97] -= 1s_count[ord(s[i+m-1]) - 97 ] += 1if s_count == p_count:res.append(i)return res

543. 二叉树的直径Easy

经过一个节点 n o d e node node的最长路径和是：左子树最大深度加上右子树最大深度再加1。在求树的最大深度时，也会递归求每一个节点左子树和右子树的最大深度，所以只需要在求树的最大深度基础上进行一下修改。每次递归的时候都求一下当前最大路径。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:self.res = 0def dfs(root):if not root: return 0L = dfs(root.left)R = dfs(root.right)self.res = max(self.res, L + R + 1)return max(L, R) + 1dfs(root)return self.res - 1

238. 除自身以外数组的乘积

这一题主要难在两个额外的要求上，不能使用除法，必须在 O ( n ) O(n) O(n)的复杂度以内。

方法就是，两次遍历数组。维护一个全为1的数组 r e s res res，每次遍历到 i i i，都记录 i i i左边的所有数的乘积，然后让 r e s [ i ] res[i] res[i]乘上去。这样一来， r e s res res中每个数都是它在 n u m s nums nums中对应位置的左边的数的乘积。第二次便利的时候，记录每一个数右边的所有数的乘积，然后每个数乘。两次遍历就行了。

为了更简化，可以在一次遍历的时候直接把左右两边都算了。

class Solution:def productExceptSelf(self, nums: List[int]) -> List[int]:# 方法就是，记录每一个数字左边所有数字的积，记录每一个数字右边数字的积。# 然后每一个数字左边的积乘上右边的积即可。left_times = 1right_times = 1n = len(nums)res = [1] * nfor i in range(n):# 从左到右乘左边的数之积res[i] *= left_timesleft_times *= nums[i]# 从右到左res[n - i - 1] *= right_timesright_times *= nums[n - i - 1] return res

560. 和为 K 的子数组

暴力解法，两层循环，i为子数组结尾，j为子数组开头，判断他们之间的和是不是等于k。会超时。

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 要求的连续子数组count = 0n = len(nums)for i in range(n):sum = 0for j in range(i, -1, -1):sum += nums[j]if sum == k:count += 1return count

暴力解法

这一题是要找到所有连续子数组的和等于k的个数。那么怎么求一个数组的连续子数组呢。可以使用两层循环来实现。

n = len(nums)subnums = []
for i in range(n):for j in range(i, n):subnums.append(nums[i:j+1])

既然这样，稍作修改，就可以求连续子数组和为k的个数了。

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 要求的连续子数组count = 0n = len(nums)for i in range(n):for j in range(i, n):if sum(nums[i:j+1]) == k:count += 1return count

很明显，这么做的时间复杂度是 O ( n 3 ) O(n^3) O(n3)。因为除了两层for循环，还有一层求和。

其实，可以对上面方法做一些优化。因为我们求 n u m s [ i : j + 1 ] nums[i:j+1] nums[i:j+1]的下一次 n u m s [ i : j + 1 + 1 ] nums[i:j+1+1] nums[i:j+1+1]，其实只比前一次多了一个 n u m s [ j + 1 ] nums[j+1] nums[j+1]。那么我们就没必要每次都从i开始算了。

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 要求的连续子数组count = 0n = len(nums)for i in range(n):sum = 0for j in range(i, n):sum += nums[j]if sum == k:count += 1return count

这一下，时间复杂度降到了 O ( n 2 ) O(n^2) O(n2)。

但是很可惜，这样依然会超时。

前缀和

什么是前缀和：前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）

通常，会在前缀和首位放一个0。比如数组 [ 1 , 2 , 3 ] [1,2,3] [1,2,3]。其前缀和是 [ 0 , 1 , 2 , 6 ] [0,1,2,6] [0,1,2,6]

前缀和通常可以帮助我们快速计算某个区间内的和。比如我们要算 i , j i,j i,j之间的和，那么就是 n u m s [ i ] + n u m s [ i + 1 ] + ⋯ + n u m s [ j ] nums[i] + nums[i+1] + \cdots +nums[j] nums[i]+nums[i+1]+⋯+nums[j]。他可以看作是 n u m s [ 0 ] + n u m s [ 1 ] + ⋯ + n u m s [ i ] + n u m s [ i + 1 ] + ⋯ + n u m s [ j ] nums[0] + nums[1] + \cdots + nums[i] + nums[i+1] + \cdots +nums[j] nums[0]+nums[1]+⋯+nums[i]+nums[i+1]+⋯+nums[j]减去 n u m s [ 0 ] + n u m s [ 1 ] + ⋯ + n u m s [ i − 1 ] nums[0] + nums[1] + \cdots + nums[i-1] nums[0]+nums[1]+⋯+nums[i−1]。这个式子也是 p r e S u m [ j ] − p r e S u m [ i − 1 ] [j] - [i-1] [j]−[i−1]。

那么，我们先遍历一次数组，求出前缀和数组。之后这个数组可以代替我们最开始暴力解法的 s u m sum sum函数。但是很遗憾，这种做法复杂度还是 O ( n 2 ) O(n^2) O(n2)

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 要求的连续子数组count = 0n = len(nums)preSum = [0]# 求前缀和数组tmp = 0for i in range(n):tmp += nums[i]preSum.append(tmp)# 求和为k的连续子数组，求i到j之间的和for i in range(1, n+1):for j in range(i, n+1):if preSum[j] - preSum[i-1] == k:  # preSum[j] - preSum[i-1]代表着在nums数组中，前j个数之和减去前i-1个数之和count += 1return count

进一步优化的话，我们可以边算前缀和，边统计。遍历过程中，我们统计历史中每一个前缀和出现的个数，然后计算到 i i i位置（含 i i i）的前缀和 p r e s u m 减去目标 k k k在历史上出现过几次，假如出现过 m m m次，代表第 i i i位以前（不含 i i i）有 m m m个连续子数组的和为 p r e s u m − k - k −k，这 m m m个和为 p r e s u m − k - k −k的连续子数组，每一个都可以和 p r e s u m 组合成为 p r e s u m − ( p r e s u m − k ) = k - ( - k) = k −(−k)=k。

用ppt画了个示意图，红色的是当前遍历到的前缀和 p r e s u m ，加入他之前有两个前缀和等于 p r e s u m − k - k −k（蓝色范围），那么很明显，就会有两个连续子数组的和为 k k k，对应图中橙色范围。

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 要求的连续子数组count = 0n = len(nums)preSums = collections.defaultdict(int)preSums[0] = 1presum = 0for i in range(n):presum += nums[i]# if preSums[presum - k] != 0:count += preSums[presum - k]   # 利用defaultdict的特性，当presum-k不存在时，返回的是0。这样避免了判断preSums[presum] += 1  # 给前缀和为presum的个数加1return count