Palindrome数は異なる検出技術


Palindromeは、左から右か右から左にあるかどうか読むならば、同じ数です.
たとえば、121はあなたがそれを読んでどちらの側から問題ではない、それは同じままです- 121.
問題文は次のようになります.
整数は前方と同じ後方を読むとき、palindromeです.
整数x , 返り値x は整数値です.
あなたが問題に遭遇するときはいつでも、解決に飛び込んではいけません.この例では、以下の質問をインタビュアーに問い合わせることができます.
  • なら0 palindrome?またはすべての1桁の数字はpalindromeですか?
  • 負の数字は?例えば121はpalindromeですが、- 121についてはどうですか?それは否定的な徴候を考慮しているpalindromeでありません.
  • インタビュアーがこのような質問をはっきりさせようとしましょう.
  • すべての1桁の数字は、palindromeではありません.
  • すべての負の数は、palindromeでありません.
  • 今すぐ解決策にジャンプしましょう.

    ファーストテクニック


    ほとんどの人の心に浮かぶ最初の解決策は、
  • 数値を文字列に変換します.
  • 文字列を反転し、両方の文字列を比較します.
  • class Solution:
        def isPalindrome(self, x: int) -> bool:
            xString = str(x)
            return xString == xString[::-1]
    
    このソリューションは、実際に正しいですが、それは文字列を作成するためにいくつかの余分なメモリが必要とインタビュアーは余分なスペースを使用しないように制限を置くことができます.その場合、この解決策は、最善のものではありません.

    セカンドテクニック


    非恒常的な余剰空間の使用を避けるためには、以下のようにします.
  • 整数自体を元に戻す
  • を返します.
    それではどうしたらいいですか.
  • 例を見てみましょう5445 .
    数学では、10のモジュラスを取ることによって数の最後の桁を得ることができることを知っています.したがって、モジュラスを取って、反転された数の数を足し続けることになります.そして、我々はこの場合、否定的なものを気にしないので、正の数を戻すだけです.
    Pythonコードは、正の数を元に戻すようになります.
    def revertNumber(x: int) -> int:
        if x < 0:
            raise ValueError('Only positive integers are allowed') 
    
        revertedNumber = 0
    
        while(x > 0):
            revertedNumber = revertedNumber * 10 + x % 10
            x = x // 10
    
        return revertedNumber
    
    我々は今、我々はこの関数を使用してpalindromesを検出することができますので、番号を元に戻す機能があります.
    def isPalindrome(x: int) -> bool:
        return x == revertNumber(x)
    

    最後のアプローチ


    だから今では文字列の作成と反転より効率的な解決策があります.
    でも……この問題は、逆の数が100より大きい場合に問題があるint.MAX , 整数オーバーフロー問題が発生します.
    この状況を避けるために、私たちは解決策を少し変更することができます.私たちは数の半分を逆にして、元の数の前半と比較することができます.例えば、
  • 5445ならば、我々は半分の数を逆にするでしょう54 .
  • これを比較すれば54 これは番号の前半と同じですので、これはpalindromeです.
  • def isPalindrome(x: int) -> bool:
        # Special cases:
        # As discussed above, when x < 0, x is not a palindrome.
        # Also if the last digit of the number is 0, in order to be a palindrome,
        # the first digit of the number also needs to be 0.
        # Only 0 satisfy this property.
        if (x < 0 or (x % 10 == 0 and x != 0)):
            return False
    
        revertedNumber = 0
    
        while(x > revertedNumber):
            revertedNumber = revertedNumber * 10 + x % 10
            x //= 10
    
        # When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
        # For example when the input is 10501, at the end of the while loop we get x = 10, revertedNumber = 105,
        # since the middle digit doesn't matter in Palindrome(it will always equal to itself), we can simply get rid of it.
        return x == revertedNumber or x == revertedNumber//10
    
    複雑性解析
    時間の複雑さ:o(log 10(n)).私たちは入力をすべての反復に対して10で割ったので、時間の複雑さはo(log 10(n))である
    空間の複雑さ: O ( 1 )