LeetCode Hot 100

ForHHeart / 2024-09-24 / 原文

1 Tree

1.1 Recursion

PreOrderTraversal

https://leetcode.cn/problems/binary-tree-preorder-traversal/

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        self.res = []
        def dfs(node):
            if node is None:
                return
            self.res.append(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return self.res

InOrderTraversal

https://leetcode.cn/problems/binary-tree-inorder-traversal/

PostOrderTraversal

https://leetcode.cn/problems/binary-tree-inorder-traversal/

二叉树的最大深度

二叉树的直径

1.2 LevelOrderTraversal

二叉树的层序遍历: https://leetcode.cn/problems/binary-tree-level-order-traversal/

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans = []
        from collections import deque
        q = deque([root])
        while q:
            tmp = []
            for _ in range(len(q)): # for loop [], until it's full
                node = q.popleft()
                tmp.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            ans.append(tmp)
        return ans

二叉树的锯齿形层序遍历: https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

# 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 zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans = []
        from collections import deque
        q = deque([root])
        while q:
            tmp = []
            for _ in range(len(q)): # for loop [], until it's full
                node = q.popleft()
                tmp.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            ans.append(tmp[::-1] if len(ans)%2 else tmp)
        return ans

找树左下角的值: https://leetcode.com/problems/find-bottom-left-tree-value/

# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return
        from collections import deque
        q = deque([root])
        tmp = []
        while q:
            node = q.popleft()
            tmp.append(node.val)
            if node.right: q.append(node.right)
            if node.left: q.append(node.left)
        return tmp[-1]

1.3 BST

BST(Binary Search Tree)，二叉搜索树具有左子树 < Root < 右子树的性质。

将有序数组转换为二叉搜索树: https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def dfs(nums, lo, hi):
            if lo > hi: return
        # 以升序数组的中间元素作为根节点 root
            mid = lo + (hi - lo) // 2
            root = TreeNode(nums[mid])
            root.left = dfs(nums, lo, mid - 1)
            root.right = dfs(nums, mid + 1, hi)
            return root
        return dfs(nums, 0, len(nums)-1)

验证二叉搜索树: https://leetcode.cn/problems/validate-binary-search-tree/

1.4 Common Ancestor

https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

2 Sliding Window

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        cnt = Counter()
        left = 0
        for right, c in enumerate(s): # add the new character to the s, from right
            cnt[c] += 1
            while cnt[c] > 1: # abcb -> bcb -> cb
                cnt[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

https://leetcode.cn/problems/find-all-anagrams-in-a-string

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, m, res = len(s), len(p),[]
        if n < m: return res
        p_cnt = [0] * 26
        s_cnt = [0] * 26
        for i in range(m): # initialize p_cnt
            p_cnt[ord(p[i]) - ord("a")] += 1
            s_cnt[ord(s[i]) - ord("a")] += 1
        if s_cnt == p_cnt:
            res.append(0)

        for i in range(m,n): # sliding window
            s_cnt[ord(s[i-m])-ord("a")] -= 1
            s_cnt[ord(s[i])-ord("a")] += 1
            if s_cnt == p_cnt:
                res.append(i-m+1) # start index
        return res

3 Prefix Sum

区域和检索: https://leetcode.cn/problems/range-sum-query-immutable/

和为k的子数组: https://leetcode.cn/problems/subarray-sum-equals-k/

计算前缀和s，注意要初始化一个0
因为s[j] - s[i] = k，所以s[j] - k = s[i]
每次寻找 s[j] 前面有多少个前缀和等于 s[j]−k，用哈希表记录前缀和的个数，就能 O(1) 算出前面有多少个 s[j]−k
遍历前缀和s, ans += cnt[s[j] - k], cnt[s[i]] += 1，顺序不能颠倒，因为如果k=0，会多记一次

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        s = [0] * (len(nums) + 1)
        for i, num in enumerate(nums):
            s[i+1] = s[i] + num

        ans = 0
        cnt = Counter()
        for sj in s:
            ans += cnt[sj - k]
            cnt[sj] += 1

        return ans

4 Stack

有效的括号: https://leetcode.cn/problems/valid-parentheses/

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s)%2 != 0:
            return False
        mp = {"}":"{", ")":"(", "]":"["}
        st = []
        for c in s:
            if c not in mp: # c是左括号
                st.append(c)
            elif not st or st.pop() != mp[c]: # c是右括号
                return False # 没有左括号，或右括号不匹配
        return not st # 所有左括号必须匹配完毕，检查左括号比右括号多的情况，如{{}

5 Linked List

5.1 反转链表

206.反转链表: https://leetcode.cn/problems/reverse-linked-list/

初始化：pre指向null，cur指向head
先暂存head.next，再改变head.next，最后更新head：
- tmp = cur.next
- cur.next = pre
- pre = cur
- cur = tmp
必记性质：反转结束后，pre指向这一段的末尾，cur指向这一段末尾的下一个节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

92.反转链表II: https://leetcode.cn/problems/reverse-linked-list-ii/

5.2 快慢指针

链表的中间节点: https://leetcode.cn/problems/middle-of-the-linked-list/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

环形链表: https://leetcode.cn/problems/linked-list-cycle/

关注fast和slow的相对运动，相当于fast相对运动一格，如果有环，最终fast肯定会与slow相遇

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast is slow:
                return True
        return False

环形链表II: https://leetcode.cn/problems/linked-list-cycle-ii/

哈希表记录遍历过的节点，记录大于2表示有环，且为入口

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        visited = Counter()
        while head:
            if visited[head]:
                return head
            visited[head] += 1
            head = head.next
        return None

Follow up: Can you solve it using O(1) (i.e. constant) memory?

最差情况: 当慢指针进入环时，快指针刚好在慢指针前面，根据相对距离分析，快指针需要走(环长-1)步的相对距离才能追上慢指针，其余任何情况快指针走的步数都小于(环长-1)，所以慢指针移动的距离是小于环长的。

slwo和fast相遇之后：head从出发点出发，slow从相遇点出发，head和slow相遇的位置必定是入口，这是因为设相遇点到入口的距离为c, a - c = (k - 1)(b + c)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast is slow: # 有环
                while slow is not head:
                    slow = slow.next
                    head = head.next
                return slow
        return None

重排链表: https://leetcode.cn/problems/reorder-list/

找到链表中点，反转链表

先暂存head.next，再改变head.next，最后更新head：
- tmp = head.next
- tmp2 = head2.next
- head.next = head2
- head2.next = tmp
- head = tmp
- head2 = tmp2

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head):
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverseList(self, head):
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

    def reorderList(self, head: Optional[ListNode]) -> None:
        mid = self.middleNode(head)
        head2 = self.reverseList(mid)

        while head2.next:
            tmp = head.next
            tmp2 = head2.next
            head.next = head2
            head2.next = tmp
            head = tmp
            head2 = tmp2

回文链表: https://leetcode.cn/problems/palindrome-linked-list/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head):
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverseList(self, head):
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if head is None:
            return True

        mid = self.middleNode(head)
        head2 = self.reverseList(mid)
        while head2:
            if head.val != head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True

5.3 删除链表

5.4 前后指针

相交链表: https://leetcode.cn/problems/intersection-of-two-linked-lists/

初始化: A指向headA，B指向headB，同时开始向前遍历
遍历链表: a + (b - c) = b + (a - c)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        A = headA
        B = headB
        while A!=B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A