Location>code7788 >text

LeetCode Problem Set - 7 - Integer Inversion

Popularity:266 ℃/2024-12-14 22:24:26

Question: Given a 32-bit signed integer x, return the result of inverting the numeric part of x. If the inverted integer exceeds the 32-bit signed integer range [-231 - 231 - 1], return zero. If the inverted integer exceeds the range [-231, 231 - 1] for 32-bit signed integers, return 0.

It is assumed that the environment does not allow storing 64-bit integers (signed or unsigned).

01String Conversion Method for Long Types

Although the topic requirements do not allow the use of 64-bit integers, but we still use the simplest and most intuitive most logical way of thinking to realize, and then use this to open the mind to find a better way.

My first reaction to this question was to convert the integer x to a string, then call the string method directly to invert the string, and finally convert the inverted string to a long type and compare whether it is within the valid range or not.

Of course this is the general idea of solving the problem, and there are many details to be dealt with in it.

First of all need to deal with the negative sign, if it is a negative number we need to take its absolute value, and then reverse the absolute value, and in the absolute value need to pay attention to the int of the minimum value of -2147483648, and the maximum value of 2147483647, so we can not directly on the int integer x directly to take the absolute value of the need to first x to long type of integer, otherwise it will be reported as an error.

Then invert the absolute value into a character array, while determining the positive and negative signs, if it is negative then you need to add the negative sign '-' before the character array.

Finally, directly use the method to convert the character array, while determining its effective range, and output the results, the specific code is as follows:

//String long
public static int ReverseLongString(int x)
{
    //Is the number negative
    var isNegative = x < 0; //take the absolute value, must be converted to long first.
    //Take the absolute value, must first be converted to long type
    //otherwise -2147483648 will report an error
    var abs = ((long)x);; //convert the value to a string.
    //convert the value to a string and reverse it to get a collection of characters
    var reversedChars = ().
    if (isNegative)
    {
        // if isNegative then add the negative sign '-' before the byte array
        reversedChars = ('-');
    }
    // Convert to long type and a valid int value, then return the result
    if (((), out long result) && result >= && result <= )
    {
        return (int)result.
    }
    return 0; }
}

02String conversion method for int types

Since the question asks us not to use the 64-bit integer long type, can we convert directly to the int type?

According to the previous solution,Same idea.,Let's start by puttingintinteger (math.)xConvert to String,Then just use the conversion directly。This filters out all overflow values using conversion failures。

The specific implementation code is as follows:

//String int
public static int ReverseIntString(int x)
{
    //convert the value to a string and remove the minus sign '-' and finally reverse it to get the set of characters
    var reversed = ().TrimStart('-').Reverse();
    //convert to int, return if successful
    if (((), out int result))
    {
        // according to the original sign, return the result
        return x < 0 ? -result : result;
    }
    return 0; }
}

03Mathematical Methods

The above two methods are still essentially through the string conversion, on the efficiency is relatively low, so we can mathematically calculate the way to achieve its conversion.

As shown above, we take the 12345 reversal as an example to explain the reversal process in detail.

(1) By 12345%10, the trailing digit 5 is obtained, which in turn will be used as the first digit of the new value, the new value 5;

(2) By 1234%10, the trailing number 4 is obtained and the new value is 5*10+4=54;

(3) By 123%10, the trailing number 3 is obtained and the new value is 54*10+3=543;

(4) By 12%10, the trailing number 2 is obtained and the new value is 543*10+2=5432;

(5) By 1%10, the trailing digit 1 is obtained and the new value is 5432*10+1 = 54321;

There is also a focus on the judgment of overflow, the first two methods are essentially through the conversion method to trigger an exception to intercept the overflow, while in this method we can directly determine whether the overflow in the process of real-time calculations.

Because the 32-bit signed integer x value range is -2147483648<=x<=2147483647, if you want to ensure that the reversal over the non-overflow, then in the processing of the ninth position when the entire value should be between (-214748364, 214748364), otherwise the result will certainly overflow, and the first digit of the valid int value is the maximum of 2, even if reversed over the impossibility of greater than 7 or less than -8, so only need to determine whether the ninth digit is legal to complete the overflow judgment.

The specific implementation code is as follows:

//Math method
public static int ReverseMath(int x)
{
    var result = 0; while (x !
    while (x ! = 0)
    {
        //To determine the overflow, since the input is a 32-bit signed integer x
        //i.e. the input -2147483648<=x<=2147483647
        //so flipping the last digit to 1 or 2 does not cause an overflow
        // so just determine the nine digits > / 10 or < / 10
        if (result < / 10 || result > / 10)
        {
            return 0; }
        }
        // Get the number at the end of the current digit
        var digit = x % 10; }
        // Remove the last digit
        x /= 10; //reverse and accumulate the result
        //Reverse and accumulate the result
        result = result * 10 + digit.
    }
    return result; }
}

04Benchmarking

We do a simple benchmark test, respectively, on the three methods of 1 million times randomly generated integer values in the range -2147483648 to 2147483647 between the value of the test, the following results.

It is easy to see from the above graph that the math approach is far superior to the string processing approach in terms of overall performance.

classifier for sums of money: The test method code as well as the sample source code have been uploaded to the code repository for those who are interested./hugogoos/Planner