Обмен технологиями

Ликоу 7. Подробное объяснение двух алгоритмов обращения целых чисел.

2024-07-12

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

Учитывая 32-битное целое число x со знаком, верните результат инвертирования числовой части x.

Если перевернутое целое число выходит за пределы диапазона 32-битного целого числа со знаком [−2 ^31, 2 ^31 − 1], возвращается 0.

Предположим, что среда не позволяет хранить 64-битные целые числа (со знаком или без знака).

Пример 1:
Ввод: х = 123
Выход: 321

Пример 2:
Ввод: х = -123
Выход: -321

Пример 3:
Ввод: х = 120
Выход: 21

Пример 4:
Ввод: х = 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-битным целым числом, во избежание переполнения необходимо определить, выйдет ли обратный результат за пределы диапазона 32-битного целого числа со знаком [−2 ^31, 2 ^31−1] перед вычислением rev. В последнее время.

Поскольку вопрос требует, чтобы среда не могла хранить 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;

Когда х&gt;0,
оборот * 10 + цифра &lt;= (макс/10) * 10 + 7
=>
(об - макс/10)*10 &lt;= 7 - цифра;

Когда обороты &lt; макс/10:
То есть это может быть верно, когда цифра &lt;= 17. Поскольку цифра &lt;= 9, уравнение всегда выполняется.

Когда оборот = макс/10:
цифра &lt;= 7;
Если x в это время все еще можно разобрать, это означает, что количество цифр в x такое же, как max, и в этот момент цифра является старшей цифрой x, и поскольку x &lt;= 2 ^31 - 1 = 2147483647, старшая цифра x равна 2. То есть цифра &lt;= 2, поэтому уравнение всегда выполняется.

Когда оборот &gt; макс/10:
Поскольку анализ в данный момент представляет собой ситуацию, когда x&gt;0, эта ситуация не имеет места.

Таким образом, это можно упростить до x &lt;= max/10, поэтому в коде, когда x&gt;max/10, вы можете вернуть 0;


Далее ситуация, когда x&lt;0, может быть проанализирована таким же образом.