内容简介：给定一个整型数，判断这个数是否为回文数我们根据例子很容易得出，负数不是回文数，一位正整数肯定是回文数。
https://leetcode.com/problems/palindrome-number/
给定一个整型数，判断这个数是否为回文数
我们根据例子很容易得出，负数不是回文数，一位正整数肯定是回文数。
Solution1
首先用最简单的方法，把数字转换成字符串，从两边向中间依次判断对应位的数字是否相等。
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) {
return false;
}
if( x == 0) {
return true;
}
std::string str = to_string(x);
int middle = str.length()/2;
for (int i = 0; i < middle; ++i) {
if(str[i] != str[str.length() - 1 - i]) {
return false;
}
}
return true;
}
};
Solution2
题目的最后问能否不通过转换成字符串的方式解决这个问题，那就尝试一下吧。不通过字符串，其实我们还是要从两边到中间依次比较对应位的数字。那么问题来了，如何依次取得左右两边的数字呢？
我们以 12341 这个数字为例，想要获得最低位数字 1 很简单只要 12341 % 10
就得到了。那么如何获得最高位数字 1 呢？我们发现 12345/10000 -> 1
，也就是说用这个数除以 10^4
就行了，其中的 4 是 12341 的位数 5 减去 1。我们可以通过循环 / 10
的方式取得一个数字的位数。
12341 % 10 -> 1 12341 / (10 ^ 4) -> 1
当我们比较取得的最高位和最低位之后，发现是相等的，要继续循环，需要把原来的这个数字掐头去尾。我们来看看如何实现：
12341 % (10 ^ 4) -> 2341 2341 / 10 -> 234
也就是说，我们可以通过把这个数先 % (10 ^ 4)
再 / 10
来实现掐头去尾。
上完整代码：
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) {
return false;
}
if( x < 10) {
return true;
}
int div = 1;
int x1 = x;
while(x1 >= 10) {
div *= 10;
x1 /= 10;
}
while (x > 0) {
int l = x / div;
int r = x % 10;
if (l != r) {
return false;
}
x = x % div / 10;
div /= 100;
}
return true;
}
};
这里我们考虑一种特殊情况，比如 x 是 100341，那么掐头去尾之后，x 变成了 34，而不是 0034，这会不会对我们的结果造成影响呢？
我们发现执行第二次循环的时候 div = 10000
，那么 34 / 10000 -> 0
，也就是说我们还是取到了正确的数字 0 而不是3 。这得益于我们保留了之前的 div 的值然后每次 / 100
，而不是每次都重新计算 x 的位数。
执行第三次循环的时候 x = 3, div = 100
，那么 3 / 100 -> 0
，我们依然取得了正确的数字，也就是说我们上面的解法是正确的。
提交之后成功通过，运行时间 44 ms。
Solution2 优化
我们观察一下上面解法中获取 x 位数的部分：
int div = 1;
int x1 = x;
while(x1 >= 10) {
div *= 10;
x1 /= 10;
}
我们发现我们每次运算的时候都要把 div * 10
然后把 x1 / 10
。那为什么不把这两部分结合起来直接用 while(x / div >= 10)
来当循环条件呢？
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) {
return false;
}
if( x < 10) {
return true;
}
int div = 1;
while(x / div >= 10) {
div *= 10;
}
while (x > 0) {
int l = x / div;
int r = x % 10;
if (l != r) {
return false;
}
x = x % div / 10;
div /= 100;
}
return true;
}
};
再提交一下，这次的运行时间是 32 ms。
总结
虽然是一道看起来非常简单的题目，用转换成字符串的方式实现可能花不了几分钟的时间，但是不用字符串转换的方式要花点时间琢磨。这一题完整实现下来我自己也有新的收获，挺开心的。
参考资料
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Introduction to Programming in Java
Robert Sedgewick、Kevin Wayne / Addison-Wesley / 2007-7-27 / USD 89.00
By emphasizing the application of computer programming not only in success stories in the software industry but also in familiar scenarios in physical and biological science, engineering, and appli......一起来看看 《Introduction to Programming in Java》 这本书的介绍吧!
