CodeTop - Top 50

二分查找

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -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 search(self, nums: List[int], target: int) -> int:
        # 初始化左边界 (l) 和右边界 (r)
        l, r = 0, len(nums) - 1
        
        # 使用二分查找在 nums 中搜索 target
        while l < r:
            # 计算中间位置 m，注意使用 (l + r + 1) // 2 避免死循环
            m = (l + r + 1) // 2
            
            # 如果中间值小于等于目标值，说明目标值在右侧或中间值就是目标值
            # 将左边界移动到 m
            if nums[m] <= target:
                l = m
            else:
                # 否则，目标值在左侧，将右边界移动到 m - 1
                r = m - 1
        
        # 循环结束后，检查 nums[l] 是否等于目标值
        # 如果等于，返回 l；否则返回 -1 表示未找到
        return l if nums[l] == target else -1

用栈实现队列

232. 用栈实现队列

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

方案：二栈模拟

这里我们维护两个栈，pop和peek，如果stk_out是空的我们就把stk_in的导进来，有的话就不去动

 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


class MyQueue:
    def __init__(self):
        # 初始化两个栈：stk_in 用于入队操作，stk_out 用于出队操作
        self.stk_in = []
        self.stk_out = []

    def push(self, x: int) -> None:
        # 将元素 x 入队，直接压入 stk_in 栈
        self.stk_in.append(x)

    def move(self):
        # 将 stk_in 栈中的所有元素移动到 stk_out 栈中
        # 这样可以实现元素的倒序，使得 stk_out 的栈顶元素是队列的头部
        while self.stk_in:
            x = self.stk_in.pop()
            self.stk_out.append(x)

    def pop(self) -> int:
        # 如果 stk_out 为空，先调用 move 方法将 stk_in 中的元素倒序到 stk_out
        if not self.stk_out:
            self.move()
        # 弹出并返回 stk_out 的栈顶元素（即队列的头部）
        return self.stk_out.pop()

    def peek(self) -> int:
        # 如果 stk_out 为空，先调用 move 方法将 stk_in 中的元素倒序到 stk_out
        if not self.stk_out:
            self.move()
        # 返回 stk_out 的栈顶元素（即队列的头部），但不弹出
        return self.stk_out[-1]

    def empty(self) -> bool:
        # 队列为空的条件是：stk_in 和 stk_out 都为空
        return not self.stk_in and not self.stk_out

排序链表

148. 排序链表

题目描述

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

方案：归并排序

用归并排序，这里注意！！！拆分的时候从dummy出发，这样slow会停在前半部分最后一个，有利于均分。我不知道为啥用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
40
41
42
43
44
45
46
47
48
49
50
51
52


class Solution:
    def splitList(self, head):
        """
        将链表分成两半，返回第二个链表的头节点。
        时间复杂度：O(n/2)
        """
        dummy = ListNode(next=head)
        slow, fast = dummy, dummy  # 快慢指针初始化
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        head2 = slow.next  # 第二部分的头节点
        slow.next = None  # 断开链表
        return head, head2

    def mergeList(self, h1, h2):
        """
        合并两个有序链表，返回合并后的头节点。
        时间复杂度：O(n)
        """
        dummy = ListNode()  # 虚拟头节点
        cur = dummy
        while h1 and h2:
            if h1.val < h2.val:
                cur.next = h1
                h1 = h1.next
            else:
                cur.next = h2
                h2 = h2.next
            cur = cur.next
        # 处理剩余节点
        if h1:
            cur.next = h1
        if h2:
            cur.next = h2
        return dummy.next

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """
        对链表进行归并排序。
        时间复杂度：O(n log n)
        """
        # 终止条件：链表为空或只有一个节点
        if not head or not head.next:
            return head
        # 分割链表
        h1, h2 = self.splitList(head)
        # 递归排序
        h1 = self.sortList(h1)
        h2 = self.sortList(h2)
        # 合并两个有序链表
        return self.mergeList(h1, h2)

下一个排列

31. 下一个排列

题目描述

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，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 的下一个排列。

必须原地修改，只允许使用额外常数空间。

方法：就只能背诵和吟唱

先找到从右往左，第一个满足nums[i] < nums[i+1]的
找到了就去从右往左找到第一个满足nums[j] > nums[i]的，他俩交换
把i+1到结尾的全部逆序

 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 nextPermutation(self, nums: List[int]) -> None:
        """
        Modify nums in-place to generate the next lexicographical permutation.
        """
        # Step 1: Find the first index `i` where nums[i] < nums[i + 1]
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        
        # Step 2: If such `i` is found, find the first index `j` where nums[j] > nums[i]
        if i >= 0:
            for j in range(len(nums)-1, -1, -1):
                if nums[i] < nums[j]:
                    nums[i], nums[j] = nums[j], nums[i]
                    break 
        
        # Step 3: Reverse the subarray from i + 1 to the end
        l, r = i + 1, len(nums) - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l, r = l + 1, r - 1

括号生成

22. 括号生成

题目描述

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

方法：DFS

 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


class Solution:
    def __init__(self):
        # 初始化一个空列表，用于存储最终生成的合法括号组合
        self.res = []

    def generateParenthesis(self, n: int) -> List[str]:
        """
        生成所有有效的括号组合。
        
        参数:
        n (int): 括号对数，即每对括号中包含的左括号和右括号的数量。

        返回:
        List[str]: 所有合法的括号组合列表。
        """
        def dfs(path, l, r):
            """
            深度优先搜索（DFS）递归函数，用于生成合法的括号组合。

            参数:
            path (str): 当前生成的括号字符串。
            l (int): 当前已使用的左括号数量。
            r (int): 当前已使用的右括号数量。
            """
            # 基线条件：如果左括号和右括号都用完了，说明找到了一个合法组合，将其加入结果列表
            if l == n and r == n:
                self.res.append(path)
                return

            # 剪枝条件：如果左括号使用数量超过了 n，说明不合法，直接返回
            if l > n:
                return

            # 如果当前左括号数量等于右括号数量，只能添加左括号
            if l == r:
                dfs(path + '(', l + 1, r)

            # 如果当前左括号数量大于右括号数量，可以添加左括号或右括号
            if l > r:
                dfs(path + '(', l + 1, r)  # 选择添加左括号
                dfs(path + ')', l, r + 1)  # 选择添加右括号

        # 从空字符串开始递归，初始左括号和右括号数量

x 的平方根

69. x 的平方根

题目描述

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

方案：二分

 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 mySqrt(self, x: int) -> int:
        """
        计算非负整数 x 的平方根，返回其整数部分。

        参数:
        x (int): 需要计算平方根的非负整数。

        返回:
        int: 平方根的整数部分。
        """
        # 初始化二分查找的左右边界
        l, r = 0, x

        # 在区间 [l, r] 中进行二分查找
        while l < r:
            # 计算中间值 m，注意为了避免死循环，取 (l + r + 1) // 2
            m = (l + r + 1) // 2

            # 如果 m 的平方小于等于 x，说明平方根在 [m, r] 区间内
            if m * m <= x:
                l = m  # 将左边界移动到 m
            else:
                # 否则，平方根在 [l, m - 1] 区间内
                r = m - 1  # 将右边界移动到 m - 1

        # 循环结束时，l == r，即为平方根的整数部分
        return l

滑动窗口最大值

239. 滑动窗口最大值

题目描述

给你一个整数数组 nums，有一个大小为 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """
        使用双端队列（deque）解决滑动窗口最大值问题。

        参数:
        nums (List[int]): 输入数组。
        k (int): 滑动窗口的大小。

        返回:
        List[int]: 每个滑动窗口的最大值组成的列表。
        """
        # 初始化一个双端队列，用于存储窗口内可能成为最大值的元素的索引
        q = deque()
        # 初始化结果列表，用于存储每个窗口的最大值
        res = []

        # 遍历数组中的每一个元素
        for i in range(len(nums)):
            # 维护单调递减队列：如果当前元素比队列尾部元素大，则移除尾部元素
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            
            # 维护窗口大小：如果队列头部元素超出窗口范围，则移除头部元素
            while q and i - q[0] >= k:
                q.popleft()
            
            # 将当前元素的索引加入队列尾部
            q.append(i)
            
            # 当窗口形成时，将队列头部元素对应的值加入结果列表
            if i >= k - 1:
                res.append(nums[q[0]])
        
        # 返回所有窗口最大值组成的列表
        return res

最长有效括号（最难）

题目描述

动态规划，空`O(n)`时`O(n)`

这个思路是这样，dp[i]表示使用当前下标的字符，最长的有效括号子串的长度

当前为(，直接跳
当前为)，前面为(，至少有2，如果前面还有的话直接继承
当前为)，前面为)，前面的)会匹配到长度为dp[i-1]的子串，当前的)匹配的就是下标为i-1-dp[i-1]的是不是(：如果是，至少有2+dp[i-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


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 如果字符串为空，直接返回 0
        if not s:
            return 0

        # 初始化动态规划数组 dp，dp[i] 表示以 s[i] 结尾的最长有效括号子串的长度
        dp = [0] * len(s)

        # 遍历字符串，从第 1 个字符开始
        for i in range(1, len(s)):
            # 如果当前字符是 '(', 则不能形成有效括号，跳过
            if s[i] == '(':
                continue

            # 如果当前字符是 ')' 且前一个字符是 '(', 则形成一对有效括号
            elif s[i - 1] == '(':
                # 以 s[i] 结尾的最长有效括号子串长度为 2，加上 s[i-2] 结尾的长度
                dp[i] = 2 + (dp[i - 2] if i > 1 else 0)

            # 如果当前字符是 ')' 且前一个字符也是 ')'
            # 需要检查是否能形成嵌套的有效括号
            else:
                # 计算可能匹配的左括号的位置 j = i - 1 - dp[i - 1]
                j = i - 1 - dp[i - 1]

                # 如果 j >= 0 且 s[j] == '(', 则匹配成功
                if j >= 0 and s[j] == '(':
                    # 以 s[i] 结尾的最长有效括号子串长度为：
                    # 当前匹配的 2 个字符 + 
                    # 以 s[i - 1] 结尾的长度 + 
                    # 以 s[j - 1] 结尾的长度
                    dp[i] = 2 + dp[i - 1] + (dp[j - 1] if j > 1 else 0)

        # 返回 dp 数组中的最大值，即整个字符串中的最长有效括号子串的长度
        return max(dp)

线性扫描，空`O(1)`时`O(n)`

第一次遍历（从左到右）：
- 使用 val 记录当前括号的平衡情况：
  - 遇到 (，val 加 1。
  - 遇到 )，val 减 1。
- 如果 val == 0，说明从 start 到 i 的子串是有效的，更新结果。
- 如果 val < 0，说明右括号比左括号多，子串无效，重置 start 和 val。
第二次遍历（从右到左）：
- 使用 val 记录当前括号的平衡情况，注意与第一次相反：
  - 遇到 )，val 加 1。
  - 遇到 (，val 减 1。
- 如果 val == 0，说明从 i 到 start 的子串是有效的，更新结果。
- 如果 val < 0，说明左括号比右括号多，子串无效，重置 start 和 val。
返回结果：
- res 保存了最长有效括号子串的长度。

 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


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 初始化结果变量，用于记录最长有效括号子串的长度
        res = 0

        # 第一次遍历：从左到右
        start, val = 0, 0  # start 记录当前有效子串的起始位置，val 记录括号的平衡情况
        for i in range(len(s)):
            # 根据当前字符更新平衡值：
            # 如果是 '(', val 加 1；如果是 ')', val 减 1
            val += int(s[i] == '(') - int(s[i] == ')')

            if val == 0:
                # 如果 val 为 0，说明从 start 到 i 的子串是有效的
                res = max(res, i - start + 1)  # 更新结果
            elif val < 0:
                # 如果 val 小于 0，说明右括号比左括号多，子串无效
                start, val = i + 1, 0  # 重置起始位置和平衡值

        # 第二次遍历：从右到左
        start, val = len(s) - 1, 0  # 重置 start 和 val
        for i in range(len(s) - 1, -1, -1):
            # 根据当前字符更新平衡值：
            # 如果是 ')', val 加 1；如果是 '(', val 减 1
            val += int(s[i] == ')') - int(s[i] == '(')

            if val == 0:
                # 如果 val 为 0，说明从 i 到 start 的子串是有效的
                res = max(res, start - i + 1)  # 更新结果
            elif val < 0:
                # 如果 val 小于 0，说明左括号比右括号多，子串无效
                start, val = i - 1, 0  # 重置起始位置和平衡值

        # 返回最终结果
        return res

栈，空`O(n)`时`O(n)`

栈的作用：
- 栈中存放的是 待匹配的左括号的位置。
- 每次遇到一个右括号时，我们需要从栈中弹出一个左括号的位置来匹配。
匹配的含义：
- 如果成功匹配（栈不为空），说明当前右括号找到了一个对应的左括号。
- 如果匹配失败（栈为空），说明当前右括号没有对应的左括号。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res, start, stack = 0, 0, []
        for i in range(len(s)):
            if s[i] == '(': 
	            # 左括号，入栈
                stack.append(i)
            elif not stack: 
	            # 右括号，未匹配，可能起始要更新
                start = i + 1
            else:
	            # 右括号，匹配，但是我们看匹配了多少
                stack.pop()
                if not stack:
                # 全部左括号均匹配，这里start有效
                    res = max(res, i-start+1)
                else:
                # 部分左括号匹配，栈顶的右侧有效
                    res = max(res, i-stack[-1])
        return res

`else`里面的第一种情况：栈为空

1
2


if not stack:
    res = max(res, i - start + 1)

触发条件
- 遇到一个右括号，并且栈为空（即当前右括号没有对应的左括号）。
- 这种情况表明，从 start 到 i 的子串是一个有效的括号子串。
为什么有效
- 从 start 到 i 的所有括号都被成功匹配了，栈为空表示没有待匹配的左括号。
更新 res
- i - start + 1 是当前有效子串的长度。
- 用 max(res, i - start + 1) 更新 res，确保记录最长的有效子串。
例子：
- 输入 s = "()"：
  - i = 1，栈为空，start = 0，子串长度为 1 - 0 + 1 = 2，res = 2。

`else`里面的第一种情况：栈不为空

1
2


else:
    res = max(res, i - stack[-1])

触发条件：
- 遇到一个右括号，并且栈不为空（即当前右括号有一个对应的左括号）。
为什么有效：
- 当前右括号匹配了栈顶的左括号，但仍然有未匹配的左括号在栈中。
- 这说明，从栈顶位置 + 1 到 i 的子串是一个有效的括号子串。
更新 res：
- i - stack[-1] 是当前有效子串的长度。
- 用 max(res, i - stack[-1]) 更新 res，确保记录最长的有效子串。
例子：
- 输入 s = "(()"：
  - i = 2，栈不为空，栈顶为 0，子串长度为 2 - 0 = 2，res = 2。

缺失的第一个正数

41. 缺失的第一个正数

题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

方法：原地哈希

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)  # 数组的长度

        # 第一步：原地哈希，将数值放到其对应的索引位置
        for i in range(len(nums)):
            # 检查当前数值是否为 1 到 n 的正整数，并且是否未放到正确的位置
            while nums[i] > 0 and nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                # 计算当前数值应该放置的索引位置
                j = nums[i] - 1
                # 交换 nums[i] 和 nums[j]，将数值放到正确的位置
                nums[i], nums[j] = nums[j], nums[i]

        # 第二步：遍历数组，找到第一个不满足 nums[i] == i + 1 的位置，即缺失的最小正整数
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1  # 返回缺失的最小正整数

        # 如果数组中所有位置都满足 nums[i] == i + 1，说明缺失的最小正整数是 n + 1
        return n + 1

最小覆盖子串

76. 最小覆盖子串

二分查找

题目描述

方案：龙龙二分

用栈实现队列

题目描述

方案：二栈模拟

排序链表

题目描述

方案：归并排序

下一个排列

题目描述

方法：就只能背诵和吟唱

括号生成

题目描述

方法：DFS

x 的平方根

题目描述

方案：二分

滑动窗口最大值

题目描述

方法：优先队列

最长有效括号（最难）

题目描述

动态规划，空O(n)时O(n)

线性扫描，空O(1)时O(n)

栈，空O(n)时O(n)

else里面的第一种情况：栈为空

else里面的第一种情况：栈不为空

缺失的第一个正数

题目描述

方法：原地哈希

最小覆盖子串

动态规划，空`O(n)`时`O(n)`

线性扫描，空`O(1)`时`O(n)`

栈，空`O(n)`时`O(n)`

`else`里面的第一种情况：栈为空

`else`里面的第一种情况：栈不为空