hot100整理之python版

hot100整理之python版

哈希

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        res = 0
        st = set(nums)  # 使用哈希集合，从而使查找为O(1)
        # 这里不能遍历nums，否则会多次处理相等的元素
        for num in st:
            if num - 1 in st:   # 从最小的开始
                continue
            last = num + 1
            while last in st:
                last = last + 1
            res = max(res, last - num)
        return res

双指针

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        res = 0
        while left != right:
            h = min(height[left], height[right])
            w = right - left
            res = max(res, h * w)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return res

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i, num in enumerate(nums):
            if num > 0: # 剪枝
                break
            if i > 0 and nums[i] == nums[i - 1]:    # 去重
                continue
            # 双指针收缩
            j = i + 1
            k = len(nums) - 1
            while j < k:
                sum = nums[i] + nums[j] + nums[k]
                if sum > 0:
                    k -= 1
                elif sum < 0:
                    j += 1
                else:
                    res.append([nums[i], nums[j], nums[k]])
                    # 去重
                    while j < k and nums[j] == nums[j + 1]:
                        j += 1
                    while j < k and nums[k] == nums[k - 1]:
                        k -= 1
                    j += 1
                    k -= 1
        return res

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n <= 2:
            return 0
        # 使用单调栈记录索引，从栈顶到栈底单调递增，从而找到凹槽
        stack = []
        stack.append(0)
        res = 0
        for i in range(1, n):
            top = stack[-1]
            while stack and height[top] < height[i]:
                mid = stack.pop()
                if stack:
                    left = stack[-1]
                    h = min(height[left], height[i]) - height[mid]
                    w = i - left - 1
                    res += h * w
                    top = stack[-1]
            stack.append(i)
        return res

滑动窗口

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        slow = fast = 0
        st = set()
        res = 0
        while fast != len(s):
            if s[fast] in st:
                # 出现重复元素，将重复元素及其之前的元素全部清除
                while s[slow] != s[fast]:
                    st.remove(s[slow])
                    slow += 1
                slow += 1   # 移动到重复元素的下一位
                fast += 1
            else:
                st.add(s[fast])
                fast += 1
            res = max(res, fast - slow)
        return res

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        counter = Counter(p)    # 统计p中元素出现的频率
        res = []
        left = 0
        for right, c in enumerate(s):
            counter[c] -= 1 # s中出现就减一，减到零说明找到
            while counter[c] < 0:   # c出现过多
                counter[s[left]] += 1
                left += 1
            if right - left + 1 == len(p):  # 没有超出的了，说明s子串与p构成异位词
                res.append(left)
        return res

子串

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 哈希表键为前缀和，值为该前缀和的个数，遍历查找s[j] - s[i] = k，即统计有多少以j结尾的子数组
        res = sum = 0
        cnt = defaultdict(int)
        cnt[0] = 1
        for num in nums:
            sum += num  # 统计当前前缀和，即s[j]
            res += cnt[sum - k] # 寻找所有的s[i]
            cnt[sum] += 1
        return res

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 使用单调队列，队列单调递减，从而保证队首为最大值
        # 同时在其后面出现的次大值不会消亡，而其前面比最大值小的会消亡
        # 考虑到滑动窗口右移，左边消亡的值没有留下的意义
        res = [0] * (len(nums) - k + 1)
        q = deque()

        for i, num in enumerate(nums):
            while q and nums[q[-1]] <= num: # 相等也要移除，因为前面的离开了而最大值不变
                q.pop() # 维护单调性
            q.append(i)
            
            left = i - k + 1
            if q[0] < left: # 队首离开窗口
                q.popleft()
            
            if left >= 0:
                res[left] = nums[q[0]]
        
        return res

最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        cnt = defaultdict(int)
        for c in t:
            cnt[c] += 1
        less = len(cnt)  # 记录子串中有多少字母出现次数达不到t中的出现次数

        resLeft, resRight = -1, len(s)
        left = 0
        for right, c in enumerate(s):
            cnt[c] -= 1 # 右端点进入子串
            if cnt[c] == 0:
                less -= 1   # 达到了
            while less == 0:    # 已全部达到，进一步缩小
                if right - left < resRight - resLeft:
                    resLeft, resRight = left, right
                x = s[left]
                if cnt[x] == 0:
                    less += 1
                cnt[x] += 1 # 左端点移出子串
                left += 1
        return "" if resLeft < 0 else s[resLeft : resRight + 1]

普通数组

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 反转三次即可
        def reverse(start: int, end: int) -> None:
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

        k %= len(nums)  # 否则会溢出
        reverse(0, len(nums) - 1)
        reverse(0, k - 1)
        reverse(k, len(nums) - 1)

除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * len(nums)
        # 先计算后面数字的乘积
        for i in range(len(nums) - 2, -1, -1):
            res[i] = res[i + 1] * nums[i + 1]
        # 再乘上前面数字的乘积
        pre = 1
        for i, x in enumerate(nums):
            res[i] *= pre
            pre *= x
        return res

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 通过交换位置，使得数字1在下标0处，数字2在下标1处，以此类推
        for i in range(0, len(nums)):
            # 使用while，保证最后nums[i] = i + 1
            while 1 <= nums[i] <= len(nums) and nums[i] != nums[nums[i] - 1]:   # 不使用nums[i] = i + 1，防止落入死循环
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
        # 从小到大检查哪个正数缺失
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        return len(nums) + 1

矩阵

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        col0 = any(matrix[i][0] == 0 for i in range(m))
        row0 = any(matrix[0][j] == 0 for j in range(n))

        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        
        if col0:
            for i in range(m):
                matrix[i][0] = 0
        
        if row0:
            for j in range(n):
                matrix[0][j] = 0

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 一次转置和一次行翻转
        m, n = len(matrix), len(matrix[0])
        # 转置
        for i in range(m):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # 行翻转
        for i in range(m):
            for j in range(n // 2):
                matrix[i][j], matrix[i][n - 1 - j] = matrix[i][n - 1 - j], matrix[i][j]

搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 使用右上角判断，以排除一定比目标值大或者一定比目标值小的部分
        i, j = 0, len(matrix[0]) - 1
        while i < len(matrix) and j >= 0:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                j -= 1
            else:
                i += 1
        return False

图论

岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        # 使用dfs遍历岛屿的每一块
        def dfs(i: int, j: int) -> None:
            if(i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1'):
                return
            grid[i][j] = '2'    # 2表示已经访问
            dfs(i, j - 1)
            dfs(i, j + 1)
            dfs(i - 1, j)
            dfs(i + 1, j)
        
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    dfs(i, j)
                    res += 1
        return res

腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        # bfs，使用队列记录新的腐烂的橘子
        fresh = 0   # 记录是否将所有橘子腐烂
        res = 0
        m, n = len(grid), len(grid[0])
        q = []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    fresh += 1
                elif grid[i][j] == 2:
                    q.append((i, j))
        while q and fresh:
            res += 1
            tmp = q
            q = []
            for i, j in tmp:
                for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                    if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                        grid[x][y] = 2
                        fresh -= 1
                        q.append((x, y))
        return -1 if fresh != 0 else res

课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 三色标记法，0表示未访问，1表示正在访问，2表示已经访问
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[b].append(a)  # 使用链表表示该图
        
        colors = [0] * numCourses
        def dfs(course : int) -> bool:
            colors[course] = 1  # 正在访问
            for nxt in graph[course]:
                # 正在访问，或者未访问的在深度搜索后出现了环
                if colors[nxt] == 1 or colors[nxt] == 0 and dfs(nxt):
                    return True
            colors[course] = 2
            return False
        
        for course in range(numCourses):
            if colors[course] == 0 and dfs(course): # 有环
                return False
        return True

实现 Trie (前缀树)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Node:
    def __init__(self):
        self.son = {}
        self.end = False    # 以这个节点为结尾，组成的前缀是否构成插入的字符串


class Trie:
    # 即26叉树

    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if not c in cur.son:
                cur.son[c] = Node()
            cur = cur.son[c]
        cur.end = True

    def search(self, word: str) -> bool:
        return True if self.find(word) == 2 else False

    def startsWith(self, prefix: str) -> bool:
        return True if self.find(prefix) else False

    def find(self, s: str) -> int:
        # 0表示未找到，1表示只找到前缀，2表示找到完整的字符串
        cur = self.root
        for c in s:
            if not c in cur.son:
                return 0
            cur = cur.son[c]
        return 2 if cur.end else 1
        


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

回溯

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        numString = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        res = []
        path = []

        def backtracking(index: int) -> None:
            if len(path) == len(digits):
                res.append("".join(path[:]))
                return
            for c in numString[int(digits[index])]:
                path.append(c)
                backtracking(index + 1)
                path.pop()
        
        if not digits or len(digits) == 0:
            return res
        backtracking(0)
        return res

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        path = []   # path记录左括号的索引

        # 使用balance记录左括号数与右括号数之差，index则为上一个左括号的索引
        def backtracking(index: int, balance: int) -> None:
            if len(path) == n:
                ans = [')'] * 2 * n
                for i in path:
                    ans[i] = '('
                res.append(''.join(ans))
                return
            # 每次加入b个右括号，再加入一个左括号
            for b in range(balance + 1):
                path.append(index + b + 1)
                backtracking(index + b + 1, balance - b + 1)
                path.pop()

        backtracking(-1, 0)
        return res

单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        def backtracking(i: int, j: int, index: int) -> bool:
            if board[i][j] != word[index]:
                return False
            
            if index == len(word) - 1:  # 减一是因为刚刚已判断出最后一位匹配
                return True
            
            board[i][j] = '0'   # 标记为已经访问
            
            for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):
                if 0 <= x < m and 0 <= y < n and backtracking(x, y, index + 1):
                    return True
            
            board[i][j] = word[index]   # 回溯
            return False

        for i in range(m):
            for j in range(n):
                if backtracking(i, j, 0):
                    return True

        return False

分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        path = []

        def check(prefix: str) -> bool:
            for i in range(len(prefix) // 2):
                if prefix[i] != prefix[len(prefix) - i - 1]:
                    return False
            return True

        def backtracking(index: int) -> None:
            if index == len(s):
                res.append(path[:])
                return

            prefix = []
            for i in range(index, len(s)):
                # 构造以index开始，i结束的回文
                prefix.append(s[i])
                if check(prefix):
                    path.append(''.join(prefix))
                    backtracking(i + 1)
                    path.pop()
        
        backtracking(0)
        return res

N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        board = [-1] * n # 记录皇后在每一行的第几列
        # 都是从上到下的顺序
        usedCol = [False] * n
        used45 = [False] * (2 * n - 1)
        used135 = [False] * (2 * n - 1)

        def backtracking(row: int) -> None:
            if row == n:
                path = []
                for i in range(n):
                    s = ['.'] * n
                    s[board[i]] = 'Q'
                    path.append(''.join(s))
                res.append(path[:])
            
            for i in range(n):
                if usedCol[i] or used45[i + row] or used135[n - 1 + row - i]:
                    continue
                board[row] = i
                usedCol[i] = True
                used45[i + row] = True
                used135[n - 1 + row - i] = True
                backtracking(row + 1)
                used135[n - 1 + row - i] = False
                used45[i + row] = False
                usedCol[i] = False
            
        backtracking(0)
        return res

栈

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class MinStack:
    # 栈中元素配对，前者为当前元素，后者为前缀最小值

    def __init__(self):
        self.stack = [(0, inf)] # 放一个哨兵，从而不必检查栈空

    def push(self, val: int) -> None:
        self.stack.append((val, min(val, self.getMin())))

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

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

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


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def decodeString(self, s: str) -> str:
        # 认为每出现一组[]陷入一次递归，使用栈来模拟
        res = ""
        k = 0   # 记录[]前的那个数字
        stack = []
        
        for c in s:
            if c.isalpha():
                res += c
            elif c.isdigit():
                k = k * 10 + int(c)
            elif c == '[':  # 之前的结果入栈，防止丢失
                stack.append((res, k))
                res = ""
                k = 0   # 因此在else处不用k = 0，因为最深的[]没有数字出现
            else:   # 递归结束，出栈进行拼接、
                pre_res, pre_k = stack.pop()
                res = pre_res + res * pre_k

        return res

柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 该单调栈从栈顶到栈底单调递减
        heights.append(-1)  # 从而保证到最后时，栈中元素都出来进行计算
        stack = [-1]    # 保证栈空时入栈
        res = 0
        for right in range(len(heights)):
            # left和right之间的所有柱子中，mid是最矮的那个，故高计算正确
            # 因为mid左边的柱子中，第一个比它矮的依然在栈中，即left
            # 而mid右边如果有比它矮的柱子，则mid会提前出栈
            # 而left和right都比mid矮，因此宽是最大的
            while heights[stack[-1]] > heights[right]:
                mid = stack.pop()
                left = stack[-1]
                h = heights[mid]
                w = right - left - 1
                res = max(res, h * w)
            stack.append(right)
        return res

堆

数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_select(nums, k) -> int:
            pivot = random.choice(nums) # 随机选择基准数
            big, equal, small = [], [], []
            for num in nums:
                if num > pivot:
                    big.append(num)
                elif num < pivot:
                    small.append(num)
                else:
                    equal.append(num)
            if k <= len(big):
                return quick_select(big, k)
            elif len(nums) - len(small) < k:
                return quick_select(small, k - len(nums) + len(small))
            else:
                return pivot
        return quick_select(nums, k)

前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 使用桶排序
        # step1: 使用哈希表统计每个元素出现的次数
        cnt = Counter(nums)
        max_cnt = max(cnt.values())

        # step2: 出现次数相同的元素放在同一个桶中
        buckets = [[] for _ in range(max_cnt + 1)]
        for x, c in cnt.items():
            buckets[c].append(x)
        
        # step3: 倒序遍历buckets，从而得到答案
        res = []
        for bucket in reversed(buckets):
            res += bucket
            if len(res) == k:
                return res

数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MedianFinder:
    # 分为两个堆left和right，保证left的最大值小于right的最小值的同时，维护left - right <= 1
    # 当left == right时，将元素添加到right中，并将right的最小值移到left中
    # 当left - right == 1时，将元素添加到left中，并将left的最大值移到right中
    # 使用left的最大值和right的最小值来计算中位数

    def __init__(self):
        self.left = []
        self.right = []

    def addNum(self, num: int) -> None:
        if len(self.left) == len(self.right):
            heapq.heappush(self.right, num)
            heapq.heappush(self.left, -heapq.heappop(self.right))
        else:
            heapq.heappush(self.left, -num)
            heapq.heappush(self.right, -heapq.heappop(self.left))

    def findMedian(self) -> float:
        if len(self.left) == len(self.right):
            return (-self.left[0] + self.right[0]) / 2
        else:
            return -self.left[0]

贪心

跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
0 <= j <= nums[i] 且
i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def jump(self, nums: List[int]) -> int:
        # 当触及到当前跳跃极限时进行跳跃，并更新覆盖范围
        # 这次跳跃本质上是跳到了能触及下次跳跃极限的位置
        # 这样是正确的，因为迭代器局限在当前覆盖范围之内
        # nextJump表示的是在[0, curJump]这个区间里，所能达到的最远距离
        # 而curJump反映的是上一次所能达到的最远距离
        # 当遍历到curJump时，说明必须跳一次才能到达更远的距离了，这次跳的距离不确定
        curJump, nextJump, res, i = 0, 0, 0, 0
        while i <= curJump and curJump < len(nums) - 1:
            nextJump = max(nextJump, i + nums[i])
            if i == curJump:
                curJump = nextJump
                res += 1
            i += 1
        return res

划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 类似于跳跃游戏，遍历字母，找到它们最后出现在哪里，当触及到边缘时，分割出一个区间
        further = [0] * 26
        # 记录最后一次出现在哪里
        for i, c in enumerate(s):
            further[ord(c) - 97] = i
        most,last = 0, -1
        res = []
        for i, c in enumerate(s):
            most = max(most, further[ord(c) - 97])
            if i == most:
                res.append(most - last)
                last = most
        return res

动态规划

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [inf] * (n + 1)
        dp[0] = 0
        i = 1
        while i * i <= n:
            j = i * i
            while j <= n:
                dp[j] = min(dp[j], dp[j - i * i] + 1)
                j += 1
            i += 1
        return dp[n]

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

1
2
3
4
5
6
7
8
9
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for i in range(len(s) + 1):
            for word in wordDict:
                if s[i - len(word): i] == word and dp[i - len(word)]:
                    dp[i] = True
        return dp[len(s)]

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 这里的tails用于记录长度为i + 1的递增子序列的最后一个元素
        tails, res = [0] * len(nums), 0
        for num in nums:
            # 二分查找到可以插入新的元素的递增子序列
            i, j = 0, res
            while i < j:
                m = (i + j) // 2
                if tails[m] < num:
                    i = m + 1
                else:
                    j = m
            tails[i] = num
            if j == res:
                res += 1
        return res

乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。

1
2
3
4
5
6
7
8
9
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # dp[0]表示以i结尾的最大值，dp[1]表示最小值，从而包含到正负性
        dp = [nums[0]] * 2       
        res = nums[0]
        for i in range(1, len(nums)):
            dp[0], dp[1] = max(nums[i], nums[i] * dp[0], nums[i] * dp[1]), min(nums[i], nums[i] * dp[0], nums[i] * dp[1])
            res = max(res, dp[0])
        return res

分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 即能否塞满sum / 2的背包
        # dp[i]表示容量为i的最大价值
        # 这里让重量等于价值，防止价值超出target
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2
        dp = [0] * (target + 1)
        for i in range(len(nums)):
            # 倒序遍历，防止提前更新数据
            for j in range(target, nums[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
            # 剪枝
            if dp[target] == target:
                return True
        return dp[target] == target

最长有效括号

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 “(()())”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # dp[i] 表示以i结尾的有效长度
        res = 0
        dp = [0] * len(s)
        for i in range(1, len(s)):
            # 有效的括号一定以')'结尾
            if s[i] == ')':
                if s[i - 1] == '(':
                    dp[i] = (dp[i - 2] if i - 2 >= 0 else 0) + 2
                # 跳过中间的有效部分后，如果不是'('，那也就不是有效的了
                elif i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(':
                    dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] - 2 >= 0 else 0) + 2
            res = max(res, dp[i])
        return res

多维动态规划

最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 中心扩散法，枚举中心向两边扩散到最长回文
        n = len(s)
        res_left = res_right = 0

        for i in range(2 * n - 1):
            # 包揽奇数回文串和偶数回文串
            l, r = i // 2, (i + 1) // 2
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            # 结束时，s[l + 1]到s[r - 1]为回文串
            if r - l - 1 > res_right - res_left:
                res_left, res_right = l + 1, r  # 左闭右开
        return s[res_left: res_right]

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 类似于编辑距离，dp[i][j]记录text[:i]和text2[:j]的最长公共子序列
        # 从dp[0][0]开始，即表示两者都为空
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    # 不用考虑dp[i - 1][j]和dp[i][j - 1]的原因是，这两个只比dp[i - 1][j - 1]多一个字符
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]

链表

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # 从中间节点开始反转链表
    def findMid(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast, slow = head, head
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        return slow
    
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur, prev = head, None
        while cur:
            cur.next, cur, prev = prev, cur.next, cur
        return prev
    
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        mid = self.findMid(head)
        head2 = self.reverseList(mid)
        while head2:
            if head.val != head2.val:
                return False
            head, head2 = head.next, head2.next
        return True

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 让fast先走n步
        fast, slow = head, ListNode(-1, head)   # 规避删除节点是head
        res = slow
        for _ in range(n):
            fast = fast.next
        while fast:
            fast, slow = fast.next, slow.next
        slow.next = slow.next.next
        return res.next

两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 递归
        if not head or not head.next:
            return head
        cur = head.next
        head.next = self.swapPairs(cur.next)
        cur.next = head
        return cur

K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        n = 0   # 获取长度
        cur = head
        while cur:
            cur = cur.next
            n += 1
        prev, cur = None, head
        dum = ListNode(-1, head)
        start = dum
        while n >= k:
            n -= k
            # k个一组进行链表反转
            for _ in range(k):
                cur.next, cur, prev = prev, cur.next, cur
            # start为反转链表的前一节点，cur此时落在下一个反转链表的开头，prev为本次反转链表的开头
            start.next.next, start.next, start = cur, prev, start.next
        return dum.next

随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
            
        # step1: 将原链表和新链表交错在一起
        cur = head
        while cur:
            cur.next, cur = Node(cur.val, cur.next), cur.next
        
        # step2: 遍历链表找到random，利用交错的特性来完成random的拷贝
        cur = head
        while cur:
            if cur.random:
                # 进行拷贝
                cur.next.random = cur.random.next
            cur = cur.next.next
        
        # step3: 分离出新链表
        cur = head.next
        while cur.next:
            cur.next, cur = cur.next.next, cur.next.next
        return head.next

排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 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, fast, prev = head, head, None
        while fast and fast.next:
            prev, slow, fast = slow, slow.next, fast.next.next
        prev.next = None    # 断开两个链表的连接
        return slow

    def mergeTwoLists(self, head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
        dum = ListNode(-1)
        cur = dum
        while head1 and head2:
            if head1.val < head2.val:
                cur.next = head1
                head1 = head1.next
            else:
                cur.next = head2
                head2 = head2.next
            cur = cur.next
        cur.next = head1 if head1 else head2
        return dum.next

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

        # 保证两个子链表排好序
        head = self.sortList(head)
        head2 = self.sortList(head2)

        return self.mergeTwoLists(head, head2)

合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # 两两一组，四四一组，以此类推进行自底向上的合并
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dum = ListNode(-1)
        cur = dum
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return dum.next
    
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        m = len(lists)
        if m == 0:
            return None
        step = 1
        while step < m:
            for i in range(0, m - step, step * 2):
                lists[i] = self.mergeTwoLists(lists[i], lists[i + step])
            step *= 2
        return lists[0]

LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Node:
    def __init__(self, key = 0, value = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    # 双向环形链表+字典快速查找
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dum = Node()
        self.dum.prev = self.dum    # 为最后一个，即即将过期的那个
        self.dum.next = self.dum    # 为第一个，即才访问的那个
        self.diction = {}

    def get(self, key: int) -> int:
        node = self.getNode(key)
        return node.value if node else -1

    def put(self, key: int, value: int) -> None:
        node = self.getNode(key)
        if node:
            # 更新value
            node.value = value
        else:
            self.diction[key] = node = Node(key, value)
            self.push_front(node)
            if len(self.diction) > self.capacity:
                last_node = self.dum.prev
                del self.diction[last_node.key]
                self.remove(last_node)

    def getNode(self, key: int) -> Optional[Node]:
        if key not in self.diction:
            return None
        node = self.diction[key]
        # 使用过，放在最前面
        self.remove(node)
        self.push_front(node)
        return node

    def remove(self, node: Node) -> None:
        node.prev.next, node.next.prev = node.next, node.prev
    
    def push_front(self, node: Node) -> None:
        node.prev, node.next, self.dum.next.prev, self.dum.next = self.dum, self.dum.next, node, node   # 注意从左到右依次赋值
        


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

二叉树

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def check(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
            if not left and not right:
                return True
            elif left and right:
                if left.val != right.val:
                    return False
                outside = check(left.left, right.right)
                inside = check(left.right, right.left)
                return outside and inside
            else:
                return False
        return check(root.left, root.right)

二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # 链为叶子节点到当前节点之间的长度，直径为左右两子树的最长链之和
        res = 0
        def computeChain(root: Optional[TreeNode]) -> int:
            if not root:
                return -1
            leftChain = computeChain(root.left) + 1
            rightChain = computeChain(root.right) + 1
            nonlocal res
            res = max(res, leftChain + rightChain)
            return max(leftChain, rightChain)
        computeChain(root)
        return res

二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root:
            return res
        q = deque()
        q.append(root)
        # 使用队列辅助
        while q:
            path = []
            for _ in range(len(q)): # 当前层的节点数
                node = q.popleft()
                path.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(path)
        return res

二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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:
    head = None

    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        # 将先序遍历倒过来，从而倒着将树整理成链表
        # 每次使用头插法即可
        if not root:
            return root
        self.flatten(root.right)
        self.flatten(root.left)
        root.left = None
        root.right = self.head
        self.head = root

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # 使用哈希表预处理中序遍历，便于快速查找位置，节约时间
        index = {x: i for i, x in enumerate(inorder)}

        def findNode(pre_l: int, pre_r: int, in_l: int, in_r: int) -> Optional[TreeNode]:
            if pre_l > pre_r:  # 空节点
                return None
            start = preorder[pre_l]
            root = TreeNode(start)
            mid = index[start]
            left_len, right_len = mid - in_l, in_r - mid
            root.left = findNode(pre_l + 1, pre_l + left_len, in_l, mid - 1)
            root.right = findNode(pre_r - right_len + 1, pre_r, mid + 1, in_r)
            return root
        
        return findNode(0, len(preorder) - 1, 0, len(inorder) - 1)

路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # 类比和为K的子数组，使用哈希表，键为前缀和，值为个数
        res = 0
        cnt = defaultdict(int)
        cnt[0] = 1

        def recursive(node: Optional[TreeNode], s: int) -> None:
            if not node:
                return

            nonlocal res
            s += node.val   # 以该节点结尾的当前前缀和
            res += cnt[s - targetSum]
            cnt[s] += 1

            recursive(node.left, s)
            recursive(node.right, s)
            cnt[s] -= 1 # 回溯，因此数量减一
        
        recursive(root, 0)
        return res

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 后序遍历自底向上
        # 只返回p, q, None, 或者它们共同的祖先
        if not root or root == p or root == q:
            return root
        left, right = self.lowestCommonAncestor(root.left, p, q), self.lowestCommonAncestor(root.right, p, q)
        if not left and not right:  # 都为空，说明p,q都没出现
            return None
        if left and not right:  # 其中一个不为空，说明已经找到或者只找到一个
            return left
        if not left and right:
            return right
        if left and right:  # 左右各一个，说明当前节点为公共祖先
            return root

二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
        # 同样是只算链的和
        res = -inf

        def computeChain(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            left_chain = computeChain(node.left)
            right_chain = computeChain(node.right)
            nonlocal res
            res = max(res, left_chain + right_chain + node.val)
            # 链可以没有元素，res计算时保证了node.val，从而保证路径中至少有一个节点，而链不用，因此和0比较
            return max(max(left_chain, right_chain) + node.val, 0)
        
        computeChain(root)
        return res

技巧

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # 使用擂台比较，考虑到严格众数比其他数加起来都多，它一定会留到最后
        res = hp = 0
        for x in nums:
            # 每次hp = 0将该数字作为擂主，直到出现次数抵消，开启新擂主
            if hp == 0:
                res, hp = x, 1
            else:
                hp += 1 if x == res else -1
        return res

颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 使用插入排序，将nums[i]插入到nums[:i]的序列中去
        # 只用将0,1,2结尾的三个数字向后移动，因此维护它们的位置
        p0 = p1 = 0
        for i, x in enumerate(nums):
            # 倒着插入，从而保证覆盖
            nums[i] = 2
            if x <= 1:
                nums[p1] = 1
                p1 += 1
            if x == 0:
                nums[p0] = 0
                p0 += 1

下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        # step1: 从右向左找到第一个小于右侧相邻数字的数x，此时x右边单调递减
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        # step2: 找到x右边最小的大于x的数字y，进行交换，此时单调递减不变
        # 注意如果step1没找到，说明已经是最大排列
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        # step3: 反转y右边的数，变成最小排列
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # 使用环形链表，假设当前元素为i，则其指向nums[i]
        # 环的入口的下标就是重复元素，因为进入环需要有元素指向该下标，而环内也有元素指向该下标
        # 而nums[0] != 0，因此不用担心自环
        slow, fast = 0, 0
        while True:
            fast = nums[fast]
            fast = nums[fast]
            slow = nums[slow]
            if fast == slow:
                break
        slow = 0
        while fast != slow:
            fast = nums[fast]
            slow = nums[slow]
        return slow

二分查找

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 寻找最小的满足nums[i] >= target的下标，因此可能溢出len，也可能不存在target，后续用此进行判断
        def lower_bound(t: int) -> int:
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] >= t:
                    right = mid - 1
                else:
                    left = mid + 1
            return left # 此时left = right + 1，因此返回left
        
        start = lower_bound(target)
        # 借lower_bound函数的漏洞判断存在与否
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        # 因为都是整数，故+1找下一位
        end = lower_bound(target + 1)
        return [start, end - 1]

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 通过比较x与nums[-1]来判断x在第一段还是第二段
        # check函数用以判断target是否在mid的左边（或者相等）
        def check(i: int) -> bool:
            x = nums[i]
            if x > nums[-1]:    # 在第一段，此时target也必须在第一段
                return target > nums[-1] and x >= target
            else:
                return target > nums[-1] or x >= target
        
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return right if nums[right] == target else -1

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 均分两个数组合并在一起的数组，从而利用前数组的最大值和后数组的最小值求得中位数
        # 从枚举nums1中有多少元素在前数组中，到二分查找
        # 这里需要保证nums1长度小于nums2，防止j变为负数
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        # 计算有多少元素在前数组中
        left, right = 0, m
        while left <= right:
            i = (left + right) // 2 # nums1中有多少元素在前数组中
            j = (m + n + 1) // 2 - i    # 规定奇数时前数组比后数组多一个元素
            nums1_left = nums1[i - 1] if i > 0 else float('-inf')
            nums1_right = nums1[i] if i < m else float('inf')
            nums2_left = nums2[j - 1] if j > 0 else float('-inf')
            nums2_right = nums2[j] if j < n else float('inf')
            if nums1_left <= nums2_right and nums2_left <= nums1_right:
                left_max = max(nums1_left, nums2_left)
                right_min = min(nums1_right, nums2_right)
                if (m + n) % 2 == 0:
                    return (left_max + right_min) / 2
                else:
                    return left_max
            elif nums1_left < nums2_right:   # 太小，多选
                left = i + 1
            else:   # 太大，少选
                right = i - 1
力扣 > hot100
#leetcode #hot100
hot100整理之python版
http://example.com/2025/09/14/hot100整理之python版/
作者
jietiDdd
发布于
2025年9月14日
许可协议