No.9 回文数 (easy)

发表于 更新于

题目描述

给你一个整数 x​ ，如果 x​ 是一个回文整数，返回 true​ ；否则，返回 false​ 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121​ 是回文，而 123​ 不是。

  • 示例 1：

    输入： x = 121
    输出： true

  • 示例 2：

    输入： x = -121
    输出： false
    解释： 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

  • 示例 3： ​

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

解题思路

  1. 最简单的就是将x转化为字符串，然后使用左右两个指针获取来进行对应比较，这里就不再赘述；

  2. 省去转化为字符串这一步，使用数学的方式获取对应位上的数字进行比较，这里给出C++代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public:
    	bool isPalindrome(int x) {
    		// 负数不是回文数
    		if (x < 0)
    			return false;
    		// 获取位数digits，更简洁的办法可以用log10(Number)+1，
    		// 但需除开Number为0的情况
    		int digits = 0;
    		int tmp = x;
    		while (tmp != 0) {
    			tmp /= 10;
    			digits++;
    		}
    		// 第1位与最后1位对应要相等，以此类推，如果有反例则不是回文
    		for (int i = 0; i <= digits / 2 - 1; i++) {
    			if (((x / (int)(pow(10.0, digits - i - 1))) % 10) !=
    				((x / (int)(pow(10.0, i))) % 10))
    				return false;
    		}

    		return true;
    	}
    };

  3. 使用反转数字（revertedNum）的方式（题解给出的“奇淫技巧”），这里给出两个形象的例子帮助理解：

    1. x = 121

    2. x = 12 | revertedNum = 1

    3. x = 1 | revertedNum = 12

    4. if revertedNum/10 == x，是回文数，反之则不是 // 上一步revertedNum > x 说明左右两部已经形成，而中间是2或是3都无影响，因此除去之后得到对应的两个要素

    1. x = 2112
    2. x = 211 | revertedNum = 2
    3. x = 21 | revertedNum = 21
    4. if revertedNum == x，是回文数，反之则不是 // 上一步revertedNum == x 说明左右两部已经形成，因此除去之后，得到左半部和右半部

    根据上述的两个例子，去除特殊情况（x=10，x=100不是回文），得到如下代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public:
    	bool isPalindrome(int x) {
    		// 负数不是回文数；除0以外，个位为0不是回文
    		if (x < 0 || x % 10 == 0 && x/10 != 0)
    			return false;
    		int revertedNum = 0;
    		while( revertedNum < x ){
    			revertedNum = revertedNum * 10 + x % 10;
    			x /= 10;
    		}
    		return revertedNum/10 == x || revertedNum == x;
    	}
    };

‍