5.回文数-判断

发表于 | 分类于 | 阅读次数

题目

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

例：121 -> true，-121 -> false

题解

一、字符串的反转

1
2
3
4
5
6
7
8
public boolean isPalindrome(int x) {
    String str = String.valueOf(x);
    String reserveStr = new StringBuilder(str).reverse().toString();
    if (str.equals(reserveStr)) {
        return true;
    }
    return false;
}

二、数学：去首去尾，首尾比较

例：x = 12321

  • 得到首位left： 12321 / 10000 = 1; (此处div=10000为计算得出)
  • 得到末位right：12321 % 10 =1; (此处10为定值，用来取个位上的数)
  • 若left=right，去首尾缩减，x -> 232 ：(12321 % 10000) / 10 。即(x % div) / 10。
  • x已缩减两位数-> div减小。div -> div / 100。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isPalindrome(int x) {
    if (x < 0) { //若<0 ，直接返回
        return false;
    }
    int div = 1;
    while (x / div >= 10) { //此处是>=10，若<10，表示已为个位数，div无需再扩大。
        div *= 10; //计算出除数div
    }
    while (x > 0) { //直到x->0
        int left = x / div;
        int right = x % 10;
        if (left != right) {
            return false;
        }
        x = (x % div) / 10;
        div = div / 100;
    }
    return true;
}

思考：
若是121，10021第二次循环时x都为2。怎么判断的？

  • 10021： 第二次循环时x=2,div=100 ->
    left=2 / 100=0；right=2 % 10=2; -> left!=right -> return false
  • 121：第二次循环时x=2,div=1 -> left=2 /1 =2；right=2 % 10=2；x=(2 % 1) / 10=0 -> 结束循环 -> return true

三、巧妙数学-对折比较

取后半段，进行翻转 -> 就是取x个位数并组装rightPart> x不断缩减个位数

例x=12321，初始rightPart = 0;

  • 取x的个位数lastNum = 12321 % 10 ->1;
  • 将lastNum组装：rightPart = rightPart*10 + lastNum ->1；
  • x缩减成->1232：x=x/10;
  • 循环上面操作。直到x <= rightPart（此时说明已经对折到半或过半了）

思考：

  • 若数字长度为奇数(如12321)，rightPart(123)位数会比x最后值多一位。12!=123,但也应返回true -> 将rightPart去一位(12==123/10) -> x ==rightPart/10
  • 若是70、7，最后x都为0，rightPart都为7。70->false，7->true；因此循环前若x个位是0 -> 直接返回false

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isPalindrome(int x) {
    if (x < 0 || (x != 0 && x % 10 == 0)) {
        return false;
    }
    int rightPart = 0;
    //rightPart为后半部分反转后的数
    while (x > rightPart) {
        rightPart = rightPart * 10 + x % 10;
        x = x / 10;
    }
    //当原数字长度为奇数时，x == rightPart / 10
    if (x == rightPart || x == rightPart / 10) {
        return true;
    }
    return false;
}

题目：力扣No.9-回文数