内容简介：给定一个整型数，判断这个数是否为回文数我们根据例子很容易得出，负数不是回文数，一位正整数肯定是回文数。
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。
总结
虽然是一道看起来非常简单的题目，用转换成字符串的方式实现可能花不了几分钟的时间，但是不用字符串转换的方式要花点时间琢磨。这一题完整实现下来我自己也有新的收获，挺开心的。
参考资料
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
家事的撫慰（下冊）
Cheryl Mendelson / 甘錫安 / 大家出版社 / 2014-1-28 / NT$520
家事界暢銷參考書籍 各大媒體一致盛讚 亞馬遜讀者四星半高度評鑑 誠品、博客來、香港誠品 三選書 家務界經典暢銷書│各大媒體一致盛讚│讀者四星半高度評鑑 「這個世代最重要的家事著作！」──《大西洋月刊》 恢復家務打理者應有的地位，賦予應有的尊嚴和價值。 以生理的勞動、心力的投入，以及正確的持家知識，換得情感上的溫暖與安全。 ．家裡空氣有異味，用香味來......一起来看看 《家事的撫慰（下冊）》 这本书的介绍吧!
图片转BASE64编码
在线图片转Base64编码工具
HEX HSV 转换工具
HEX HSV 互换工具