【一文解决】回文数的三种解法(来源:力扣腾讯精选50题)
【一文解决】回文数(来源:力扣腾讯精选50题)
- 题目描述
- 分析
- 解法一:转字符串判断
- 解法二:取数字首尾进行判断
- 解法三:反转数字后半段
今天做到了一道简单但是有点意思的题,跟我来一起看看吧!
在开始今天的题目之前,记得动动手指给我点个赞哦!
题目描述
给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。
回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
例如,121 是回文,而 123 不是。
分析
一拿到题目,第一个想法是把数字转换为字符串,然后再判断字符串是否是回文即可。
这个思路很容易就能想到但是空间复杂度会比较高。
于是可以考虑从数的角度出发:
- 按照回味的思想,取数的首位和末尾,一一比较
- 将数进行反转,再比较。但是从数的范围考虑,反转整个数可能会导致溢出,而根据回文数的特点,我们可以只反转数字的后半部分,再与前半部分的数比较是否相等即可。
另外:通过题目给出的例子,
- 可以判定负数一定不是回文数,我们可以先剔除。
- 末尾是0的数一定不是回文数(因为高位不可能是0)0除外
//根据例子可直接得出if (x < 0 || (x % 10 == 0 && x != 0)) return false;
下面给出该题的三种解法及Java代码)
解法一:转字符串判断
这个很简单了,直接上代码!
public boolean isPalindrome(int x) { String s = String.valueOf(x); int left = 0; int right = s.length() - 1; while (left < right){ if (s.charAt(left) == s.charAt(right)){ left++; right--; }else { return false; } } return true; }
解法二:取数字首尾进行判断
数字的末位很好取,关键在于首位如何取?
方法一:
我们可以令一个数不断除10,最后这个数为0,而变为0之前,拿到的那个数就是首位,所以应该执行如下操作:
- 循环除10
- 结束条件:数变为0之前,即 x / 10 > 0
方法二:(其实大同小异)
让这个数 x 除1、10、100、1000……直到这个数 x 小于10。
下面采用方法二。
之后就是依次比较。
- 取首位和末位进行比较
- 去掉首位,去掉末位,注意:此时去掉了两位,最高位要降低两位(除以100)
- 循环,注意循环条件是 x > 9
上代码!
public boolean isPalindrome(int x) { if (x < 0 || (x % 10 == 0 && x != 0)) return false; //找最高位 int high = 1; while (x / high > 9){ high *= 10; } //分别去首位和末尾进行判断 while (x > 0){ int h = x / high; int l = x % 10; if (h != l) return false; x %= high;//去掉最高位 x /= 10;//去掉最低位 high /= 100;//去掉两位后,新的最高位降低两位 } return true; }
解法三:反转数字后半段
这个解法要注意的地方是:
- 如何判断已经反转了后半段?(循环在哪里结束)
- 区分奇偶情况
下面直接画图解释:
上图可知,判断循环结束的条件就是反转后的数≥新的数。
红框相等,则返回true,否则返回false.
下面上代码!
public boolean isPalindrome(int x) { if (x < 0 || (x % 10 == 0 && x != 0)) return false; int num = 0; while ( num < x){ num = (num * 10) + (x % 10);//拼接反转的数 x /= 10; } return x == num || x == num / 10; }
以上就是关于回文数的三个讲解啦!!
三个讲解的思路依次从一般逐渐提高,
但是其实并不复杂,代码的细节处只要考虑到就好了。
如果你觉得文章对你有用,记得一键三连哦~~
文章思路和代码参考力扣题解,在此真诚感谢各路大佬的领路!