题解 | #回文数字#
回文数字
http://www.nowcoder.com/practice/35b8166c135448c5a5ba2cff8d430c32
算法思想一：双指针
解题思路：
1、特殊情况，当 x<0 时，直接返回 false
2、将 x 转换为字符串，设置双指针left 指向第一个数字，right 指向最后一位数字
3、对比 left、right指向的数字是否相同
1、不同则直接返回 false
2、相同，则left++，right--，循环步骤 3
4、当left >= right 停止循环，返回 True
代码展示：
Python版本
class Solution: def isPalindrome(self , x ): # write code here if x < 0: return False tmp = str(x) # 定义双指针 left = 0 right = len(tmp)-1 # 循环跳出条件 while left < right: if tmp[left] == tmp[right]: # 对比 left += 1 right -= 1 else: return False return True
复杂度分析
时间复杂度O(N)：N表示数字的位数，遍历整个数字位数
空间复杂度O(N)：数字转换为字符串
算法思想二：数字解法
解题思路：
通过取整和取余操作获取整数中对应的数字进行比较。例如：1221 这个数字。
通过计算 1221 / 1000， 得首位1
通过计算 1221 % 10， 可得末位 1
进行比较
再将 22 取出来继续比较
图解：
代码展示：
JAVA版本
import java.util.*;
public class Solution {
/**
*
* @param x int整型
* @return bool布尔型
*/
public boolean isPalindrome (int x) {
// write code here
// 边界判断
if (x < 0) return false;
int div = 1;
//
while (x / div >= 10) div *= 10;
// 循环停止
while (x > 0) {
int left = x / div;
int right = x % 10;
// 如果不同则表示不是回文
if (left != right) return false;
x = (x % div) / 10;
div /= 100;
}
return true;
}
} 复杂度分析
时间复杂度O(N)：N表示数字的位数
空间复杂度O(1)：额外常数空间
算法思想三：普通解法
解题思路：
最好理解的一种解法就是先将 整数转为字符串 ，然后将字符串与翻转后的字符串对比，相同则是回文，不同则不是代码展示：
Python版本
# class Solution: def isPalindrome(self , x ): # write code here x = str(x) return x == x[::-1]
复杂度分析
时间复杂度O(N)：N表示数字的位数，遍历整个数字位数
空间复杂度O(N)：数字转换为字符串
投递中国农业发展银行等公司10个岗位 >
