1. 项目概述最近在刷LeetCode热题100的第55~61题这几道题涵盖了动态规划、回溯算法、链表操作等经典题型。作为算法练习的黄金题库这些题目不仅考察基础数据结构的掌握程度更能训练我们分析问题和优化解法的能力。本文将详细拆解每道题的解题思路、代码实现和优化技巧特别适合准备技术面试或想系统提升算法能力的开发者。2. 题目解析与解题思路2.1 第55题跳跃游戏给定一个非负整数数组nums你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。核心思路贪心算法维护一个变量max_reach表示当前能到达的最远位置遍历数组时更新max_reach max(max_reach, i nums[i])如果max_reach len(nums)-1则返回True如果遍历到某个i时i max_reach说明无法继续前进返回Falsedef canJump(nums): max_reach 0 for i in range(len(nums)): if i max_reach: return False max_reach max(max_reach, i nums[i]) if max_reach len(nums)-1: return True return True优化点提前终止当max_reach已经覆盖终点时可以直接返回边界处理空数组和单元素数组的特殊情况2.2 第56题合并区间给出一个区间的集合请合并所有重叠的区间。解题步骤首先按区间的起始位置排序初始化结果列表放入第一个区间遍历后续区间如果当前区间起始结果列表中最后一个区间的结束则合并否则直接加入结果列表def merge(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) res [intervals[0]] for interval in intervals[1:]: if interval[0] res[-1][1]: res[-1][1] max(res[-1][1], interval[1]) else: res.append(interval) return res注意事项必须首先排序时间复杂度O(nlogn)合并时要取两个区间结束值的最大值3. 关键算法实现与优化3.1 第57题插入区间给出一个无重叠的有序区间列表插入一个新的区间并合并必要的区间。解题策略初始化结果列表和插入标志遍历原区间列表新区间在当前位置左侧且无交集直接插入有交集合并区间在右侧继续遍历如果遍历结束仍未插入添加到末尾def insert(intervals, newInterval): res [] inserted False for interval in intervals: if interval[1] newInterval[0]: res.append(interval) elif interval[0] newInterval[1]: if not inserted: res.append(newInterval) inserted True res.append(interval) else: newInterval[0] min(newInterval[0], interval[0]) newInterval[1] max(newInterval[1], interval[1]) if not inserted: res.append(newInterval) return res性能分析时间复杂度O(n)只需一次遍历空间复杂度O(n)存储结果3.2 第58题最后一个单词的长度给定一个字符串s由若干单词组成单词之间用空格隔开。返回字符串中最后一个单词的长度。边界情况处理字符串末尾可能有多个空格字符串可能全为空格空字符串情况def lengthOfLastWord(s): end len(s) - 1 while end 0 and s[end] : end - 1 if end 0: return 0 start end while start 0 and s[start] ! : start - 1 return end - start优化技巧从字符串末尾开始遍历避免处理前面多余空格先找到第一个非空格字符再向前找空格4. 链表操作专题4.1 第61题旋转链表给定一个链表的头节点head将链表每个节点向右移动k个位置。关键步骤计算链表长度nk k % n 处理k大于n的情况找到倒数第k1个节点作为新尾节点调整指针指向形成新链表def rotateRight(head, k): if not head or not head.next or k 0: return head # 计算链表长度 n 1 tail head while tail.next: tail tail.next n 1 k k % n if k 0: return head # 找到新尾节点 new_tail head for _ in range(n - k - 1): new_tail new_tail.next # 调整指针 new_head new_tail.next new_tail.next None tail.next head return new_head常见错误未处理k大于链表长度的情况指针调整顺序错误导致链表断裂边界条件处理不全空链表、单节点链表等5. 回溯算法实战5.1 第60题排列序列给出集合[1,2,...,n]返回第k个排列。数学解法计算阶乘数组用于快速确定每个位置的数字每次确定一位数字后调整k值和剩余数字列表注意k的索引从0开始还是1开始def getPermutation(n, k): factorials [1] nums [1] for i in range(1, n): factorials.append(factorials[-1] * i) nums.append(str(i1)) k - 1 res [] for i in range(n-1, -1, -1): idx k // factorials[i] k - idx * factorials[i] res.append(nums.pop(idx)) return .join(res)优化点预计算阶乘值避免重复计算使用列表而不是字符串操作提高效率注意k的索引调整6. 动态规划深度解析6.1 第59题螺旋矩阵II给定正整数n生成一个包含1到n²所有元素的螺旋矩阵。分层处理法定义矩阵的四个边界top, bottom, left, right按照右→下→左→上的顺序填充数字每完成一个方向后调整对应边界循环直到所有位置填充完毕def generateMatrix(n): matrix [[0]*n for _ in range(n)] num 1 top, bottom 0, n-1 left, right 0, n-1 while num n*n: # 向右 for i in range(left, right1): matrix[top][i] num num 1 top 1 # 向下 for i in range(top, bottom1): matrix[i][right] num num 1 right - 1 # 向左 for i in range(right, left-1, -1): matrix[bottom][i] num num 1 bottom - 1 # 向上 for i in range(bottom, top-1, -1): matrix[i][left] num num 1 left 1 return matrix边界处理奇数n时中心点单独处理确保循环条件正确避免重复填充7. 刷题经验与技巧总结在实际刷题过程中我总结了以下几点经验模板化思维对于常见题型如回溯、DP要建立解题模板但不要死记硬背理解其背后的思想更重要。边界测试一定要测试各种边界情况如空输入、极值、特殊排列等。这是面试中常见的考察点。复杂度分析养成分析时间/空间复杂度的习惯这能帮助发现优化点。多解法比较对每道题尝试思考多种解法比较它们的优劣。比如第55题既可以用贪心也可以用动态规划。调试技巧对于链表问题画图辅助理解指针变化使用print输出中间结果编写小的测试用例验证代码逻辑错题本记录做错的题目和错误原因定期复习。这是提升最快的途径之一。最后分享一个实用技巧在解决数组/矩阵问题时先明确遍历顺序和边界条件再写代码可以避免很多索引错误。对于递归问题先写终止条件再写递归逻辑会更清晰。