Hot 100 第二部分

Hot 100 第二部分

Hot 100 指的是 LeetCode 上的一个题单

撰写第 34 ~ 67 题

为什么是 67 呢，因为没开会员写不了 253 会议室 II 哈哈哈

339 除法求值

这是一个判断图是否有环的问题，因此最优解就是并查集，更新带上权值即可

这里注意下我们一开始时不知道已有的所有节点，所以只能用字典构路径，而不是用数组

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        father = {}   # father[x] = parent
        devide = {}   # devide[x] = x / father[x]

        def add(x: str) -> None:
            if x not in father:
                father[x] = x
                devide[x] = 1.0

        def find(x: str):
            """
            return (root, x/root)
            devide[x] = x / root
            """
            if x not in father:
                return None, -1.0
            if father[x] == x:
                return x, 1.0

            p = father[x]
            root, w = find(p)          # w = p / root
            father[x] = root
            devide[x] *= w             # (x/p) * (p/root) = x/root
            return root, devide[x]

        def union(a: str, b: str, val: float) -> None:
            """
            a / b = val
            wa = a/rootA
            wb = b/rootB
            rootA / rootB = val * wb / wa
            """
            add(a)
            add(b)

            ra, wa = find(a)
            rb, wb = find(b)
            if ra == rb:
                return
            father[ra] = rb
            devide[ra] = val * wb / wa

        for (a, b), val in zip(equations, values):
            union(a, b, val)

        ret = []
        for x, y in queries:
            if x not in father or y not in father:
                ret.append(-1.0)
                continue
            rx, wx = find(x)
            ry, wy = find(y)
            if rx != ry:
                ret.append(-1.0)
            else:
                ret.append(wx / wy)

        return ret

394 字符串解码

因为有嵌套的存在，所以一般使用栈的形式处理这种

遇到 ‘[’ 就进，遇到 ‘]’ 就退到上一个 ‘[’ ，然后把处理完的字符串放进去

数字处理时候，遇到 ‘[’ 表示当前数字完结了，把数字放进栈

标准解答会更加简洁，我这边写的则相对直观一点

class Solution:
    def decodeString(self, s: str) -> str:
        str_stk = []
        num_stk = []
        num = 0

        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '[':
                num_stk.append(num)
                num = 0 # 这个数字处理完了，清空并入栈
                str_stk.append(c)
            elif c == ']':
                parts = []
                while str_stk and str_stk[-1] != '[':
                    parts.append(str_stk.pop())
                str_stk.pop()  # 弹出 '['
                repeat_str = "".join(reversed(parts)) # 注意这里弹出来是颠倒的
                k = num_stk.pop()
                str_stk.append(repeat_str * k) # 放回栈中
            else:
                str_stk.append(c)

        return "".join(str_stk)

347 前 K 个高频元素

使用 heapq 的 api，小顶堆解法

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        mp = Counter(nums)
        heap = []
        for key, val in mp.items():
            if len(heap) < k:
                heapq.heappush(heap, (val, key))
            elif val > heap[0][0]:
                heapq.heapreplace(heap, (val, key))

        return [key for _, key in heap]

338 比特位计数

这个实际上使用dp来写，而不是逐个运算，最后一个用位运算

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        for num in range(1, n + 1):
            dp[num] = dp[num >> 1] + (num & 1)
        return dp

337 打家劫舍 III

经典 dp, 注意是取最优解, 而不是一定偷

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return (0, 0)  # (不偷, 偷)

            l0, l1 = dfs(node.left)
            r0, r1 = dfs(node.right)

            not_rob = max(l0, l1) + max(r0, r1) # 孩子可以偷也可以不偷
            rob = l0 + r0 + node.val    # 一定不能偷

            return (not_rob, rob)

        return max(dfs(root))

121 买卖股票的最佳时机

计算最大差值，抛砖引玉的砖

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_p = float('inf')
        ret = 0
        for p in prices:
            ret = max(p - min_p, ret)
            min_p = min(p, min_p)

        return ret

312 戳气球

这道题是一个 hard 的区间dp，将一个长问题分为多个子区间去完成，要点就是状态转移是**“最后一步的操作”，**区间有可能是二维双向扩展的，他们的特点是dp需要重建，做一个决策会改变问题结构

相似的题目还有：516, 647, 1039, 1130, 375, 546（越来越难）

dp 数组含义：在区间 (l, r)（注意是开区间）里最后戳的是 k，那么最后一次得到的金币

这个就能够固定左右边界，然后获得的收益只和 k 有关系了，而问题被分成了 k 左右两个区间

把 dp 数组设置为 dp[a][b] 是区间 (a, b) 之间的最优解，从最小的区间开始向上推进

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        a = [1] + nums + [1]
        m = len(a)
        dp = [[0] * m for _ in range(m)]

        # dp[l][r] 表示开区间 (l, r) 全部戳完的最大金币
        for l in range(m - 1, -1, -1):
            for r in range(l + 2, m):   # 至少留一个 k：l < k < r
                best = 0
                for k in range(l + 1, r):
                    best = max(best, dp[l][k] + dp[k][r] + a[l] * a[k] * a[r])
                dp[l][r] = best

        return dp[0][m - 1]

309 买卖股票的最佳时机含冷冻期

代码随想录经典题，略

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        free, hold, frozen = 0, -prices[0], 0
        for p in prices[1:]:
            new_frozen = hold + p
            new_free = max(free, frozen)
            new_hold = max(hold, free - p)
            free, hold, frozen = new_free, new_hold, new_frozen
        return max(free, frozen)

301 删除无效的括号

hard 回溯，有一定的难度，注意回溯的一个特征就是找到所有的解

注意到：在某个区间内，) 数量一定是小于等于 ( 数量的，否则必定无法匹配成功，这是剪枝的关键地方

不能全局到结尾来统计左右括号数量，一定要逐个区间计算，否则会出现 )( 不用删的错误情况

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        lrem = rrem = 0
        for c in s:
            if c == '(':
                lrem += 1
            elif c == ')':
                if lrem == 0:
                    rrem += 1   # 左边没了，只能删右边
                else:
                    lrem -= 1   # 预计匹配，左边少删一个

        def is_valid(s):
            balance = 0
            for c in s:
                if c == '(':
                    balance += 1
                elif c == ')':
                    balance -= 1
                if balance < 0:
                    return False
            return (balance == 0)

        def dfs(start: int, lrem: int, rrem: int, cur: str):
            # 只要超删就剪枝
            if lrem < 0 or rrem < 0:
                return
            # 删够了才检查合法性
            if lrem == 0 and rrem == 0 and is_valid(cur):
                ret.append(cur)
                return

            for i in range(start, len(cur)):
                # 只对括号尝试删除
                if cur[i] not in '()':
                    continue
                # 去重：同一层如果连续相同字符，只删第一个
                if i > start and cur[i] == cur[i - 1]:
                    continue

                nxt = cur[:i] + cur[i + 1:]
                if cur[i] == '(':
                    dfs(i, lrem - 1, rrem, nxt)
                else:  # cur[i] == ')'
                    dfs(i, lrem, rrem - 1, nxt)


        ret = []
        dfs(0, lrem, rrem, s)
        return ret

300 最长递增子序列

dp方法就是从前面找一个比他小的进行状态累加

但是有 二分+贪心 的最优解，比较难想：如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小

贪心就在于：我一定会在同一个位置选择更小的那个数，使得后面的数尽可能比我这个位置的数字大

如果这个数比我所有已知的数字都大，那么就是我的序列就上升一次，否则替换一个台阶

具体的讲解可以看看

from bisect import bisect_left
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = [] # 这是一个有序数组
        for n in nums:
            idx = bisect_left(tails, n) # 找到 <= x 的下标位置
            if idx == len(tails): # 是结尾，直接加入
                tails.append(n)
            else:
                tails[idx] = n
        return len(tails)

287 寻找重复数

图论判环算法

297 二叉树的序列化与反序列化

主要是要标记 null 这一个注意点，如果是前序遍历就是顺序解码

可以回去复习一下：根据前+中遍历来恢复一个二叉树的算法

class Codec:
    def serialize(self, root):
        # 前序遍历
        ret: str = []
        def preTraversal(curr):
            nonlocal ret
            if curr is None:
                ret.append('#')
                return

            ret.append(str(curr.val))
            preTraversal(curr.left)
            preTraversal(curr.right)

        preTraversal(root)
        # print(ret)
        return ','.join(ret)

    def deserialize(self, data):
        it = iter(data.split(','))
        def build():
            x = next(it)
            if x == '#':
                return None
            node = TreeNode(int(x))
            node.left = build()
            node.right = build()
            return node

        return build()

287 寻找重复数

这题目和 142 环形链表 II 都使用 Floyid 算法可以判断环的位置

把下标看成是一个节点，把 nums[i] 看成是下一个节点，就是一个链表找环的题目

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # Floyid 环算法
        slow = nums[0]
        fast = nums[nums[0]]

        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]
        # 找到相遇点，回去找入环点
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow

283 移动零

双指针移动所有不是 0 的数据

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        # 原地修改不返回， 把所有不是 0 的全部向前移动
        n = len(nums)
        slow = 0
        for fast in range(n):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
        while slow < n:
            nums[slow] = 0
            slow += 1

279 完全平方数

动态规划经典题目

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1) # 1 ~ n
        dp[0] = 0
        for i in range(1, n + 1):
            for sq in range(int(sqrt(i)) + 1):
                dp[i] = min(dp[i], dp[i - sq * sq] + 1)
        return dp[n]

253 会议室 II

没会员，下次一定

240 搜索二维矩阵 II

把起点设置在左下角，或者右上角，就可以每次判断去除一整行或者列

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        i, j = m -1, 0
        while i >= 0 and j < n:
            if matrix[i][j] > target:
                i -= 1
            elif matrix[i][j] < target:
                j += 1
            else:
                return True
        else:
            return False

239 滑动窗口最大值

可以用 top k 的同样思路，使用大顶堆，一旦堆顶过期了就弹出，否则只需要 push 就行了

这里写一下更优解法，单调队列的方式，这个还是蛮难写的，要重点学一学：

1. 如果遇到 i < j 且 nums[i] <= nums[j] 的时候，一旦 nums[j]入队就可以把 nums[i]直接丢弃了（只要 nums[j] 在就一定是他更大）
2. 如果出口处这个最大的元素已经被窗口抛弃了，则正常弹出

这两条规则分别对应 窗口右侧加入，窗口左侧放入两种操作，这就构成了我们的整个单调队列，最大值永远是出口处的元素

从右侧放进来的元素，会从右边一直删除元素直到，他左边那个值比他大（或者他就是最大的），这样左边永远是更大的值

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = deque()  # 存下标，保证 nums[q] 单调递减（队首最大）

        for i in range(k):
            while q and nums[q[-1]] <= nums[i]:
                q.pop()          # 从队尾弹出更小/相等的
            q.append(i)
        ret = [nums[q[0]]]

        for i in range(k, n):
            if q and q[0] <= i - k:
                q.popleft() # 先移除过期（只可能在队首）
            while q and nums[q[-1]] <= nums[i]:
                q.pop() # 比当前值来的早，还比当前值小，没有任何维护的意义

            q.append(i)
            ret.append(nums[q[0]])

        return ret

22 括号生成

是 LeetCode 301 删除无效的括号 的派生题目，是那道题的子集，更简单的版本

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        path = []

        def backtrace(left, right):
            if left == 0 and right == 0:
                res.append("".join(path))
                return

            if left > right:    # 右括号数 > 左括号
                return

            if left > 0:
                path.append('(')
                backtrace(left - 1, right)
                path.pop()

            if right > 0:
                path.append(')')
                backtrace(left, right - 1)
                path.pop()

        backtrace(n, n)
        return res

49 字母异位词分组

判断异位词应该使用 Hash，这里主要使用一个 26 维的向量（实际上就是一个 hash）作为 key

外层再进行一个 hash 将所有的（26维向量相同）异位词放一起

这里插播一个 python 的要点，dict.get() 拿到的不是原来的数据，修改是不会写入到 dict 中的，应该使用 dict.setdefault 或者直接初始化 dict 为 mp = defaultdict(list)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = {}
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            key = tuple(count)
            mp.setdefault(key, []).append(s)
        return list(mp.values())

48 旋转图像

这题有两种解法，一个是四点交换（算边界条件麻烦点），一个是转置+对称交换

其中四点变换（计算机方法）的方法更加适合 cpp 因为看起来清晰点，而且操作更加底层

实际上这两个算法的复杂度都是空间 O(1) 时间 O(n^2) ，没有什么区别，这里用 cpp 写吧，逻辑清楚点，不然就是 4 元素 tuple 直接交换了

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i <= n / 2 - 1; i++) {
            for (int j = 0; j <= (n - 1) / 2; j++) {
                // 四点变换
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i -1][n - j -1];
                matrix[n - i -1][n - j -1] = matrix[j][n - i -1];
                matrix[j][n - i -1] = tmp;
            }
        }
    }
};

46 全排列

全排列回溯可以用 标记数组的方式来一个个遍历

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        used = [False] * n
        ret = []
        curr = []

        def backtrace():
            if len(curr) == n:
                ret.append(curr.copy())
                return

            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                curr.append(nums[i])
                backtrace()
                curr.pop()
                used[i] = False

        backtrace()
        print(ret)
        return ret

42 接雨水

传奇背诵题接雨水，要么单调栈，要么双指针

class Solution:
    def trap(self, height: List[int]) -> int:
        stk = []
        ret = 0
        n = len(height)
        for i in range(n):
            while stk and height[stk[-1]] <= height[i]:
                # 单调栈：非空且栈顶 <= 当前值，需要弹出
                mid_idx = stk.pop()
                if stk: # 表示 mid_idx 左边有比他大的, 可以接水
                    left_idx = stk[-1]
                    l = i - left_idx -1
                    h = min(height[left_idx], height[i]) - height[mid_idx]
                    ret += l * h
                    # print(f"{l} * {h}, {ret}, ({left_idx}, {mid_idx}, {i})")
            stk.append(i)
        return ret

39 组合总和

经典回溯

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ret = []
        n = len(candidates)
        def backtrace(idx, path, left):
            if left == 0:
               ret.append(path.copy())
               return

            for i in range(idx, n):
                if candidates[i] > left:
                path.append(candidates[i])
                    break
                backtrace(i, path, left - candidates[i])
                path.pop()
        backtrace(0, [], target)
        return ret

543 二叉树的直径

递归简单题

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        ret = 0

        def dfs(root):
            if root is None:
                return 0

            l = dfs(root.left)
            r = dfs(root.right)
            nonlocal ret
            ret = max(l + r, ret)
            return max(l, r) + 1
        dfs(root)
        return ret

34 在排序数组中查找元素的第一个和最后一个位置

这道题目很好，涉及到了二分查找的本质，我们可以从中抽象出二分查找的通用模板

二分查找边界的本质：一个结构，对某一个 bool 表达式的值呈现单调性，我们通过对半取区间来找到第一个发生变化的区间

False False False True True True
                ↑
           我们要找的点

所以说，找下界就是找到第一个让 nums[i] >= target 从 false 变为 true 的点，上界就是第一个让 nums[i] > target 从 false 变为 true的点

我们列出循环不变量的表达式（伪代码）：bool [0, l) == Talse , bool [r, n) == True

所以有这个通用公式（面向于我们从 False 转到 True 的数组单调性）：

if f(mid) == True: # f(mid) == True, 保证了 [r, n) 是 True
    r = mid
else:  # 保证了 [0, mid + 1) 是 False
    l = mid + 1

最后这道题的解法是

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 二分查找, 一个是 [0, l) <= target, 另一个是 [l, n) > target
        n = len(nums)
        def lower():  # 找到第一个 nums[i] >= target
            l, r = 0, n
            while l < r: # [l, r)
                mid = (l + r) >> 1
                if nums[mid] >= target:
                    r = mid
                else:
                    l = mid + 1
            return l

        def upper(): # 找到第一个 nums[i] > target
            l, r = 0, n
            while l < r: # [l, r)
                mid = (l + r) >> 1
                if nums[mid] > target:
                    r = mid
                else:
                    l = mid + 1
            return l
        l = lower()
        u = upper()

        if l == n or nums[l] != target:
            return(-1, -1)
        else:
            return(l, u - 1)

33 搜索旋转排序数组

两次二分，实际上和上一题目同类型，理解了二分就很快写得出来

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        last = nums[-1]

        def find_split():
            l, r = 0, n
            while l < r:
                mid = (l + r) // 2
                if nums[mid] <= last:
                    r = mid
                else:
                    l = mid + 1
            return l

        pivot = find_split()

        def bin_search(l, r):  # 等值二分查找
            while l < r:
                mid = (l + r) // 2
                if nums[mid] == target:
                    return mid
                if nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid
            return -1

        if target <= last:
            return bin_search(pivot, n)
        else:
            return bin_search(0, pivot)

32 最长有效括号

这道题有两种写法，一个是 dp （讨论两种情况），另一个是双向扫描贪心（太难想到了）

由于 dp 虽然不是最优解但是也有一定的参考价值，这里把两种方式都写一下

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        dp = [0] * n  # dp[i]: 以 i 结尾的最长有效括号长度
        ret = 0
        for i in range(1, n):
            if s[i] == '(':
                continue  # 以 '(' 结尾不可能是有效括号
            if s[i - 1] == '(':
                # 情况1：紧邻 ()
                dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
            else:
                # 情况2：...))  尝试跨过 dp[i-1] 那段去找 '('
                pre = dp[i - 1]
                j = i - pre - 1  # 可能与 s[i] 匹配的 '(' 位置
                if j >= 0 and s[j] == '(':
                    dp[i] = pre + 2 + (dp[j - 1] if j >= 1 else 0)
            ret = max(ret, dp[i])
        return ret

遇到 '('：left += 1，遇到 ')'：right += 1

若 right > left：说明右括号过多，当前段不可能再变合法，重置 left = right = 0

若 left == right：当前段合法，长度 2 * right，更新答案

左右各扫描一次就能补齐所有答案

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        ans = 0

        # left -> right
        left = right = 0
        for ch in s:
            if ch == '(':
                left += 1
            else:
                right += 1
            if right > left:
                left = right = 0
            elif left == right:
                ans = max(ans, 2 * right)

        # right -> left
        left = right = 0
        for ch in reversed(s):
            if ch == '(':
                left += 1
            else:
                right += 1
            if left > right:
                left = right = 0
            elif left == right:
                ans = max(ans, 2 * left)

        return ans

31 下一个排列

模拟思路题目，写过一遍就好了

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        pre = -1
        i = n - 1
        def reverse_nums(nums, a, b):
            while a < b:
                nums[a], nums[b] = nums[b], nums[a]
                a += 1
                b -= 1
        while i >= 0:
            if nums[i] < pre:
                break
            pre = nums[i]
            i -= 1
        else:
            reverse_nums(nums, 0, n - 1)    # 重新排列最小值
            return
        # 找到第一个 比 nums[i] 大的交换一下
        for j in range(n - 1, i, -1):
            if nums[i] < nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
                break
        reverse_nums(nums, i + 1, n - 1)

538 把二叉搜索树转换为累加树

这道题有一个 Moris 遍历的方法，可以使用 O(1) 的空间，后面可以学习一下，这里先放一个普通DFS 解法

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        total = 0
        def dfs(root):
            if root is None:
                return
            # 右中左
            nonlocal total
            dfs(root.right)
            total += root.val
            root.val = total
            dfs(root.left)
        dfs(root)
        return root

23 合并 K 个升序链表

这里直接使用最小堆，注意 heapq 中没有 cmp 的 key 只能自行构造元组

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        heapq.heapify(heap)
        uid = 0

        for node in lists:
            if node:
                uid += 1
                heapq.heappush(heap, (node.val, uid, node))

        dummy = ListNode()
        curr = dummy
        while heap: # 只要非空
            _, _, nd = heapq.heappop(heap)
            curr.next = nd
            curr = curr.next
            if nd.next is not None:
                uid += 1
                heapq.heappush(heap, (nd.next.val, uid, nd.next))
        return dummy.next

560 和为 K 的子数组

这不是一个 dp 题目，连续子数组求和是前缀和的应用场景

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        total = 0
        count = defaultdict(int)
        count[0] = 1
        ret = 0
        for n in nums:
            total += n # 当前位置的前缀和
            ret += count[total -  k]    # 找已经遇到的更小的前缀和点
            count[total] += 1
        return ret

21 合并两个有序链表

白给题目

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        curr = dummy
        l1, l2 = list1, list2
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 if l1 is not None else l2
        return dummy.next

20 有效的括号

白给题经典栈解法，注意最后栈一定要保持是空的

class Solution:
    def isValid(self, s: str) -> bool:
        mp = {')' : '(', '}'  : '{', ']' : '['}
        stk = []
        for c in s:
            if c not in mp:
                stk.append(c)
            else:
                if not stk or stk.pop() != mp[c]:
                    return False
        return not stk # 最后栈必须是空的

19 删除链表的倒数第 N 个结点

简单的双指针题目，但是要注意的边界条件其实蛮多的，建议是实际手写一次试一下

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow, fast = dummy, dummy
        for i in range(n):
            fast = fast.next
        while fast.next is not None:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next

17 电话号码的字母组合

相对简单好想到的回溯算法

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        mp = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno',
              'pqrs', 'tuv', 'wxyz']
        n = len(digits)
        ret = []
        if not digits:
            return []
        def backtrace(path, idx):
            if idx == n:
                ret.append("".join(path))
                return
            for c in mp[int(digits[idx])]:
                path.append(c)
                backtrace(path, idx + 1) # 下一个字母
                path.pop()
        backtrace([], 0)
        return ret