LeetCode 9. 回文数

Categories:

Tags:

题目描述
思路分析
1. 解法一：反转后半段数字（推荐）
2. 解法二：字符串双指针
相似题目

题目描述

✅ 9. 回文数

思路分析

解法一：反转后半段数字（推荐）

核心思路：

负数一定不是回文数，直接返回 false。

末尾为 0 且本身不为 0 的数不是回文数（如 10、100），直接返回 false。

不将整数转为字符串，而是将数字的后半段反转，再与前半段比较：

每次取出 x 的个位拼到 reversedHalf，同时 x /= 10。

当 reversedHalf >= x 时，说明已经处理了一半的数字。

最终判断：

偶数位回文：x == reversedHalf

奇数位回文：x == reversedHalf / 10（中间位不影响结果）

复杂度分析：

时间复杂度：O(log n)，其中 n 表示输入整数的值，循环次数约为数字位数的一半

空间复杂度：O(1)，仅使用常数个额外变量

class Solution {
    public boolean isPalindrome(int x) {
        // 负数或末尾为 0（且本身不为 0）直接排除
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int reversedHalf = 0;
        // 仅反转后半段数字，避免整数溢出
        while (x > reversedHalf) {
            reversedHalf = reversedHalf * 10 + x % 10;
            x /= 10;
        }

        // 偶数位：x == reversedHalf；奇数位：x == reversedHalf / 10（跳过中间位）
        return x == reversedHalf || x == reversedHalf / 10;
    }
}

func isPalindrome(x int) bool {
    // 负数或末尾为 0（且本身不为 0）直接排除
    if x < 0 || (x%10 == 0 && x != 0) {
        return false
    }

    reversedHalf := 0
    // 仅反转后半段数字，避免整数溢出
    for x > reversedHalf {
        reversedHalf = reversedHalf*10 + x%10
        x /= 10
    }

    // 偶数位：x == reversedHalf；奇数位：x == reversedHalf / 10（跳过中间位）
    return x == reversedHalf || x == reversedHalf/10
}

解法二：字符串双指针

核心思路：

负数直接返回 false。

将整数转换为字符串，使用双指针从两端向中间比较字符。

若任意位置首尾字符不相等，则不是回文数。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示输入整数的值，字符串长度等于数字的位数

空间复杂度：O(log n)，其中 log n 表示存储字符串所需的空间

class Solution {
    public boolean isPalindrome(int x) {
        // 负数不是回文数
        if (x < 0) {
            return false;
        }

        String s = Integer.toString(x);
        int left = 0, right = s.length() - 1;

        // 双指针从两端向中间比较
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

func isPalindrome(x int) bool {
    // 负数不是回文数
    if x < 0 {
        return false
    }

    s := strconv.Itoa(x)
    left, right := 0, len(s)-1

    // 双指针从两端向中间比较
    for left < right {
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    return true
}

相似题目

题目	难度	考察点
125. 验证回文串	简单	双指针 / 字符串
234. 回文链表	简单	链表 / 快慢指针
680. 验证回文串 II	简单	双指针 / 字符串
5. 最长回文子串	中等	动态规划 / 中心扩展
647. 回文子串	中等	动态规划 / 中心扩展
131. 分割回文串	中等	回溯 / 动态规划
336. 回文对	困难	哈希表 / 字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/76476487