|
| 1 | +#LeetCode 第 9 号问题：回文数 |
| 2 | + |
| 3 | +>本文首发于公众号「五分钟学算法」，是[图解 LeetCode](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。 |
| 4 | +> |
| 5 | +>个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com) |
| 6 | +
|
| 7 | + |
| 8 | + |
| 9 | +题目来源于 LeetCode 第 9 号问题：回文数。题目难度为 Easy，目前通过率为 56.0%。 |
| 10 | + |
| 11 | +##题目描述 |
| 12 | + |
| 13 | +判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 |
| 14 | + |
| 15 | +**示例 1:** |
| 16 | + |
| 17 | +``` |
| 18 | +输入: 121 |
| 19 | +输出: true |
| 20 | +``` |
| 21 | + |
| 22 | +**示例 2:** |
| 23 | + |
| 24 | +``` |
| 25 | +输入: -121 |
| 26 | +输出: false |
| 27 | +解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 |
| 28 | +``` |
| 29 | + |
| 30 | +**示例 3:** |
| 31 | + |
| 32 | +``` |
| 33 | +输入: 10 |
| 34 | +输出: false |
| 35 | +解释: 从右向左读, 为 01 。因此它不是一个回文数。 |
| 36 | +``` |
| 37 | + |
| 38 | +**进阶:** |
| 39 | + |
| 40 | +你能不将整数转为字符串来解决这个问题吗？ |
| 41 | + |
| 42 | + |
| 43 | + |
| 44 | +##题目解析 |
| 45 | + |
| 46 | +###解法一：普通解法 |
| 47 | + |
| 48 | +最好理解的一种解法就是先将**整数转为字符串** ，然后将字符串分割为数组，只需要循环数组的一半长度进行判断对应元素是否相等即可。 |
| 49 | + |
| 50 | +####动画描述 |
| 51 | + |
| 52 | + |
| 53 | + |
| 54 | +####代码实现 |
| 55 | + |
| 56 | +```java |
| 57 | +///简单粗暴，看看就行 |
| 58 | +classSolution { |
| 59 | +publicbooleanisPalindrome(intx) { |
| 60 | +String reversedStr= (newStringBuilder(x+"")).reverse().toString(); |
| 61 | +return (x+"").equals(reversedStr); |
| 62 | + } |
| 63 | +} |
| 64 | +``` |
| 65 | + |
| 66 | + |
| 67 | + |
| 68 | +###解法二：进阶解法---数学解法 |
| 69 | + |
| 70 | +通过取整和取余操作获取整数中对应的数字进行比较。 |
| 71 | + |
| 72 | +举个例子：1221 这个数字。 |
| 73 | + |
| 74 | +- 通过计算 1221 / 1000， 得首位1 |
| 75 | +- 通过计算 1221 % 10， 可得末位 1 |
| 76 | +- 进行比较 |
| 77 | +- 再将 22 取出来继续比较 |
| 78 | + |
| 79 | +####动画描述 |
| 80 | + |
| 81 | + |
| 82 | + |
| 83 | +####代码实现 |
| 84 | + |
| 85 | +```java |
| 86 | +classSolution { |
| 87 | +publicbooleanisPalindrome(intx) { |
| 88 | +//边界判断 |
| 89 | +if (x<0)returnfalse; |
| 90 | +int div=1; |
| 91 | +// |
| 92 | +while (x/ div>=10) div*=10; |
| 93 | +while (x>0) { |
| 94 | +int left= x/ div; |
| 95 | +int right= x%10; |
| 96 | +if (left!= right)returnfalse; |
| 97 | + x= (x% div)/10; |
| 98 | + div/=100; |
| 99 | + } |
| 100 | +returntrue; |
| 101 | + } |
| 102 | +} |
| 103 | +``` |
| 104 | + |
| 105 | + |
| 106 | + |
| 107 | +###解法三：进阶解法---巧妙解法 |
| 108 | + |
| 109 | +直观上来看待回文数的话，就感觉像是将数字进行对折后看能否一一对应。 |
| 110 | + |
| 111 | +所以这个解法的操作就是**取出后半段数字进行翻转**。 |
| 112 | + |
| 113 | +这里需要注意的一个点就是由于回文数的位数可奇可偶，所以当它的长度是偶数时，它对折过来应该是相等的；当它的长度是奇数时，那么它对折过来后，有一个的长度需要去掉一位数（除以 10 并取整）。 |
| 114 | + |
| 115 | +具体做法如下： |
| 116 | + |
| 117 | +- 每次进行取余操作 （ %10），取出最低的数字：`y = x % 10` |
| 118 | +- 将最低的数字加到取出数的末尾：`revertNum = revertNum * 10 + y` |
| 119 | +- 每取一个最低位数字，x 都要自除以 10 |
| 120 | +- 判断`x` 是不是小于`revertNum` ，当它小于的时候，说明数字已经对半或者过半了 |
| 121 | +- 最后，判断奇偶数情况：如果是偶数的话，revertNum 和 x 相等；如果是奇数的话，最中间的数字就在revertNum 的最低位上，将它除以 10 以后应该和 x 相等。 |
| 122 | + |
| 123 | +####动画描述 |
| 124 | + |
| 125 | + |
| 126 | + |
| 127 | +####代码实现 |
| 128 | + |
| 129 | +```java |
| 130 | +classSolution { |
| 131 | +publicbooleanisPalindrome(intx) { |
| 132 | +//思考：这里大家可以思考一下，为什么末尾为 0 就可以直接返回 false |
| 133 | +if (x<0|| (x%10==0&& x!=0))returnfalse; |
| 134 | +int revertedNumber=0; |
| 135 | +while (x> revertedNumber) { |
| 136 | + revertedNumber= revertedNumber*10+ x%10; |
| 137 | + x/=10; |
| 138 | + } |
| 139 | +return x== revertedNumber|| x== revertedNumber/10; |
| 140 | + } |
| 141 | +} |
| 142 | +``` |
| 143 | + |
| 144 | + |
| 145 | + |
| 146 | + |