9.md

9. 回文数

数学方式

思路

• 标签：数学
• 从两头向中间依次比较左数和右数是否相等：比较最高位和最低位，比较之后，去除最高位和最低位，循环
  • 如果 x 为负数，x 肯定不是回文数
  • 最高位，当前数除以除数，需要先利用循环得到除数：left = 1234321 / 1000000 = 1，
  • 最低位，取余：right = x % 10
  • 去除最高位和最低位：x = 1234321 % 1000000 / 10 = 234321 / 10 = 23432
  • 除数对应变化：div = 1000000 / 100 = 10000
• 时间复杂度：O(n)，当为回文数时，循环次数最多：2/n-1（不算循环得到除数的时间），n 为数组的长度。
• 空间复杂度：O(1)，没有利用多余空间

代码

// Java
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0)
            return false;
        int div = 1; // 除数
        while (x /div >= 10)
            div *= 10;
        while (x > 0) {
            int left = x /div;
            int right = x % 10;
            if (left != right)
                return false;
            x = x % div / 10;
            div /= 100;
        }
        return true;
    }
}

// JavaScript
var isPalindrome = function (x) {
    if (x < 0)
        return false;
    let div = 1;
    while (parseInt(x /div) >= 10) {
        div *= 10;
    }
    while (x > 0) {
        let left = parseInt(x /div);
        let right = x % 10;
        if (left !== right) {
            return false;
        }
        x = parseInt(x % div / 10);
        div = parseInt(div / 100);
    }
    return true;
};

画解

数组方式

思路

• 标签：数组
• 使用数组存放每个数字
• 数组跟数学的方法思想一致：比较之后，去除最高位和最低位
• 时间复杂度：O(n)，跟数学方式一样
• 空间复杂度：O(n)，需要数组存放元素

代码

// Java
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        char[] arr = Integer.toString(x).toCharArray();
        while (arr.length > 1) {
            if (arr[0] != arr[arr.length - 1]) {
                return false;
            }
            arr = Arrays.copyOfRange(arr, 1, arr.length - 1);
        }
        return true;
    }
}

// JavaScript
var isPalindrome = function (x) {
    let tempString = x + "";
    let arr = tempString.split("");
    if (x < 0) {
        return false;
    }
    while (arr.length > 1) {
        if (arr[0] !== arr[arr.length - 1]) {
            return false;
        }
        arr = arr.slice(1, arr.length - 1);
    }
    return true;
};

字符串方式

思路

• 标签：字符串
• 直接使用 reverse() 方法反转字符串，再比较
• 时间复杂度：利用函数，不能量化
• 空间复杂度：利用函数，不能量化

代码

// Java
class Solution {
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        String reverse = new StringBuilder(s).reverse().toString();
        return s.equals(reverse);
    }
}

测试用例

描述	1	2	3	4	5
输入	0	10	1001	1000021	1234321
输出	true	false	false	false	true