1. 算法面试精讲数组旋转、股票买卖与链表操作实战今天要拆解的三道经典算法题恰好覆盖了面试中最常出现的三大数据结构数组、动态规划和链表。189题考察数组旋转的多种解法121题是动态规划的入门必刷题19题则检验对链表指针操作的熟练度。这三道题在各大厂面试中出现频率极高掌握它们能显著提升面试通过率。我在面试候选人和被面试的过程中发现很多工程师对这类基础题存在一看就会一写就废的情况。本文将结合代码实现、复杂度分析和实际面试案例带大家彻底吃透这三道题的核心考点。无论你是准备面试的新手还是想巩固基础的资深工程师都能从中获得可直接复用的解题模板。2. 189. Rotate Array - 数组旋转的三种解法对比2.1 问题重述与边界条件给定一个整数数组nums将数组向右旋转k个位置其中k是非负数。要求使用O(1)的额外空间原地修改。关键边界条件当k大于数组长度时实际有效旋转次数是k % nums.length空数组或单元素数组旋转后不变需要处理k0的特殊情况实际面试中约30%的候选人会忽略k大于数组长度的情况这是面试官常设的陷阱。2.2 暴力解法与优化思路最直观的方法是每次旋转一个元素重复k次def rotate(nums, k): n len(nums) k % n for _ in range(k): previous nums[-1] for i in range(n): nums[i], previous previous, nums[i]时间复杂度O(n*k)空间复杂度O(1)。当n较大时性能极差但适合作为讨论优化的起点。2.3 三次反转法推荐这是最优的原地解法def rotate(nums, k): def reverse(start, end): while start end: nums[start], nums[end] nums[end], nums[start] start 1 end - 1 n len(nums) k % n reverse(0, n-1) # 反转整个数组 reverse(0, k-1) # 反转前k个 reverse(k, n-1) # 反转剩余部分时间复杂度O(n)空间复杂度O(1)。关键在于理解反转顺序整体反转[1,2,3,4,5] → [5,4,3,2,1]前k个反转[5,4,3,2,1] → [4,5,3,2,1] (k2)剩余反转[4,5,3,2,1] → [4,5,1,2,3]2.4 环状替换法的陷阱另一种思路是将元素直接放到最终位置def rotate(nums, k): n len(nums) k % n start count 0 while count n: current, prev start, nums[start] while True: next_idx (current k) % n nums[next_idx], prev prev, nums[next_idx] current next_idx count 1 if start current: break start 1虽然也是O(n)时间但实现复杂且容易出错。面试时除非特别要求建议优先使用反转法。3. 121. Best Time to Buy and Sell Stock - 动态规划入门3.1 问题建模给定数组prices其中prices[i]是某股票第i天的价格。只能完成一次交易买一次卖一次求最大利润。示例 输入[7,1,5,3,6,4] 输出5第2天买入第5天卖出3.2 暴力解法的局限双重循环枚举所有买卖组合def maxProfit(prices): max_profit 0 for i in range(len(prices)): for j in range(i1, len(prices)): profit prices[j] - prices[i] if profit max_profit: max_profit profit return max_profit时间复杂度O(n²)在LeetCode上会超时。需要更优解法。3.3 动态规划思路维护两个变量min_price遍历过程中的最低价max_profit当前能获得的最大利润def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: if price min_price: min_price price elif price - min_price max_profit: max_profit price - min_price return max_profit时间复杂度O(n)空间复杂度O(1)。这是动态规划的简化形式本质上是在遍历时不断更新状态。3.4 常见错误分析没有处理空数组情况应返回0将max_profit初始化为极小负数而非0股票可以不买把min_price更新和max_profit更新放在同一个if分支逻辑错误4. 19. Remove Nth Node From End of List - 链表双指针技巧4.1 问题描述给定一个链表删除链表的倒数第n个节点并返回头节点。示例 输入1-2-3-4-5, n2 输出1-2-3-54.2 双指针解法使用快慢指针快指针先走n步def removeNthFromEnd(head, n): dummy ListNode(0) dummy.next head fast slow dummy for _ in range(n): fast fast.next while fast.next: slow slow.next fast fast.next slow.next slow.next.next return dummy.next时间复杂度O(L)空间复杂度O(1)其中L是链表长度。4.3 边界条件处理使用dummy节点处理删除头节点的情况确保n不超过链表长度题目通常保证链表长度为1时删除后返回None4.4 递归解法了解即可虽然可以递归解决但空间复杂度O(L)def removeNthFromEnd(head, n): def remove(node): if not node: return 0, node i, node.next remove(node.next) return i1, (node, node.next)[i1 n] return remove(head)[1]面试中通常要求最优解递归可作为备选方案讨论。5. 面试实战技巧与组合题5.1 面试回答策略先确认题目条件和边界如k是否可能大于数组长度从暴力解法开始逐步优化解释每种解法的时间/空间复杂度最后选择最优解法实现5.2 常见follow-up问题Rotate Array 如果要求左旋转怎么做 → 反转顺序变为后n-k个→前k个→整体Best Time to Buy and Sell Stock 如果可以交易多次呢 → 贪心法累加所有上升段Remove Nth Node 不用dummy节点怎么处理 → 需要额外判断头节点情况5.3 组合题示例给定一个价格序列你可以在旋转后的任意位置买入卖出一次求最大可能利润解法思路找出旋转点类似旋转数组问题将数组分为两个有序部分分别在两部分用股票问题的解法比较两种情况的利润取最大值6. 代码模板与记忆要点6.1 旋转数组模板def rotate(nums, k): k % len(nums) nums.reverse() nums[:k] reversed(nums[:k]) nums[k:] reversed(nums[k:])6.2 股票问题模板def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit6.3 链表删除模板def removeNthFromEnd(head, n): dummy ListNode(0, head) slow fast dummy for _ in range(n): fast fast.next while fast.next: slow, fast slow.next, fast.next slow.next slow.next.next return dummy.next6.4 复杂度对比表题目最优解法时间复杂度空间复杂度189三次反转O(n)O(1)121动态规划O(n)O(1)19双指针O(L)O(1)7. 避坑指南与调试技巧7.1 旋转数组常见bug忘记处理kn的情况 → 添加k % n反转区间写错 → 记住是[0,k-1]和[k,n-1]修改了原数组但忘记返回 → 注意题目是否要求返回void7.2 股票问题调试要点初始化min_price为INFmax_profit为0先更新min_price再计算profit空数组直接返回07.3 链表问题调试技巧使用dummy节点避免头节点特殊处理画图辅助理解指针移动测试用例要包含删除头节点删除尾节点单节点链表常规情况我在面试中遇到过一位候选人在旋转数组问题上花了20分钟调试最后发现是因为在Python中直接对切片赋值创建了新对象而非原地修改。正确的做法是使用nums[:] reversed(nums[:])或者按照我们之前的分段反转方法。这种语言特性造成的陷阱特别值得注意。