合参君1. LeetCode热题100解析：以189题为例
作为程序员面试的"金标准"，LeetCode题库中有些题目因其经典性和高频出现率被称为"必刷题"。其中编号189的"旋转数组"就是典型代表——它在亚马逊、微软等大厂面试中的出现频率高达62%（根据2023年LeetCode企业题库统计）。我第一次遇到这道题是在一次电话面试中，当时被要求在不使用额外空间的情况下完成操作，结果因为边界条件处理不当惨遭挂面。后来系统刷题时发现，这道题看似简单实则暗藏多个考察维度，是检验基础算法能力的试金石。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 题目本质与解法分析
2.1 问题重述与示例
给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。例如：
code复制输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
要求使用空间复杂度O(1)的原地算法解决（即不能使用额外数组存储结果）。
2.2 暴力解法及其缺陷
最直观的思路是每次右移一位，重复k次：
python复制def rotate(nums, k):
for _ in range(k):
previous = nums[-1]
for i in range(len(nums)):
nums[i], previous = previous, nums[i]
这种解法时间复杂度O(n*k)，当k接近n时退化为O(n²)，在LeetCode上会超时。我在第一次实现时就踩了这个坑——没有考虑k>n的情况（当k=n时数组相当于没有旋转）。
2.3 环状替换法
更优的解法是利用数学规律进行元素替换：
python复制def rotate(nums, k):
k %= len(nums)
count = 0
start = 0
while count < len(nums):
current = start
prev = nums[start]
while True:
next_idx = (current + k) % len(nums)
nums[next_idx], prev = prev, nums[next_idx]
current = next_idx
count += 1
if current == start:
break
start += 1
这个解法的精妙之处在于：
k %= len(nums)处理了k>n的情况- 通过gcd(n,k)确定需要多少轮替换（上述代码用count变量控制）
- 空间复杂度O(1)，时间复杂度O(n)
关键提示：当n和k的最大公约数等于1时，只需要一次遍历就能完成所有元素替换；否则需要gcd(n,k)次遍历。这是理解环状替换法的核心。
3. 最优解：三次反转法
3.1 算法步骤
更优雅的解法是利用数组反转特性：
- 反转整个数组
- 反转前k个元素
- 反转剩余元素
以nums = [1,2,3,4,5,6,7], k=3为例：
code复制原始数组: 1 2 3 4 5 6 7
全部反转: 7 6 5 4 3 2 1
前k个反转: 5 6 7 4 3 2 1
剩余反转: 5 6 7 1 2 3 4
3.2 代码实现
python复制def reverse(nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
def rotate(nums, k):
n = len(nums)
k %= n
reverse(nums, 0, n-1)
reverse(nums, 0, k-1)
reverse(nums, k, n-1)
3.3 复杂度分析
- 时间复杂度：O(n)（三次反转每次都是O(n)）
- 空间复杂度：O(1)（原地操作）
- 优势：代码简洁，不易出错，适合面试场景
4. 边界条件与测试用例
4.1 必须考虑的边界情况
- k=0：数组不应变化
- k=数组长度：数组不应变化
- k>数组长度：取模运算处理
- 空数组或单元素数组：直接返回
- k=1和k=n-1的特殊情况
4.2 推荐测试用例
python复制test_cases = [
([1,2,3,4,5], 2, [4,5,1,2,3]), # 常规情况
([1,2,3,4], 4, [1,2,3,4]), # k等于长度
([1], 10, [1]), # 单元素+k>n
([], 3, []), # 空数组
([1,2,3,4,5], 7, [4,5,1,2,3]) # k>n
]
5. 面试实战技巧
5.1 解题思路引导
当面试官提出这个问题时，建议按以下步骤展开：
- 确认需求："请问k是否可能大于数组长度？是否需要处理空数组情况？"
- 提出暴力解法并分析复杂度
- 优化思路："我们可以利用反转的特性来优化空间复杂度..."
- 讨论边界条件
- 手写代码并逐步验证
5.2 常见follow-up问题
- 如果允许使用额外空间，你会如何解决？（直接切片拼接）
- 如何向左旋转数组？（可以转换为向右旋转n-k次）
- 如果数组很大但内存有限怎么办？（外部排序思想）
5.3 代码实现中的坑
- 忘记处理k>n的情况（必须取模）
- 反转区间写错（特别是第三次反转的起始位置）
- 原地修改时索引计算错误
- 没有处理空数组导致越界
6. 同类题目拓展
掌握189题后，可以解决以下变种问题：
- 剑指Offer 58-II：左旋转字符串（本质相同）
- LeetCode 61：旋转链表
- LeetCode 151：反转字符串中的单词（类似反转思想）
- LeetCode 186：反转字符串中的单词II
我在刷题过程中发现，许多数组操作问题都可以用反转的思想来解决。比如反转字符串中的单词（151题）就是先整体反转再逐个单词反转，这与189题的解法有异曲同工之妙。