【开篇语】你能不将整数转为字符串来解决这个问题吗?
【leetcode-9】https://leetcode-cn.com/problems/palindrome-number/
【题目】
给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。
回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121 是回文,而 123 不是。
示例 1:
输入:x = 121
输出:true
示例 2:
输入:x = -121
输出:false
解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入:x = 10
输出:false
解释:从右向左读, 为 01 。因此它不是一个回文数。
示例 4:
输入:x = -101
输出:false
提示:
-231 <= x <= 231 - 1
【思路】
本题咱们直接进入进阶场,来考虑在不转换成字符串的情况下解题,我们的思路可以延下面几点进行:
- 基本方法上讲数字本身反转,反转后与原数比较,if 原数 == 反转数;then 通过。(这种方式会遇到整数溢出)
- 负数不是回文数。
- 考虑:if 原数前半段 == 反转数;也符合条件!用这种方式~
例如,输入 1221
,我们可以将数字“1221”的后半部分从“21”反转为“12”,并将其与前半部分“12”进行比较,因为二者相同,我们得知数字 1221
是回文。
【关键点】
- 如何得知已经取得了二分之一长度?
我们将原始数字除以 10,然后给反转后的数字乘上 10,所以,当原始数字小于等于反转后的数字时,就意味着我们已经处理了一半位数的数字。
- 奇数如何比较?
if 原数 == 反转数/10 ;
【代码】
bool isPalindrome(int x) {
if(x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while(x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
//奇数偶数都需要考虑
return x == revertedNumber || x == revertedNumber/10;
}