Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Inverts the output of the given integer.”

Title link: Source: LeetCode

Link: leetcode-cn.com/problems/re…

2

Takes a 32-bit signed integer x and returns the result of partially reversing the number in x.

Returns 0 if the inverted integer exceeds the range of 32-bit signed integers [-231,231-1].

Assume that the environment does not allow storage of 64-bit integers (signed or unsigned).

Such as:

Input: x = 123 Output: 321

Input: x = -123 Output: -321

Input: x = 120 Output: 21

Second, the problem solving

1. Analysis of ideas

This problem is very simple if the data overflow problem is not considered, you can use a layer of loop to get the end of the number.

For example, 123:1) 123%10 to 3, then 123/10 2) 12%10 to 2, then 12/10 3) 1%10 to 1, then 1/10

With modulo and division, numbers like 12300 can be solved perfectly.

The value range of the converted integer is [-231,231-1], which does not meet the requirement of returning 0.

There are two overflow conditions, one is greater than the maximum value of the integer MAX_VALUE and the other is less than the minimum value of the integer MIN_VALUE. Let the current calculation result be digit and the next digit be rev.

  • Digit * 10 + rev > MAX_VALUE

Overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow overflow

  • Digit * 10 + pop < MIN_VALUE

When digit < = MIN_VALUE / 10 and rev < -8, overflow when digit < = MIN_VALUE / 10 and rev < -8, 8 is the units digit of -2^31

2. Code implementation

Iterating over the string S from left to right, adding each character to the appropriate line, comparing the appropriate line using the current line and current direction variables.

The current direction changes only when you move up to the top row or down to the bottom row.

public class Solution 
{
    public int Reverse(int x) 
    {
        int rev = 0;
        while(x ! =0) 
        {
            if (rev < int.MinValue / 10 || rev > int.MaxValue / 10) 
            {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        returnrev; }}Copy the code

Execution Result:

3. Time complexity

Time order of log∣x∣

The number of flips is x decimal bits.

Space complexity: O(1)

There are constant variables, so space complexity is O(1).

Third, summary

If you have a 10-digit number less than 2^31, the first digit can only be 1 or 2, and the last digit can only be 1 or 2, which is less than 7.

If it’s greater than 7, the input overflows. So we don’t have to worry about the bottom 7 and the bottom 8, we just have to make sure that the other 9 bits satisfy.