欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode_#9_回文数 Palindrome Number_C++题解

程序员文章站 2022-10-06 13:38:52
9. 回文数 Palindrome Number 题目描述 Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. 判断一 ......

9. 回文数 palindrome number

题目描述

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.
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

example 3:

input: 10
output: false

explanation: reads 01 from right to left. therefore it is not a palindrome.
解释: 从右向左读, 为 01 。因此它不是一个回文数。

follow up 进阶

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

你能不将整数转为字符串来解决这个问题吗?

自解_string

class solution {
public:
    bool ispalindrome(int x) {
        if (x < 0) return false;
        string ori = to_string(x);
        for (int i = 0; i < ori.length() / 2 + 1; i++){
            if (ori[i] != ori[ori.length()-i-1])
                return false;
        }
        return true;
    }
};

自解_long

class solution {
public:
    bool ispalindrome(int x) {
        if (x < 0) return false;
        int ori = x;
        long long rev = 0;
        while (x > 0){
            rev = rev * 10 + x % 10;
            x = x / 10;
        }
        return rev == ori? true : false;
    }
};

参考官方题解_翻转一半

class solution {
public:
    bool ispalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int rev = 0;
        while (x > rev){
            rev = rev * 10 + x % 10;
            x = x / 10;
        }
        return rev == x || rev / 10 == x;
    }
};

反转后的数字大于int_max时,将遇到整数溢出问题。考虑只反转 int 数字的一半,如果该数字是回文,其后半部分反转后应该与原始数字的前半部分相同。

  • 反转后半部分的数字的方法与第7题基本一致,当原始数字小于反转后的数字时,就意味着我们已经处理了一半位数的数字。
  • 处理特殊情况:x < 0;数字的最后一位是 0,第一位数字也是 0 的只有 0 满足
  • 当数字长度为奇数时,由于处于中位的数字不影响回文(它总是与自己相等),可以通过 rev / 10 将其去除。
各种情况验证
  • 数字长度为奇数时,最后循环结束一定为 rev 比 x 多一位,由 rev / 10 == x 进行回文判断
  • 数字长度为偶数时,当循环到rev与x位数相等时
    • 若 x > rev,此时 x 不是回文,但符合循环条件继续进入循环,使得 rev 较 x 多两位,由 rev == xrev / 10 == x 进行回文判断, 均不成立,判断正确
    • 若 x <= rev,跳出循环,二者位数相等,由 rev == x 进行回文判断