LeetCode-9 回文数

> 题目：9. 回文数

> 难度：简单

> 分类：字符串、数学

> 解决方案：双指针、整数取余

今天我们学习第9题回文数，这是一个关于数学的简单题，这个题目比较简单，最好能手写出该题。下面我们看看这道题的题目描述。

题目描述

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

示例 1:

输入: 121输出: true

示例 2:

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

示例 3:

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

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

分析

看完这个题目，对于回文数我们应该不陌生。我们在LeetCode-5 最长回文子串中介绍过回文串，即从左向右读和从右向左读的结果是一样的字符串。本题是判断一个整数是否为一个回文数，最简单的做法是先将这个整数转化为字符串，然后使用双指针的方式判断这个字符串是否为回文串。

具体 java代码如下所示：

public boolean isPalindrome(int x) {
    // 将整数转化为字符数组    char[] str = String.valueOf(x).toCharArray();    // 创建左右指针    int left = 0, right = str.length-1;    // 遍历字符串    while(left < right){        // 如果左指针指向的字符与右指针指向的字符不同时，直接返回false        if (str[left] != str[right])            return false;        left++;        // 左指针向右移动        right--;    // 右指针向左移动    }
    return true;}

【 图1.回文字符串提交结果】

将整数转化为字符串后这个题目的思路就很清晰了。注意看进阶部分的提示：你能不将整数转为字符串来解决这个问题吗？ 因此我们需要换一种思路来解决这个题目。 我们想一想整数如果是负数，则直接返回 false，如示例2中可以知道一个负数不可能为回文数。由于整数不可能为0开头（除整数0外），因此整数的个位数为0也直接返回 false，如示例3所示。排除完这两种特殊情况后，我们该如何判断剩下的整数是不是回文数呢？要判断一个数是否为回文数，则需要判断前半段和后半段是否对称，我们将后半段部分的数字翻转一下，然后判断翻转后的数字是否与前半部分的数字是否相等即可。我们可以将整数对10取余得到整数的个位数。由于数字位数为奇数个和偶数个的情况不一样，我们通过两个实例分析，如下图2所示。

【图2.整数翻转实例】

通过分析之后，具体代码就不难实现了。 java代码如下所示：

public boolean isPalindrome(int x) {
    // 排除负数和以0结尾的整数（除0以外）    if ((x < 0) || (x % 10 == 0 && x != 0 ))        return false;
    int reverNum = 0;    // 翻转整数过程    while (x > reverNum){        reverNum = reverNum * 10 + x % 10;  // 计算翻转数字        x /= 10;                            // 计算剩余数字    }
    return reverNum == x || reverNum / 10 == x; // reverNum == x为整数位数偶数个时的判断条件；reverNum / 10 == x为整数位数奇数个时的判断条件
}

【 图3.回文数提交结果】

Github地址

LeetCode-9 回文数：https://github.com/JacobLei/leetcode/blob/master/src/main/java/A9_PalindromeNumber.java

参考链接

9.回文数：https://leetcode-cn.com/problems/palindrome-number/