原题描述
+
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。但你不能使用转字符串后判断的方法。
示例 1
输入:121
输出:true
示例 2
输入:-121
输出:false
示例 3
输入:10
输出:false
原题链接:https://leetcode-cn.com/problems/palindrome-number
思路解析
+
这是一道简单题,通过率在50%以上。
其实字符串转数字的方式反而麻烦。在之前的LeetCode题目7:整数反转中你已经知道了怎么把一个整数数字做反转,现在依然可以利用它来做回文判断。
示例中你已经知道了有两种情况是不可能返回true的:
1. 负数;
2. 尾数为0的数。
那么你可能还需要知道的是,回文的判断只需要搜索一半数字即可。比如4554,当你不断把尾数截取,并迭代构造反转整数的过程中,一定会经历下面的过程:
origin: 4554 -> 455 -> 45 -> 4 -> 0
reverted: 0 -> 4 -> 45 -> 455 -> 4554
其实revert反转到45的时候,就可以停下来了。因为此时origin正是整数前半部分,如果是回文,那么reverted和origin应该是相等的。
另外你需要注意的是:奇数位的整数是否是回文与正中间的数字无关。
好了,自己写写代码试试吧~
复杂度分析
+
C++参考代码
+
public:
bool isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0))
return false;
int revert = 0;
while(x > revert) {
revert = revert * 10 + x % 10;
x /= 10;
}
return revert == x || revert / 10 == x ? true: false;
}
};