LEETCODE 9. Palindrome Number 解题思路分析

题目大意：

回文数

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

示例 1:

输入: 121
输出: true

示例 2:

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

示例 3:

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

进阶:

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=9

解题思路分析：

题目要求不能使用字符串来解题，那么我们就需要找到数字上每一位的方法。之前文章我们多次提到过，求数字上每一位的方法，即使用当前数字与10求余数，该余数即是当前数字最低位上的数字，接下来我们将当前数字除以10，继续求它与10的余数，该数字即是次低位上的数字，重复上述过程直到当前数字为0为止。

另外判断回文的方式也不难，我们采用剥洋葱的方式从最外层向内比较，解题时可以定义左右两个指针，初始时左指针指向下标0，右指针指向末尾，如果当前俩指针指向的值不一致，直接返回false。反之，左指针加一，右指针减一，继续比较，重复此过程直到左指针不再小于右指针为止。

实现代码：

public boolean isPalindrome(int x) {
    if(x<0) return false;
    // 保存x上每一位的数
    List<Integer> list = new ArrayList<>();
    // 取得x上的每一位
    while(x>0){
        list.add(x%10);
        x/=10;
    }
    // 定义左右指针
    int left=0,right=list.size()-1;
    while(left<right){
        // 左右指针指向的数字不同时，返回false
        if(list.get(left) != list.get(right)){
            return false;
        }
        left++;
        right--;
    }
    return true;
}

本题解法执行时间为8ms。

Runtime: 8 ms, faster than 40.92% of Java online submissions for Palindrome Number.

Memory Usage: 40.6 MB, less than 5.02% of Java online submissions for Palindrome Number.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-9-palindrome-number-解题思路分析/