Title link: leetcode-cn.com/problems/re…

Method 1: mathematical method

When we see the problem of integer reversal, we first associate it with taking the absolute value of the value and then mod it by dividing ten to reverse the integer. Then we consider whether we need to take negative numbers and the range of values.

/** * @param {number} x * @return {number} */
var reverse = function(x) {
    let result = 0;
    let value = Math.abs(x);
    while(value ! = =0) {
        result = result * 10 + value % 10;
        value = Math.floor(value / 10);
    }
    result = x > 0 ? result : - result;
    return (result > Math.pow(2.31) - 1 || result < - Math.pow(2.31)?0 : result);
};
Copy the code
  • Time complexity: O(log(n))
  • Space complexity: O(1)

At this point, I thought I was done, and I passed all the test cases. But! If you recall the instructions in the question:

Suppose our environment can store only 32-bit signed integers.

When we tested the above program, it was not in such a harsh environment, so we first got result, and then judged whether it was within the range of the required value. If not, return (0), so we passed all test cases normally. But really, in an environment where only 32-bit signed integers can be stored, if the integer reverses beyond the required value range, we get no result at all, because we overflow. Therefore, overflow judgment is required when integer inversion is performed.

  1. Loop through the numbersxEach bit of the unwrap, in integer inversion, each step to determine whether overflow;
  2. There are two overflow conditions, one is greater than the integer maximumMAX_VALUEAnd the other is less than the integer minimumMIN_VALUE, set the current calculation result asresultAnd the next one ispop;
  3. fromresult * 10 + pop > MAX_VALUEThe overflow condition looks like:
    • When there is aresult > MAX_VALUE / 10And there arepopWhen it needs to be added, it must overflow;
    • When there is aresult === MAX_VALUE / 10 且 pop > 77 is the units digit of 2^ 31-1 (2^ 31-1 = 2147483647).
  4. fromresult * 10 + pop < MIN_VALUEThe overflow condition looks like:
    • When there is aresult < MIN_VALUE / 10And there arepopWhen it needs to be added, it must overflow;
    • When there is aresult === MIN_VALUE / 10 且 pop < -88 is the units digit of -2^31 (-2^31 = -2147483648).
/** * @param {number} x * @return {number} */
var reverse = function(x) {
    let result = 0;
    let value = Math.abs(x);
    let MIN_VALUE = - Math.pow(2.31);
    let MAX_VALUE = Math.pow(2.31) - 1;
    while(value ! = =0) {
        let pop = value % 10;
        // Overflow judgment
        if (result > MAX_VALUE / 10 || (result === MAX_VALUE / 10) && pop > 7) return 0;
        if (result < MIN_VALUE / 10 || (result === MIN_VALUE && pop < - 8 -)) return 0;
        result = result * 10 + pop;
        value = Math.floor(value / 10);
    }
    return (x >= 0 ? result : - result);
};
Copy the code

Method 2: the JavaScript reverse() method

JavaScript string conversion methods can be used, but string conversion is inefficient and apI-dependent. Tests on Leetcode.com show that it consumes more time and memory than method 1.

Let ret = coefficient * str.split(” “).reverse().join(” “); If the value of the conversion exceeds the range required by the problem, the step overflows, so this method does not apply. If you have a better way, very hope to communicate with you to learn.

/** * @param {number} x * @return {number} */
var reverse = function(x) {
    let coefficient = x >= 0 ? 1 : - 1;
    let str = Math.abs(x) + ' ';
    let ret = coefficient * str.split(' ').reverse().join(' ');
    return (ret > Math.pow(2.31) - 1 || ret < - Math.pow(2.31)?0 : ret);
};
Copy the code

I don’t know how to calculate the time complexity and space complexity of method 2 here, please get the guidance of the big guy.

More antithesis

Please follow: github.com/leviding/le…

My level is limited, welcome to exchange and share your ideas, welcome big guy criticism and correction.

Scan the QR code below and follow the wechat public account “Technology Chat” to subscribe for more exciting content.