LeetCode 9. 回文数：两种高效解法详解

LeetCode入门级经典题——9.回文数这道题看似简单却藏着两种思路截然不同的高效解法尤其适合刚接触算法的小伙伴巩固基础。话不多说我们直接进入正题一、题目回顾题目很简洁给你一个整数 x 如果 x 是一个回文整数返回 true 否则返回 false 。核心定义回文数是指正序从左向右和倒序从右向左读都是一样的整数。举几个例子帮大家快速理解输入121 → 输出true正序121倒序121一致输入-121 → 输出false正序-121倒序121-不一致输入10 → 输出false正序10倒序01即1不一致这里有个小细节负数一定不是回文数因为负号倒序后会在末尾无法匹配末尾为0的非0整数也不是回文数比如10、100倒序后开头为0和原数不一致这两个细节会成为我们优化解法的关键。二、解法一完整反转整数直观易懂1. 解法思路最直观的思路就是将整数完整反转然后和原数对比如果相等就是回文数否则不是。核心步骤先判断边界如果 x 0直接返回 false负数无回文定义两个变量cur 保存原数的副本用于后续反转操作避免修改原数revN 保存反转后的整数初始为0循环反转通过取余cur % 10获取 cur 的末尾数字通过乘10revN * 10将反转后的数字左移一位再加上末尾数字同时将 cur 除以10向下取整直到 cur 变为0对比反转后的数字revN和原数x相等则返回 true否则返回 false。2. 代码实现TypeScriptfunctionisPalindrome_1(x:number):boolean{if(x0)returnfalse;letcurx;letrevN0;while(cur!0){revNcur%10revN*10;curMath.floor(cur/10);}returnrevNx;};3. 解法分析优势思路简单、代码简洁容易理解和上手适合算法新手入门练习。注意点虽然题目中没有明确说明整数溢出的问题但在实际场景中反转后的整数可能会超过 Number 的最大范围比如 x 2^31 - 1反转后会溢出。不过在 LeetCode 这道题的测试用例中这种情况不会出现所以该解法可以直接通过。时间复杂度O(n)n 是整数 x 的位数因为循环次数等于 x 的位数。空间复杂度O(1)只使用了3个变量cur、revN、x没有使用额外的空间。三、解法二反转一半整数优化高效1. 解法思路解法一的优化版我们不需要反转整个整数只需要反转整数的后半部分然后和前半部分对比即可这样可以减少一半的循环次数效率更高。核心逻辑先判断边界① x 0 → false② x 末尾为0且 x ≠ 0 → false比如10、100定义变量 revertedNumber 保存反转的后半部分初始为0循环反转后半部分当 x revertedNumber 时说明还没反转到一半继续取 x 的末尾数字添加到 revertedNumber 中同时 x 除以10向下取整对比判断循环结束后有两种情况如果 x 的位数是偶数比如1221则 x 应该等于 revertedNumberx12revertedNumber12如果 x 的位数是奇数比如12321则 x 应该等于 revertedNumber 除以10去掉中间的数字3x12revertedNumber123 → 123/1012。2. 代码实现TypeScriptfunctionisPalindrome_2(x:number):boolean{if(x0||(x%100x!0)){returnfalse;}letrevertedNumber:number0;while(xrevertedNumber){revertedNumberrevertedNumber*10x%10;xMath.floor(x/10);}returnxrevertedNumber||xMath.floor(revertedNumber/10);};3. 解法分析优势相比解法一循环次数减少了一半效率更高同时避免了反转整个整数可能出现的溢出问题因为只反转一半反转后的数字一定不会超过原数也就不会溢出。注意点边界判断的第二个条件x % 10 0 x ! 0容易遗漏比如输入10不判断的话循环后 x1revertedNumber0会误判为 true加上这个条件就能避免。时间复杂度O(n/2) O(n)虽然循环次数减少一半但时间复杂度的量级不变不过实际运行速度会更快。空间复杂度O(1)和解法一一样只使用了少量变量无额外空间消耗。四、两种解法对比总结解法核心思路优势注意点解法一完整反转反转整个整数与原数对比思路简单、代码简洁易理解可能存在整数溢出LeetCode测试用例无影响解法二反转一半反转后半部分与前半部分对比效率更高无溢出问题边界判断易遗漏末尾为0的非0整数五、刷题小技巧边界条件优先考虑这道题的边界负数、末尾为0的非0数是解题的关键先处理边界能减少后续逻辑的复杂度也能避免误判。优化思路的核心当需要反转整数时优先考虑“反转一半”既能提高效率又能规避溢出风险这种“减半操作”在很多整数相关的算法题中都能用到。测试用例覆盖写完代码后记得测试几个典型用例负数、末尾为0的数、奇数位整数、偶数位整数、单个数字确保代码的正确性。六、总结LeetCode 9.回文数是一道非常适合入门的算法题两种解法各有优劣解法一适合新手理解思路解法二适合优化效率。通过这道题我们可以巩固“整数反转”的核心逻辑同时学会关注边界条件和算法优化。