X

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.

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