Leetcode 9 Palindrome Number 回文数字判定

ningwang 发布于2019-08-14 17:14 / 2784人阅读

摘要：难度本题要求判定一个整数是否为回文数字比如都是回文数字但是不是回文数字所有负数都不是回文数字本题还有一个关键要求不能使用额外空间我理解这里的额外空间是指堆空间在程序中不能去额外的什么变量更不用说提升空间复杂度直接上的解法解法

Determine whether an integer is a palindrome. Do this without extra space.

Some hints: Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the
restriction of using extra space.

You could also try reversing an integer. However, if you have solved
the problem "Reverse Integer", you know that the reversed integer
might overflow. How would you handle such case?

There is a more generic way of solving this problem.

难度: Easy

本题要求判定一个整数是否为回文数字, 比如 1, 121, 都是回文数字, 但是-1, 12, 不是回文数字.
所有负数都不是回文数字.

本题还有一个关键要求, 不能使用额外空间. 我理解这里的额外空间是指堆空间. 在程序中不能去额外的new 什么变量, 更不用说提升空间复杂度.

直接上AC的解法:

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int digits = 0;
        int tmp = x;
        while (tmp != 0) {
            tmp = tmp / 10;
            digits++;
        }
        for (int i = 1; i <= digits / 2; i++) {
            if (getDigit(x, i) != getDigit(x, digits + 1 - i)) {
                return false;
            }
        }
        return true;
    }

    private int getDigit(int target, int pos) {
        for (int i = 0; i < pos - 1; i++) {
            target = target / 10;
        }
        return target % 10;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isPalindrome(1));
        System.out.println(s.isPalindrome(12));
        System.out.println(s.isPalindrome(11));
        System.out.println(s.isPalindrome(121));
        System.out.println(s.isPalindrome(1212));
        System.out.println(s.isPalindrome(-1));
        System.out.println(s.isPalindrome(-11));
        System.out.println(s.isPalindrome(-121));
        System.out.println(s.isPalindrome(-2147447412));
    }
}

解法很直接, 从两头开始往中间判定数字是否相同, 不同直接返回false.
其中getDigit方法是获取这个数的第n位数字, 为了满足不使用额外空间的要求, 这么解实际上提升了时间复杂度.

GPU云服务器云服务器回文数字python palindrome LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66510.html

leetcode 9 Palindrome Number

摘要：有一点需要注意的是，负数不算作回文数。而第题当时的方法是，对整数取除的余数，即是当前整数的最后一位。那么它翻转后一半的数字之后，应该和前半段的数字相等，我们将采用这种思路进行解题。题目详情 Determine whether an integer is a palindrome. Do this without extra space.题目要求我们在不占用额外空间的前提下，判断一个整...

darkbug 2019-08-16 11:02 评论0 收藏0
[Leetcode] Palindrome Number 回文数

摘要：反转比较法复杂度时间空间思路回文数有一个特性，就是它反转后值是一样的。代码逐位比较法复杂度时间空间思路反转比较有可能会溢出，但我们遍历每一位的时候其实并不用保存上一位的信息，只要和当前对应位相等就行了。首先，负数是否算回文。 Palindrome Number Determine whether an integer is a palindrome. Do this witho...

_Suqin 2019-08-14 12:17 评论0 收藏0
javascript初探LeetCode之9.Palindrome Number

摘要：题目分析这是上的第题，难度为，判断整型数字是否为回文串，需要注意两点负数都不是回文小于的非负整数都是回文这一题与第题类似，也可以有两种思路数组法和模十法。所以代码可以如下改进能被整除的非整数和负数，返回题目 Determine whether an integer is a palindrome. Do this without extra space. 分析这是leetcode上...

icyfire 2019-08-21 16:58 评论0 收藏0
LeetCode - 009 - 回文数（palindrome-number）

摘要：最后，我们判断一开始的两种情况，并返回或者即可。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-05-22 19:30:42 Recently revised in 2019-05-23 11:42:52 一目录不折腾的前端，和咸鱼有什么区别目录一目录二前言三解题 3.1 解题 - 数组操作 ...

hikui 2019-05-23 16:23 评论0 收藏0
[Leetcode] Palindrome Number 回文数

摘要：首尾比较法复杂度时间空间，为所求的长度思路先求记为的长度根据长度制造掩码循环当当最高位等于最低位还有数字等待判断最高位通过掩码和整除取得，最低位通过取余取得判断过后更新掩码，删掉最高位，删掉最低位注意求长度的如何取得一个的最高位假设答设置一 Palindrome Number Determine whether an integer is a palindrome. Do this w...

lixiang 2019-08-14 14:03 评论0 收藏0