#LeetCodeブラシ問題#,#整数反転#,#文字列スライス#

LeetCodeブラシ問題第2題、整数反転
タイトルの説明
32ビットのシンボル付き整数を与えます.この整数の各ビットの数字を反転する必要があります.例えば、入力:321、出力123入力:-321、出力:-123入力:120、出力:21注意事項:我々の環境が32ビットの符号付き整数しか記憶できないと仮定すると、その数値範囲は[−231,231−1]である.この仮定に基づいて、反転後に整数がオーバーフローした場合は0を返します.
解題構想1:文字列スライス逆シーケンスを実現
1.元の配列をintからstr文字列の形式に変換し、「-」号の提出と追加を容易にする.2.Pythonの文字列スライス法を利用して、新しい文字列を逆順序で出力し、文字列の先頭に存在する可能性のある「0」と末尾に存在する可能性のある「-」の2文字を除去する.3.新しく生成された逆シーケンス文字列をint形式に変換する.4.最後に逆順配列の大きさ範囲を判定する.コードは次のとおりです.

class Solution:
    def reverse(self, x: int) -> int:
        if x == 0:
            return 0
        str_x = str(x) #    x         
        x = ''
        if str_x[0] == '-': #             "-"      
            x += '-'
        x += str_x[len(str_x)-1::-1].lstrip("0").rstrip("-") # .lstrip()            ，.rstrip()            
        x = int(x) #               int    
        if -2**31<x<2**31-1: #   x     
            return x
        return 0
"""
len(str_x)-1::-1,           ，                    ，
A:B:x,A     ，B     ，x   ，B    ，  A::x   。
""" 

実行は48 msで通過した.時間複雑度O(n).空間的複雑度はO(n)である.
問題を解く構想2:最適化解
考え方は以下の通りです.反転整数の1桁の数字を一度に構築することができます.このようにすると,元の整数に別の数字を付加してオーバーフローを招くかどうかを事前にチェックすることができる.整数を反転する方法は、反転文字列とクラス比できます.「ポップアップ」xの最後の数字を繰り返し、resの後ろに「プッシュ」したい.最後にresはxとは逆になる.時間複雑度:O(log(x)),xには約log 10(x)ビット数がある.空間複雑度:O(n)コードは以下の通りである.

class Solution:
    def reverse(self, x: int) -> int:
        y, res = abs(x), 0
        #         [−2^31,  2^31 − 1]
        boundry = (1<<31) -1 if x>0 else 1<<31
        while y != 0:
            res = res*10 +y%10
            if res > boundry :
                return 0
            y //=10
        return res if x >0 else -res

実行はパスし、実行時間は42 msです.
問題解決の考え方3:スタックを用いて解決する
方法3 LeetCodeテーマ討論区から来て、構想は参考に値すると思って、みんなの参考に供します.

class Solution:
    def reverse(self, x: int) -> int:
        x_list = list(str(x))
        res_stack = []
        is_minus = False  #       
        
        while x_list:
            v = x_list.pop()
            if v == '-':
                is_minus = True
                continue
            res_stack.append(v)
        res = int(''.join(res_stack))
        
        if is_minus:
            res *= -1
        
        #     
        v_max = 0xffffffff/2
        if res > (v_max -1) or res < (v_max*(-1)):
            res = 0
            
        return res