今天刷 LeetCode, 遇到一道简单算法题, Palindrome Number, 但解题过程比较有意思, 借此文记录下
解析题目
问题描述: Determine whether an integer is a palindrome. Do this without extra space. 判断一个 int 类型的数是否为回文数? 不使用额外空间
关于什么是回文数? 给个定义: 正反方向输出的值相等的数称为回文数 没理解到的, 可以去网上搜下
举例: 1122111211 等是回文数;-1012123323 等就不是回文数
那什么是回文字符串呢? 可以参考这篇文章算法 Longest Palindromic Substring
分析思路
理解题目后, 总共想到三个思路:
按位比较: 1. 计算整数的位数 (长度), 2. 从第一位和最后一位开始依次递增和增减循环比较
反转输入 int, 与原数比较看是否相等 之前有道题是: 反转一个 int 数, 其中需要考虑溢出问题
转成字符串, 按位比较 但题目限制不能占用额外内存
考虑使用第一种思路, 这道题比较简单, 有了思路后, 按说就可以编码了, 但为了养成好习惯, 别着急编码还是想下 case 情况先我只想到两个: 1. 负数不是回文数 2. 考虑位数奇偶数情况虽然少, 过程不能省
开始编码, 贴下我第一版代码
- public boolean isPalindrome(int x) {
- if (x <0) { // 负数情况
- return false;
- }
- final int originX = x;
- int bitCount = 1;
- // 算出有多少位 (长度)
- while (x>= 10) {
- x /= 10;
- bitCount++;
- }
- int l = 0;
- int r = bitCount - 1;
- // 依次比较
- while (getBitNum(originX, bitCount, l) == getBitNum(originX, bitCount, r)) {
- l++;
- r--;
- if (l>= r) {
- return true;
- }
- }
- return false;
- }
- // 去取原数对应位下标的数值
- int getBitNum(int num, final int len, int index) {
- int temp = 1;
- while (len - index> 1) {
- temp *= 10;
- index++;
- }
- return (num / temp) % 10;
- }
LeetCode 上类似白板编程, 代码比较龊, 请见谅编写完了自测 case, 好都没问题, 这么简单那就提交吧, 提交是通过了, 但提示该算法击败了 1.7% 的其它用户提交, 也就是说效率很差, 垫底了这样怎么行呢, 毕竟咋还是有追求的程序猿对吧于是分析代码, 其中三处循环, 还有嵌套; 估算时间复杂度为: O(nlog10n)* (ps: 时间复杂度计算, 不是很清楚, 有知道的大神请留言指教, 谢谢)
怀着焦虑的心情, 点开了官方推荐解法页面看到一半, 哎呀, 这不是上文中我想到的第二条思路吗, 反转 int 整数但官方建议只反转 int 的一半, 然后与剩下一半比较, 如果相等则是回文数这就完美避开了 Integer.MAX_VALUE 溢出问题, 不得不服
想着先不看其代码实现, 自己写一下再说, 于是在之前基础上改出了下面的代码
- boolean isPalindromeNum(int x) {
- if (x <0) {
- return false;
- }
- final int originX = x;
- int bitCount = 1;
- while (x>= 10) {
- x /= 10;
- bitCount++;
- }
- int index = 0;
- int halfNum = 0;
- final int halfLen = bitCount / 2;
- int tempX = originX;
- while (index <halfLen) {
- halfNum = halfNum * 10 + tempX % 10;
- tempX /= 10;
- index++;
- }
- // 判断奇偶情况
- return halfNum == (bitCount % 2 == 0 ? tempX : tempX / 10);
提交跑起来, 嗯快了不少, 击败了 48%, 感觉不错对吧这会去看官方给出的 C# 代码实现, 看完感觉受到一万点伤害, 吐血了不说了, 贴代码
- boolean isPalindromeNumOfficial(int x) {
- // Special cases:
- // As discussed above, when x < 0, x is not a palindrome.
- // Also if the last digit of the number is 0, in order to be a palindrome,
- // the first digit of the number also needs to be 0.
- // Only 0 satisfy this property.
- if (x < 0 || (x % 10 == 0 && x != 0)) {
- return false;
- }
- int revertedNumber = 0;
- while (x> revertedNumber) {
- revertedNumber = revertedNumber * 10 + x % 10;
- x /= 10;
- }
- // When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
- // For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,
- // since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
- return x == revertedNumber || x == revertedNumber / 10;
- }
注释写的很清楚了, 主要有三点: 1. 判断尾数为 0 的情况 2. 取消判断位数的逻辑 3. 聪明处理奇偶位数情况
小结
小小一道简单的算法题, 都能频繁带给你刺激, 是不是很过瘾想想平时我们写的代码, 是不是应该翻出来再斟酌斟酌, 哈哈哈
最后贴下转字符串思路实现的代码
- // 转字符串在比较 , 速度是很快的
- public boolean isPalindromeForString(int x) {
- String num = String.valueOf(x);
- if (num == null || num.length() == 0) return true;
- int start = 0,
- end = num.length() - 1;
- while (start < end) {
- if ((char) num.charAt(start) != (char) num.charAt(end)) return false;
- start++;
- end--;
- }
- return true;
- }
以上代码均由 Java 实现, 项目地址 https://github.com/yangjiantao/DSAA
来源: https://juejin.im/entry/5aa41ea5518825558154977e