算法习题篇之Palindrome

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?

判断一个数是不是回文数，这个数从前面和从后面读起来都一样。

你能够不把这个数转化为字符串来进行判断嘛！

思路很简单，如果是负数肯定不对，是个位数为true；

其他的情况，先算出位数，然后对比相应位置的数是否相等就OK了

接下来就是我的垃圾代码；

class Solution { public boolean isPalindrome(int x) { if(x<0){ return false; } if(x<10){ return true; } int n=1; int temp = x; for(int i =1 ;i<=10;i++){ temp = temp/10; if(temp>0){ n++; }else { break; } } for(int i = 1;i<=n/2;i++){ int temp1 = (int)(x%java.lang.Math.pow(10,i)); int temp2 =(int) (x%java.lang.Math.pow(10,n+1-i)); if(temp1==0||temp2==0){ if(temp1!=0||temp2!=0){ return false; } } int temp3 = (int)(java.lang.Math.pow(10,(i-1))); int temp4 = (int)(java.lang.Math.pow(10,(n-i))); if(temp1/temp3!=temp2/temp4){ return false; } } return true; } }

当然还是有大神的干货的，但是差评比着好评多就不知道为什么了，反正比我写的好就对了，

然后代码如下，思路很简单，设置一个新数y，从x的最后一位开始复制，直到y的值比着x大，循环结束

然后比较x和y。 或x和y/10 是否相等就ok了。

public class Solution { public bool IsPalindrome(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; } }

比较清晰的一个思路：

设置一个list集合把x的每一位放到集合里，嗯在比较就OK了！

class Solution { public boolean isPalindrome(int x) { if(x < 0){ return false; } else if(x < 10){ return true; } ArrayList<Integer> original = new ArrayList<Integer>(); while(x > 0){ int remainder = x % 10; original.add(remainder); x = x / 10; } int left = 0; int right = original.size() - 1; while(left < right){ if(original.get(right) != original.get(left)){ return false; } left++; right--; } return true; } }

ok 这道简单的题也就分析到这里了。