题目描述

在不使用额外的内存空间的条件下判断一个整数是否是回文。
回文指逆序和正序完全相同。（负数不是回文）

例1
输入：121
返回值：true

题目分析

对于判断数字是否是回文有两种方式：
①数字转字符串，双指针判断：可以将数字转换成字符串，然后再采用判断字符串是否是回文的方式进行判断。
②反转数字：主要是将数字的高位数字与低位数字调换，计算反转后的数字是否与之前相等。对于反转数字来说，可能会导致溢出的情况，需要进行溢出判断。

解题思路

方法1：数字转字符串，双指针判断是否回文

判断字符串是否是回文的方式比较简单，使用双指针，一个指向字符串头部，一个指向字符串尾部，两隔指针指向的字符相同就往中间移一位，继续比较，直到两个指针相遇，比较过程如下：

因为双指针判断只要有一次比较不同就会直接返回结果，花费的时间其实会比反转数字少一些。

方法2：反转数字，判断数字是否与原来相同

反转数字需要从数字x的个位开始记录res，使x不断向右移位（/10）获取其他位上的数字，然后res不断向左移位（X10）加上其他位的数字，具体实现过程如下：

// 记录反转数字
int res = 0;
while(x>0){
    // 记录x每一位上的数
	int div = x %10;
    // res需要往高位移（原来的低位转向高位）
    res = res*10 + div;
    // x向低位移
    x = x / 10;
}

代码实现

方法1：双指针判断

import java.util.*;
public class Solution {
    /**
     * 
     * @param x int整型 
     * @return bool布尔型
     */
    public boolean isPalindrome (int x) {
        // write code here
        if(x<0) return false;
        // 转换成字符串
        String xs = String.valueOf(x);
        // 利用双指针
        int left = 0;
        int right = xs.length()-1;
        // 比较字符串的头部和尾部是否相同
        while(left < right){
            // 不相同直接返回
            if(xs.charAt(left) != xs.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}

时间复杂度：$O(n)O(n)$，n是数字字符串长度，判断最多需要遍历所有字符，所以时间复杂度为$O(n)O(n)$；

空间复杂度：$O(n)O(n)$，使用了额外的字符串空间。

方法2：翻转数字

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return bool布尔型
     */
    public boolean isPalindrome (int x) {
        // write code here
        if(x<0) return false;
        int reverse = 0;
        int tmp = x;
        while(tmp>0){
            int div = tmp%10;
            // 判断是否会溢出
            if(reverse >= Integer.MAX_VALUE/10 && div > 7) return false;
            // 获得反向数字
            reverse = reverse*10 + div;
            tmp = tmp/10;
        }
        return x == reverse;
    }
}

时间复杂度：$O(n)O(n)$，n是数字长度，需要遍历数字每位上的数，所以时间复杂度为$O(n)O(n)$；

空间复杂度：$O(1)O(1)$，只需要常数级别整型变量。