从0开始 LeetCode

算法小白一枚，会尽力理解每一道的思路并描述出来，希望能和大家一起进步！

面试经典 150 题

点击题目自动跳转到对应LeetCode题目链接

数组

LeetCode 88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

1
2
3
4
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

1
2
3
4
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

1
2
3
4
5
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

推荐解法：

利用双指针从后向前归并，避免元素移动，实现原地高效合并两个有序数组。

  1. 初始化三个指针：p, q1, q2

  2. 从后向前，选择较大的元素放入 nums1[p]

  3. 处理 nums2剩余元素（如果有）

  4. 原地完成，无需返回

  • 时间复杂度：O(m + n)
  • 空间复杂度：O(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 merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p = m + n - 1          # nums1 的最后一个位置
        q1 = m - 1             # nums1 的最后一个有效元素
        q2 = n - 1             # nums2 的最后一个有效元素

        # 从后往前，依次选择较大的元素放入 nums1[p]
        while q1 >= 0 and q2 >= 0:
            if nums1[q1] >= nums2[q2]:
                nums1[p] = nums1[q1]
                q1 -= 1
            else:
                nums1[p] = nums2[q2]
                q2 -= 1
            p -= 1

        # 如果 nums2 还有剩余元素，直接拷贝到 nums1 前面
        while q2 >= 0:
            nums1[p] = nums2[q2]
            q2 -= 1
            p -= 1

LeetCode 27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

示例 1：

1
2
3
4
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

1
2
3
4
5
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

推荐解法：

  1. 指针定义：

    • slow：指向下一个可以放置非 val 元素的位置
    • fast：遍历整个数组，寻找需要保留的元素

  2. 遍历过程：

    • 使用 fast遍历数组中的每一个元素如果当前元素
    • nums[fast] != val，则将其复制到 nums[slow]，然后 slow++
    • 如果 nums[fast] == val，则跳过该元素

  3. 结果：

    • 遍历结束后，slow即为新数组的长度（不包含 val 的元素个数）
    • 原数组前 slow个元素即为处理后的结果（顺序可能改变，但符合题意）
  • 时间复杂度：O(n)，只需遍历一次数组
  • 空间复杂度：O(1)，原地修改，仅使用常数额外空间
1
2
3
4
5
6
7
8
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow

LeetCode 26. 删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k。去重后，返回唯一元素的数量 k。

nums 的前 k 个元素应包含 排序后 的唯一数字。下标 k - 1 之后的剩余元素可以忽略。

示例 1：

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4,_,_,_,_,_]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

推荐解法：

  1. 初始化慢指针 slow = 0

  2. 快指针 fast从 1遍历到 len(nums) - 1

  3. 比较 nums[slow]与 nums[fast]：

    • 若不相等，说明找到了新元素，将 slow前移并更新 nums[slow] = nums[fast]

  4. 遍历结束后，返回 slow + 1作为新数组长度

  • 时间复杂度：O(n)，数组只遍历一次
  • 空间复杂度：O(1)，只用了常数级别的额外空间
1
2
3
4
5
6
7
8
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0
        for fast in range(1,len(nums)):
            if nums[slow] != nums[fast]:
                slow += 1
                nums[slow] = nums[fast]
        return slow + 1

LeetCode 80. 删除有序数组中的重复项 ||

给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：

1
2
3
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

笨比解法：

1
2
3
4
5
6
7
8
9
10
11
# 我的写法是判断快指针当前位置的元素，是否和慢指针当前以及当前-1的元素是否相等
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 1
        for fast in range(2,len(nums)):
            if nums[fast] == nums[slow] and nums[fast] == nums[slow - 1]:
                pass
            else:
                slow += 1
                nums[slow] = nums[fast]
        return slow + 1

推荐解法：

  1. 若数组长度 ≤ 2，直接返回 len(nums)
  2. 初始化 slow = 2
  3. 遍历 fast从 2 到末尾：若 nums[fast] != nums[slow - 2]，则保留该元素：nums[slow] = nums[fast]，slow += 1
  4. 返回 slow作为新数组长度
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 最优官方解法为
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) <= 2:
            return len(nums)

        slow = 2
        for fast in range(2, len(nums)):
            #我的理解是 slow 为下一个要修改的index，index-2 去判断是否连续三个数值相同
            #例如当前 fast 为2，那么会去对比 slow-2 也就是 index 为0的元素
            #数组是按照升序排列的，如果fast与slow-2相等，则代表这三个索引元素相同
            if nums[fast] != nums[slow - 2]:
                nums[slow] = nums[fast]
                slow += 1
        return slow

LeetCode 169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

1
2
输入：nums = [3,2,3]
输出：3

示例 2：

1
2
输入：nums = [2,2,1,1,1,2,2]
输出：2

推荐解法：

使用 Boyer-Moore 投票算法，通过抵消思想在线性时间内找出出现次数超过半数的多数元素，无需额外空间

  1. 初始化 count = 0, candidate = 0
  2. 遍历每个元素：若 count == 0，选当前元素为候选，若当前元素 == 候选，count + 1，否则count - 1
  3. 最终 candidate即为所求
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = 0
        for num in nums:
            if count == 0:
                candidate = num
                count += 1
            elif candidate == num:
                count += 1
            else:
                count -= 1
        return candidate
# 想起一道有点像的题目：求当前直播间在线人数 进来一个 +1 退出一个 -1 
# 这里多了候选人的概念，票数归零换候选人，多一个相同元素就投一票

LeetCode 189. 轮转数组

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

示例 1:

1
2
3
4
5
6
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

1
2
3
4
5
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

笨比解法：

1
2
3
4
5
6
7
8
9
# 我只想到了辅助数组法，显然效率低
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n  # 防止 k 超过数组长度
        nums_copy = nums.copy()  # 辅助数组
        
        for i in range(n):
            nums[(i + k) % n] = nums_copy[i]

推荐解法：

  1. 计算实际需要轮转的步数：k %= n（防止 k 大于数组长度）

  2. 反转整个数组 nums

  3. 反转前 k个元素

  4. 反转后 n - k个元素

  • 时间复杂度：O(n)（每个元素被访问常数次）

  • 空间复杂度：O(1)（原地修改，最优）

Step 1：反转整个数组

  • 把整个数组的元素顺序颠倒过来
  • 原数组：[1, 2, 3, 4, 5, 6, 7]→ 反转后：[7, 6, 5, 4, 3, 2, 1]

Step 2：反转前 k 个元素

  • 我们希望前 k 个元素（原来是后 k 个）恢复原来的顺序
  • 比如 k = 3，我们反转前 3 个：[7, 6, 5]→ [5, 6, 7]

Step 3：反转后 n - k 个元素

  • 剩下的后 n - k 个元素（原来是前 n - k 个）也要恢复原来的顺序
  • 比如后 4 个：[4, 3, 2, 1]→ [1, 2, 3, 4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 最优解法代码（数组翻转法）
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n  # 防止k超过数组长度
        
        # 定义一个辅助翻转函数
        def reverse(start: int, end: int):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
        
        # 三次翻转
        reverse(0, n - 1)      # 第一步：反转整个数组
        reverse(0, k - 1)      # 第二步：反转前k个元素
        reverse(k, n - 1)      # 第三步：反转后n-k个元素
#循环左移与循环右移原理相同，只是最后三次翻转略有区别

LeetCode 121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

笨比解法：

1
2
3
4
5
6
7
8
9
# 楼主的笨蛋暴力算法，双循环
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        for i in range(len(prices)):
            for j in range(i + 1, len(prices)):
                profit = prices[j] - prices[i]
                max_profit = profit if max_profit < profit else max_profit
        return max_profit

推荐解法：

  1. min_price：记录遍历至今的最低价格（可能是最佳买入点）
  2. max_profit：记录当前的最大利润
  3. 遍历每一天的价格：用 min()动态更新最低价格计算当前利润：当前价格 - 最低价格用 max()动态更新最大利润
  • 时间复杂度：O(n)（只需遍历一次数组）
  • 空间复杂度：O(1)（只用了常数个额外变量）
1
2
3
4
5
6
7
8
9
10
11
# 最优解法
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        min_price = prices[0]
        max_profit = 0
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)
        return max_profit

LeetCode 122. 买卖股票的最佳时机 ||

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股。

返回 你能获得的 最大 利润 。

示例 1：

1
2
3
4
5
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2：

1
2
3
4
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

示例 3：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

推荐解法：

  1. 初始化总利润 total = 0

  2. 遍历 i从 0到 len(prices) - 2：如果 prices[i] < prices[i + 1]，则 total += prices[i + 1] - prices[i]

  3. 返回 total

  • 时间复杂度：O(n)，只需遍历一次数组
  • 空间复杂度：O(1)，只用了常数个变量
1
2
3
4
5
6
7
8
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        total = 0
        for i in range(len(prices) - 1):
            # 只要第二天的价格高于今天就买入，否则跳过
            if prices[i] < prices[i + 1]:
                total += prices[i + 1] - prices[i]
        return total

LeetCode 55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

笨比解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 我只能想到通过判断下一步还能不能走
# 看个乐子就好，还是得学习正规的贪心解法
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        step = nums[0]
        # 如果初始为0，并且数组长度大于1直接返回False
        if step == 0 and len(nums) > 1:
            return False
        # 如果数组只有一个元素，直接返回True
        if len(nums) == 1:
            return True
        
        for i in range(1,len(nums) - 1):
            step -= 1
            if step < nums[i] and step >= 0:
                step = nums[i]
        if step > 0:
            return True
        else:
            return False

推荐解法：

在遍历数组的过程中，动态维护一个变量 max_reach，表示当前能到达的最远下标。

只要这个最远下标能够覆盖到最后一个位置（即 max_reach >= len(nums) - 1），就说明可以到达终点。

  1. 初始化 max_reach = 0，表示当前能跳到的最远下标

  2. 遍历数组中的每一个位置 i：如果 i > max_reach，说明当前位置已经跳不到了 → 返回 False用 i + nums[i]计算从当前位置最多能跳到哪里，并更新 max_reach = max(max_reach, i + nums[i])如果 max_reach >= len(nums) - 1，说明可以到达或超过终点 → 返回 True

  3. 如果遍历结束都没有返回，说明也能到达终点 → 返回 True

  • 时间复杂度 O(n) ， 只遍历一次数组
  • 空间复杂度O(1)， 只用了常数级别的额外变量（max_reach）
1
2
3
4
5
6
7
8
9
10
11
12
# 贪心算法
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0          # 当前能到达的最远下标
        n = len(nums)          # 数组的长度
        for i in range(n):     # 遍历每一个位置 i
            if i > max_reach:  # 如果当前位置已经超过了能到达的最远位置
                return False   # 说明跳不到这里，更到不了终点
            max_reach = max(max_reach, i + nums[i])  # 更新能到达的最远位置
            if max_reach >= n - 1:  # 如果最远位置已经可以到达或超过终点
                return True         # 直接返回 True
        return True  # 正常结束循环，说明可以到达终点

🎯 示例：nums = [2, 3, 1, 1, 4]，目标：判断是否能跳到最后一个下标 4

  • n = 5，最后一个下标是 4

我们一步步走：

i nums[i] i + nums[i] max_reach (更新前/后) 说明
0 2 0 + 2 = 2 0 → 2 初始 max_reach = 0，现在能跳到 2
1 3 1 + 3 = 4 2 → 4 当前位置 1 可到达，最多跳到 4，更新 max_reach = 4
注意：此时 4 >= 4（最后一个下标），所以直接 return True ✅

→ 所以这个例子返回 True，正确 ✅

❌ 示例：nums = [3, 2, 1, 0, 4]

  • n = 5，目标是到达下标 4
i nums[i] i + nums[i] max_reach (更新前/后) 说明
0 3 0 + 3 = 3 0 → 3 初始能跳到 3
1 2 1 + 2 = 3 3 → 3 当前最远还是 3
2 1 2 + 1 = 3 3 → 3 还是 3
3 0 3 + 0 = 3 3 → 3 位置 3 的 nums[i]=0，还是只能到 3
4 4 4 + 4 = 8 但 i=4 > max_reach=3 → 触发 if i > max_reach → return False ❌

→ 所以这个例子返回 False，正确 ❌

LeetCode 45. 跳跃游戏 ||

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

  • 0 <= j <= nums[i] 且
  • i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

1
2
输入: nums = [2,3,0,1,4]
输出: 2

推荐解法：

在遍历数组的过程中，维护几个关键变量，来记录当前跳跃能覆盖的范围，以及何时需要进行下一次跳跃，从而确保用最少的跳跃次数覆盖到终点。

  1. 初始化：

    • jumps = 0：跳跃次数
    • current_end = 0：当前这跳能跳到的最远位置
    • farthest = 0：遍历过程中能到达的最远位置

  2. 遍历数组的每一个位置 i（注意：我们不遍历最后一个位置，因为一旦到达或超过它，就不需要再跳了）：

    • farthest = max(farthest, i + nums[i])：计算从当前位置 i 最多能跳到哪里，更新最远可达位置
    • 如果 i == current_end，说明我们已经到达了当前这跳的边界，必须再跳一次：
      • jumps += 1：跳跃次数 +1
      • current_end = farthest：更新下一跳的边界为当前能跳到的最远位置
      • 如果此时 current_end >= 最后一个下标，其实已经可以提前结束

  3. 遍历结束后，返回 jumps

时间复杂度 O(n) —— 只遍历一次数组（最多到 n-1）
空间复杂度 O(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:
        jumps = 0
        current_end = 0
        farthest = 0
        n = len(nums)
        
        # 注意：我们不遍历最后一个位置，因为到达那里就已经成功了
        for i in range(n - 1):
            farthest = max(farthest, i + nums[i])  # 当前能跳到的最远位置
            if i == current_end:  # 到达当前这跳的边界，必须跳了
                jumps += 1
                current_end = farthest  # 更新下一跳的边界
                if current_end >= n - 1:
                    break  # 如果已经可以到达或超过终点，提前结束
        return jumps

LeetCode 27. H 指数

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

示例 1：

1
2
3
4
输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

示例 2：

1
2
输入：citations = [1,3,1]
输出：1

笨比解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 楼主的笨比方法
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        if len(citations) == 1:
            if citations[0] == 0:
                return 0
            if citations[0] >= 1:
                return 1
        for i in range(len(citations)):
            count = 0
            for j in range(len(citations)):
                if citations[j] >= n:
                    count += 1
            if count >= n:
                return n
            n -= 1
        if n <= 0:
            return 0

推荐解法：排序 + 遍历

  1. 先对引用次数数组进行降序排序

  2. 然后从前往后遍历，寻找最大的 h 满足：

    • 第 i 篇（从 0 开始）的引用次数 citations[i] >= i + 1
    • i + 1 表示当前是第几篇论文，因为下标从 0 开始

  3. 最大的满足条件的 i + 1就是 H 指数

时间复杂度 O(n log n) —— 主要是排序的时间复杂度
空间复杂度 O(1) 或 O(n)（取决于排序的实现，Python 的 sort() 通常是 Timsort，额外空间较小） 
1
2
3
4
5
6
7
8
9
10
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort(reverse=True)  # 降序排序
        h = 0
        for i in range(len(citations)):
            if citations[i] >= i + 1:  # 当前这篇的引用 >= 当前是第几篇
                h = i + 1
            else:
                break
        return h

推荐解法：计数排序 + 从后统计

  1. 统计引用次数出现的频率

    • 因为引用次数可能很大（比如 1000），但我们最多有 n 篇论文，所以 h 最大为 n

    • 我们可以定义一个大小为 n + 1的数组 count，其中：

      • count[i]表示 引用次数为 i 的论文有几篇

      • 特别地，引用次数超过 n 的，我们统统记在 count[n] 中（因为超过 n 的引用对 h 的贡献都是“至少有 n 篇引用 >= n”）

  2. 从高引用往低引用累加论文总数

    • 从 i = n开始往 0 遍历：
      • 累加论文数量：total += count[i]
      • 如果 total >= i，说明有至少 i 篇论文的引用 >= i，此时 i 就是 H 指数，返回 i

  3. 如果一直没有返回，返回 0（不过题目一般保证有解）

时间复杂度 O(n) —— 遍历 citations 一次，遍历 count 数组一次（最多 n+1 次）
空间复杂度 O(n) —— 我们用了一个大小为 n+1 的数组 count 来统计
索引 i（引用次数） count[i] = 该引用出现的论文篇数 含义解释
0 1 有 1 篇论文引用 0 次
1 1 有 1 篇论文引用 1 次
2 0 没有论文引用 2 次
3 1 有 1 篇论文引用 3 次
4 0 没有论文引用 4 次
5 2 有 2 篇论文引用 >= 5 次（分别是 6 和 5） 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        count = [0] * (n + 1)  # count[i] 表示引用次数为 i 的论文数量

        # 统计每个引用出现的次数，超过n的记为n
        for c in citations:
            if c >= n:
                count[n] += 1
            else:
                count[c] += 1

        total = 0
        # 从高引用往低引用遍历
        for i in range(n, -1, -1):
            total += count[i]  # 累加当前引用及更高引用的总论文数
            if total >= i:     # 如果累计篇数 >= 当前引用次数 i
                return i       # i 就是 H 指数
        return 0

LeetCode 380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

  • RandomizedSet() 初始化 RandomizedSet 对象
  • bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
  • bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
  • int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

推荐解法：哈希表 + 动态数组

  1. insert(val)：

    • 如果 val 不存在 → 插入到数组末尾，并记录其索引到哈希表 → 返回 True
    • 如果 val 已存在 → 啥也不做 → 返回 False

  2. remove(val)：

    • 如果 val 不存在 → 返回 False

    • 如果 val 存在：

      • 找到该值在数组中的索引 idx
      • 把数组最后一个元素 last_val 移动到 idx 的位置（覆盖要删除的元素）
      • 更新哈希表中 last_val 的索引为 idx
      • 删除数组最后一个元素（pop）
      • 从哈希表中删除 val返回 True
      • 🎯 核心技巧：通过 “交换最后一个元素” 来实现 O(1) 的删除，避免移动数组元素

  3. getRandom()：

    • 从数组中随机选择一个索引，返回对应元素使用
    • random.choice(self.nums)或 random.randint实现
insert(val) O(1) 列表追加 + 哈希表插入
remove(val) O(1) 哈希表查找 + 数组末尾元素覆盖 + pop()
getRandom() O(1) 列表随机访问（random.choice 
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
class RandomizedSet:

    def __init__(self):
        self.nums = []             # 列表，存储元素，用于 getRandom
        self.val_to_index = {}     # 哈希表：val -> 在 nums 中的索引

    def insert(self, val: int) -> bool:
        if val in self.val_to_index:
            return False
        self.nums.append(val)
        self.val_to_index[val] = len(self.nums) - 1
        return True

    def remove(self, val: int) -> bool:
        if val not in self.val_to_index:
            return False
        idx = self.val_to_index[val]
        last_value = self.nums[-1]
        
        # 用最后一个元素覆盖要删除的位置
        self.nums[idx] = last_value
        
        # 关键！更新该值的索引为 idx
        self.val_to_index[last_value] = idx
        
        # 删除最后一个元素
        self.nums.pop()
        del self.val_to_index[val]
        
        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)

LeetCode 238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。

示例 1:

1
2
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

1
2
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

推荐解法：前后缀积

步骤 1：计算每个元素左边所有数的乘积

  • 初始化一个变量 left_product = 1
  • 遍历数组，对于每个 i：
    • 先把 left_product存入 answer[i]（表示当前元素左边的乘积）
    • 然后更新 left_product *= nums[i]（为下一个元素累乘）

→ 这样一遍下来，answer[i]中存的是 nums[0] * ... * nums[i-1]

步骤 2：计算每个元素右边所有数的乘积，并乘到 answer[i] 上

  • 初始化一个变量 right_product = 1
  • 从右向左遍历数组，对于每个 i：
    • 把 right_product乘到 answer[i]上（表示当前元素右边的乘积）
    • 然后更新 right_product *= nums[i]（为下一个元素累乘）

→ 最终，answer[i] = (左边所有数乘积) × (右边所有数乘积)

时间复杂度 O(n) —— 两次遍历数组，一次从左到右，一次从右到左
空间复杂度 O(1)（不考虑返回数组的空间） —— 只用了常数个额外变量 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n

        # 从左到右，计算每个元素左边所有数的乘积
        left_product = 1
        for i in range(n):
            answer[i] = left_product
            left_product *= nums[i]

        # 从右到左，计算每个元素右边所有数的乘积，并乘到 answer[i] 上
        right_product = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right_product
            right_product *= nums[i]

        return answer

LeetCode 134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

1
2
3
4
5
6
7
8
9
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

笨比解法：

注：此代码无法通过测试用例，超过了时间限制。楼主只能想到的最笨的暴力双循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        length = len(gas)
        for i in range(length):
            gas_total = 0
            for j in range(length):
                gas_total += gas[(i + j) % length]
                # 判断当前汽油是否大于消耗,大于则 break
                if gas_total < cost[(i + j) % length]:
                    break
                # 用目前总汽油减去本站要消耗的汽油    
                gas_total -= cost[(i + j) % length]
            # 如果一直没有发生 break 则返回此站点
            else:
                return i
        return -1

推荐解法：贪心算法

我们尝试从第 0 个加油站开始，模拟行驶并累计油量：

  • 用 current_gas表示当前剩余油量
  • 用 start表示当前尝试的起点

遍历每个站点 i：

  1. 累加当前获得的油 - 消耗的油：

    1
    current_gas += gas[i] - cost[i]

  2. 如果 current_gas < 0，说明从当前 start出发走不到 i+1，因此：放弃这个起点 start将起点设为下一个站 i+1重置 current_gas = 0（重新开始累计）

遍历结束后：

  • 如果总油量够（total_gas >= total_cost），则 最后一个尝试的 start 就是答案

  • 如果总油量不够，直接返回 -1

时间复杂度 O(n)，我们只遍历了一次加油站数组
空间复杂度 O(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 canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        total_gas = 0
        total_cost = 0
        current_gas = 0
        start = 0

        for i in range(n):
            total_gas += gas[i]
            total_cost += cost[i]
            current_gas += gas[i] - cost[i]

            # 如果当前累计油量 < 0，说明从 start 出发走不到 i+1
            if current_gas < 0:
                start = i + 1          # 将起点设为下一个站
                current_gas = 0        # 重新累计油量

        # 如果总油量 >= 总消耗，说明一定有解，返回 start
        # 否则返回 -1
        return start if total_gas >= total_cost else -1

LeetCode 135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子中，评分更高的那个会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

1
2
3
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

1
2
3
4
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

推荐解法：双向遍历 + 贪心

为了满足题目中“相邻孩子中，评分高的必须获得更多糖果”的要求，我们需要考虑两个方向：

  1. 从左到右遍历：保证每个孩子，如果他比左边的孩子评分高，则糖果比左边多 1；
  2. 从右到左遍历：保证每个孩子，如果他比右边的孩子评分高，则糖果比右边多 1；

最终，每个孩子的糖果数取这两种情况的最大值，就能同时满足左右两边的约束，而且总糖果数最小。

时间复杂度 O(n) —— 两次遍历数组，一次从左到右，一次从右到左
空间复杂度 O(n) —— 用了一个 candies 数组，存储每个孩子的糖果数 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n  # 每人至少一个糖果

        # 从左到右遍历，保证比左边评分高的孩子糖果更多
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        # 从右到左遍历，保证比右边评分高的孩子糖果更多
        total = candies[-1]  # 先把最后一个糖果计入总数
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                if candies[i] <= candies[i + 1]:
                    candies[i] = candies[i + 1] + 1
            total += candies[i]

        return total

LeetCode 42. 接雨水

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

示例 1：

接雨水

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

推荐解法：动态规划

  1. 预处理：从左到右遍历一遍，记录每个位置 i 的 左边最大值，存入数组 left_max从右到左遍历一遍，记录每个位置 i 的 右边最大值，存入数组 right_max

  2. 计算雨水：

    • 遍历每个位置 i，计算：

      1
      water = min(left_max[i], right_max[i]) - height[i]

    • 如果 water > 0，就累加到总雨水量中

时间复杂度 O(n) —— 三次遍历数组，每次 O(n)
空间复杂度 O(n) —— 用了两个辅助数组：left_max 和 right_max 
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 trap(self, height: List[int]) -> int:
        if not height:
            return 0

        n = len(height)
        left_max = [0] * n
        right_max = [0] * n

        # 从左到右计算每个位置的左边最大值
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])

        # 从右到左计算每个位置的右边最大值
        right_max[-1] = height[-1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        # 计算总雨水量
        total = 0
        for i in range(n):
            water = min(left_max[i], right_max[i]) - height[i]
            if water > 0:
                total += water

        return total

优雅解法：双指针

  1. 定义两个指针：left从数组最左边开始（索引 0）right从数组最右边开始（索引 n-1）

  2. 维护两个变量：left_max：表示 left指针左侧（包括自己）的最高柱子高度right_max：表示 right指针右侧（包括自己）的最高柱子高度

  3. 移动策略：比较 left_max和 right_max：如果 left_max < right_max：说明 左边的限制更小（短板），可以确定 left位置的积水，然后移动 left++否则：说明 右边的限制更小（短板），可以确定 right位置的积水，然后移动 right--

  4. 积水计算：对于当前指针位置，积水高度为：min(left_max, right_max) - height[i]如果 > 0，就累加到总雨水量中

时间复杂度 O(n) —— 只遍历了一次数组，左右指针相遇结束
空间复杂度 O(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 trap(self, height: List[int]) -> int:
        if not height:
            return 0

        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        total = 0

        while left < right:
            if left_max < right_max:
                # 左边是短板，处理 left 位置
                left += 1
                left_max = max(left_max, height[left])
                total += left_max - height[left]
            else:
                # 右边是短板，处理 right 位置
                right -= 1
                right_max = max(right_max, height[right])
                total += right_max - height[right]

        return total

LeetCode 13. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

笨比解法：

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
class Solution:
    def romanToInt(self, s: str) -> int:
        roman_to_int = {'I' : 1, 'V' : 5,'X' : 10,'L' : 50,'C' : 100,'D' : 500,'M' : 1000}

        stack = []
        for item in s:
            stack.append(item)

        popped_item = stack.pop()
        total = roman_to_int[popped_item]
        while stack:
            current_pop = stack.pop()
            if current_pop == 'I':
                if popped_item == 'V' or popped_item == 'X':
                    total -= 1
                else:
                    total += 1
            elif current_pop == 'X':
                if popped_item == 'L' or popped_item == 'C':
                    total -= 10
                else:
                    total += 10
            elif current_pop == 'C':
                if popped_item == 'D' or popped_item == 'M':
                    total -= 100
                else:
                    total += 100
            else:
                total += roman_to_int[current_pop]
            popped_item = current_pop
        return total

推荐解法：

  1. 建立罗马字符到整数的映射表

  2. 从左往右扫描字符串：如果当前字符比下一个字符小，则减去当前值否则累加当前值

时间复杂度 O(n) —— 遍历一次字符串
空间复杂度 O(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 romanToInt(self, s: str) -> int:
        roman = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        total = 0
        n = len(s)
        for i in range(n):
            val = roman[s[i]]
            # 如果当前字符不是最后一个，且当前值 < 下一个值，则减去当前值
            if i < n - 1 and val < roman[s[i + 1]]:
                total -= val
            else:
                total += val
        return total

LeetCode 12. 整数转罗马数字

七个不同的符号代表罗马数字，其值如下：

符号 值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

  • 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
  • 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
  • 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。

给定一个整数，将其转换为罗马数字。

示例 1：

输入： num = 3749

输出： “MMMDCCXLIX”

解释：

1
2
3
4
5
3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC 由于 500 (D) + 100 (C) + 100 (C)
  40 = XL 由于 50 (L) 减 10 (X)
   9 = IX 由于 10 (X) 减 1 (I)
注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位

示例 2：

输入： num = 58

输出：“LVIII”

解释：

1
2
50 = L
 8 = VIII

示例 3：

输入： num = 1994

输出：“MCMXCIV”

解释：

1
2
3
4
1000 = M
 900 = CM
  90 = XC
   4 = IV

推荐解法：贪心算法 + 硬编码映射

思路：

将所有可能的罗马数字符号及其对应的数值按照从大到小的顺序存储，然后贪心地每次尽可能选取最大的那个符号，减去对应数值，直到数字变为 0。

步骤：

  1. 定义一个列表 val_sym，其中每个元素是一个元组 (数值, 符号)，按数值从大到小排序。
  2. 初始化结果字符串 res = ‘’。
  3. 遍历 val_sym 中的每个 (value, symbol)：当 num >= value 时，将 symbol 添加到 res，并减去 value；重复直到 num < value，再处理下一个较小的符号。
  4. 最终返回 res。
时间复杂度 O(1) —— 因为 val_sym 是固定 13 项，num 最大为 3999，循环次数非常有限，可视为常数时间
空间复杂度 O(1) —— 使用固定大小的映射表，输出字符串长度最多为 15，也是常数空间 
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 intToRoman(self, num: int) -> str:
        # 定义数值与罗马数字的对应关系，按从大到小排序
        val_sym = [
            (1000, 'M'),  # 1000 → M
            (900, 'CM'),  # 900 → CM
            (500, 'D'),   # 500 → D
            (400, 'CD'),  # 400 → CD
            (100, 'C'),   # 100 → C
            (90, 'XC'),   # 90 → XC
            (50, 'L'),    # 50 → L
            (40, 'XL'),   # 40 → XL
            (10, 'X'),    # 10 → X
            (9, 'IX'),    # 9 → IX
            (5, 'V'),     # 5 → V
            (4, 'IV'),    # 4 → IV
            (1, 'I')      # 1 → I
        ]

        res = ''  # 结果字符串
        for value, symbol in val_sym:
            # 当 num >= 当前值时，不断累加对应符号
            while num >= value:
                res += symbol  # 添加罗马符号
                num -= value   # 减去对应数值
            # 如果 num 已经减到 0，提前退出循环
            if num == 0:
                break
        return res

LeetCode 58. 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

1
2
3
输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为 5。

示例 2：

1
2
3
输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为 4。

示例 3：

1
2
3
输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。

笨比解法：字符串反转 + 遍历

将字符串反转，这样原字符串末尾的最后一个单词就位于新字符串的开头。然后从新字符串开头开始遍历，跳过开头的空格，统计第一个连续非空格字符序列的长度。

时间复杂度 O(n)
空间复杂度 O(n) —— 因为生成了反转字符串 
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s = s[::-1]  # 反转字符串
        total = 0
        for i in range(len(s)):
            if total == 0 and s[i] == ' ':
                continue  # 跳过开头的空格
            elif total != 0 and s[i] == ' ':
                break  # 遇到空格，说明单词结束
            total += 1
        return total

推荐解法：

从字符串末尾开始，先跳过所有末尾空格，找到最后一个单词的结尾，然后向前统计该单词的字符个数，直到遇到空格或字符串开头。

时间复杂度 O(n) —— 最多遍历整个字符串
空间复杂度 O(1) —— 常数空间 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        length = 0
        i = len(s) - 1  # 从末尾开始

        # 跳过末尾的空格
        while i >= 0 and s[i] == ' ':
            i -= 1

        # 统计最后一个单词的长度
        while i >= 0 and s[i] != ' ':
            length += 1
            i -= 1

        return length

LeetCode 14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

1
2
3
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

推荐解法：横向扫描

我们要在多个字符串中找它们共有的最长的前缀，也就是从第一个字符开始，判断所有字符串的对应位置是否都一样，一直到出现不一样的字符或某个字符串结束为止。

具体步骤：

  1. 特殊情况处理：如果输入数组为空，直接返回 ""。
  2. 以第一个字符串作为初始的公共前缀（prefix）。
  3. 遍历其余的每一个字符串，和当前的 prefix进行逐字符比较，找出它们共有的最长前缀部分。
  4. 不断缩短 prefix，直到它成为所有已遍历字符串的公共前缀。
  5. 如果在某次比较中 prefix 变为空字符串，说明已经没有公共前缀，可以直接返回 ""。
  6. 遍历完所有字符串后，返回最终的 prefix。

这是一种直观的 “横向扫描”（Horizontal Scanning） 方法，易于理解和实现

时间复杂度 O(S)，其中 S 是所有字符串中字符的总数。最坏情况下，所有字符串都会被比较到最短长度。
空间复杂度 O(1)，只使用了常数级别的额外空间（如 prefix, i 等变量）。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        
        # 初始公共前缀设为第一个字符串
        prefix = strs[0]
        
        for s in strs[1:]:  # 从第二个字符串开始比较
            i = 0
            # 逐字符比较，直到字符不同 或 某个字符串结束
            while i < len(prefix) and i < len(s) and prefix[i] == s[i]:
                i += 1
            # 更新公共前缀为共同的部分
            prefix = prefix[:i]
            # 如果已经没有公共前缀，提前结束
            if not prefix:
                break
        
        return prefix

LeetCode 151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
2
3
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

推荐解法:

利用 Python 内置函数：

  1. 使用 s.strip()去掉首尾空格

  2. 使用 s.split()按空格分割单词（自动处理多个空格）

  3. 使用 [::-1]将单词列表倒序

  4. 使用 ' '.join(...)拼接为最终字符串

时间复杂度 O(n) split()、reverse()、join() 都是线性时间
空间复杂度 O(n) 需要存储所有单词的列表 
1
2
3
class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(s.strip().split()[::-1])

LeetCode 6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

1
string convert(string s, int numRows);

示例 1：

1
2
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

1
2
3
4
5
6
7
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

1
2
输入：s = "A", numRows = 1
输出："A"

推荐解法：

  • rows是一个字符串列表，rows[i]存放第 i 行的字符。

  • 我们遍历原字符串的每个字符，决定它属于哪一行：初始在第 0 行，方向向下 (going_down = False，我们用 not来切换方向，你也可以用布尔值 True/False直接表示方向)。当到达第 0 行或第 numRows-1行时，就改变方向。根据当前方向，更新 current_row += 1（向下）或 current_row -= 1（向上）。

  • 最后，将每一行的字符串拼接起来返回。

时间复杂度 O(n) 遍历字符串的每个字符一次
空间复杂度 O(n) 需要存储每一行的字符，最坏情况下接近 n 个字符 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s  # 只有一行，或行数大于等于字符串长度，直接返回原字符串

        # 初始化每一行字符串的列表
        rows = [''] * numRows
        current_row = 0
        going_down = False  # 初始方向，之后根据边界翻转

        for char in s:
            rows[current_row] += char  # 将当前字符添加到对应行
            # 如果在第一行或最后一行，改变方向
            if current_row == 0 or current_row == numRows - 1:
                going_down = not going_down
            # 根据方向更新当前行
            current_row += 1 if going_down else -1

        # 将每一行拼接起来
        return ''.join(rows)

LeetCode 28. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

1
2
3
4
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

1
2
3
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

推荐解法：暴力匹配

  1. 遍历 haystack，尝试从索引 i开始，取长度为 len(needle)的子串。

  2. 如果当前子串与 needle完全相等，则返回当前索引 i。

  3. 如果遍历完所有可能的起始位置（i最多到 len(haystack) - len(needle)）都没有找到匹配，则返回 -1。

时间复杂度 O((n - m + 1) × m) ≈ O(n×m) 最坏情况 最坏情况下，比如 haystack = "aaaaa", needle = "aaab"，需要比较很多次
空间复杂度 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
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(haystack)
        m = len(needle)
        
        # 如果 needle 为空字符串，按题意通常返回 0，但题目中 needle 长度 >=1
        # 如果 needle 比 haystack 还长，肯定匹配不到
        if m == 0:
            return 0
        if m > n:
            return -1

        # 枚举 haystack 中的每个起始位置 i
        for i in range(n - m + 1):
            # 检查从 i 开始，长度为 m 的子串是否等于 needle
            if haystack[i:i + m] == needle:
                return i
        
        return -1
    
    	# 下面为楼主写的
        # haystack_len = len(haystack)
        # needle_len = len(needle)

        # for i in range(haystack_len - needle_len + 1):
        #     if haystack[i] == needle[0]: 
        #         if haystack[i:i + needle_len] == needle:
        #             return i
        # return -1

优雅解法：KMP 算法

步骤 1：构建 next 数组（⏳重点！）

next[i] 表示：needle[0:i] 这个子串中，最长相等的前缀和后缀的长度（不包括自身，即真前缀/真后缀）

比如 needle = “ababc”，对于子串 “aba”（即前三个字符）：

  • 前缀有：[“a”, “ab”, “aba”]
  • 后缀有：[“a”, “ba”, “aba”]
  • 最长相等的前缀和后缀是 “a” 和 “a” → 长度为 1，所以 next[2] = 1

构建方法（使用双指针）：

  1. 定义两个指针：j：前缀末尾指针（也表示当前匹配的前缀长度）i：后缀末尾指针，从 1 开始遍历 needle
  2. 初始化 next[0] = 0，因为单个字符没有真前缀/后缀
  3. 遍历 needle，i 从 1 到 m-1：如果 needle[i] == needle[j]，则 j += 1，next[i] = j，i += 1如果不相等：若 j > 0，则 j = next[j - 1]（回退）若 j == 0，则 next[i] = 0，i += 1

步骤 2：使用 next 数组进行匹配

  1. 使用两个指针：i：遍历 haystackj：遍历 needle

  2. 遍历 haystack 的每个字符：如果 haystack[i] == needle[j]，则 i 和 j 同时向后移动如果不相等：若 j > 0，则 j = next[j - 1]（利用 next 数组跳过已匹配部分）若 j == 0，则 i += 1（从头开始匹配）

  3. 如果 j == m，说明找到了完整匹配，返回起始位置 i - j

  4. 如果遍历完都未找到，返回 -1

时间复杂度 O(n + m) 构建 next 数组 O(m)，匹配过程 O(n)
空间复杂度 O(m) 需要额外的 next 数组，长度为 m 
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 strStr(self, haystack: str, needle: str) -> int:
        n = len(haystack)
        m = len(needle)
        
        if m == 0:
            return 0
        if m > n:
            return -1

        # Step 1：构建 next 数组
        next = [0] * m
        j = 0
        for i in range(1, m):
            # 不匹配时，回退 j
            while j > 0 and needle[i] != needle[j]:
                j = next[j - 1]
            # 匹配时，j 增加
            if needle[i] == needle[j]:
                j += 1
            next[i] = j

        # Step 2：使用 next 数组进行匹配
        j = 0
        for i in range(n):
            # 不匹配时，利用 next 数组回退
            while j > 0 and haystack[i] != needle[j]:
                j = next[j - 1]
            # 匹配时，j 增加
            if haystack[i] == needle[j]:
                j += 1
            # 找到一个完整匹配
            if j == m:
                return i - m + 1  # 起始索引 = i - (m - 1)
        
        return -1  # 未找到

LeetCode 68. 文本左右对齐

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意:

  • 单词是指由非空格字符组成的字符序列。
  • 每个单词的长度大于 0，小于等于 maxWidth。
  • 输入单词数组 words 至少包含一个单词。

示例 1:

1
2
3
4
5
6
7
输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

示例 2:

1
2
3
4
5
6
7
8
9
10
输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐，而不是左右两端对齐。       
     第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

1
2
3
4
5
6
7
8
9
10
输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

推荐解法：

  1. 用 i 遍历所有单词，外层 while i < n 表示处理每一行

  2. 确定当前行能放多少个单词（贪心）：

    • 用 cur_len 记录当前行已占长度（字母 + 必须的最小空格）
    • 加入第 1 个单词时不需要前置空格，之后每个单词至少要 +1 空格
    • 使用 (i > start) 巧妙判断是否需要加 1（面试最爱考点）

  3. 得到本行单词

    words[start:i]

    后：

    • 计算纯字母长度 letter_len
    • 如果是最后一行或只有一个单词 → “ “.join + 右侧补空格
    • 否则 → 计算总空格数，用整除+取模分配到 gaps 个间隔里，左边多余的空格优先放

  4. 构造好本行字符串后加入结果，进入下一行

项目 复杂度 说明
时间复杂度 O(N) N 为所有单词的总字符数，每个字符最多被访问常数次（加入字符串时）
空间复杂度 O(maxWidth) 用来构造每一行的临时字符串（不计输出空间的话可视为 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
class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        res = []          # 存储最终的每一行字符串
        i = 0             # 当前处理到的单词下标
        n = len(words)
        
        while i < n:
            # ------------------- 1. 贪心确定当前行能放多少个单词 -------------------
            start = i                    # 本行第一个单词的下标
            cur_len = 0                  # 当前行已占长度（包含必须的最小空格）
            
            while i < n:
                # 计算如果把 words[i] 加入，需要的额外长度
                # 第一个单词不需要前置空格，其余每个单词至少要 +1 空格
                if cur_len + len(words[i]) + (i > start) > maxWidth:
                    break                # 装不下，结束本行
                cur_len += len(words[i]) + (i > start)
                i += 1                   # 成功加入，指向下一个单词
            
            # 此时 words[start:i] 就是本行的所有单词
            # cur_len = 所有字母长度 + (单词数-1) 个最小空格
            
            # ------------------- 2. 构造当前行的字符串 -------------------
            word_list = words[start:i]
            word_cnt = len(word_list)
            letter_len = sum(len(w) for w in word_list)   # 纯字母总长度
            
            # 情况1：最后一行 或 只有一个单词 → 左对齐
            if i == n or word_cnt == 1:
                line = " ".join(word_list)                # 单词之间一个空格
                line += " " * (maxWidth - len(line))      # 右侧补满剩余空格
            else:
                # 情况2：普通行，需要左右对齐
                total_spaces = maxWidth - letter_len      # 要分配的总空格数
                gaps = word_cnt - 1                       # 单词间间隔数
                base = total_spaces // gaps               # 每个间隔至少放的空格数
                extra = total_spaces % gaps               # 左侧额外多 1 个空格的间隔数
                
                line = ""
                for j in range(gaps):
                    line += word_list[j]
                    # 当前间隔要放的空格数：基础 + 是否属于左侧多 1 的部分
                    spaces = base + (1 if j < extra else 0)
                    line += " " * spaces
                line += word_list[-1]                     # 最后一个单词后面不加空格
            
            res.append(line)
        
        return res

双指针

LeetCode 125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：

1
2
3
输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：

1
2
3
4
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

简洁写法：

思路步骤

  1. 用生成器表达式遍历原字符串，只保留字母和数字，并全部转成小写 → 得到 clean

  2. 直接比较 clean 是否等于它的逆序 clean[::-1]（Python 切片神器）

  3. 相等就是回文

项目 复杂度 说明
时间复杂度 O(n) n 为原字符串长度，每个字符访问常数次
空间复杂度 O(n) 创建了新的 clean 字符串（最坏情况和原串等长） 
1
2
3
4
5
6
7
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 关键：用 isalnum() 保留字母和数字（而不是 isalpha()！）
        clean = ''.join(c.lower() for c in s if c.isalnum())
        
        # Python 最优雅的回文判断：正着读 == 倒着读
        return clean == clean[::-1]

推荐解法：双指针原地比较

思路步骤

  1. 左右两个指针 left、right 分别从字符串头尾开始
  2. 左指针一直向右跳，直到遇到字母或数字（跳过非法字符）
  3. 右指针一直向左跳，直到遇到字母或数字
  4. 比较这两个字符（忽略大小写），不相等直接返回 False
  5. 相等则左右指针各进一步，继续比较
  6. 相遇或交叉时说明全部匹配，返回 True
项目 复杂度 说明
时间复杂度 O(n) 最坏每个字符都会被访问几次
空间复杂度 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
class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        
        while left < right:
            # 1. 左指针跳过所有非字母数字字符
            while left < right and not s[left].isalnum():
                left += 1
            
            # 2. 右指针跳过所有非字母数字字符
            while left < right and not s[right].isalnum():
                right -= 1
            
            # 3. 现在 left 和 right 都指向合法字符，比较（忽略大小写）
            if s[left].lower() != s[right].lower():
                return False
            
            # 4. 匹配成功，继续向中间收缩
            left += 1
            right -= 1
        
        # 相遇或交叉，说明全部匹配
        return True

LeetCode 392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

1
2
输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

1
2
输入：s = "axc", t = "ahbgdc"
输出：false

简洁写法：

利用 Python 的迭代器特性：依次从 t 中找 s 的每个字符，找不到就失败。

时间复杂度 O(m) 最坏遍历一次 t
空间复杂度 O(1) 迭代器不占额外空间 
1
2
3
4
5
6
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # t_iter 是 t 的迭代器，每次 next() 取出下一个字符
        t_iter = iter(t)
        # 所有 s 中的字符都要能在 t 中按顺序找到
        return all(char in t_iter for char in s)

推荐解法：双指针

思路步骤

  1. 如果 s 为空，直接返回 True（空串是任何串的子序列）
  2. 用 i 指向 s 的当前位置，j 指向 t 的当前位置
  3. 遍历 t（j 从 0 到 len(t)-1）
    • 如果 t[j] == s[i]，说明匹配到一个字符，i++
    • 如果 i == len(s)，说明 s 所有字符都找到了，直接返回 True
  4. 遍历完 t 后，如果 i == len(s) 返回 True，否则 False
时间复杂度 O(m) m 为 t 的长度（长的那个）
空间复杂度 O(1) 只用了两个指针 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # s 是可能的子序列（短的），t 是母串（长的）
        n, m = len(s), len(t)
        
        # 空字符串是任何字符串的子序列
        if n == 0:
            return True
            
        i = 0  # i 指向 s 当前需要匹配的字符位置
        
        # 只遍历一次 t
        for j in range(m):
            if i < n and s[i] == t[j]:
                i += 1          # 匹配成功，找 s 的下一个字符
                if i == n:      # s 已经全部匹配完
                    return True
                    
        # 遍历完 t 后，检查是否 s 全部匹配
        return i == n

LeetCode 167. 两数之和 || - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

1
2
3
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

1
2
3
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

1
2
3
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

推荐解法：双指针

思路步骤

  1. 初始化 left = 0，right = len-1
  2. 循环条件：left < right
  3. 计算 sum = numbers[left] + numbers[right]
    • sum == target → 返回 [left+1, right+1]（题目要求1-based索引）
    • sum > target → right–
    • sum < target → left++
  4. 题目保证有解，所以一定能找到
时间复杂度 O(n) 只遍历一次数组
空间复杂度 O(1) 只用了两个指针 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0                    # 左指针（小的数）
        right = len(numbers) - 1    # 右指针（大的数）
        
        while left < right:
            total = numbers[left] + numbers[right]
            
            if total == target:
                # 题目要求返回 1-based 索引
                return [left + 1, right + 1]
            elif total > target:
                right -= 1         # 和太大，右边变小
            else:  # total < target
                left += 1          # 和太小，左边变大
        
        # 题目保证一定有解，不会走到这里
        return [-1, -1]

LeetCode 11. 盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 1：

img

1
2
3
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

1
2
输入：height = [1,1]
输出：1

推荐解法：双指针

思路步骤

  1. left = 0, right = len-1
  2. 维护 max_area
  3. while left < right:
    • 计算当前面积：min(height[left], height[right]) × (right - left)
    • 更新 max_area
    • 如果 left 更矮 → left++（移动矮的）
    • 否则 → right–（移动矮的或等高的）
  4. 返回 max_area
时间复杂度 O(n) 只遍历一次数组
空间复杂度 O(1) 只用了两个指针 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0
        
        while left < right:
            # 当前宽度 = right - left
            current_area = min(height[left], height[right]) * (right - left)
            max_area = max(max_area, current_area)
            
            # 关键：移动较矮的那根柱子
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return max_area

LeetCode 15. 三数之和

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

**注意：**答案中不可以包含重复的三元组。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
2
3
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

1
2
3
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

推荐解法：排序 + 双指针

思路步骤

  1. 先对 nums 排序
  2. 遍历 i 从 0 到 n-3（留两个位置）
    • 如果 i > 0 且 nums[i] == nums[i-1] → 跳过（去重）
    • 否则固定 nums[i]，在 [i+1, n-1] 用双指针找两数之和为 -nums[i]
  3. left = i+1, right = n-1
    • sum = nums[i] + nums[left] + nums[right]
    • sum == 0 → 加入答案 → left++ 和 right– 同时跳过重复
    • sum < 0 → left++
    • sum > 0 → right–
  4. 返回所有不重复的三元组
时间复杂度 O(n²) 排序 O(n log n) + 外层 O(n) × 内层双指针 O(n)
空间复杂度 O(1) 或 O(log n) 不计输出空间的话（排序可能用 log 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
29
30
31
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()                    # 第一步：排序！必须的！
        res = []
        
        for i in range(n - 2):         # i 最多到 n-3
            # 去重：当前 i 和前一个相同，直接跳过
            if i > 0 and nums[i] == nums[i - 1]:
                continue
                
            # 双指针找 nums[left] + nums[right] = -nums[i]
            left, right = i + 1, n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                
                if total == 0:
                    res.append([nums[i], nums[left], nums[right]])
                    # 跳过重复的 left 和 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
                elif total < 0:
                    left += 1
                else:
                    right -= 1
        
        return res

滑动窗口

LeetCode 209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

1
2
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

进阶：

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

推荐解法：滑动窗口

思路步骤

  1. 初始化 left = 0, current_sum = 0, min_len = 无穷大
  2. 遍历右指针 right 从 0 到 n-1
    • 扩大窗口：current_sum += nums[right]
    • 收缩窗口：while current_sum ≥ target 且 left ≤ right
      • 更新 min_len = min(min_len, right - left + 1)
      • current_sum -= nums[left], left += 1
  3. 返回 min_len 如果是无穷大则返回 0
时间复杂度 O(n) 每个元素最多被加减一次（左右指针各走一遍）
空间复杂度 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
from typing import List

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        left = 0                    # 窗口左边界
        current_sum = 0             # 当前窗口和
        min_len = float('inf')      # 记录最小长度，初始无穷大
        
        for right in range(n):
            # 1. 扩大窗口
            current_sum += nums[right]
            
            # 2. 收缩窗口：只要和 ≥ target，就一直缩，直到不满足
            while current_sum >= target:
                # 更新答案：当前窗口长度
                min_len = min(min_len, right - left + 1)
                # 收缩左边界
                current_sum -= nums[left]
                left += 1
        
        # 如果 min_len 没变过，说明没找到，返回 0
        return 0 if min_len == float('inf') else min_len

LeetCode 3. 无重复字符的最长子串

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

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

推荐解法：滑动窗口 + 哈希表

思路步骤

  1. 用字典 last_seen 记录每个字符最后出现的下标
  2. left = 0 表示当前窗口左边界
  3. 遍历 right 从 0 到 n-1：
    • 如果 s[right] 已经在窗口内（last_seen[s[right]] >= left） → 把 left 跳到 last_seen[s[right]] + 1
    • 更新 last_seen[s[right]] = right
    • 更新答案 max_len = max(max_len, right - left + 1)
时间复杂度 O(n) 每个字符最多被访问两次（right 和 left 各一次）
空间复杂度 O(min(m, n)) m 为字符集大小（ASCII ≤ 128），最坏 O(n) 
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 lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}        # 字符 → 最后出现的位置
        left = 0              # 窗口左边界
        max_len = 0
        n = len(s)
        
        for right in range(n):
            char = s[right]
            
            # 如果 char 已经在当前窗口内出现过
            if char in last_seen and last_seen[char] >= left:
                # 跳过重复部分：左边界直接跳到重复字符的下一个位置
                left = last_seen[char] + 1
            
            # 更新该字符的最新位置
            last_seen[char] = right
            
            # 更新答案
            max_len = max(max_len, right - left + 1)
        
        return max_len

LeetCode 30. 串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

1
2
3
4
5
6
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

1
2
3
4
5
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

1
2
3
4
5
6
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

推荐解法：跳跃式滑动窗口 + 双哈希表

思路步骤

  1. 所有单词长度相同 → 合法答案的起始位置一定是对齐单词边界的 → 只需枚举 word_len 种偏移（offset）即可
  2. 每次窗口移动一个单词长度（不是1！）
  3. 用两个 Counter：
    • target：words 中每个单词应该出现的次数（目标）
    • window：当前窗口中实际出现的次数
  4. 当某个单词超量时，左边界不断右移，直到数量恢复正常
  5. 当窗口长度刚好且 window == target → 找到一个答案
时间复杂度 O(n × k) n 为 s 长度，k 为单词个数（实际远小于暴力）
空间复杂度 O(k) 两个 Counter 哈希表 
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
from collections import Counter
from typing import List

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []
        
        word_len = len(words[0])           # 单个单词长度
        word_num = len(words)              # 单词数量
        total_len = word_len * word_num    # 目标子串总长度
        target = Counter(words)            # 目标：每个单词应出现次数
        n = len(s)
        ans = []
        
        # 只需尝试 word_len 种起始偏移（0 ~ word_len-1）
        for offset in range(word_len):
            left = offset                  # 窗口左边界
            window = Counter()             # 当前窗口的单词计数
            
            # 跳跃式遍历：每次移动一个单词长度
            for start in range(offset, n - word_len + 1, word_len):
                word = s[start:start + word_len]
                
                # 情况1：遇到不在 words 中的词 → 直接清空窗口，重新开始
                if word not in target:
                    window.clear()
                    left = start + word_len
                    continue
                
                # 情况2：加入当前单词
                window[word] += 1
                
                # 情况3：某个单词超量了 → 疯狂收缩左边界，直到不超
                while window[word] > target[word]:
                    left_word = s[left:left + word_len]
                    window[left_word] -= 1
                    left += word_len
                
                # 情况4：窗口长度刚好，检查是否完全匹配
                if start - left + word_len == total_len and window == target:
                    ans.append(left)
        
        return ans

LeetCode 76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

1
2
3
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

1
2
3
4
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

矩阵

哈希表

区间

栈

链表

二叉树

二叉树层次遍历

二叉搜索树

图

图的广度优先搜索

字典树

回溯

分治

Kadance 算法

二分查找

堆

位运算

数学

一维动态规划

LeetCode 70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

笨比解法：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def climbStairs(self, n: int) -> int:
        def dp(i):
            if i == 1:
                return 1
            elif i == 2:
                return 2
            else:
                return dp(i - 1) + dp(i - 2) 
        return dp(n)

一般解法：递归 + 记忆化（推荐，优化递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {}  # 用于记忆化，存储已经计算过的 dp(i)

        def dp(i):
            if i in memo:
                return memo[i]
            if i == 1:
                return 1
            elif i == 2:
                return 2
            else:
                memo[i] = dp(i - 1) + dp(i - 2)
                return memo[i]
        
        return dp(n)

推荐解法：动态规划（迭代，自底向上）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2

        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]

优雅解法：动态规划 + 变量滚动（推荐！）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2

        prev1, prev2 = 1, 2  # 分别代表 dp[i-2], dp[i-1]
        for i in range(3, n + 1):
            curr = prev1 + prev2
            prev1, prev2 = prev2, curr
        
        return prev2
方法 类型 是否推荐 特点
递归（无记忆化） 暴力 ❌ 不推荐 逻辑对，但超时
递归 + 记忆化 优化递归 ✅ 推荐（理解用） 有缓存，可通过
动态规划（数组） 标准 DP ✅ 推荐 时间 O(n)，空间 O(n)
动态规划（变量滚动） 最优 DP ✅⭐⭐⭐ 最推荐 时间 O(n)，空间 O(1)

LeetCode 198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

1
2
3
4
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

推荐解法：动态规划

  1. 处理边界：如果只有一个房屋，返回 nums[0]；两个房屋返回 max(nums[0], nums[1])

  2. 初始化：prev2 = nums[0]（相当于 dp[0]）prev1 = max(nums[0], nums[1])（相当于 dp[1]）

  3. 从第 2 个房屋开始遍历（i = 2）：当前最大金额 curr = max(prev1, prev2 + nums[i])更新：prev2 = prev1，prev1 = curr

  4. 最终 prev1就是答案（即 dp[n-1]）

时间复杂度 O(n) —— 只遍历一次数组
空间复杂度 O(1) —— 只用了常数个额外变量（prev1, prev2, curr） 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        if n == 1:
            return nums[0]
        
        # 初始化前两个状态
        prev2 = nums[0]            # dp[i-2]，初始为第1间房
        prev1 = max(nums[0], nums[1])  # dp[i-1]，初始为前两间房的最大值

        # 从第2间房开始遍历（i从2到n-1）
        for i in range(2, n):
            curr = max(prev1, prev2 + nums[i])  # 当前最大金额
            prev2, prev1 = prev1, curr  # 滚动更新

        return prev1  # 最终结果在第n-1间房

多维动态规划