기술나눔

한어Русский язык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 ^31−1 = 2147483647;
1
2

분석하려면:
최소 = (최소/10) * 10 - 8;
최대 = (최대/10) * 10 + 7;

x>0일 때,
rev * 10 + 숫자 <= (최대/10) * 10 + 7
=>
(rev - 최대/10)*10 <= 7 - 숫자;

회전 < 최대/10인 경우:
즉, 숫자 <= 17일 때 참일 수 있습니다. 숫자 <= 9이므로 방정식은 항상 유지됩니다.

rev = 최대/10인 경우:
숫자 <= 7;
이때 x를 분해할 수 있다면 x의 자릿수가 max와 같다는 뜻이고, 이때 digit는 x의 가장 높은 자릿수이고 x <= 2 ^31 - 1 = 2147483647이기 때문에, x의 가장 높은 숫자는 2입니다. 즉, 숫자<=2이므로 방정식은 항상 유지됩니다.

회전수 > 최대/10일 때:
이때의 분석은 x>0인 상황이므로 이 상황은 성립하지 않는다.

따라서 x <= max/10으로 단순화할 수 있으므로 코드에서 x>max/10일 때 0을 반환할 수 있습니다.

---

다음으로 x<0인 상황도 같은 방식으로 분석할 수 있다.