LeetCode - Reverse Integer

加上两个限制:

1. C++不将 long long 作为64位类型使用
   
2. 不使用 string 到 long long 的类型转换
   

思路1

32位整型能表示的范围为[-2³¹, 2³¹ - 1]

2³¹

2147483648

如果使用无符号32位存储2³¹

当 x 等于-2³¹时, 表达式 -x 的结果仍为整型, 编译器会报错: 可以使用 abs(x)

讨论x=-2³¹

反转的结果必定越界

那么, 剩下的讨论范围为[-2³¹ + 1, 2³¹ - 1], 绝对值是32位整型可以表示的

拆解输入

使用除余取出低位, 使用除法抹去低位

输入

2340798150

拆解后存入顺序容器

INDEX    0 1 2 3 4 5 6 7 8 9
ELEMENT  0 5 1 8 9 7 0 4 3 2

拼接

• 方法1: 索引从0开始 / 从高位开始
  

  Copy1int res = 0;
  2for (auto i = 0; i < n; ++i)
  3{
  4    res *= 10;
  5    res += digits[i];
  6}

  不需要处理前缀 0
  

• 方法2: 从低位开始
  

  Copy1int res = 0;
  2int times = 1;
  3for (auto i = n - 1; i >=0; --i)
  4{
  5    res += times * digits[i];
  6    times *= 10;
  7}

判断越界

• 常规思路: 反转结果长度与2³¹ - 1相同时, 按位比较
  

• 拼接时判断
  

从高位开始

循环的最后存在越界可能

Copy 1if (res * 10 > pow(2, 31) - 1)
 2{
 3    return 0;
 4}
 5// ...
 6if (res + digits[i] > pow(2, 31) - 1)
 7{
 8    return 0;
 9}
10// ...

处理表达式结果越界

Copy 1if (res > (pow(2, 31) - 1) / 10)
 2{
 3    return 0;
 4}
 5// ...
 6if (res > pow(2, 31) - 1 - digits[i])
 7{
 8    return 0;
 9}
10// ...

解答

Copy 1class Solution {
 2public:
 3    int reverse(int x) {
 4        int min = -pow(2, 31);
 5
 6        if (x == 0 || x == min)
 7        {
 8            return 0;
 9        }
10
11        int symbol = 1;
12        int limit = pow(2, 31) - 1;
13        if (x < 0)
14        {
15            x = -x;
16            symbol = -1;
17        }
18
19        vector<int> digits;
20        while(x > 0)
21        {
22            digits.push_back(x % 10);
23            x /= 10;
24        }
25
26        int res = 0, n = digits.size();
27        for (int i = 0; i < n; ++i)
28        {
29            if (res > limit / 10)
30            {
31                return 0;
32            }
33            res *= 10;
34
35            if (res > limit - digits[i])
36            {
37                return 0;
38            }
39            res += digits[i];
40        }
41
42        return res * symbol;
43    }
44};

改良

1. 拆解时, 索引从0开始: 可以省去第二次遍历
   

2. 判断越界时, 如果输入为负数, 将其 INT_MIN / 10 比较; 为正数, 与 INT_MAX / 10 比较
   

3. 累加低位时, 可以不用判断越界
   
   2³¹的个位为 8 , 2³¹ - 1的个位为 7
   

   如果前面所有位数计算完毕恰好为 2147483640 , 最后一位不可能为 7 或 8 , 或者大于这两个数
   

   因为 2147483648 和 2147483647 的反转数不能作为输入
   

Copy 1class Solution {
 2public:
 3    int reverse(int x) {
 4        int ans = 0;
 5        while(x != 0)
 6        {
 7            if (ans > INT_MAX / 10 || ans < INT_MIN / 10)
 8            {
 9                return 0;
10            }
11
12            ans = ans * 10 + x % 10;
13            x /= 10;
14        }
15
16        return ans;
17    }
18};