7. Reverse Integer

题目

第一问: 请实现整数的逆序，该整数为32位有符号整数

思路

在接触到这道题之后，我们首先思考一下都有哪些情况需要处理：

首先是正整数、负整数以及0。

其次对于这种规定了输入数据范围的题目，我们都需要想一想边界情况的处理，对于本问，也就是一个整数逆序完是否会溢出。

答案是肯定的，32位有符号整数的范围是[−2³¹, 2³¹ − 1]，即[-2147483648, 2147483647]，当一个10位数，它的个位数大于2，那他逆序完一定会溢出。

所以在我们逆序完一个整数之后，需要判断这个整数是否会超过32位有符号整数，也就是int的范围即可。

class Solution {
  public int reverse(int x) {
  // 定义数组存储每一位，因为是32位整数，所以最多不会超过10位
    int[] digits = new int[10]; 

    // 分离每一位，并存入数组
    // 如果是负数，则存入的每一位都是负值
    // 最后逆序加总得到的值也是负数
    // 所以正数负数均可以使用同一套逻辑分离数位
    int digitsPointer = 0;
    while (x != 0) {
      digits[digitsPointer++] = x % 10;
      x /= 10;
    }

    // 逆序相加，这里使用long来存储，因为会有int溢出的情况
    long sum = 0, factor = 1;
    for(int i = digitsPointer - 1; i >= 0; i --) {
      sum += digits[i] * factor;
      factor *= 10;
    }

    // 判断是否越界
    // Java 中，Integer.MAX_VALUE对应的是2147483647
    // Integer.MIN_VALUE对应的是-2147483648
    if (sum >= 0) {
      return sum > Integer.MAX_VALUE ? 0 : (int)sum;
    } else {
      return sum < Integer.MIN_VALUE ? 0 : (int)sum;
    }
    
  }
}

上面我们通过数组存储了每一位，但其实完全没有必要使用数组。

class Solution {
  public int reverse(int x) {
    long sum = 0;
    while (x != 0) {
      // 在这里，我们失去了数组的帮助
      // 需要通过每次让上次的结果乘以10加上本轮数字的个位数
      // 以达到逆序的效果
      // 比如 123, 则sum值的变化为
      // 0 -> 0 * 10 + 3 = 3 -> 3 * 10 + 2 = 32 -> 32 * 10 + 1 = 321
      
      sum = sum * 10 + (x % 10);
      x /= 10;
    }

    // 判断是否越界
    if (sum >= 0) {
      return sum > Integer.MAX_VALUE ? 0 : (int)sum;
    } else {
      return sum < Integer.MIN_VALUE ? 0 : (int)sum;
    }
  }
}

第二问：在上面的方法中，你使用了’long’来存储最终的结果，这种情况下，你需要更大的数据类型来计算最终的结果。能否只使用’int’来完成逆序的实现呢？

思路

对于一个算法，如果你需要开辟更大的数据类型来存储对应的结果，那么当输入的数据超过了最大的数据类型的时候，这个算法就无法正常工作了。

这道题会溢出的边界情况，当且仅当循环运行到第十次的时候，也就是循环的最后一次乘以十再加总的过程中才会发生（因为int最大是十位数）。

至于为什么会溢出，详见二进制专题。

对于本题来说，我们假设上一次循环得到的最终结果为a, 本轮的结果为c, 则c = a * 10 + x % 10，设b = x % 10, 则有c = a + b

记不发生溢出时的结果为c1, 发生溢出时候的结果为c2，显然c1 != c2:

有 c1 != c2 => c1 - b != c2 - b => (c1 - b) / 10 != (c2 - b) / 10

又有 b = x % 10 => b / 10 == 0, 则有 c1 / 10 != c2 / 10

因为c1 = a + b => c1 / 10 = a + b / 10 = a

综上 a != c2 / 10

即上一轮的结果 != 溢出时的本轮结果 / 10

结论：

若本轮结果/10与上一轮结果相同，则没有溢出；

若本轮结果/10与上一轮结果不同，则溢出；

class Solution {
  public int reverse(int x) {
    int lastSum = 0;
    
    while (x != 0) {
      int newSum = lastSum * 10 + x % 10;

      // 本轮结果/10 不等于 上一轮结果，则溢出
      if (newSum / 10 != lastSum) {
        return 0;
      }

      lastSum = newSum;

      x /= 10;
    }

    return lastSum;
  }
}