LeetCode算法题解：数组与字符串高频问题精讲

2026年3月6日 互联网

一、数组元素循环移位问题

问题描述：给定一个整数数组，将所有元素向右循环移动k个位置（k为非负整数），要求空间复杂度为O(1)。

1.1 暴力解法分析

最直观的解法是进行k次单步旋转，每次将数组末尾元素移动到头部。以示例[1,2,3,4,5,6,7]移动3次为例：

  1. def rotate_brute_force(nums, k):
  2.     n = len(nums)
  3.     k = k % n  # 处理k大于数组长度的情况
  4.     for _ in range(k):
  5.         nums.insert(0, nums.pop())  # 每次移动末尾元素到头部
  6.     return nums

该解法时间复杂度为O(n*k)，空间复杂度O(1)，但当k接近n时效率极低。

1.2 数学规律优化

通过观察发现，最终数组可视为原数组的”拼接重组”。具体步骤：

  1. 反转整个数组：[7,6,5,4,3,2,1]
  2. 反转前k个元素：[5,6,7,4,3,2,1]
  3. 反转剩余元素：[5,6,7,1,2,3,4]

实现代码：

  1. def rotate_optimized(nums, k):
  2.     n = len(nums)
  3.     k %= n
  5.     def reverse(start, end):
  6.         while start < end:
  7.             nums[start], nums[end] = nums[end], nums[start]
  8.             start += 1
  9.             end -= 1
  11.     reverse(0, n-1)
  12.     reverse(0, k-1)
  13.     reverse(k, n-1)
  14.     return nums

该解法仅需3次线性遍历，时间复杂度降至O(n)，空间复杂度保持O(1)。

二、股票交易利润最大化问题

问题描述：给定股票价格数组，设计算法计算最大利润。限制条件：可进行多次交易，但必须卖出后才能再次买入。

2.1 贪心算法应用

关键观察点：只要第i天价格高于第i-1天，即可在i-1天买入、i天卖出。这种局部最优策略可累积为全局最优解。

示例分析：
输入[7,1,5,3,6,4]的交易过程：

  • 第2天(1)买入，第3天(5)卖出 → 利润+4
  • 第4天(3)买入，第5天(6)卖出 → 利润+3
    总利润=7

实现代码：

  1. def max_profit(prices):
  2.     profit = 0
  3.     for i in range(1, len(prices)):
  4.         if prices[i] > prices[i-1]:
  5.             profit += prices[i] - prices[i-1]
  6.     return profit

时间复杂度O(n)，空间复杂度O(1)，适用于大规模数据。

2.2 动态规划扩展

若增加交易次数限制（如最多k次交易），需使用动态规划：

  1. def max_profit_k_transactions(prices, k):
  2.     n = len(prices)
  3.     if n <= 1 or k == 0:
  4.         return 0
  6.     # 特殊情况处理：当k>=n/2时等同于无限次交易
  7.     if k >= n // 2:
  8.         return max_profit(prices)
  10.     dp = [[0] * n for _ in range(k+1)]
  11.     for i in range(1, k+1):
  12.         max_diff = -prices[0]
  13.         for j in range(1, n):
  14.             dp[i][j] = max(dp[i][j-1], prices[j] + max_diff)
  15.             max_diff = max(max_diff, dp[i-1][j] - prices[j])
  16.     return dp[k][n-1]

该解法通过状态转移方程dp[i][j] = max(dp[i][j-1], prices[j] + max_diff)实现，其中max_diff记录历史最优买入时机。

三、排序数组去重问题

问题描述：给定已排序数组，原地删除重复元素，使每个元素最多出现一次，返回新数组长度。

3.1 双指针经典解法

使用快慢指针技术：

  • 慢指针指向已处理区域的末尾
  • 快指针遍历数组寻找新元素

实现步骤：

  1. 初始化慢指针i=0
  2. 快指针j从1开始遍历
  3. 当nums[j] != nums[i]时，i+=1并复制元素

代码实现：

  1. def remove_duplicates(nums):
  2.     if not nums:
  3.         return 0
  4.     i = 0
  5.     for j in range(1, len(nums)):
  6.         if nums[j] != nums[i]:
  7.             i += 1
  8.             nums[i] = nums[j]
  9.     return i + 1

该解法时间复杂度O(n)，空间复杂度O(1)，且保持了原始顺序。

3.2 扩展：允许最多k次重复

若需保留每个元素最多k次重复，可修改比较条件：

  1. def remove_duplicates_k(nums, k):
  2.     n = len(nums)
  3.     if n <= k:
  4.         return n
  6.     i = k  # 前k个元素无需处理
  7.     for j in range(k, n):
  8.         if nums[j] != nums[i-k]:
  9.             nums[i] = nums[j]
  10.             i += 1
  11.     return i

四、双指针技术综合应用

问题描述：给定人员体重数组和船载重限制，计算最少需要多少艘船才能运送所有人员。

4.1 贪心策略实现

关键思路：

  1. 将数组排序
  2. 使用双指针从最重和最轻两端向中间遍历
  3. 尝试将最轻和最重的人配对

示例分析：
输入people=[1,2], limit=3：

  • 1+2=3 ≤ limit → 可配对
  • 所需船数=1

代码实现：

  1. def num_rescue_boats(people, limit):
  2.     people.sort()
  3.     left, right = 0, len(people)-1
  4.     boats = 0
  5.     while left <= right:
  6.         if people[left] + people[right] <= limit:
  7.             left += 1
  8.         right -= 1
  9.         boats += 1
  10.     return boats

时间复杂度O(n log n)（排序主导），空间复杂度O(1)。

4.2 边界条件处理

需特别注意以下情况：

  • 单人重量超过limit时直接返回-1
  • 空数组直接返回0
  • 所有人重量相同且为limit/2的偶数倍时

优化后的完整实现：

  1. def num_rescue_boats_robust(people, limit):
  2.     if not people:
  3.         return 0
  4.     if max(people) > limit:
  5.         return -1
  7.     people.sort()
  8.     left, right = 0, len(people)-1
  9.     boats = 0
  10.     while left <= right:
  11.         if people[left] + people[right] <= limit:
  12.             left += 1
  13.         right -= 1
  14.         boats += 1
  15.     return boats

五、总结与提升建议

  1. 模式识别：数组类问题常涉及双指针、反转、滑动窗口等模式，需通过大量练习建立条件反射
  2. 复杂度权衡：在时间复杂度和空间复杂度间寻找平衡点，如用额外空间换取时间效率
  3. 边界测试：特别注意空数组、单元素数组、重复元素等边界情况
  4. 通用解法：尝试将具体问题抽象为通用模型，如将股票问题转化为区间求和问题

建议开发者建立错题本，记录典型问题的多种解法及其适用场景。对于高频面试题，建议实现后进行压力测试（如10万级数据量），验证算法的实际性能表现。

最新文章