LeetCode刷题之旅【简单篇】——9.回文数
文章目录
题目
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: trueExample 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.
个人思路
方案1:转成字符串
首先,将数字转换成字符串;而后进行判断,使用循环,每次取字符串i位置字符和length-1-i位置字符进行比较(length为字符串的长度),如果不同则返回false。
下面,考虑i的取值,从0到length/2(不包括),如果length为奇数,如果给定的数字是回文数,那么跳出循环后i刚好是字符串最中间的位置,不论该位置是什么数,这个数字都是回文数;如果length为偶数,那么i在循环中最后取值为length/2-1,由于字符串计数是从0开始的,这时i和length-1-i刚好是字符串最中间的两个位置,只要比较就可以了。通过上述分析,可以看到我们并不需要进行特殊处理。
另外,从给定示例可以看到,负数均不是回文数。
下面是代码:
class Solution {
public boolean isPalindrome(int x) {
if(x < 0){
return false;
}
String str = String.valueOf(x);
int len = str.length();
for(int i = 0; i < len / 2; i++){
if(str.charAt(i) != str.charAt(len - 1 - i)){
return false;
}
}
return true;
}
}
执行结果为:
执行用时 :10 ms, 在所有 Java 提交中击败了69.46%的用户
内存消耗 :38.9 MB, 在所有 Java 提交中击败了5.14%的用户
方案二:将数据翻转
题目中有一个进阶问题:
Could you solve it without converting the integer to a string?
回文数翻转后和原数相等。我们可以将给定的数据进行翻转,如果翻转后的数字超限或者和原数不相等,则不是回文数。那么我们可以用上整数反转这里的成果:
class Solution {
public boolean isPalindrome(int x) {
if(x < 0){
return false;
}
if(reverse(x)==x){
return true;
} else {
return false;
}
}
public static int reverse(int x){
int result = 0;
while(x!=0){
if(x>0 && result > (Integer.MAX_VALUE-x%10)/10)
return 0;
result = result * 10 + x % 10;
x = x / 10;
}
return result;
}
}
执行结果为:
执行用时 :10 ms, 在所有 Java 提交中击败了69.46%的用户
内存消耗 :39 MB, 在所有 Java 提交中击败了5.14%的用户
其他思考
方案三:翻转一半
看了一下讨论区的思路,官方说,我们可以将数只翻转一半。这里特别讨厌的是,需要将10的倍数特殊处理>-<别扭得很
class Solution {
public boolean isPalindrome(int x) {
if(x < 0){
return false;
}
if(x % 10 == 0 && x > 0)
return false;
int xr = 0;
while(x > xr){
xr = xr * 10 + x % 10;
x = x / 10;
}
return xr == x || xr / 10 == x;
}
}
执行结果为:
执行用时 :9 ms, 在所有 Java 提交中击败了99.22%的用户
内存消耗 :39.1 MB, 在所有 Java 提交中击败了5.14%的用户
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论