设为首页 加入收藏

TOP

LeetCode_#9_回文数 Palindrome Number_C++题解
2019-03-14 18:08:06 】 浏览:23
Tags:LeetCode_#9_ 文数 Palindrome Number_C 题解

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;
    }
};
  • int转string在C++11中增加了全局函数to_string来支持

    参考:C++ int与string的相互转换(含源码实现)

  • 需要额外的非常量空间来创建问题描述中所不允许的字符串。

自解_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 进行回文判断

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Ubuntu下VsCode+CMake 交叉编译 下一篇loj#6030. 「雅礼集训 2017 Day1..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }