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 == x
与rev / 10 == x
进行回文判断, 均不成立,判断正确 - 若 x <= rev,跳出循环,二者位数相等,由
rev == x
进行回文判断
- 若 x > rev,此时 x 不是回文,但符合循环条件继续进入循环,使得 rev 较 x 多两位,由
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/604818.html