leetcode打卡16：题号9——回文数

题目：

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121 输出: true 示例 2:

输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3:

输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。 进阶:

你能不将整数转为字符串来解决这个问题吗？

题目理解：

这道题其实很简单，大多数人会想到直接用字符串的方式去实现即可，将int转为String，之后判断首位是否相等，此方法的时间复杂度是o（n） 还有一个想法就是直接将int整数反转，然后判断两个数等不等，但是整个整数反转的话可能会出现溢出的情况，所以这个方法需要注意这个地方 但是实际上我们可以使用反转一半整数的方法去实现，也就是将后半段的整数反转，然后直接判断与前半段的整数是否相等

解法一（字符串）：

先判断是否为负数，如果是的话直接返回false 之后将整数转为字符串，首位遍历判断即可 算法的时间复杂度是：0（n）

public boolean isPalindrome(int x) {
          
   
    if(x < 0) return false;
    String num = String.valueOf(x);
    for(int i = 0,j = num.length()-1; ;i++,j--){
          
   

        if(i == j || i == j+1) break;
        if(num.charAt(i) != num.charAt(j)) return false;

    }
    return true;
}

解法二（反转一半整数）：

首先判断是否为负数，或者尾数为0的数，因为尾数为0的数如果是回文数必定为0 之后开始每次将x % 10，取出尾数，进行计算存储，就相当于整数反转，然后x / 10 只不过这里我们需要判断一个临界条件，就是什么时候反转到我们需要的地方，如果为长度偶数，那么此时 x == xrev，如果为长度奇数，那么 x = xrev/10 举个例子： 长度为偶数：1221 x = xrev = 12 结束 长度为奇数：12121 x = 12 xrev = 121 结束 时间复杂度为：logn， 空间复杂度为0（1）

public boolean isPalindrome1(int x) {
          
   
        if(x < 0 || (x%10 == 0 && x != 0)) return false;
        int xresver = 0;
        while(x > xresver){
          
   
            xresver = xresver * 10 + x % 10;
            x = x / 10;
        }

        if (x == xresver || x == xresver/10) return true;
        else return false;

    }