Leetcode 9 Palindrome Number 回文數(shù)字判定

ningwang 發(fā)布于2019-08-14 17:14 / 2836人閱讀

摘要：難度本題要求判定一個整數(shù)是否為回文數(shù)字比如都是回文數(shù)字但是不是回文數(shù)字所有負數(shù)都不是回文數(shù)字本題還有一個關鍵要求不能使用額外空間我理解這里的額外空間是指堆空間在程序中不能去額外的什么變量更不用說提升空間復雜度直接上的解法解法

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

本題要求判定一個整數(shù)是否為回文數(shù)字, 比如 1, 121, 都是回文數(shù)字, 但是-1, 12, 不是回文數(shù)字.
所有負數(shù)都不是回文數(shù)字.

本題還有一個關鍵要求, 不能使用額外空間. 我理解這里的額外空間是指堆空間. 在程序中不能去額外的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));
    }
}

解法很直接, 從兩頭開始往中間判定數(shù)字是否相同, 不同直接返回false.
其中getDigit方法是獲取這個數(shù)的第n位數(shù)字, 為了滿足不使用額外空間的要求, 這么解實際上提升了時間復雜度.

云服務器 GPU云服務器回文數(shù)字python palindrome LeetCode LeetCode_String

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66510.html

leetcode 9 Palindrome Number

摘要：有一點需要注意的是，負數(shù)不算作回文數(shù)。而第題當時的方法是，對整數(shù)取除的余數(shù)，即是當前整數(shù)的最后一位。那么它翻轉后一半的數(shù)字之后，應該和前半段的數(shù)字相等，我們將采用這種思路進行解題。題目詳情 Determine whether an integer is a palindrome. Do this without extra space.題目要求我們在不占用額外空間的前提下，判斷一個整...

darkbug 2019-08-16 11:02 評論0 收藏0
[Leetcode] Palindrome Number 回文數(shù)

摘要：反轉比較法復雜度時間空間思路回文數(shù)有一個特性，就是它反轉后值是一樣的。代碼逐位比較法復雜度時間空間思路反轉比較有可能會溢出，但我們遍歷每一位的時候其實并不用保存上一位的信息，只要和當前對應位相等就行了。首先，負數(shù)是否算回文。 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

摘要：題目分析這是上的第題，難度為，判斷整型數(shù)字是否為回文串，需要注意兩點負數(shù)都不是回文小于的非負整數(shù)都是回文這一題與第題類似，也可以有兩種思路數(shù)組法和模十法。所以代碼可以如下改進能被整除的非整數(shù)和負數(shù)，返回題目 Determine whether an integer is a palindrome. Do this without extra space. 分析這是leetcode上...

icyfire 2019-08-21 16:58 評論0 收藏0
LeetCode - 009 - 回文數(shù)（palindrome-number）

摘要：最后，我們判斷一開始的兩種情況，并返回或者即可。本許可協(xié)議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-05-22 19:30:42 Recently revised in 2019-05-23 11:42:52 一目錄不折騰的前端，和咸魚有什么區(qū)別目錄一目錄二前言三解題 ?3.1 解題 - 數(shù)組操作 ...

hikui 2019-05-23 16:23 評論0 收藏0
[Leetcode] Palindrome Number 回文數(shù)

摘要：首尾比較法復雜度時間空間，為所求的長度思路先求記為的長度根據(jù)長度制造掩碼循環(huán)當當最高位等于最低位還有數(shù)字等待判斷最高位通過掩碼和整除取得，最低位通過取余取得判斷過后更新掩碼，刪掉最高位，刪掉最低位注意求長度的如何取得一個的最高位假設答設置一 Palindrome Number Determine whether an integer is a palindrome. Do this w...

lixiang 2019-08-14 14:03 評論0 收藏0