1. 题目描述

problem link

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

2. 解题

经典的回文数问题,常规思路是转成字符串,然后翻转字符串看和原字符串是否相等,这里不做赘述。

附加条件里要求不把数字转成字符串完成这个题,常规思路是把这个数翻转,通过除10模10取出每一位。但把一个整型翻转有溢出的风险,而且判断这种溢出比较麻烦,所以我们用Solution里的解法来做这道题。(好吧其实我就根本看不懂评论区里的大佬对溢出的讨论!!!)

这次同样是翻转数字的思路,但我只翻转一半。就是把给定的数字的后半部分翻转过来,如果和前半部分相等,那么就是回文数,不相等自然就不是。但是如何判断什么时候是一半呢?假设输入x = 123321,用tmp来记录翻转后的数,第一次取出x的最后一位给tmpx成了12332,tmp成了1,tmp小于x。下一次x成了1233,tmp成了12,tmp还是小于x。再下一次x成了123,tmp成了123,此时tmpx相等了,这时候也就是取出一半的时候!还有种情况是中间的数字只有一个比如12321,进行上面的步骤发现x等于tmp / 10的时候也就是取出一半的时候。所以根据这个方法,当tmp >= x的时候停止循环,比较x是否等于tmp或者等于tmp / 10,就可以判断出是否是回文数。

这个方法有一个漏洞,即不能处理最后一位是0的数。但我们知道最后一位是0的数除了0自己,都不是回文数,所以在开头判断一下就行了。

3. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef int bool;
#define true 1
#define false 0

bool isPalindrome(int x) {
    if (x < 0 || (x != 0 && x % 10 == 0)) {
        return false;
    }

    int tmp = 0;
    while(x > tmp) {
        tmp = tmp * 10 + x % 10;
        x /= 10;
    }

    if (x == tmp || x == tmp / 10) {
        return true;
    }
    else {
        return false;
    }
}

int main() {
    if (isPalindrome(12321) == true) {
        printf("Bingo\n");
    }

    system("pause");
    return 0;
}
Last modification:September 8th, 2019 at 08:24 pm