『javaアルゴリズムシリーズ打カード4日目』

32ビットの符号付き整数を指定し、整数の数値を反転します.
例 1:

  : 123
  : 321

 例2:

  : -123
  : -321

例3:

  : 120
  : 21

注意:
我々の環境では32ビットの符号付き整数しか記憶できないと仮定し,その数値範囲は[−231,  231 − 1].この仮定によれば,反転後の整数がオーバーフローすると0を返す.
ソリューション
方法:数値&オーバーフロー前のチェックをポップアップおよびプッシュ
構想
反転整数の1桁の数値を一度に構築することができます.このようにすると,元の整数に別の数字を付加してオーバーフローを招くかどうかを事前にチェックすることができる.
アルゴリズム#アルゴリズム#
整数を反転する方法は、反転文字列とクラス比できます.
「ポップアップ」を繰り返したい xx を選択し、 \text{rev}rev で行ないます.最後に、text{rev}rev と xx 反対です.
補助スタック/配列の助けなしに「ポップアップ」と「プッシュ」の数字を使用するには、数学的な方法を使用します.

//pop operation:
pop = x % 10;
x /= 10;

//push operation:
temp = rev * 10 + pop;
rev = temp;

しかし、この方法は危険です. \text{temp} =\text{rev}\cdot 10 +\text{pop}temp=rev⋅10+pop オーバーフローの原因となります.
幸いなことに、この文がオーバーフローを引き起こすかどうかを事前にチェックするのは簡単です.
説明を容易にするために \text{rev}rev 正数です.
場合 temp =\text{rev}\cdot 10 +\text{pop}temp=rev⋅10+pop 溢れ出すならきっと \text{rev}\geq\frac{INTMAX}{10}rev≥​10​​INTMAX​​.
場合 \text{rev}>frac{INTMAX}{10}rev>10 INTMAX、では temp =\text{rev}\cdot 10 +\text{pop}temp=rev⋅10+pop きっと溢れ出す.
場合 \text{rev}=frac{INTMAX}{10}rev==10 INTMAX、では \text{pop} > 7pop>7,temp =\text{rev}\cdot 10 +\text{pop}temp=rev⋅10+pop 溢れ出す.
当 \text{rev}rev 負の場合、同様の論理を適用できます.
複雑度分析
時間複雑度:O(log(x))O(log(x)),xx の中には \log_{10}(x)log​10​​(x) ビット数.
空間複雑度:O(1)O(1).