和为 K 的子集(返回子集数量)

我们完全没必要设置一个 path, 只需要动态维护当前子集的和就好, 这样做还有一个好处是, 我们可以方便剪枝, 题目明确 nums 内都是正数, 所以 cur_sum 已经比 k 大的时候, 已经没必要继续 dfs了

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        res = 0
        n = len(nums)
      
        def dfs(count, cur_sum):
            nonlocal res
            # 终止条件
            if cur_sum == k:
                res += 1
                return
            # 剪枝条件
            if count == n or cur_sum > k:
                return
            # 不选当前节点
            dfs(count + 1, cur_sum)
            # 选当前节点
            dfs(count + 1, cur_sum + nums[count])
      
        dfs(0, 0)
        return res

和为k的子数组

其实这就跟两数之和是一个思路寻找 target - cur, 引入 defaultdict省略了一个 if判断, dic存储的是前缀和相等的计数

值得一提的是, dic[0]我们需要初始化为 1, 因为单独一个数作为子数组的情况是存在的

from collections import defaultdict
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dic = defaultdict(int)
        dic[0] = 1
        cur = 0
        ans = 0
        # 前缀和 + 计数
        for num in nums:
            cur += num
            ans += dic[cur - k]
            dic[cur] += 1

        return ans

func subarraySum(nums []int, k int) int {
    count := make(map[int]int)
    count[0] = 1
    cur := 0
    ans := 0

    for _, v := range nums{
        cur += v
        if c, ok := count[cur - k]; ok {
            ans += c
        }
        count[cur] ++
    }

    return ans
}

滑动窗口最大值

要点:

• 通过直接维护当前窗口的最大值必定超时, 普通的出入动态维护容易漏, 难以处理多个最大值, 最大值弹出之后, 难以更新当前最大值
• 使用双端队列动态维护一个不减的队列
• 队列内存储的应该是下标, 逻辑如下:
  1. 新入队的下标一定是最大的, 所以下标必定递增
  2. 我们需要维护队列里面没有比入队更小的数, 他只会出现在队尾, 因为我们是动态维护
  3. 犹豫每次只会入一个元素, 也就是至多只有一个元素过期, 我们的队列是递增的, 所以只会出现在队首, 需要判断队首有没有过期
  4. 当现在已经遍历到了窗口大小时, 维护的队首就是最大值

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        res = []

        for i, v in enumerate(nums):
            # 弹出队尾比入队小的值
            while q and nums[q[-1]] <= nums[i]:
                q.pop()
            # 加入当前元素
            q.append(i)
            # 检查队首是否过期
            if q[0] <= i - k :
                q.popleft()
            # 检查是否已经出现答案
            if i >= k - 1:
                res.append(nums[q[0]])
      
        return res

全排列

经典dfs, 提供我的两种写法

# 原地修改法
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans, n = [], len(nms)
        path = [0] * n

        def dfs(cnt: int, s):
            if cnt == n:
                ans.append(path.copy())
            for i in s:
                path[cnt] = i
                dfs(cnt + 1, s - {i})
      
        dfs(0, set(nums))
        return ans
# 回溯写法(空间开销高一点)
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans, n = [], len(nums)
        path = []

        def dfs(cnt: int, s):
            if cnt == n:
                ans.append(path.copy())
            for i in s:
                path.append(i)
                dfs(cnt + 1, s - {i})
                path.pop()
              
        dfs(0, set(nums))
        return ans

# 需注意, 这样的排列没办法处理重复, 直截了当的方法是每次 append 检查当前 ans 是否已有相同的排列, 但是这样复杂度会增加 n, 我们可以先 sort 然后就可以通过计数和一个布尔数组的方法来判断有没有取过, 没有写, 遇到具体题目再补

子集

经典 dfs, 这里给出我的两种思路

# 传路径写法
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)

        def dfs(cnt: int, path):
            # 终止条件
            if cnt == n:
                ans.append(path.copy())
                return
            # 选
            dfs(cnt + 1, path + [nums[cnt]])
            # 不选
            dfs(cnt + 1, path)

        dfs(0, [])
        return ans
# 回溯写法
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans, path = [], []
        n = len(nums)

        def dfs(cnt: int):
            if cnt == n:
                ans.append(path.copy())
                return 
              
            dfs(cnt + 1)
            path.append(nums[cnt])
            dfs(cnt + 1)
            path.pop()

        dfs(0)
        return ans
# 还有位运算写法, 不熟练, 没写

电话号码的字母组合

关键在于, 怎么设置入参, 初版我采用了当前可选字符作为一个入参

# 第一次尝试(回溯)
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {
            '1': '',
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
        }

        n = len(digits)
        ans = []
        path = [''] * n
      
        if n == 0:
            return []
        digits += '1'
        def dfs(cur, cnt):
            if cnt == n:
                ans.append(''.join(path))
                return
          
            for i in cur:
                path[cnt] = i
                dfs(dic[digits[cnt + 1]], cnt + 1)

        dfs(dic[digits[0]], 0)
        return ans

但是这个版本有很多不必要的操作(但是易于理解)

• 首先, 引入了 1 这个键来防止取 cur 越界
• 其次, dfs 的入参没有设置好, 完全没必要入一个dic[digits[0]], 这完全可以在函数内部取, 而不是通过入参, 就是这个原因, 导致必须加长一个字符
• 所以, 我优化了一个版本, 简化了入参, 减少了开销, 也更加简洁

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
        }

        n = len(digits)
        ans = []
        path = [''] * n
      
        if n == 0:
            return []

        def dfs(cnt):
            if cnt == n:
                ans.append(''.join(path))
                return
          
            for i in dic[digits[cnt]]:
                path[cnt] = i
                dfs(cnt + 1)

        dfs(0)

        return ans