-Reverse INTEGER

The problem

Given a 32-bit signed integer, reverse digits of an integer. 

 Example 1: 


Input: 123
Output: 321


 Example 2: 


Input: -123
Output: -321


 Example 3: 


Input: 120
Output: 21


 Note: 
Assume we are dealing with an environment which could only store integers within the 32-bit signed integerRange: [−231, 231 − 1]. For the purpose of this problem, assume that yourfunction returns 0 when the reversed integer overflows. 


Copy the code

Translation:

Given a 32-bit signed integer, invert it.

Example 1:

Input :123 Output :321

Example 2:

Input :-123 Output :-321

Example 3:

Input :120 Output :21

Note: Assume we are working with an environment that can only store integers in the range of 32-bit signed integers :[-231,231-1]. For this problem, assume that the function returns 0 on a reverse integer overflow.

Their thinking

If you want to reverse an integer, you need to pay attention to the following three points:

1. signed
2. 32-bit digits that may overflow if reversed
3. If you flip it, you get rid of the ones that start with 0.

If the value is greater than an Integer, it returns 0. We can use long instead, or we can catch exceptions when converting an Integer

First, take the absolute value, obtain a single digit, and then concatenate it into the final result, remove the value with a head of 0, and finally assign the millionaire, replace it with long, and compare the maximum value of integer.

The problem solving method

1. The first method of disintegration is to edit it as we would like, with the following code

   // get rid of the 0 specialif (x == 0) {
           return0; } // int temp = x; boolean isMinus =false;
       if (x < 0) {
           temp = -temp;
           isMinus = true; } StringBuilder StringBuilder = new StringBuilder(temp+"").reverse(); Int zoreCount = 0;for (int i = 0; i < stringBuilder.length(); i++) {
           if (stringBuilder.charAt(i) == '0') {
               zoreCount++;
           } else {
               break; }}if(zoreCount>0){
           stringBuilder.delete(0,zoreCount);
       }
       try{
           return Integer.valueOf(isMinus?"-"+stringBuilder.toString():stringBuilder.toString());
       }catch (Exception e){
           return 0;
       }
   Copy the code

   Time complexity: this scheme does not use a cycle, in fact, it should be used for a cycle in the flipping process, but it does not calculate. On this side, when the head is judged to be 0, it cycles once, so it is denoted as N, so f(n)=(log10(n)-1)+0)/2=log10(n)/2; So O(f(n))=O(log base 10(n)), so T(log base 10(n))=O(n).

   Space complexity: This scheme uses StringBuilder, which is equivalent to replicating an array, so the space complexity is O(1);

2. The second way to solve the problem is as follows:

   Long temp = x; long temp = x; boolean isMinus =false;
       if (x < 0) {
           temp = -temp;
           isMinus = true; } long value = 0; // Get the length.while(temp / 10 ! = 0 || temp % 10 ! = 0) { long remainder = temp % 10; value = value * 10 + remainder;if (value > Integer.MAX_VALUE) {
               return 0;
           }
   
           temp = temp / 10;
       }
   
       return(int) value * (isMinus ? 1:1);Copy the code

   Time complexity: the scheme used the single cycle, so (n) = f (log10 (n) + 1) / 2 = log10 (n) / 2; So O (f (n)) = O (log10 (n)) = O (log10 (n)), T (n) = O (log10 (n))

   Space complexity: This scheme does not use extra space to store values, so it is O(1);

conclusion

The general solution to this problem is as described above, scheme 2 does not use the string and starts directly from itself, which is faster in space and time than Scheme 1. The only thing is that it needs to be controlled by long. In case int is the minimum negative value, once it becomes positive, it overflows.