LeetCode 第7题

题目

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。 示例 1: 输入: 123 输出: 321 示例 2: 输入: -123 输出: -321 示例 3: 输入: 120 输出: 21 注意: 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

思路

一开始的思路是把数字取模然后放到int数组里，但是这样复杂又难实现，时间复杂度上也没优势

后来看到网络上的答案，思路是这样的： 首先把要判断这个数是否超范围 然后再把这个数x拿来取模，获得最后一个数并赋值给一个新的变量 然后x自除10，进入下一次循环 第二次循环的时候新变量自乘10再加取模得到的数。最后返回这个新变量

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int reverse(int x) {
        int rev = 0;            //新变量
        while (x != 0) {
            //判断我们取得的数是否超范围
            // 2^31-1 = 2147483647   |  -2^31 = -2147483648
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
             int pop = x % 10;        //取模拿到个位数
             rev = rev * 10 + pop;      //自身×10空出个位，然后加上刚刚取模出来的数
             x /= 10;                   //迭代条件。因为x是int类型，所以÷10以后小数点就被省略了
        }
        return rev;
    }
}

这种思路，就不需要把数字切成一个一个再拼接。直接利用数字的特性，通过取模和乘除运算带达到效果。

  • 时间复杂度：O(log(x))，x 中大约有 log{10}(x)位数字。
  • 空间复杂度：O(1)