LeetCode Hot 100 算法题解与思路总结

需要查找某个元素是否存在，并且用到下标和值，所以用dict 结构

通过一次遍历，利用哈希表记录已访问过的数字及其索引，从而能以 O(1) 的速度瞬间找回使当前数凑成目标值的那个'补数'

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for index, value in enumerate(nums):
            if target - value in hashmap:
                return [index, hashmap[target - value]]
            else:
                hashmap[value] = index

字母异位词分组

数组结构

利用**'字符出现的频率'作为哈希表的唯一键**来对字母异位词进行分组

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        for str in strs:
            counts = [0] * 26
            for ch in str:
                counts[ord(ch) - ord("a")] += 1
            mp[tuple(counts)].append(str)
        return list(mp.values())

最长连续序列

set 结构

利用哈希表实现 O(1) 查找，并采用'只从序列车头（即 num-1 不存在时）开始往后数'的剪枝策略，确保每个数字只被遍历常数次，从而将 O(n^2) 的搜索优化为 O(n) 的线性处理

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hashset = set(nums)
        maxLength = 0
        for num in hashset:
            if num - 1 not in hashset:
                curLength = 1
                while num + 1 in hashset:
                    curLength += 1
                    num += 1
                maxLength = max(curLength, maxLength)
        return maxLength

242. 有效的字母异位词

自己创建哈希表（固定长度数组模拟哈希表）和哈希函数（字符偏移量映射索引），通过哈希表中最后的值（加减抵消的逻辑）来判断两个组的词相不相同

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        hashmap = [0] * 26
        for i in s:
            hashmap[ord(i) - ord('a')] += 1
        for i in t:
            hashmap[ord(i) - ord('a')] -= 1
        for i in hashmap:
            if i != 0:
                return False
        return True

349. 两个数组的交集

set 结构

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        res = set1.intersection(set2)
        return list(res)

字符串

344. 反转字符串

双指针，python 中字符列表 List[str] 可以直接替换两个字符的位置

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left = 0
        right = len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

151. 翻转字符串里的单词

利用快慢指针删除多的空格，再配合'先整体翻转、后单词局部翻转'的策略实现单词顺序的倒置。不能一蹴而就，一步一步地达成目标

class Solution:
    def reverseRange(self, s, start, end):
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

    def reverseWords(self, s: str) -> str:
        s_list = list(s)
        slow = 0
        fast = 0
        n = len(s)
        while fast < n:
            if s_list[fast] != ' ':
                if slow != 0:
                    s_list[slow] = ' '
                    slow += 1
                while fast < n and s_list[fast] != ' ':
                    s_list[slow] = s_list[fast]
                    slow += 1
                    fast += 1
                fast += 1
        s_list = s_list[:slow]
        s_list.reverse()
        left = 0
        for right in range(len(s_list)):
            if s_list[right] == ' ':
                self.reverseRange(s_list, left, right - 1)
                left = right + 1
            elif right == len(s_list) - 1:
                self.reverseRange(s_list, left, right)
        return "".join(s_list)

双指针

原理

使用场景：利用数据结构的有序性或特定逻辑（两个影响题目答案的限制条件），用两个变量（指针）同时遍历，从而把 O(n^2) 的暴力复杂度降到 O(n)

指针的移动是有目的的（为了求出最后的答案而移动，不是乱移动），两个 for 循环嵌套也就是双指针，只不过指针的移动是固定的

快慢指针：

• 快指针一直移动，直到最后一个元素，每次移动代表着根据题意处理接下来的一个元素
• 慢指针在快指针进行判断且满足题意时移动，每次移动代表着慢指针之前的元素就是要的答案

左右指针：两个指针分别位于首尾，并向中间靠拢的技巧

• 使用场景：需要用到左右指针的关系，比如：左指针小于右指针，或者需要左右指针之间的距离。
• 根据题意来决定如何移动左右指针
• 模板：while left < right

移动零

快慢指针

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        n = len(nums)
        slow = 0
        fast = 0
        while fast < n:
            if nums[fast] != 0:
                nums[fast], nums[slow] = nums[slow], nums[fast]
                slow += 1
                fast += 1

盛水最多的容器

左右指针

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        left = 0
        right = n - 1
        maxVol = 0
        while left < right:
            vol = (right - left) * min(height[left], height[right])
            maxVol = max(vol, maxVol)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return maxVol

15. 三数之和（三元组不重复）

左右指针

先排序以方便去重和左右指针的方向感，再固定一个数，利用左右指针从两端向中间'夹逼'寻找另外两个数。

用三个数之和来决定左指针动还是右指针动

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        for i in range(len(nums)):
            if nums[i] > 0:
                return result
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left = i + 1
            right = len(nums) - 1
            while left < right:
                sum_val = nums[i] + nums[left] + nums[right]
                if sum_val < 0:
                    left += 1
                elif sum_val > 0:
                    right -= 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
        return result

二分查找

原理

使用条件：数组是有序的

使用场景：寻找特定值

时间复杂度：O(log n)

本质：将搜索范围一分为二，缩小搜索区域（用双指针来控制）

循环条件是小于等于号（left <= right）：因为当最后只剩两个相邻值时，例如：left = 1 和 right = 2 时，mid = (left + right) // 2 = 1，查找的 mid 就是 left，如果 left 不是要查找的值，就需要再次循环去看 right，left 必须要可以等于 mid + 1，而 mid + 1 就等于 right

模板：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

搜索插入的位置

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

搜索二维矩阵

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        while left <= right:
            mid = (left + right) // 2
            row = mid // n
            col = mid % n
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

第一个和最后一个位置

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def findFirst(nums, target):
            left, right = 0, len(nums) - 1
            first = -1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    first = mid
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return first

        def findLast(nums, target):
            left, right = 0, len(nums) - 1
            last = -1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    last = mid
                    left = mid + 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return last

        first = findFirst(nums, target)
        last = findLast(nums, target)
        if first == -1 or last == -1:
            return [-1, -1]
        return [first, last]

搜索旋转排序数组

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

寻找排序数组中最小值

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        return nums[left]

滑动窗口

原理

本质：用双指针（类似快慢指针）来表示一个可以移动的大小可变区间，调节子序列的起始位置和终止位置

优点：始终处理连续的子串或子数组，避免了重复计算

模板：left = 0（指向左边界），右指针用 for 循环来表示，for 循环内部的左指针根据题意移动。指针移动时增减哈希表里的元素（用哈希表来知道窗口内部是个什么情况）

无重复字符的最长子串

利用'滑动窗口'机制，通过 right 指针向右扩张寻找新字符，一旦撞上重复字符，就移动 left 指针像'挤牙膏'一样将其剔除，从而动态维护窗口内始终是不重复的子串

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        hashset = set()
        maxLength = 0
        for right in range(len(s)):
            while s[right] in hashset:
                hashset.remove(s[left])
                left += 1
            hashset.add(s[right])
            curLength = right - left + 1
            maxLength = max(maxLength, curLength)
        return maxLength

找字符串中所有异位词

维护一个长度恒等于 p 的'定长滑动窗口'，通过 Counter 实时对比窗口内外的字符频率分布，当两者完全匹配时，即锁定了异位词的起始位置。

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

链表

原理

学会去运用节点的指向来完成想要的操作

模板：

1. dummy_head = ListNode() 用来表示头节点

   作用：避免多写步骤去处理头节点

   注意：此时 dummy_head 并没有和题目给出的链表相连接（也就是没有指向链表的头节点），想要连接可以这样初始化，dummy_head = ListNode(0, head)

2. current = dummy_head，用来遍历的节点

   作用：不改变 head

   移动链表的节点：

   current = current.next

3. 修改节点指向时，需要保存中间节点

160. 相交链表

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        visited = set()
        currentA = headA
        while currentA:
            visited.add(currentA)
            currentA = currentA.next
        currentB = headB
        while currentB:
            if currentB in visited:
                return currentB
            currentB = currentB.next
        return None

消除长度差来实现同步。走过你的路，我们终会相遇（数学方法）

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        pA = headA
        pB = headB
        while pA != pB:
            if pA:
                pA = pA.next
            else:
                pA = headB
            if pB:
                pB = pB.next
            else:
                pB = headA
        return pA

206. 反转链表

解题思路：想清楚怎么连接链表 + 保存中间节点（不然就丢失了后续的指向）

快慢指针法：

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = None
        fast = head
        while fast:
            temp = fast.next
            fast.next = slow
            slow = fast
            fast = temp
        return slow

递归法：根据双指针改来的

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self.reverse(head, None)

    def reverse(self, cur: ListNode, pre: ListNode):
        if cur == None:
            return pre
        temp = cur.next
        cur.next = pre
        return self.reverse(temp, cur)

回文链表

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        vals = []
        current_node = head
        while current_node is not None:
            vals.append(current_node.val)
            current_node = current_node.next
        left, right = 0, len(vals) - 1
        while left < right:
            if vals[left] != vals[right]:
                return False
            left += 1
            right -= 1
        return True

141. 环形链表

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

快慢指针，弗洛伊德循环查找算法（数学方法）

• 慢指针（slow）：每次只走一步
• 快指针（fast）：每次走两步

如果链表没有环，快指针会率先到达终点（指向 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 slow == fast:
                return True
        return False

21. 合并两个有序链表

想清楚链表怎么连接

用一个新链表来保存结果

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

两数之和

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        carry = 0
        dummy_head = ListNode()
        current = dummy_head
        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            sum_val = val1 + val2 + carry
            carry = sum_val // 10
            current.next = ListNode(sum_val % 10)
            current = current.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        return dummy_head.next

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

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        def getLength(head: ListNode) -> int:
            length = 0
            while head:
                length += 1
                head = head.next
            return length

        dummy_head = ListNode(0, head)
        cur = dummy_head
        length = getLength(head)
        for i in range(0, length - n):
            cur = cur.next
        cur.next = cur.next.next
        return dummy_head.next

用双指针找到要删除节点的前一个节点：因为快指针先走了 n + 1 步，然后快指针和慢指针一起走，直到快指针走完全部节点，此时，慢指针就是倒数第 n + 1 个数

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

24. 两两交换链表中的节点

模拟行为：

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(0, head)
        cur = dummy_head
        while cur.next and cur.next.next:
            temp = cur.next
            temp1 = cur.next.next.next
            cur.next = cur.next.next
            cur.next.next = temp
            temp.next = temp1
            cur = cur.next.next
        return dummy_head.next

递归：

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        newHead = head.next
        head.next = self.swapPairs(newHead.next)
        newHead.next = head
        return newHead

排序链表

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        left = self.sortList(head)
        right = self.sortList(mid)
        return self.mergeTwoLists(left, right)

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy_head = ListNode()
        current = dummy_head
        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
        if l1:
            current.next = l1
        if l2:
            current.next = l2
        return dummy_head.next

203. 移除链表元素

虚拟头节点法，以空间换简洁，如果没有虚拟头节点，在操作链表（尤其是删除和插入）时，通常需要写两套逻辑：一套处理普通节点，一套处理头节点。

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy_head = ListNode(0, head)
        current = dummy_head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        return dummy_head.next

707. 设计链表

虚拟头节点，取点，加点，删点（这三个操作，借助 current 的移动来完成）

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class MyLinkedList:
    def __init__(self):
        self.dummy_head = ListNode()
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        current = self.dummy_head
        for i in range(index):
            current = current.next
        return current.next.val

    def addAtHead(self, val: int) -> None:
        mid = self.dummy_head.next
        self.dummy_head.next = ListNode(val, mid)
        self.size += 1

    def addAtTail(self, val: int) -> None:
        current = self.dummy_head
        while current.next:
            current = current.next
        current.next = ListNode(val)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return
        current = self.dummy_head
        for i in range(index):
            current = current.next
        mid = current.next
        current.next = ListNode(val, mid)
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        current = self.dummy_head
        for i in range(index):
            current = current.next
        current.next = current.next.next
        self.size -= 1

数组

原理

可以直接取出或使用某个 index 位置的元素

方法：

二分法，双指针（快慢，左右），滑动窗口，模拟行为，前缀和

最大子数组和

暴力递归（枚举所有子数组）

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        max_sum = float('-inf')
        for i in range(n):
            for j in range(i, n):
                cur_sum = sum(nums[i:j + 1])
                max_sum = max(max_sum, cur_sum)
        return max_sum

动态规划

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [float('-inf')] * n
        dp[0] = nums[0]
        max_sum = nums[0]
        for i in range(1, n):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
            max_sum = max(max_sum, dp[i])
        return max_sum

合并区间

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        merge = []
        for interval in intervals:
            if not merge or merge[-1][1] < interval[0]:
                merge.append(interval)
            else:
                merge[-1][1] = max(merge[-1][1], interval[1])
        return merge

轮转数组

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        length = len(nums)
        ans = [0] * length
        for i in range(length):
            ans[(i + k) % length] = nums[i]
        nums[:] = ans

除自身以外数组的乘积

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        pre, post, answer = [0] * len(nums), [0] * len(nums), [0] * len(nums)
        pre[0] = 1
        for i in range(1, len(nums)):
            pre[i] = pre[i - 1] * nums[i - 1]
        post[len(nums) - 1] = 1
        for i in reversed(range(len(nums) - 1)):
            post[i] = post[i + 1] * nums[i + 1]
        for i in range(len(nums)):
            answer[i] = pre[i] * post[i]
        return answer

27. 移除元素

暴力解法

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i, l = 0, len(nums) - 1
        while i < l:
            if nums[i] == val:
                for j in range(i, l):
                    nums[j] = nums[j + 1]
                l -= 1
                i -= 1
            i += 1
        return l

最优解：双指针，需要的留在前面，不需要的放在后面

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0
        fast = 0
        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow

977. 有序数组的平方和

双指针 - 左右指针，每次可以找到一个最大的值出来

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left = 0
        right = n - 1
        result = [0] * n
        idx = n - 1
        while left <= right:
            if nums[left] * nums[left] < nums[right] * nums[right]:
                square = nums[right] * nums[right]
                result[idx] = square
                right -= 1
            else:
                square = nums[left] * nums[left]
                result[idx] = square
                left += 1
            idx -= 1
        return result

209. 长度最小的子数组

滑动窗口，如果大于了目标值，窗口前端就缩小

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        left = 0
        right = 0
        cur_sum = 0
        res = float('inf')
        for right in range(n):
            cur_sum += nums[right]
            while cur_sum >= target:
                res = min(res, right - left + 1)
                cur_sum -= nums[left]
                left += 1
        return res if res != float('inf') else 0

59. 螺旋矩阵Ⅱ

模拟行为：根据边界，循环填值

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        if n <= 0:
            return []
        matrix = [[0] * n for _ in range(n)]
        top, bottom, left, right = 0, n - 1, 0, n - 1
        num = 1
        while top <= bottom and left <= right:
            for i in range(left, right + 1):
                matrix[top][i] = num
                num += 1
            top += 1
            for i in range(top, bottom + 1):
                matrix[i][right] = num
                num += 1
            right -= 1
            for i in range(right, left - 1, -1):
                matrix[bottom][i] = num
                num += 1
            bottom -= 1
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1
        return matrix

区间和

前缀和，ACM 写法（需要自己处理原始的字符流，还要打印结果）

import sys
input = sys.stdin.read

def main():
    data = input().split()
    index = 0
    n = int(data[index])
    index += 1
    vec = n * [0]
    for i in range(n):
        vec[i] = int(data[index])
        index += 1
    p = [0] * n
    pre_sum = 0
    for i in range(n):
        pre_sum += vec[i]
        p[i] = pre_sum
    results = []
    while index < len(data):
        a = int(data[index])
        b = int(data[index + 1])
        index += 2
        if a == 0:
            sum_value = p[b]
        else:
            sum_value = p[b] - p[a - 1]
        results.append(sum_value)
    for result in results:
        print(result)

if __name__ == "__main__":
    main()

栈

原理

使用场景：匹配问题（利用栈（Stack）的'后进先出'特性，实时对比当前字符与栈顶元素）

用于嵌套的题型（一个代码块中包含另一个代码块），子操作很像但又不完全相同

利用栈的先入后出（题目数据符合的一种顺序，进入栈的都被存储下来了，取出的时候顺序是反的）

注意栈里放的是什么，获得的启发：用数据结构里的数据表示更多与解题有关的信息，不同算法使得相同的数据结构（但是里面的数据不一样）可以解决不同的题

模板：在某些条件下（对题意抽象）入栈和出栈

20. 有效的括号

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        pairs = {")":"(", "}":"{", "]":"["}
        stack = []
        for x in s:
            if x not in pairs:
                stack.append(x)
            else:
                if not stack or stack[-1] != pairs[x]:
                    return False
                stack.pop()
        return not stack

仅使用栈，用于对称匹配

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item:
                return False
            else:
                stack.pop()
        return True

最小栈

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = [math.inf]

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

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

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

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

字符串解码

class Solution:
    def decodeString(self, s: str) -> str:
        count_stack = []
        string_stack = []
        current_num = 0
        current_string = ""
        for char in s:
            if char.isdigit():
                current_num = current_num * 10 + int(char)
            elif char == "[":
                count_stack.append(current_num)
                string_stack.append(current_string)
                current_num = 0
                current_string = ""
            elif char == "]":
                repeat_times = count_stack.pop()
                last_string = string_stack.pop()
                current_string = last_string + current_string * repeat_times
            else:
                current_string += char
        return current_string

每日温度

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        answer = [0] * n
        stack = []
        for i in range(n):
            cur = temperatures[i]
            while stack and cur > temperatures[stack[-1]]:
                index = stack.pop()
                wait_days = i - index
                answer[index] = wait_days
            stack.append(i)
        return answer

232. 用栈实现队列

利用两个栈，将入第一个栈的元素放到第二个栈里，第二个栈出来的时候就是先入先出了

class MyQueue:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, x: int) -> None:
        self.stack_in.append(x)

    def pop(self) -> int:
        for i in range(len(self.stack_in)):
            self.stack_out.append(self.stack_in.pop())
        return self.stack_out.pop()

    def peek(self) -> int:
        for i in range(len(self.stack_in)):
            self.stack_out.append(self.stack_in.pop())
        temp = self.stack_out.pop()
        self.stack_out.append(temp)
        return temp

    def empty(self) -> bool:
        return not self.stack_out

225. 用队列实现栈

利用两个队列，想要实现先入后出，通过将队列前 n-1 个元素迁移到辅助队列来孤立并获取原本位于队尾的最新元素

class MyStack:
    def __init__(self):
        self.queue_in = deque()
        self.queue_out = deque()

    def push(self, x: int) -> None:
        self.queue_in.append(x)

    def pop(self) -> int:
        for i in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        self.queue_in, self.queue_out = self.queue_out, self.queue_in
        return self.queue_out.popleft()

    def top(self) -> int:
        for i in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        self.queue_in, self.queue_out = self.queue_out, self.queue_in
        temp = self.queue_out.popleft()
        self.queue_out.append(temp)
        return temp

    def empty(self) -> bool:
        return not self.queue_in

1047. 删除字符中的所有相邻重复项

匹配问题，利用栈（Stack）的'后进先出'特性，通过实时对比当前字符与栈顶元素，实现相邻重复项的成对抵消

class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = []
        for item in s:
            if res and res[-1] == item:
                res.pop()
            else:
                res.append(item)
        return "".join(res)

二叉树

原理

适合用递归、栈，因为二叉树可以分为多个子二叉树，子问题操作步骤相同，子二叉树都满足条件的话，二叉树也就满足条件

递归：用于大问题可以拆分为许多操作步骤一样的子问题

新定义一个递归函数的时机：原函数的参数不够或返回值不方便直接递归的时候就

特点自己调用自己（大问题 -> 类似的子问题，模板：调用自己时传入的参数会变）根据如何拆成子问题的思路，来写子问题的基本操作和 return base case（最小子问题的出递归条件）

递归三部曲

0. 理解递归的作用是什么 确定递归函数的参数和返回值 确定终止条件（base case，出递归的条件） 确定单层递归的逻辑（前中后序的哪一种？）

遍历树的时候进行操作：

1. 深度优先搜索（递归法和迭代法），判断使用前中后哪个序的递归逻辑，然后用递归三部曲

2. 广度优先搜索（迭代法：借助队列）

# 广度优先搜索
def levelOrder(root):
    result = []
    if not root:
        return result
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level_nodes = []
        for _ in range(level_size):
            node = queue.popleft()
            level_nodes.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_nodes)
    return result

求深度（高度）的变形？

104. 二叉树的最大深度

深度：二叉树中任意一个节点到根节点的距离。自顶向下：使用前序遍历

高度：二叉树中任意一个节点到叶子节点的距离。自底向上：使用后序遍历，将左右的处理过程返回给中节点

此题，根节点的高度就是二叉树的最大深度，所以用后续遍历

递归的作用是求高度

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return self.getHeight(root)

    def getHeight(self, root: TreeNode) -> int:
        if not root:
            return 0
        leftHeight = self.getHeight(root.left)
        rightHeight = self.getHeight(root.right)
        maxHeight = max(leftHeight, rightHeight) + 1
        return maxHeight

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        leftHeight = self.maxDepth(root.left)
        rightHeight = self.maxDepth(root.right)
        maxHeight = max(leftHeight, rightHeight) + 1
        return maxHeight

层序遍历

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        depth = 0
        queue = deque([root])
        while queue:
            n = len(queue)
            for i in range(n):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1
        return depth

111. 二叉树的最小深度

根节点的最小高度就是最小深度，所以也是用的后序

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return self.getHeight(root)

    def getHeight(self, root: TreeNode) -> int:
        if not root:
            return 0
        leftHeight = self.getHeight(root.left)
        rightHeight = self.getHeight(root.right)
        if root.left == None and root.right != None:
            return 1 + rightHeight
        if root.left != None and root.right == None:
            return 1 + leftHeight
        minHeight = min(leftHeight, rightHeight) + 1
        return minHeight

226. 翻转二叉树

利用前序遍历的递归法，改单层递归逻辑

每次将中间节点的左节点和右节点交换位置

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

101. 对称二叉树

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.isMirror(root.left, root.right)

    def isMirror(self, left: TreeNode, right: TreeNode) -> bool:
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val) and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)

因为要比较左节点的左右节点和右节点的左右节点是否对称，所以递归中需要传入两个节点。

处理了左右节点后才知道中节点，所以使用后序递归（收集孩子的信息向上一步返回的题目时候用后序列）

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.compare(root.left, root.right)

    def compare(self, left: TreeNode, right: TreeNode) -> bool:
        if left == None and right != None:
            return False
        elif left != None and right == None:
            return False
        elif left == None and right == None:
            return True
        elif left.val != right.val:
            return False
        outside = self.compare(left.left, right.right)
        inside = self.compare(left.right, right.left)
        return outside and inside

110. 平衡二叉树

处理递归时，决定是'只用一个函数'还是'多加一个辅助函数'：取决于你从子节点需要获取的信息，是否就是最终要求的答案

左右子树高度差的绝对值要小于一，利用递归后序 + 找高度

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        if self.getHeight(root) == -1:
            return False
        else:
            return True

    def getHeight(self, root: TreeNode) -> int:
        if not root:
            return 0
        leftHeight = self.getHeight(root.left)
        if leftHeight == -1:
            return -1
        rightHeight = self.getHeight(root.right)
        if rightHeight == -1:
            return -1
        if abs(leftHeight - rightHeight) > 1:
            return -1
        else:
            return 1 + max(leftHeight, rightHeight)

222. 完全二叉树的节点个数

完全二叉树的情况下，左深度和右深度相同的话，就是满二叉树，满二叉树的节点个数是 2 的深度次方 - 1，利用递归后序（普通二叉树在这里就可以直接算出来）再在 base case 里加上判断是否是完全二叉树的操作

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left = root.left
        right = root.right
        leftDepth = 0
        rightDepth = 0
        while left:
            left = left.left
            leftDepth += 1
        while right:
            right = right.right
            rightDepth += 1
        if leftDepth == rightDepth:
            return (2 << leftDepth) - 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

二叉树的直径

利用计算高度来计算直径，所以需要一个新的函数（计算高度的函数）

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: TreeNode) -> int:
        ans = 0
        def depth(node: TreeNode):
            nonlocal ans
            if not node:
                return 0
            leftHigh = depth(node.left)
            rightHigh = depth(node.right)
            ans = max(ans, (leftHigh + rightHigh))
            maxHeight = max(leftHigh, rightHigh) + 1
            return maxHeight
        depth(root)
        return ans

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        def dfs(node: TreeNode) -> int:
            if not node:
                return 0
            left_h = dfs(node.left)
            right_h = dfs(node.right)
            self.ans = max(self.ans, left_h + right_h)
            return max(left_h, right_h) + 1
        dfs(root)
        return self.ans

102. 二叉树的层序遍历

弹出的时候把这个节点的左右节点加进队列

弹出的个数取决于当前队列中元素的个数

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        res = []
        queue = deque([root])
        while queue:
            level = []
            for i in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(level)
        return res

108. 有序数组转二叉搜索树

二叉搜索树的中序遍历就是从小到大的有序数组

分治策略，通过递归地将当前有序数组的中心元素作为子树根节点，从而确保构建出的二叉搜索树（BST）是高度平衡的

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        left = 0
        right = len(nums) - 1
        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

98. 验证二叉搜索树

单层递归逻辑：前序

因为不仅节点的左孩子要比它小、右孩子要比它大，而且整个左子树的所有节点都要小于当前节点，整个右子树的所有节点都要大于当前节点。所以需要 low 和 high

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def reverse(node, low=-float('inf'), high=float('inf')) -> bool:
            if not node:
                return True
            if not (low < node.val < high):
                return False
            return (reverse(node.left, low, node.val) and reverse(node.right, node.val, high))
        return reverse(root)

由于二叉搜索树的性质，中序遍历的出来的数组应是递增的，所以可以借助判断元素是不是单调递增的来判断是否是二叉搜索树

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        vec = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            vec.append(root.val)
            dfs(root.right)
        dfs(root)
        for i in range(1, len(vec)):
            if vec[i] <= vec[i - 1]:
                return False
        return True

二叉搜索树中第 k 小元素

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        vec = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            vec.append(root.val)
            dfs(root.right)
        dfs(root)
        return vec[k - 1]

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        current = root
        while stack or current:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            k -= 1
            if k == 0:
                return current.val
            current = current.right

199. 二叉树的右视图

方法一：

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return result
        queue = deque([root])
        while queue:
            k = -1
            level_size = len(queue)
            for _ in range(level_size):
                node = queue.popleft()
                k += 1
                if k == level_size - 1:
                    result.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result

方法二：

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return result
        queue = deque([root])
        while queue:
            level_size = len(queue)
            leve_nodes = []
            for _ in range(level_size):
                node = queue.popleft()
                leve_nodes.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(leve_nodes[-1])
        return result

层序遍历的变形，将每一层的最后一个值拿出来就是右视图的值

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        res = []
        queue = deque([root])
        while queue:
            n = len(queue)
            for i in range(len(queue)):
                node = queue.popleft()
                if i == n - 1:
                    res.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return res

二叉树展开为链表

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        arr = []
        def dfs(node: TreeNode):
            if not node:
                return
            arr.append(node)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        for i in range(len(arr)):
            arr[i].left = None
            if i + 1 < len(arr):
                arr[i].right = arr[i + 1]

144. 94 145 二叉树的前中后序遍历

递归法

写的时候思考递归三部曲。前中后序的递归，仅仅差别在 res.append(node.val) 的位置

原函数的参数不够或返回值不方便直接递归的时候就新定义一个递归函数

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(node):
            if node is None:
                return
            res.append(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return res

迭代法

利用栈，一点一点得到结果，让栈里出的顺序满足遍历的顺序。栈的作用：在递归遍历中，计算机底层会自动利用系统栈来保存每一层函数的局部变量和返回地址。当改用迭代法时，这套自动化的'保存机制'没了，所以必须手动维护一个栈来记录那些'已经路过但尚未处理完'的节点

前序遍历，利用栈的'后进先出'（LIFO）特性，通过先压入右子节点再压入左子节点的顺序，手动模拟递归调用栈，从而实现'根→左→右'的前序遍历顺序

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

后续遍历，将前序代码改成变成中右左，再反转数组 res，变成左右中

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return res[::-1]

中序遍历，不能用修改前序遍历的代码来达成，因为访问顺序和处理顺序不一样，所以需要使用一个指针来控制访问顺序和处理顺序一致

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        res = []
        stack = []
        cur = root
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                res.append(cur.val)
                cur = cur.right
        return res

106. 从中序与后序遍历序列构造二叉树

用后序找中间节点，利用其去中序中切割左右区间，再利用左区间的长度去切割后序

递归三部曲，单层递归逻辑就是解题的逻辑，而不是前中后序

想明白递归的作用是什么，此题就是把数组分成左边和右边，对应左子树和右子树

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not postorder:
            return None
        root_val = postorder[-1]
        root = TreeNode(root_val)
        separator_index = inorder.index(root_val)
        inorder_left = inorder[:separator_index]
        inorder_right = inorder[separator_index + 1:]
        postorder_left = postorder[: len(inorder_left)]
        postorder_right = postorder[len(inorder_left): -1]
        root.left = self.buildTree(inorder_left, postorder_left)
        root.right = self.buildTree(inorder_right, postorder_right)
        return root

105. 从前序与中序遍历序列构造二叉树

本质和 106 一样

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        rootVal = preorder[0]
        root = TreeNode(rootVal)
        separatorIndex = inorder.index(rootVal)
        inorderLeft = inorder[:separatorIndex]
        inorderRight = inorder[separatorIndex + 1:]
        preorderLeft = preorder[1: 1 + len(inorderLeft)]
        preorderRight = preorder[1 + len(inorderLeft):]
        root.left = self.buildTree(preorderLeft, inorderLeft)
        root.right = self.buildTree(preorderRight, inorderRight)
        return root

617. 合并二叉树

前序递归

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
        root = TreeNode()
        root.val = root1.val + root2.val
        root.left = self.mergeTrees(root1.left, root2.left)
        root.right = self.mergeTrees(root1.right, root2.right)
        return root

700. 二叉搜索树中的搜索

递归三部曲 + 单层递归逻辑时用上搜索二叉树的性质

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root == None or root.val == val:
            return root
        if root.val < val:
            return self.searchBST(root.right, val)
        if root.val > val:
            return self.searchBST(root.left, val)

236. 二叉树的最近公共祖先

后序遍历自底向上回溯，当某个节点发现其左、右子树各包含一个目标节点（p 或 q）时，该节点即为最近公共祖先

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == p or root == q or root == None:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left is not None and right is not None:
            return root
        if left is None and right is not None:
            return right
        elif left is not None and right is None:
            return left
        else:
            return None

图论

原理

邻接表：用一个列表来存储每个节点的相邻节点

入度：指向该节点边的数量

深度优先搜索（递归）

广度优先搜索（队列）

拓扑排序：对有向无环图的顶点进行排序，使得对于每个有向边 u→v，顶点 u 都在顶点 v 之前

岛屿数量

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        def dfs(x, y):
            if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == '0':
                return
            grid[x][y] = "0"
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)
        island_count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i, j)
                    island_count += 1
        return island_count

课程表

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        int_degree = [0] * numCourses
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            int_degree[course] += 1
        queue = deque([i for i in range(numCourses) if int_degree[i] == 0])
        complete_courses = 0
        while queue:
            course = queue.pop()
            complete_courses += 1
            for next_course in graph[course]:
                int_degree[next_course] -= 1
                if int_degree[next_course] == 0:
                    queue.append(next_course)
        return complete_courses == numCourses

堆

原理

定义：一种特殊（最大堆或最小堆）的完全二叉树

最小堆：任意一个节点的值 <= 它的子节点的值。根节点是堆中最小的值。

用下列方法进行堆的操作：

• 插入：heapq.heappush(heap, item)：把新元素放在数组末尾，然后'上浮'到合适位置
• 取出最小：heapq.heappop(heap)：把堆顶元素删除，用最后一个元素补到堆顶，然后'下沉'
• 查看最小：heap[0]

数组中的第 K 个最大元素

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quickSelect(left, right, k_smallest):
            if left == right:
                return nums[left]
            real_index_k = len(nums) - k
            pivot_index = random.randint(left, right)
            nums[right], nums[pivot_index] = nums[pivot_index], nums[right]
            pivot = nums[right]
            i = left - 1
            for j in range(left, right):
                if nums[j] <= pivot:
                    i += 1
                    nums[i], nums[j] = nums[j], nums[i]
            nums[i + 1], nums[right] = nums[right], nums[i + 1]
            pivot_index = i + 1
            if pivot_index == real_index_k:
                return nums[pivot_index]
            elif pivot_index < real_index_k:
                return quickSelect(pivot_index + 1, right, real_index_k)
            else:
                return quickSelect(left, pivot_index - 1, real_index_k)
        return quickSelect(0, len(nums) - 1, k)

前 K 个高频元素

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)
        min_heap = []
        for num, count in freq.items():
            heapq.heappush(min_heap, (count, num))
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        return [num for count, num in min_heap]

贪心算法

原理

每一步执行当前看起来最好的决定。通过更新，得到目前看来最好的结果

全局最优可以由局部最优推导而来

模板：每一次 for 循环得到局部最优（1. 用 max 或 min 找到最好的决定 2. 根据题目想要的结果写代码），执行完 for 循环得到全局最优

买股票的最佳时机

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices or len(prices) < 2:
            return 0
        min_price = prices[0]
        max_profit = 0
        for price in prices[1:]:
            max_profit = max(max_profit, price - min_price)
            min_price = min(price, min_price)
        return max_profit

跳跃游戏

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        if n <= 1:
            return True
        max_reach = 0
        for i in range(n):
            if max_reach < i:
                return False
            max_reach = max(max_reach, i + nums[i])
            if max_reach >= n - 1:
                return True

跳跃游戏Ⅱ

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return 0
        max_reach = 0
        jumps = 0
        current_end = 0
        for i in range(n - 1):
            max_reach = max(max_reach, i + nums[i])
            if i == current_end:
                jumps += 1
                current_end = max_reach
        return jumps

划分字母区间

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        n = len(s)
        last_pos = {}
        for idx, ch in enumerate(s):
            last_pos[ch] = idx
        res = []
        start = 0
        end = 0
        for i, ch in enumerate(s):
            end = max(end, last_pos[ch])
            if i == end:
                length = i - start + 1
                res.append(length)
                start = i + 1
        return res

回溯法

原理

递归（探索所有可能的解）+ 回溯（找到一个解或确定当前路径不可行时（剪枝的思想））

回溯：撤销递归的基本操作

回溯法模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表);
        回溯，撤销处理结果
    }
}

路径是递归的参数（选择下一个节点进行操作），选择列表是当前存储的结果

处理节点基本就是选择节点然后加到当前的结果集'选择列表'里，回溯就是将'选择列表'里的节点拿出来

回溯三部曲函数的参数和返回值（返回值一般为 void）确定终止条件（到达了叶子节点）单层搜索的逻辑

为什么回溯法要在递归外面套一个 for 循环？

将搜索过程想象成一棵树（决策树），for 循环代表'横向'遍历，递归代表'纵向'遍历

46.全排列

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        used = [False] * len(nums)
        def backtrack():
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                path.append(nums[i])
                used[i] = True
                backtrack()
                path.pop()
                used[i] = False
        backtrack()
        return res

Python 支持闭包，内部函数可以直接访问外部函数作用域里的变量

用 used 数组标记使用过哪些元素

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False] * len(nums)
        self.backtracking(nums, used, [], res)
        return res

    def backtracking(self, nums, used, path, res):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            self.backtracking(nums, used, path, res)
            used[i] = False
            path.pop()

78. 子集

利用 startIndex 保证不重复

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.backtracking(nums, 0, [], res)
        return res

    def backtracking(self, nums, startIndex, path, res):
        res.append(path[:])
        if startIndex >= len(nums):
            return
        for i in range(startIndex, len(nums)):
            path.append(nums[i])
            self.backtracking(nums, i + 1, path, res)
            path.pop()

90. 子集Ⅱ

去重问题，类似组合总和Ⅱ

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False] * len(nums)
        nums.sort()
        self.backtracking(nums, 0, used, [], res)
        return res

    def backtracking(self, nums, startIndex, used, path, res):
        res.append(path[:])
        if startIndex >= len(nums):
            return
        for i in range(startIndex, len(nums)):
            if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == False:
                continue
            path.append(nums[i])
            used[i] = True
            self.backtracking(nums, i + 1, used, path, res)
            used[i] = False
            path.pop()

17. 电话号码的字母组合

选下一个数字对应的字母时，用 index + 1

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        self.backtracking(digits, 0, [], res)
        return res

    def backtracking(self, digits, index, path, res):
        phone_map = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
        }
        if len(digits) == len(path):
            res.append(''.join(path))
            return
        possibleLetters = phone_map[digits[index]]
        for i in possibleLetters:
            path.append(i)
            self.backtracking(digits, index + 1, path, res)
            path.pop()

22. 括号生成

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        self.backtracking(n, 0, 0, [], res)
        return res

    def backtracking(self, n, left, right, path, res):
        if left == n and right == n:
            res.append(''.join(path))
            return
        if left < n:
            path.append('(')
            self.backtracking(n, left + 1, right, path, res)
            path.pop()
        if right < left:
            path.append(')')
            self.backtracking(n, left, right + 1, path, res)
            path.pop()

77. 组合

利用递归不断向下探测可能的数字组合，并在返回时通过 pop() 撤销当前选择（回溯），从而系统地穷举出所有符合条件的路径

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        self.backtracking(n, k, 1, [], res)
        return res

    def backtracking(self, n, k, startIndex, path, result):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(startIndex, n + 1):
            path.append(i)
            self.backtracking(n, k, i + 1, path, result)
            path.pop()

39. 组合总和

回溯模板

结果不能重复用 startIndex，可以重复取的话，传入 i，不能重复取，传入 i + 1

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        self.backtracking(candidates, target, 0, 0, [], res)
        return res

    def backtracking(self, candidates, target, sum, startIndex, path, res):
        if sum > target:
            return
        if sum == target:
            res.append(path[:])
            return
        n = len(candidates)
        for i in range(startIndex, n):
            path.append(candidates[i])
            sum += candidates[i]
            self.backtracking(candidates, target, sum, i, path, res)
            sum -= candidates[i]
            path.pop()

40. 组合总和Ⅱ

用 used 数组去重

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        used = [False] * len(candidates)
        res = []
        candidates.sort()
        self.backtracking(candidates, target, 0, 0, used, [], res)
        return res

    def backtracking(self, candidates, target, sum, startIndex, used, path, res):
        if sum > target:
            return
        if sum == target:
            res.append(path[:])
            return
        n = len(candidates)
        for i in range(startIndex, n):
            if i > 0 and candidates[i] == candidates[i - 1] and used[i - 1] == False:
                continue
            path.append(candidates[i])
            sum += candidates[i]
            used[i] = True
            self.backtracking(candidates, target, sum, i + 1, used, path, res)
            path.pop()
            used[i] = False
            sum -= candidates[i]

131. 分割回文串

类似于组合问题，startIndex 就是切割线，[startIndex，i] 就是子串范围

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        self.backtracking(s, 0, [], res)
        return res

    def backtracking(self, s, startIndex, path, res):
        if startIndex == len(s):
            res.append(path[:])
            return
        for i in range(startIndex, len(s)):
            if self.isPalindrom(s, startIndex, i):
                path.append(s[startIndex : i + 1])
                self.backtracking(s, i + 1, path, res)
                path.pop()

    def isPalindrom(self, s, left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

动态规划

原理

本质：拆解问题（如何从子问题推导出父问题）+ 记住答案（下次使用）

动态规划的题都可以用暴力递归来解决，而暴力递归缺点是重复计算子问题导致效率低，动态规划的思想就是把计算过的子问题给保存下来，下次需要时可以直接用。另外，当父问题可以由已知的基本子问题推导出来时，就可以不再使用递归，大大提高效率。

解题步骤（从递归到动态规划）：

• Recursion（暴力递归）
• Memorize（存储计算过的值）
• Bottom-Up（自底向上动态规划）

这三步之间是有关系的，所以我们遇到动态规划的题目时，可以先写出暴力递归的解法，然后在此基础上，将其修改为动态规划。

暴力递归改动态规划的模板：

• if 的边界条件不变
• 创建用来存储的 dp 数组，并给出初始值
• 使用 for 循环自底向上构建 dp 数组：for 循环中，将递归调用变成从 dp 数组中取值，子问题的基本操作不变

注意

• for 循环的起始值从 dp 基础值的后一个位开始
• dp 数组保存的是暴力递归 return 的东西

动规五部曲

1. dp 数组以及下标的含义（包含所有状态）
2. 递推公式（跟前面有关系，或是 max 比较两个，本质还是要求出 dp 的下标含义）
3. dp 数组如何初始化
4. 遍历顺序（for 循环从哪开始）
5. 打印 dp 数组

509. 斐波那契数

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

70. 爬楼梯

暴力递归

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

动态规划

假设你现在站在第 3 阶台阶上。根据规则（每次只能爬 1 阶或 2 阶），你在到达第 3 阶的前一秒，只有两种可能的状态：

• 状态 A：你站在第 2 阶，然后跨了 1 阶上来的
• 状态 B：你站在第 1 阶，然后跨了 2 阶上来的

所以：到达第 3 阶的总方案数 = 经过第 2 阶上来的方案数 + 经过第 1 阶上来的方案数

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

杨辉三角形

暴力递归

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        def getValue(row, col):
            if col == 0 or col == row:
                return 1
            return getValue(row - 1, col - 1) + getValue(row - 1, col)
        res = []
        for row in range(numRows):
            current = []
            for col in range(row + 1):
                current.append(getValue(row, col))
            res.append(current)
        return res

动态规划

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0:
            return []
        dp = [[0] * (numRows) for _ in range(numRows)]
        res = []
        for row in range(numRows):
            current = []
            for col in range(row + 1):
                if col == 0 or row == col:
                    dp[row][col] = 1
                else:
                    dp[row][col] = dp[row - 1][col - 1] + dp[row - 1][col]
                current.append(dp[row][col])
            res.append(current)
        return res

打家劫舍

暴力递归

class Solution:
    def rob(self, nums: List[int]) -> int:
        def helper(index):
            if index >= len(nums):
                return 0
            rob_current = helper(index + 2) + nums[index]
            skip_current = helper(index + 1)
            return max(rob_current, skip_current)
        if not nums:
            return 0
        return helper(0)

动态规划

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

完全平方数

暴力递归

class Solution:
    def numSquares(self, n: int) -> int:
        def recursion(k: int) -> int:
            if k == 0:
                return 0
            min_cnt = float('inf')
            max_i = int(math.isqrt(k))
            for i in range(1, max_i + 1):
                square = i * i
                cnt = 1 + recursion(k - square)
                min_cnt = min(cnt, min_cnt)
            return min_cnt
        return recursion(n)

动态规划

class Solution:
    def numSquares(self, n: int) -> int:
        if n == 0:
            return 0
        dp = [0] + [float('inf')] * n
        for target in range(1, n + 1):
            max_i = int(math.isqrt(target))
            for i in range(1, max_i + 1):
                dp[target] = min(dp[target], 1 + dp[target - i * i])
        return dp[n]

322. 零钱兑换

完全背包类型问题，一维滚动数组

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in coins:
            for j in range(i, amount + 1):
                dp[j] = min(dp[j], dp[j - i] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

300. 最长递增子序列

回溯法

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        def backtrack(start, path):
            nonlocal res
            res = max(res, len(path))
            for i in range(start, n):
                if not path or nums[i] > path[-1]:
                    path.append(nums[i])
                    backtrack(i + 1, path)
                    path.pop()
        backtrack(0, [])
        return res

暴力递归

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        def recursion(index, previous):
            if index == n:
                return 0
            not_take = recursion(index + 1, previous)
            take = 0
            if nums[index] > previous:
                take = 1 + recursion(index + 1, nums[index])
            return max(take, not_take)
        return recursion(0, float('-inf'))

动态规划

需要两个状态所以需要 j

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

343. 整数拆分

利用动态规划（DP）从小到大递推，通过遍历每一个可能的拆分点 j，在'直接拆成两个数'与'拆出 j 后对剩余部分取最优解'之间取最大值，从而逐步构建出目标数字 n 的最大乘积

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = 0
        dp[2] = 1
        for i in range(3, n + 1):
            for j in range(1, i // 2 + 1):
                dp[i] = max(j * (i - j), j * dp[i - j], dp[i])
        return dp[n]

96. 不同的二叉搜索树

遍历每一个可能的节点作为根节点，将总方案数拆解为左子树形态数与右子树形态数的笛卡尔积（乘积）之和

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            for j in range(1, n + 1):
                dp[i] += dp[j - 1] * dp[i - j]
        return dp[n]

01 背包

二维数组

通过决策'是否放入当前物品'，利用已经计算出的前 i-1 个物品在不同容量下的局部最优解，逐步递推出当前背包容量所能装载的最大价值

dp 数组含义：在 0 到 i 任取物品，容量为 j 的背包的最大价值

n, bagweight = map(int, input().split())
weight = list(map(int, input().split()))
value = list(map(int, input().split()))
dp = [[0] * (bagweight + 1) for _ in range(n)]
for j in range(weight[0], bagweight + 1):
    dp[0][j] = value[0]
for i in range(1, n):
    for j in range(1, bagweight + 1):
        if j < weight[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
print(dp[n - 1][bagweight])

一维滚动数组

因为二维数组的 i 行只和 i - 1 行有关，所以可以简化为一维。利用滚动，即每一次 for j 的循环就是二维数组的一行，所引用的仍是上一轮物品留下的'旧值'

倒序保证物品只被加了一次

n, bagweight = map(int, input().split())
weight = list(map(int, input().split()))
value = list(map(int, input().split()))
dp = [0] * (bagweight + 1)
dp[0] = 0
for i in range(n):
    for j in range(bagweight, weight[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(dp[bagweight])

完全背包

递推公式：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])，和 01 背包的递推公式不同

这里的二维类似于 01 背包的一维滚动数组

198. 打家劫舍

在遍历每间房时权衡'抢（当前金额 + 前前家累计）'与'不抢（直接沿用前一家累计）'来获取最大化收益

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

121. 买卖股票的最佳时机

持有股票和不持有股票的两种状态，持有股票时又包括没有操作股票和当天买入股票两种状态，不持有股票同理（建模）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], -prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
        return max(dp[-1][0], dp[-1][1])

排序算法

归并排序

分而治之

• 分：大问题变小问题，使用递归
• 治：合并

class Solution:
    def mergeSort(self, nums):
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left = nums[:mid]
        right = nums[mid:]
        left = self.mergeSort(left)
        right = self.mergeSort(right)
        return self.merge(left, right)

    def merge(self, left, right):
        merge = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                merge.append(left[i])
                i += 1
            else:
                merge.append(right[j])
                j += 1
        while i < len(left):
            merge.append(left[i])
            i += 1
        while j < len(right):
            merge.append(right[j])
            j += 1
        return merge

快速排序

原理：选择一个基准值（pivot），将数组分为两部分：小于基准值的元素和大于基准值的元素，然后递归地对这两部分进行排序。

每次都只找到一个元素（基准值）的正确位置，利用递归找到所有元素的正确位置

时间复杂度：O(n log n)

def quicksort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)
        quicksort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot_index = random.randint(low, high)
    arr[high], arr[pivot_index] = arr[pivot_index], arr[high]
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

技巧

只出现一次的数字

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for i in nums:
            result ^= i
        return result

多数元素

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = 0
        for num in nums:
            if count == 0:
                candidate = num
            if num == candidate:
                count += 1
            else:
                count -= 1
        return candidate

颜色分类

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        low, index, high = 0, 0, len(nums) - 1
        while index <= high:
            if nums[index] == 0:
                nums[low], nums[index] = nums[index], nums[low]
                low += 1
                index += 1
            elif nums[index] == 1:
                index += 1
            elif nums[index] == 2:
                nums[high], nums[index] = nums[index], nums[high]
                high -= 1

下一个排列

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        if n < 2:
            return
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i >= 0:
            j = n - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

寻找重复数

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[0]
        fast = nums[nums[0]]
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]
        fast = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow