009. 回文数 | Leetcode题解
16lz
2021-01-22
题目描述:
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗？
难度：
- 难度：简单
- 支持语言：JavaScript、Java、Python
相关标签
- 数学
相关企业
- 阿里
- 京东
- 拼多多
思路 1（javascript）:
- 使用字符串就是判断回文字符串，很简单。
- 而不是用字符串就是
NO.7，反转一个数字，然后比较它们是否相等； - 注意：如果遇到负数直接返回
false。
思路 2:
- 使用除法和求余获得对应位置的数字，无字符串操作。
- 首先获取当前数量级
n，公式 n=10⌊log10x⌋n=10^{\left \lfloor\log_{10}{x}\right\rfloor}n=10⌊log10x⌋，如：x = 24, n = 10;x = 6234, n = 1000。 - 通过
x / n获取首位。 - 通过
x % 10获取末位。 (x % n) / 10去除首位和末位，（x % n去除首位，x / 10去除末位），x 位数减 2。n /= 100x 位数减 2， 故n需要除 10210^2102。
- 以 123421 为例，运算过程如下:
| x | n | x / n | x % 10 |
|---|---|---|---|
| 123421 | 100000 | 1 | 1 |
| 2342 | 1000 | 2 | 2 |
| 34 | 10 | 3 | 4 |
思路 3:
- 对于数字的末位，直接取余就可以了，对于数字的首位，我们可以这么算。
- 首先用一个变量记录数字的最高位，
- 比如
1232112321，可以标记 help 为1000010000， - 第一个末位为
11，第一个首位为12321/10000=1， - 接下来我们需要计算
232232是否为回文，怎么计算呢？ - 我们需要去掉首位和末位。
- 可以采用
x % help / 10的方式 12321%10000==2321可以将最高位去掉，然后 2321/10==232 可以将最低为去掉。- 最后不要忘记将
help/100。
思路 3 (py):
- 转成字符串: a. 双向队列 b. 双指针
- 不转字符串: a. 模拟字符串的双向队列(使用math库的log函数 获取整数的位数) b. 反转后面一半的整数(使用math库的log函数 获取整数的位数) c. 反转后面一半的整数(不适用log函数) (通过原整数x 与 reverse_x 的大小判断)
复杂度分析
- 时间复杂度：O(\log n)O(logn)，对于每次迭代，我们会将输入除以 1010，因此时间复杂度为 O(\log n)O(logn)。
- 空间复杂度：O(1)O(1)。我们只需要常数空间存放若干变量。
代码
JavaScript 实现
/**
* @来源：Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
if(x<0)return false
let n=x
let rev=0
while(n>0){
let t=n%10
rev=rev*10+t
n=~~(n/10)
}
return rev===x
};
/**
* @作者：lvshanke
* @链接：https://leetcode-cn.com/problems/palindrome-number/solution/zhi-xing-yong-shi-chao-guo-9496nei-cun-xiao-hao-ch/
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
if(x < 0) return false;
if(x < 10) return true;
let right = 1;
let left = 0;//初始为 x的总位数
let sum = x;
while(sum >= 1){//算出总位数
sum /= 10;
left++;
}
//获取第n位的数
let getNum = (_x, n) => {
return Math.floor(_x % Math.pow(10, n) / Math.pow(10, n - 1));
}
while(left > right){
if(getNum(x, left) != getNum(x, right)) return false;
left--;
right++;
}
return true;
};
/**
* @作者：Alexer-660
* @链接：https://leetcode-cn.com/problems/palindrome-number/solution/9-hui-wen-shu-jiang-ti-jie-fu-zhi-dao-liu-lan-qi-k/
*/
var isPalindrome = function(x) {
if(x<0 || (x%10 == 0 && x!=0)){
return false;
}
var reverseNumber = 0;
while(x>reverseNumber){
reverseNumber = reverseNumber*10 + x%10;
x = parseInt(x/10);
}
return x == reverseNumber || x == parseInt(reverseNumber/10)
};
Java 实现
/**
* @作者：MisterBooo
* @链接：https://leetcode-cn.com/problems/palindrome-number/solution/dong-hua-hui-wen-shu-de-san-chong-jie-fa-fa-jie-ch/
*/
class Solution {
public boolean isPalindrome(int x) {
//思考：这里大家可以思考一下，为什么末尾为 0 就可以直接返回 false
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
return x == revertedNumber || x == revertedNumber / 10;
}
}
/**
* @作者：reedfan
* @链接：https://leetcode-cn.com/problems/palindrome-number/solution/ji-bai-liao-99de-javayong-hu-dai-ma-you-ya-by-reed/
*/
public boolean isPalindrome(int x) {
if (x < 0) {
return false;
}
int help = 1;
int tmp = x;
while (tmp >= 10) {
help *= 10;
tmp /= 10;
}
while (x != 0) {
if (x % 10 != x / help) {
return false;
}
x = x % help / 10;
help /= 100;
}
return true;
}
Python 实现
# 作者：kerwin-2wghdeNo1V
#链接：https://leetcode-cn.com/problems/palindrome-number/solution/jing-xin-hui-zong-python3de-5chong-shi-xian-fang-f/
class Solution:
# 方法一: 将int转化成str类型: 双向队列
# 复杂度: O(n^2) [每次pop(0)都是O(n)..比较费时]
def isPalindrome(x: int) -> bool:
lst = list(str(x))
while len(lst) > 1:
if lst.pop(0) != lst.pop():
return False
return True
# 方法二: 将int转化成str类型: 双指针 (指针的性能一直都挺高的)
# 复杂度: O(n)
def isPalindrome(x: int) -> bool:
lst = list(str(x))
L, R = 0, len(lst)-1
while L <= R:
if lst[L] != lst[R]:
return False
L += 1
R -= 1
return True
# 方法三: 进阶:不将整数转为字符串来解决: 使用log来计算x的位数
# 复杂度: O(n)
def isPalindrome(self, x: int) -> bool:
"""
模仿上面字符串的方法:分别取'第一位的数'与'第二位的数'对比
(弊端是:频繁计算,导致速度变慢)(下面的方法三只反转一半数字,可以提高性能)
"""
if x < 0:
return False
elif x == 0:
return True
else:
import math
length = int(math.log(x, 10)) + 1
L = length-1
print("l = ", L)
for i in range(length//2):
if x // 10**L != x % 10:
return False
x = (x % 10**L) //10
L -= 2
return True
# 方法四: 进阶:不将整数转为字符串来解决: 使用log来计算x的位数
# 复杂度: O(n)
def isPalindrome(self, x: int) -> bool:
"""
只反转后面一半的数字!!(节省一半的时间)
"""
if x < 0 or (x!=0 and x%10==0):
return False
elif x == 0:
return True
else:
import math
length = int(math.log(x, 10)) + 1
reverse_x = 0
for i in range(length//2):
remainder = x % 10
x = x // 10
reverse_x = reverse_x * 10 + remainder
# 当x为奇数时, 只要满足 reverse_x == x//10 即可
if reverse_x == x or reverse_x == x//10:
return True
else:
return False
# 方法五: 进阶:不将整数转为字符串来解决: 不使用log函数
# 复杂度: O(n)
def isPalindrome(self, x: int) -> bool:
"""
只反转后面一半的数字!!(节省一半的时间)
"""
if x < 0 or (x!=0 and x%10==0):
return False
elif x == 0:
return True
else:
reverse_x = 0
while x > reverse_x:
remainder = x % 10
reverse_x = reverse_x * 10 + remainder
x = x // 10
# 当x为奇数时, 只要满足 reverse_x//10 == x 即可
if reverse_x == x or reverse_x//10 == x:
return True
else:
return False
x = 10
x = 10001
print(Solution().isPalindrome(x))
其他
- 原题leetcode链接：https://leetcode-cn.com/problems/string-to-integer-atoi/
- 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
- 说明：leetcode 题解 | 每日一题
更多相关文章
- 012. 整数转罗马数字 | Leetcode题解
- 008. 字符串转换整数 (atoi) | Leetcode题解
- 007. 整数反转 | Leetcode题解
- 输入一个整数减去6的结果
- 输入两个整数调用puts函数，求两个整数的乘积
- 输入两个整数求他们的和，差，积，商
- 在解释语言上使用非常大的整数时，会产生意想不到的结果。
- PHP平均整数红包算法
- 如何从0-X的PHP中获得一个加密的强整数?
随机推荐