技術共有

リコウ 7. 整数反転の 2 つのアルゴリズムの詳細な説明

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

32 ビット符号付き整数 x を指定すると、x の数値部分を反転した結果を返します。

反転した整数が 32 ビット符号付き整数 [-2 ^31, 2 ^31 − 1] の範囲を超える場合は、0 が返されます。

環境では 64 ビット整数 (符号付きまたは符号なし) の保存が許可されていないとします。

例 1:
入力: x = 123
出力: 321

例 2:
入力: x = -123
出力: -321

例 3:
入力: x = 120
出力: 21

例 4:
入力: x = 0
出力: 0

ヒント:

-2 ^31 <= x <= 2 ^31 - 1
  • 1

アルゴリズム 1 (64 ビット整数の格納に関係なく): 文字列の反転

#include <iostream>
#include <string>
#include <algorithm>
#include <climits>

class Solution {
public:
    int reverse(int x) {
        // 将整数转换为字符串
        std::string str = std::to_string(x);
        
        // 处理负号
        if (x < 0) {
            std::reverse(str.begin() + 1, str.end());
        } else {
            std::reverse(str.begin(), str.end());
        }
        
        // 将反转后的字符串转换回整数
        long rev = std::stoll(str);
        
        // 检查是否超出32位有符号整数范围
        if (rev > INT_MAX || rev < INT_MIN) {
            return 0;
        }
        
        return static_cast<int>(rev);
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

64 ビット整数を格納できない状況を考慮しないのは比較的簡単なので、詳細は説明しません。

アルゴリズム 2: 数学的手法

完全なコードは次のとおりです。

class Solution {
public:
    int reverse(int x) {
        int max = 2147483647;
        int min = -2147483648;
        int rev = 0;
        while(x != 0){
            if(rev > max / 10 || rev < min / 10){
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev  = rev * 10 + digit;
            
        }
        return rev;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

解析する
最初のステップは、形状を反転することです。

// 弹出 x 的末尾数字 digit
digit = x % 10
x /= 10

// 将数字 digit 推入 rev 末尾
rev = rev * 10 + digit
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

x は 32 ビット整数であるため、オーバーフローを避けるために、rev を計算する前に、反転した結果が 32 ビット符号付き整数 [-2 ^31, 2 ^31-1] の範囲を超えるかどうかを判断する必要があります。最後に。

質問では、環境が 64 ビット整数を保存できないことが必要であるため、直接指定することはできません。−2 ^ 31 ≤ rev⋅10+digit ≤2 ^ 31 −1
したがって、計算プロセス中に 32 ビット整数を超える値が表示されないようにするために、いくつかの数学的手法を採用する必要があります。ここで境界値を分解できます。覚えて:

min =2 ^31 = -2147483648;
max = 2 ^311 = 2147483647;
  • 1
  • 2

内訳すると次のようになります。
最小値 = (最小値/10) * 10 - 8;
最大値 = (最大値/10) * 10 + 7;

x&gt;0のとき、
回転数 * 10 + 数字 &lt;= (最大/10) * 10 + 7
=>
(回転数 - 最大値/10)*10 &lt;= 7 - 桁;

rev &lt; max/10 の場合:
つまり、数字 &lt;= 17 の場合に真となります。数字 &lt;= 9 であるため、方程式は常に成り立ちます。

rev = max/10 の場合:
数字 &lt;= 7;
この時点で x がまだ逆アセンブルできる場合、それは x の桁数が max と同じであることを意味し、この時点で digit は x の最上位桁であり、x &lt;= 2 ^31 - 1 = 2147483647 であるため、 x の最上位の桁は 2 です。つまり、桁&lt;=2 であるため、方程式は常に成り立ちます。

rev &gt; max/10 の場合:
この時の解析はx&gt;0の場合なのでこの状況は成り立ちません。

したがって、これは x &lt;= max/10 に単純化できるため、コードでは、x&gt;max/10 の場合は 0 を返すことができます。


次に、x&lt;0の場合も同様に解析できます。