您现在的位置是：首页 >其他 >LeetCode-回文数（C/C++）网站首页其他

题目描述

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数: 是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

• 例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

• -2^31 <= x <= 2^31- 1

进阶：你能不将整数转为字符串来解决这个问题吗？

题解

总体思路：x为整数，整数分为正数，负数，0，由示例可知负数一定不为回文数，0为回文数，但个位数为0的正整数不为回文数，正整数需进行进一步判断是否为回文数。解题有如下方法，但最后第五种方法反转一半数字最为简便和高效。

数学思路

通过取整和取余操作获取整数中对应的数字进行比较。

示例

假设我们有一个整数 x = 12321，我们需要判断它是否是回文数。以下是逐步执行 x /= 10; 的过程：

1. 初始化：x = 12321, reversedHalf = 0。
2. 第一次循环：
   • reversedHalf = reversedHalf * 10 + x % 10; -> reversedHalf = 0 * 10 + 1 = 1
   • x /= 10; -> x = 12321 / 10 = 1232
3. 第二次循环：
   • reversedHalf = reversedHalf * 10 + x % 10; -> reversedHalf = 1 * 10 + 2 = 12
   • x /= 10; -> x = 1232 / 10 = 123
4. 第三次循环：
   • reversedHalf = reversedHalf * 10 + x % 10; -> reversedHalf = 12 * 10 + 3 = 123
   • x /= 10; -> x = 123 / 10 = 12

此时，x 小于 reversedHalf，循环结束。我们需要判断 x 和 reversedHalf 是否相等，或者 x 和 reversedHalf / 10 是否相等（处理奇数位的情况）。

reversedHalf / 10; -> 123 / 10 = 12（去掉最中间的数字）

比较 x 和 reversedHalf / 10：

x == reversedHalf / 10 -> 12 == 12，结果为 true，说明 12321 是回文数。

• 比较转变后的字符串

将数字转换为字符串后，比较字符串的正序和倒序

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

bool isPalindrome(int x)
{
    // 判断x是否小于0为负数，如果是，则返回false
    if(x < 0)
    {
        return false;
    }
    //定义一个字符数组，用于储存数字的字符串形式
    char str[12];//确保空间满足题目要求范围-2^31~2^31-1及终止的空字符
    //将数字x转换成字符串形式，并储存在字符数组str中
    snprintf(str, sizeof(str),  "%d", x);
    //获取字符串长度
    int len = strlen(str);
    //遍历字符串的前半部分
    for(int i = 0; i < len/2; i++)
    {
        //判断字符串的前半部分和后半部分是否相等，如果不相等，则返回false
        if(str[i] !=  str[len - i -1])
        {
            return false;
        }
    }
    //如果字符串前半部分和后半部分相等，则返回true即验证为输入为回文数
}
//自己验证示例
int main()
{
    int x1 = 121;
    int x2 = -121;
    int x3 = 10;

    printf("输入: %d 输出: %s
", x1, isPalindrome(x1) ? "true" : "false");
    printf("输入: %d 输出: %s
", x2, isPalindrome(x2) ? "true" : "false");
    printf("输入: %d 输出: %s
", x3, isPalindrome(x3) ? "true" : "false");

    return 0;
}

时间复杂度

• O(log10(n))：将整数转换为字符串需要 O(log10(n)) 的时间。然后比较字符串的正序和倒序也需要 O(log10(n)) 的时间。
• 总体时间复杂度：O(log10(n))

空间复杂度

• O(log10(n))：需要存储整数转换后的字符串，其长度为 O(log10(n))。
• 总体空间复杂度：O(log10(n))

• 反转整个数字（处理溢出）（进阶）

选择反转整个数字，需要确保在反转过程中不会超出int类型的范围。可以使用long类型来临时储存反转后的结果，以避免溢出。

#include <stdbool.h>
#include <stdio.h>

bool isPalindrome(int x)
{
    // 判断x是否小于0，如果是，则返回false
    if(x < 0)
    {
        return false;
    }
    
    int original = x;//保存原始的x值
    long reversed = 0;//使用long类型以避免溢出
    
    //循环，直到x为0
    while(x != 0)
    {
        //将reversed乘以10，再加上x的个位数，从最后一位开始反转整个数字
        reversed = reversed * 10 + x % 10;
        //将x除以10，去掉个位数，移新x的个位数
        x /= 10;
    }    

    //判断原始的x值和反转后的reversed值是否相等，相等则返回true，输入为回文数，不相等则反之
    return original  == (int)reversed;
}
//测试示例
int main()
{
    int x1 = 121;
    int x2 = -121;
    int x3 = 10;

    printf("输入: %d 输出: %s
", x1, isPalindrome(x1) ? "true" : "false");
    printf("输入: %d 输出: %s
", x2, isPalindrome(x2) ? "true" : "false");
    printf("输入: %d 输出: %s
", x3, isPalindrome(x3) ? "true" : "false");

    return 0;
}

时间复杂度

• O(log10(n))：同样，每次循环中，我们通过 x /= 10 来减少一位数字，直到 x 变为 0。

空间复杂度

• O(1)：只使用了常量级别的额外空间来存储 reversed 和 original 的值。虽然使用了 long 类型来避免溢出，但仍然是常量级别的空间。

•  使用递归（进阶）

递归方法也可以用来比较数字的每一位，但这种方法相对复杂且不如反转一半数字的方法高效。

#include <stdbool.h>
#include <stdio.h>

// 判断一个整数是否是回文数
bool isPalindromeHelper(int x, int y, int *original) 
{
    // 如果x为0，0为回文数返回true
    if (x == 0) 
    {
        return true;
    }
    // 将y乘以10，再加上x的个位数
    y = y * 10 + x % 10;
    // 将x除以10，去掉个位数
    x /= 10;
    // 如果x为0，说明已经遍历完，返回y是否等于original
    if (x == 0) 
    {
        return *original == y;
    }
    // 递归调用isPalindromeHelper函数，继续判断
    return isPalindromeHelper(x, y, original);
}

// 判断一个整数是否为回文数
bool isPalindrome(int x) 
{
    // 如果整数小于0，则不是回文数
    if (x < 0) 
    {
        return false;
    }
    // 调用辅助函数判断是否为回文数
    return isPalindromeHelper(x, 0, &x);
}
//测试示例
int main() {
    int x1 = 121;
    int x2 = -121;
    int x3 = 10;

    printf("输入: %d 输出: %s
", x1, isPalindrome(x1) ? "true" : "false");
    printf("输入: %d 输出: %s
", x2, isPalindrome(x2) ? "true" : "false");
    printf("输入: %d 输出: %s
", x3, isPalindrome(x3) ? "true" : "false");

    return 0;
}

时间复杂度

• O(log10(n))：每次递归调用中，我们通过 x /= 10 来减少一位数字，直到 x 变为 0。
• 总体时间复杂度：O(log10(n))

空间复杂度

• O(log10(n))：递归调用的栈深度为 O(log10(n))，因为每次递归调用都会减少一位数字。
• 总体空间复杂度：O(log10(n))

•  反转一半数字比较（进阶）(官方题解推荐)

通过反转整数的一半来判断它是否为回文数，可以避免处理可能导致溢出的非常大的数字。

#include <stdbool.h>
#include <stdio.h>

bool 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;
    }

    // 当数字长度为奇数时，我们可以忽略掉最中间的数字，例如12321
    // 只需要判断123和12是否相同即可
    return x == reversedHalf || x == reversedHalf / 10;
}
//测试示例
int main() {
    int x1 = 121;
    int x2 = -121;
    int x3 = 10;

    printf("输入: %d 输出: %s
", x1, isPalindrome(x1) ? "true" : "false");
    printf("输入: %d 输出: %s
", x2, isPalindrome(x2) ? "true" : "false");
    printf("输入: %d 输出: %s
", x3, isPalindrome(x3) ? "true" : "false");

    return 0;
}

时间复杂度

• O(log10(n))：其中 n 是整数 x 的值。这是因为每次循环中，我们通过 x /= 10 来减少一位数字，直到 x 小于等于反转后的部分。

空间复杂度

• O(1)：只使用了常量级别的额外空间来存储 reversedHalf 和 x 的临时值。

结论

• 反转一半数字 和 反转整个数字（处理溢出） 是最高效的方法，它们的时间复杂度为 O(log10(n))，且空间复杂度为 O(1)。
• 比较反转后的字符串和 使用递归 的时间复杂度同样为 O(log10(n))，但由于需要额外的字符串、数组或递归栈空间，它们的空间复杂度为 O(log10(n))。