摘要:反轉(zhuǎn)比較法復(fù)雜度時(shí)間空間思路回文數(shù)有一個(gè)特性,就是它反轉(zhuǎn)后值是一樣的。代碼逐位比較法復(fù)雜度時(shí)間空間思路反轉(zhuǎn)比較有可能會(huì)溢出,但我們遍歷每一位的時(shí)候其實(shí)并不用保存上一位的信息,只要和當(dāng)前對應(yīng)位相等就行了。首先,負(fù)數(shù)是否算回文。
Palindrome Number
反轉(zhuǎn)比較法 Reverse and Compare 復(fù)雜度Determine whether an integer is a palindrome. Do this without extra space.
時(shí)間 O(n) 空間 O(1)
思路回文數(shù)有一個(gè)特性,就是它反轉(zhuǎn)后值是一樣的。所以我們可以先將其反轉(zhuǎn),然后比較反轉(zhuǎn)數(shù)和原數(shù)是否相等。該方法的問題在于溢出的判斷和處理,我們可以參考反轉(zhuǎn)整數(shù)中的幾種處理方法。
代碼javapublic class Solution { public boolean isPalindrome(int x) { long reverse = 0, original = x; if(x<0){ return false; } while(x>0){ reverse *= 10; reverse += x % 10; x /= 10; } return original == reverse; } }逐位比較法 One By One 復(fù)雜度
時(shí)間 O(n) 空間 O(1)
思路反轉(zhuǎn)比較有可能會(huì)溢出,但我們遍歷每一位的時(shí)候其實(shí)并不用保存上一位的信息,只要和當(dāng)前對應(yīng)位相等就行了。所以我們可以遍歷一遍先算出數(shù)的長度,再遍歷一遍同時(shí)對比前后的對應(yīng)位。
代碼javapublic class Solution { public boolean isPalindrome(int x) { if(x < 0){ return false; } int digits = 1; int original = x; // 計(jì)算當(dāng)前數(shù)的位數(shù),個(gè)位數(shù)不用計(jì)算,已經(jīng)默認(rèn)為1 while(x > 9){ digits *= 10; x /= 10; } // 逐位比較 x = original; while(x > 0){ int msd = x / digits; int lsd = x % 10; if(msd != lsd){ return false; } // 去除最高位和最低位 x -= msd * digits; x /= 10; digits /= 100; } return true; } }后續(xù) Follow Up
Q:在答題之前我需要知道些什么?
A:因?yàn)榛匚牡亩x原本只適用于字符串,所以我們要先問清楚數(shù)字回文是如何定義的。首先,負(fù)數(shù)是否算回文。其次,在計(jì)算回文時(shí),我們應(yīng)該按十進(jìn)制算還是其他進(jìn)制,如二進(jìn)制。
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/64384.html
摘要:最后,我們判斷一開始的兩種情況,并返回或者即可。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-05-22 19:30:42 Recently revised in 2019-05-23 11:42:52 一 目錄 不折騰的前端,和咸魚有什么區(qū)別 目錄 一 目錄 二 前言 三 解題 ?3.1 解題 - 數(shù)組操作 ...
摘要:首尾比較法復(fù)雜度時(shí)間空間,為所求的長度思路先求記為的長度根據(jù)長度制造掩碼循環(huán)當(dāng)當(dāng)最高位等于最低位還有數(shù)字等待判斷最高位通過掩碼和整除取得,最低位通過取余取得判斷過后更新掩碼,刪掉最高位,刪掉最低位注意求長度的如何取得一個(gè)的最高位假設(shè)答設(shè)置一 Palindrome Number Determine whether an integer is a palindrome. Do this w...
摘要:有一點(diǎn)需要注意的是,負(fù)數(shù)不算作回文數(shù)。而第題當(dāng)時(shí)的方法是,對整數(shù)取除的余數(shù),即是當(dāng)前整數(shù)的最后一位。那么它翻轉(zhuǎn)后一半的數(shù)字之后,應(yīng)該和前半段的數(shù)字相等,我們將采用這種思路進(jìn)行解題。 題目詳情 Determine whether an integer is a palindrome. Do this without extra space.題目要求我們在不占用額外空間的前提下,判斷一個(gè)整...
摘要:最笨的方法就是用的解法,找出所有的,然后再用中判斷回文的方法來判斷結(jié)果中是否有回文。而中心對稱點(diǎn)如果是字符,該字符會(huì)是奇數(shù)次,如果在兩個(gè)字符之間,則所有字符都是出現(xiàn)偶數(shù)次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...
摘要:難度本題要求判定一個(gè)整數(shù)是否為回文數(shù)字比如都是回文數(shù)字但是不是回文數(shù)字所有負(fù)數(shù)都不是回文數(shù)字本題還有一個(gè)關(guān)鍵要求不能使用額外空間我理解這里的額外空間是指堆空間在程序中不能去額外的什么變量更不用說提升空間復(fù)雜度直接上的解法解法 Determine whether an integer is a palindrome. Do this without extra space. Some ...
閱讀 1309·2021-09-27 13:56
閱讀 2339·2019-08-26 10:35
閱讀 3497·2019-08-23 15:53
閱讀 1849·2019-08-23 14:42
閱讀 1233·2019-08-23 14:33
閱讀 3562·2019-08-23 12:36
閱讀 1948·2019-08-22 18:46
閱讀 997·2019-08-22 14:06