Hot 100 第一部分

Hot 100 第一部分

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

一共 100 题，第一部分撰写第 1 ~ 33 题，已经全部完成

160 相交链表

这里给出最标准的写法（Python 风格）

为什么不会无限循环的原因是，两个节点走的总长度都是 a + b，最后一定会同时移动到 None 然后退出循环

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        # 快捷方法，直接到对方的头节点，然后统计第一个相等的数值
        # 本质上是将差值自动应用
        if not headA or not headB:
            return None

        pA, pB = headA, headB

        while pA is not pB:
            pA = pA.next if pA else headB
            pB = pB.next if pB else headA

        return pA

236 二叉树的公共祖先

后序遍历，上浮答案

需要明确向外传递节点的逻辑

另外可以考虑一下节点本身就是 LCA 的情况：直接把自身返回，另一个节点永远不会被返回，所以永远上报的一个是 None 一个是 LCA，最终返回的就是 LCA，这个逻辑很难想

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 后序遍历
        if not root or root is p or root is q:
            # 1. root 为 None，说明这一支没找到
            # 2. root 是 p 或 q，找到目标之一，向上返回
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        # 两边都有东西，说明 p 和 q 分布在 root 的不同子树，root 就是 LCA
        if left and right:
            return root

        # 只有一边非空，说明 p、q 都在这一边，或者只找到一个，继续向上传递
        return left if left else right

234 回文链表

有两种方式，如果需要 O(1) 的空间复杂度需要对原来的链表进行修改

如果不允许修改就使用栈的方式

重点在于计算清除中间节点和终止数量，一般推荐从0开始+对0空节点的特殊判断（本题题目限定了不会有空节点）

另外如果使用了翻转链表的方式，注意使用快慢指针的方式来找到中间节点

class Solution:
    def reverseList(self, head):
        # 从 head 开始翻转后续所有的链表
        curr = head
        pre = None
        while curr:
            temp = curr.next
            curr.next = pre
            pre = curr
            curr = temp
        return pre

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 快慢指针找到中间位置，原地翻转
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 如果 fast 不为空，说明是奇数长度，需要跳过中间节点
        if fast:
            slow = slow.next

        second = self.reverseList(slow)
        first = head
        while second is not None:
            if first.val != second.val:
                return False
            first = first.next
            second = second.next

        return True

739 每日温度

这里遇到了如何通过下标的方式来访问一个列表，答案是使用 enumeratre

如果一个 list 是空的就自动变成 False

python 中的 pop 是会返回被弹出的值的

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # 单调栈
        stk = []
        ret = [0] * len(temperatures)

        for i, num in enumerate(temperatures):
            while (stk and num > temperatures[stk[-1]]):  # list 为空自动变成 False
              idx = stk.pop()  # list 的 pop 会自动返回弹出的元素
                ret[idx] = i - idx
            stk.append(i)
        return ret

226 翻转二叉树

简单题，后序遍历递归

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 后序遍历
        if root is None:
            return None
        self.invertTree(root.left)
        self.invertTree(root.right)
        # 本层逻辑
        root.left, root.right = root.right, root.left
        return root

221 最大正方形

经典 dp 的写法：用某个结尾值来表示 dp 矩阵的意义，同时控制连续性

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # 定义一个以(x, y)为右下角的最大正方形的边长大小
        m = len(matrix)
        n = len(matrix[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        ret = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if matrix[i - 1][j - 1] == "1":
                    # 这个格子是 1
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
                else:
                    dp[i][j] = 0
                ret = max(ret, dp[i][j])
        return ret * ret

215 数组中的第 k 个最大元素

使用最小堆进行操作

注意：应该学会优先级队列的底层操作逻辑（堆，一种基于完全二叉树的数据结构）

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 最小堆，使用 heapq 实现，默认就是最小堆
        heap = []
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]

208 实现 Trie 前缀树

使用 dict 可以省去一个 标记 curr 节点代表的字符

class Trie:
    def __init__(self):
        self.children = {} # 下一个的一组树形
        self.is_node = False

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            node = node.children.setdefault(c, Trie())
        node.is_node = True

    def search(self, word: str) -> bool:
        node = self
        for s in word:
            node = node.children.get(s, None)
            if node is None:
                return False
        return node.is_node

    def startsWith(self, prefix: str) -> bool:
        node = self
        for s in prefix:
            node = node.children.get(s, None)
            if node is None:
                return False
        return True

207 课程表

拓扑排序经典题目，掌握就不难

注意一些复杂度的简化方式

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses

        for a, b in prerequisites:   # b -> a
            graph[b].append(a)
            indeg[a] += 1

        q = deque(i for i in range(numCourses) if indeg[i] == 0)
        learned = 0

        while q:
            u = q.popleft()
            learned += 1
            for v in graph[u]:
                indeg[v] -= 1
                if indeg[v] == 0: # 遍历的时候加入队列
                    q.append(v)

        return learned == numCourses

206 反转链表

交换 next 注意不能动下一个，因为下一个动了，下一次循环的时候就丢失了 next 信息

想起来简单，但是实际操作有要注意的点

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        pre = None
        while curr:
            tmp = curr.next
            curr.next = pre
            pre = curr
            curr = tmp
        return pre

200 岛屿数量

简单的遍历，这里写DFS 算法

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        m = len(grid)
        n = len(grid[0])

        def dfs(x, y):
            if not (0 <= x < m and 0 <= y < n):
                return
            if grid[x][y] == '0':
                return

            grid[x][y] = '0'  # 标记访问过
            for dx, dy in direction:
                dfs(x + dx, y + dy)

        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    dfs(i, j)

        return count

198 打家劫舍

经典 dp 表示收益最大的情况

class Solution:
    def rob(self, nums: List[int]) -> int:
        l = len(nums)
        dp = [0] * l
        dp[0] = nums[0]
        if l == 1:
            return dp[0]
        dp[1] = max(nums[1], nums[0])
        for i in range(2, l):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        return dp[l - 1]

169 多数元素

使用投票法，只要是候选人他的票数一定超过一半，很巧妙的方法求众数

或者也可以使用排序算法（应该都能想到把）

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        can = None
        count = 0
        for n in nums:
            if count == 0:
                can = n # 换人和改票数一定要绑定
                count = 1
            elif n == can:
                count += 1
            else:
                count -= 1
        return can

238 除自身以外最大数组成绩

扫描两边，分别使用前后缀

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        l = len(nums)
        pre = 1
        after = 1
        ret = [1] * l
        for i in range(l):
            ret[i] = pre
            pre *= nums[i]
        for i in reversed(range(l)):
            ret[i] *= after
            after *= nums[i]
        return ret

155 最小栈

维护两个栈即可，没有实际难度，见过就会

class MinStack:
    def __init__(self):
        self.stack = []
        self.ministack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if self.ministack:
            self.ministack.append(min(val, self.ministack[-1]))
        else:
            self.ministack.append(val)

    def pop(self) -> None:
        self.stack.pop()
        self.ministack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.ministack[-1]

152 乘积最大子数组

注意要同时维护最大值和最小值，因为负数可以乘以负数来逆袭

这里用的是 O(1) 复杂度的，但是实际上一般是写完 O(n) 再优化为滚动数组的

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        lastmin = nums[0]
        lastmax = nums[0]
        ret = nums[0]

        for i in range(1, len(nums)):
            x = nums[i]
            tmp_min = min(x, lastmax * x, lastmin * x)
            lastmax = max(x, lastmax * x, lastmin * x)
            lastmin = tmp_min
            ret = max(ret, lastmax)

        return ret

148 排序链表

链表的排序是归并排序算法

1. 反复二分法，直到只有两个节点（链表的二分法使用快慢指针实现的）
2. 比较两个链表的头，把较小的那个接到结果链表后面（此时两个链表各自内部已经排序完毕，只要左右各自轮流比较即可）

注意这里不涉及到反转操作，反转一定会出现 cur.next = prev这种操作

这个递归还是想了很久，感觉掌握还是不够好，要多练习递归

class Solution:
    @staticmethod
    def _find_mid(head):
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow  # 左半尾，方便断开

    @staticmethod
    def merge(l1, l2):
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            if l1.val > l2.val:
                curr.next = l2
                l2 = l2.next
            else:
                curr.next = l1
                l1 = l1.next
            curr = curr.next
        curr.next = l1 or l2
        return dummy.next

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        mid = self._find_mid(head)
        right = mid.next
        mid.next = None  # 断链

        left = self.sortList(head)
        right = self.sortList(right)
        return self.merge(left, right)

146 LRU 缓存

用 hash 表实现快速查找，另外就是对于 LRU 需要频繁的将某一个值移动到最头处，所以最合适的其实是链表数据，这里使用双端链表，一个头一个尾分别代表最后使用和最先使用

这里用到了 OrderedDict 的 API，没有单独写 hash 链表，可以放到单独 707, 641 去写

from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity: int):
        self.od = OrderedDict()
        self.max = capacity

    def get(self, key: int) -> int:
        if key in self.od:
            self.od.move_to_end(key)
            return self.od.get(key)
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.od:          # 对于已经存在的情况
            self.od[key] = value
            self.od.move_to_end(key)  # 移动到队伍尾
            return
        elif len(self.od) >= self.max:  # 满了要删除一个
            self.od.popitem(last=False) # 删除队伍头（最近未使用）

        self.od[key] = value    # 新插入，默认在队伍尾部

142 环形链表II

经典数学题，需要理清楚环的步数和入环点的位置关系（是 mod 整倍数关系）

这里有个 while else 的用法，是在没有 break 的时候触发的，可以注意下

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None: return None
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast: # 有环相遇了
                break
        else:
            # 到结尾了还没有相遇
            return None
        slow = head
        while slow is not fast:
            slow = slow.next
            fast = fast.next
        return slow

141 环形链表

快慢指针，方法同上一题，省略

139 单词拆分

写这道题目前要先写 518 零钱对换II，可能更好理解点

完全背包问题中的排列问题，因为 aab 和 aba 不是同一个字符串，这构成了排列关系

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        m = len(wordDict)
        n = len(s)
        dp = [False] * (n + 1) # 前 i 个字符 s[:i] 是否可以拆分
        dp[0] = True # 递推的起点，可以拆分
        for j in range(1, n + 1):
            for w in wordDict:
                L = len(w)
                if dp[j - L] == True and s[j - L:j] == w:
                    dp[j] = True
          break   # 一旦找到就去下一个分割点了
        return dp[n]

136 只出现一次的数字

抽象题，见过就秒，没见过就想不出，利用异或运算性质

x ^ x = 0  # 和自身异或是 0
x ^ 0 = x  # 和 0 异或不影响自身
x ^ y ^ z = x ^ z ^ y  # 结合律

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums)

647 回文子串

这题的边界条件比较难，我建议多做两遍

因为是左下推右上，所以外层从左到右，内层从下到上

同时通过计算距离来杜绝越界的情况，这个边界条件还是很巧妙的

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ret = 0

        for r in range(n):
            for l in range(r, -1, -1):
                if s[l] == s[r]:
                    if r - l <= 2 or dp[l + 1][r - 1]:
                        dp[l][r] = True
                        ret += 1
        return ret

128 最长连续序列

可以用 排序 + dp 的方式，但是有点太慢了，正确做法使用 set

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        ret = 0
        for n in s:
            if n - 1 not in s:
                curr = n
                while curr in s:
                    curr += 1
                ret = max(ret, curr - n)
        return ret

124 二叉树中最大路径和

后序遍历模拟，注意就是向上传递的值不允许分叉，但是计算最大结果处允许分叉

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        ret_max = float("-inf")
        def backTraversal(root):
            if root is None:
                return 0

            # 后序遍历, 屏蔽负数
            left = max(backTraversal(root.left), 0)
            right = max(backTraversal(root.right), 0)
            # 向上传递的值包含 root
            ret = max(root.val + left, root.val + right)   # 不能够左右都包含，向上路径不能分叉
            nonlocal ret_max
            ret_max = max(ret_max, root.val + left + right)   # 允许分叉的点就是全局最大值
            return ret

        backTraversal(root)
        return ret_max

322 零钱兑换

完全背包中，不在乎顺序，先遍历物品后遍历背包，内层正序遍历

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0 # 初始化为0
        # 完全背包，先物品后背包，正序遍历
        for c in coins:
            for j in range(c, amount + 1):
                dp[j] = min(dp[j], dp[j - c] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

494 目标和

数学计算一下可以发现所有的正数和应为：(sum + target) / 2，其中 sum 是数组全正的求和

这就可以简化为一个零一背包的问题，先遍历物品后遍历背包，内层需要倒序

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        n = len(nums)
        if abs(target) > s or (s + target) % 2 != 0:
            return 0    # 无解的情况
        tar = (s + target) // 2
        dp = [0] * (tar + 1) # 凑出和为 j 的可能的个数（零一背包）
        dp[0] = 1    # 初始化： 0 个数凑出 0 的个数都是 1（等价于第0轮的遍历结果）
        for num in nums:
            for j in range(tar, num - 1, -1): # 零一背包内层需要倒序
                    dp[j] += dp[j - num]
        return dp[tar]

461 汉明距离

就是计算取异或然后计算 1 的个数，这里 py 直接有 bit_count() 的 api

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # 取异或统计 1 的个数
        return (x ^ y).bit_count()

但是 底层一般考核的不是这个算法，而是Brian Kernighan 算法

实际逻辑是这样的

x      = ?????1000...000
x - 1  = ?????0111...111
----------------------
&      = ?????0000...000

底层代码是这样的

def bit_count(x):
    cnt = 0
    while x:
        x &= (x - 1)
        cnt += 1
    return

448 找到所有数组中消失的数字

经典背诵题，标记法，取模还原

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for num in nums:
            idx = (num - 1) % n   # -1 再取模，保证 0..n-1
            nums[idx] += n

        return [i + 1 for i, x in enumerate(nums) if x <= n]

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

滑动窗口，这里直接写优化版本的，只统计差异值就行，可以将空间复杂度降低到 O(1)

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        offset = ord('a')
        m, n = len(s), len(p)
        if n > m:
            return []

        diff = [0] * 26
        for c in p:
            diff[ord(c) - offset] += 1
        for c in s[:n]:
            diff[ord(c) - offset] -= 1

        diff_count = sum(1 for x in diff if x != 0)
        ret = []

        for i in range(m - n + 1):
            if diff_count == 0:
                ret.append(i)
            if i == m - n:
                break  # 最后一个窗口不需要再滑动，和初始化结合控制边界

            out_idx = ord(s[i]) - offset
            in_idx = ord(s[i + n]) - offset

            # out：窗口移出一个字符 => diff[out] += 1
            before = diff[out_idx]
            diff[out_idx] += 1
            after = diff[out_idx]
            if before == 0 and after != 0:
                diff_count += 1
            elif before != 0 and after == 0:
                diff_count -= 1

            # in：窗口移入一个字符 => diff[in] -= 1
            before = diff[in_idx]
            diff[in_idx] -= 1
            after = diff[in_idx]
            if before == 0 and after != 0:
                diff_count += 1
            elif before != 0 and after == 0:
                diff_count -= 1

        return ret

437 路径总和 III

有两种方法，DFS 遍历或者使用前缀和，使用前缀和的方法蛮难想的，建议多复习

DFS ：使用内外两层递归，一层遍历所有的节点，第二层以该节点为起点，遍历到所有的叶子结点的位置求和

前缀和：将 root -> 当前节点中的所有路径的前缀和放进一个 hash 表，查找前缀和为 prevSum = currSum - target的值即可

为什么可以用 Hash？因为不需要严格有序的顺序，只需要计数是否存在就行了

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # 前缀和, target = prefix[curr] - prefix[x] 表示从 x 到 curr 这两个值之间区间
        from collections import defaultdict
        prefix = defaultdict(int)
        prefix[0] = 1 # 允许某个节点自己达成目标
        def dfs(root, currSum):
            if root is None:
                return 0

            ret = 0
            currSum += root.val # 前缀和求值
            ret += prefix[currSum - targetSum]

            prefix[currSum] += 1 # 加入前缀表
            ret += dfs(root.left, currSum)
            ret += dfs(root.right, currSum)
            prefix[currSum] -= 1 # 退出节点的时候要回溯，因为前缀已经消失了

            return ret
        return dfs(root, 0)

416 分割等和子集

零一背包，公式题

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2
        dp = [False] * (target + 1) # 是否存在一个子集，其元素和恰好为 j
        dp[0] = True    # 什么都不选就是 0，必定存在
        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] |= dp[j - num]
            if dp[target]:
                return True

        return dp[target]

406 根据身高重建队列

这个题是个很抽象的贪心题目，感觉算是背诵题

关键：在一个人前面插入比他更矮的人， 不会影响这个人的定位，所以可以从大到小重建返回列表

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1])) # 身高降序，编号升序
        ret = []
        for h, k in people:
            ret.insert(k, [h, k])
        return ret