1. 题目背景与需求解析今天想和大家分享两道经典的LeetCode数组操作题目——回文数判断与加一运算。这两道题看似简单却涵盖了整数处理、边界条件判断等编程基本功非常适合用来检验基础算法的掌握程度。我在面试候选人和日常代码Review中经常发现即使是工作多年的开发者也会在这些基础题目上出现各种边界情况处理不当的问题。**回文数判断LeetCode 9**要求我们判断一个整数是否是回文数。回文数是指正读反读都相同的数字例如121是回文数而-121和10则不是。这个题目考察的核心是如何在不将整数转为字符串的情况下通过数学运算完成判断。**加一运算LeetCode 66**则给定一个由整数组成的非空数组该数组表示一个非负整数要求对该整数加一后返回新的数组表示。例如输入[1,2,3]应返回[1,2,4]而[9,9]则返回[1,0,0]。这道题的关键在于处理进位和数组扩容的情况。2. 回文数判断的三种解法2.1 字符串反转法最直观的思路是将整数转为字符串然后判断字符串是否与其反转相等def isPalindrome(x: int) - bool: return str(x) str(x)[::-1]这种方法虽然简洁但使用了额外的字符串空间且题目明确建议尝试不转字符串的解法。注意负数直接返回False因为负号会导致不对称。2.2 数学反转法更符合题目要求的解法是通过数学运算反转数字def isPalindrome(x: int) - bool: if x 0: return False original x reversed_num 0 while x 0: reversed_num reversed_num * 10 x % 10 x x // 10 return original reversed_num时间复杂度O(log10(n))空间复杂度O(1)。这里需要注意整数反转可能导致的溢出问题但在Python中不需要担心。2.3 优化反转法反转一半数字我们可以进一步优化只反转数字的后半部分然后与前半部分比较def isPalindrome(x: int) - bool: if x 0 or (x % 10 0 and x ! 0): return False reversed_half 0 while x reversed_half: reversed_half reversed_half * 10 x % 10 x x // 10 return x reversed_half or x reversed_half // 10这种方法将时间复杂度降低到O(log10(n)/2)同时避免了完全反转可能导致的溢出问题在其他语言中尤为重要。3. 加一运算的详细实现3.1 基础实现思路加一运算的核心在于处理进位。我们可以从数组末尾开始逐位处理def plusOne(digits: List[int]) - List[int]: n len(digits) for i in range(n-1, -1, -1): if digits[i] 9: digits[i] 1 return digits digits[i] 0 return [1] digits这个实现的关键点在于从最后一位开始遍历遇到小于9的数字直接加一返回遇到9则置0并继续处理前一位如果全部都是9则在数组前插入13.2 边界情况处理在实际编码中有几个边界情况需要特别注意全9数组如[9,9]应返回[1,0,0]单个数字[0]应返回[1][9]应返回[1,0]中间有9的数字[1,9,9]应返回[2,0,0]3.3 递归解法展示虽然迭代解法更高效但递归解法也能很好展示思路def plusOne(digits: List[int], indexNone) - List[int]: if index is None: index len(digits) - 1 if index 0: return [1] digits if digits[index] 9: digits[index] 1 return digits else: digits[index] 0 return plusOne(digits, index-1)递归解法虽然代码简洁但在处理大数组时可能会有栈溢出风险因此在实际生产中推荐使用迭代解法。4. 常见错误与调试技巧4.1 回文数判断的易错点负数处理忘记直接返回False末尾为0的数如10、100等需要特殊处理反转溢出在其他语言中需要考虑Python不需要性能优化没有考虑只反转一半的优化方案调试时可以构造以下测试用例121标准回文-121负数10末尾012321奇数位1221偶数位4.2 加一运算的易错点进位处理不完整只处理了最后一位的进位数组扩容问题没有正确处理全9数组的情况原地修改问题在某些语言中直接修改输入数组可能导致问题前导零问题虽然题目保证输入无前导零但实际应用中需要考虑调试时可以构造以下测试用例[1,2,3]常规[9,9]全9[0]单个0[1,9,9]中间有9[9]单个95. 复杂度分析与优化思考5.1 回文数判断复杂度时间复杂度字符串法O(n)n为数字位数数学反转法O(log10(n))优化反转法O(log10(n)/2)空间复杂度字符串法O(n)需要额外字符串空间数学方法O(1)5.2 加一运算复杂度时间复杂度最坏情况O(n)全9数组平均情况O(1)大多数情况只需修改最后一位空间复杂度最坏情况O(n)需要扩容数组平均情况O(1)原地修改5.3 进一步优化思路对于回文数判断可以考虑提前排除明显非回文数如负数、末尾为0的非零数使用位运算加速数字处理在某些语言中对于加一运算可以考虑提前终止遍历一旦不需要进位立即返回使用更高效的内存分配方式处理数组扩容6. 实际应用场景延伸虽然这两道题看起来是纯粹的算法练习但它们在实际开发中有广泛的应用回文数判断数据校验如校验码检查对称性检测在图像处理中密码学中的某些算法加一运算大整数运算的基础计数器实现数字仪表盘的显示更新我在实际项目中曾遇到过类似加一运算的场景实现一个分布式的ID生成器需要处理多节点间的序列号递增其核心逻辑与这道题非常相似。当时因为没有处理好进位问题导致生成了重复ID造成了严重的数据一致性问题。这个教训让我更加重视基础算法的扎实掌握。