LeetCode Notes_#9 Palindrome Number(包含#7 Reverse Integer)
Contents
Problem
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.Follow up:
Coud you solve it without converting the integer to a string?
Solution
1.转换成字符串处理
转换成str,然后翻转，再去判断是否相同
class Solution(object): def isPalindrome(self, x): """ :type x: int :rtype: bool """ if x<0: return false reverse="" y=str(x)#转化成字符串类型 for i in range(len(y)): reverse[len(y)-1-i]=y[i]#这一句是不对的，str类型不支持这么用 if y==reverse: return true else: return false
所以字符串要如何处理呢？虽然可以通过索引值去访问，但是不可以通过这样去修改
稍微改一改有问题的那句：
class Solution(object): def isPalindrome(self, x): """ :type x: int :rtype: bool """ if x<0: return False reverse="" y=str(x)#转化成字符串类型 for i in range(len(y)): reverse=reverse+y[len(y)-1-i]#不要去赋值改变原本的字符串，而是通过字符串拼接运算，反过来拼接即可 if y==reverse: return True else: return False
一轮循环,复杂度是
，但是转换成字符串可能本身就会慢很多吧，原来是int型无论多大的数字都是2Byte(or 4Byte?),但是转成字符串之后就是 2n(4n) Byte,因为每位数字单独存储，时间复杂度和空间复杂度应该都会多一些（我猜的...）
2.初等运算求反转后的数字
不转化为str类型的话，转化成列表？感觉其实没有好太多，最好能够直接通过初等运算，算出他的反转之后的数字
这就是之前做到的另外一个题了#7.ReverseInteger,顺便一起总结了吧 class Solution(object): def isPalindrome(self, x): """ :type x: int :rtype: bool """ if x<0: return False m=x#m是临时变量 tmpDigit=m%10 reverse=0 while(m!=0): tmpDigit=m%10#取出每一位数字，从个位开始 reverse=tmpDigit+reverse*10#先左移一位，然后加上原数字更靠前的一位，这样个位左移到最左边 m=m/10 if reverse==x: return True else: return False
这个过程理解了之后其实很形象，重点就在于while循环里边的三行代码，以输入123为例，重现一下整个过程：
123 123 123 3 32 321
取出原数最后一位->原数最后一位加入临时反转数->临时反转数左移一位，继续取原数的倒数第二位->...以此类推
3.其他思路
看讨论discussion又发现了一些别的思路，但是总的来说大致思路一样，官方题解里面的解答，大概意思是说，假如是回文数，那么一定是对称的，比如121,1221,那么我可以只考虑后一半和前一半是否相同即可，利用对称性节省了时间
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; }} 相关的Python知识
字符串str类型：
注意：python只有字符串str类型，却没有字符char类型，所以说把字符拆开来处理是不行的