Palindrome Number
一 问题描述
Palindrome Number
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up:
Coud you solve it without converting the integer to a string?
翻译:
判定一个整数是不是回文串。一个是否是回文串取决于正着读或反着读是否一样。
二 解法
1. 第一解法(个人,转换字符串)
分析:
将数字转换成字符串数组之后,从两端往中间比较,很容易得出结论。
代码:
var isPalindrome = function(x) {
let str = x.toString().split("");
let len = str.length - 1;
let mid = str.length / 2;
for (let i = 0; i <= mid; i++) {
if (str[i] !== str[len - i])
return false
}
return true;
};
2. 第二解法(个人,非转字符串)
分析:
将数字通过数学计算生成一个相反排列的数字,与原数字比较即可。这时候,需要先判断是否是负数。并且,js中整数除法可以除出来小数,因此需要使用Math.floor()方法向下取整。
代码:
var isPalindrome = function(x) {
let num = x;
let arc = 0;
if (x < 0)
return false;
while (num >= 10) {
arc *= 10;
arc += num % 10;
num = Math.floor(num /10);
}
arc = arc * 10 + num;
return arc === x;
};
3. 第三解法(个人,最优,非转字符串)
分析:
上述的通过数学计算,从头到尾完全反转,但实际上,是不需要这样的。回文串判断只需要前后半段比较。因此,通过新设置一个arc变量存储后半段数字,然后比较x是否大于arc,只要大于arc,就和前面的逻辑一样,一直生成后半段反转数字。
之后,判断有两个标准:
- 是否相等,如果相等, 必定是回文串
- 前半段此时已经小于后半段,说明,如果前半段乘10加上后半段的个位数如果和后半段相等,也可以判定为回文串。
注:这种判断方法不能正确处理0的问题。例如x = 10,x = 100。因为0 * 10 = 0。会干扰判断。因此在一开始需要排除掉这种情况。这种情况有两个特征,首先是x % 10 === 0,其次是x !== 0。
代码:
var isPalindrome = function(x) {
let num = x;
let arc = 0;
if (x < 0 || x % 10 === 0 && x !== 0)
return false;
while (num > arc) {
arc *= 10;
arc += num % 10;
num = Math.floor(num /10);
}
if(arc === num || num * 10 + arc % 10 === arc)
return true;
return false;
};
结果:
11509 / 11509 test cases passed.
Status: Accepted
Runtime: 164 ms
Memory Usage: 45.3 MB
Runtime:faster than 98%
By DoubleJan
2019.7.7
上一篇: Leetcode C#答案(自编)
下一篇: Python基础知识 day2