【アルゴリズム】Pythonは、数字が返信数であるか否かを判断する

5810 ワード

回文数の定義:回文数とは、正の順序(左から右へ)と逆の順序(右から左へ)が同じ整数であることを意味します.
例1:
入力:121
出力:True
例2:
入力:-121
出力:False
左から右へ-121と読みます.右から左に読むと121-.したがって、回文数ではありません.
例3:
入力:10
出力:false
右から左へ読むと、01です.したがって、回文数ではありません.
考え方:
頭に浮かぶ最初のアイデアは、数字を文字列に変換し、文字列が返事であるかどうかを確認することです.ただし、問題記述で許可されていない文字列を作成するには、追加の非常に多くのスペースが必要です.
2つ目のアイデアは、数字自体を反転させることですが、32ビットマシンのintタイプの最大値は2147483647で、反転後の数字が範囲を超えてオーバーフローする可能性があります.
2つ目の考え方では、デジタル反転によるオーバーフローを避けるために、inttext{int}int数字の半分だけを反転することを考慮しないのはなぜですか?結局、この数字が回文であれば、その後の半分が反転した後、元の数字の前半と同じになるはずです.
例えば、1221を入力すると、数字「1221」の後半を「21」から「12」に反転させ、前半の「12」と比較することができる.両者は同じであるため、数字1221が回文であることが分かる.
アルゴリズム:
まずいくつかの特殊な状況を処理しなければならない.負数は回文数ではなく、まず負数の進入を禁止しなければならない.
次に、1221のように数字を反転する方法を考え、まず1221%10で最後の数字1を得ることができ、1221/10で122を得ることができ、再び122%10で最後から2番目の数字2を得ることができ、最後に1*10+2=12で私たちが反転した数字12を得ることができ、12と元の数字の前の2桁を比較して、その数字が回文数であるかどうかを判断することができる.
もう一つの問題があります.私たちはどうして自分が半分反転したことを知っていますか.
元の数字を10で割って、反転した数字に10を乗算するので、元の数字が反転した数字より小さい場合は、半分の桁の数字を処理したことを意味します.
コード実装:
Python 

class Solution(object):    
	def isPalindrome(self, x):        
		"""        
		:type x: int        
		:rtype: bool        
		"""        
		if x<0 or (x % 10 == 0 and x != 0):            			return False        
		y=0        
		while(x>y):            
			y=x%10+y*10            
			x /= 10;        
		return x==y or x==y/10 
Java 
    
class Solution {    
    public boolean isPalindrome(int x) {        
        if(x < 0 || (x % 10 == 0 && x != 0))            		return false;        
        int res = 0;        
        while(x > res){            
            res = res * 10 + x % 10;            
            x /= 10;        
        }        
        return x == res || x == res / 10;    
    } 
}