This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Replace the string with an integer

Write a StrToInt function to convert a string to an integer. You cannot use atoi or other similar library functions.

First, the function discards useless leading whitespace characters as needed until the first non-whitespace character is found. When the first non-null character we find is a plus or minus sign, we combine the symbol with as many consecutive digits as possible to make the integer plus or minus sign. If the first non-null character is a number, it is directly combined with successive numeric characters to form an integer.

There may also be extra characters after the valid integer part of the string, which can be ignored and should have no effect on the function.

Note: Your function does not need to convert if the first non-space character in the string is not a valid integer character, the string is empty, or the string contains only whitespace characters. In any case, if the function cannot perform a valid conversion, return 0.

Description:

Assuming that our environment can store only signed integers of 32-bit size, the values range from [−231{−2^{31}}−231, 231−1{2^{31} -1}231−1]. If the numerical more than this range, please return INT_MAX (231-1) {(2 ^ {31} – 1)} (231-1) or INT_MIN (231 -) {(2 ^ – {31})} (- 231).

Example 1:

Input: "42" Output: 42Copy the code

Example 2:

Input: "-42" Output: -42 Explanation: The first non-whitespace character is a '-', which is a minus sign. We tried to combine the minus sign with all the consecutive numbers that followed, and we ended up with -42.Copy the code

Example 3:

Input: "4193 with words" Output: 4193 Explanation: Conversion ends at the number '3' because its next character is not a number.Copy the code

Example 4:

Input: "Words and 987" Output: 0 Explanation: The first non-empty character is 'w', but it is not a number or a plus or minus sign. Therefore, a valid transformation cannot be performed.Copy the code

Example 5:

Input: "-91283472332" Output: -2147483648 Description: The number "-91283472332" exceeds the range of 32-bit signed integers. So INT_MIN (−2^31) is returned.Copy the code

Thought analysis

This is a pure programming problem, the so-called pure programming problem that is more investigation in the programming ability, ability is not algorithm (because it USES a for loop), the instructions in the topic also mentioned the attention to the problem of boundary, at the same time we also pay attention to positive and negative value (+, -) problem, the problem solving process is circular judge each character string, Then determine whether the condition is met, not timely return value.

Why is this a medium question? I feel that it is a test of careful and rigorous programming, or a bit of a test of programming skills.

The code shown

Solution 1: loop through, respectively for each character processing, pay attention to the processing of the boundary. The time complexity is O(n){O(n)}O(n), and the space complexity is also O(n){O(n)}O(n).

public int strToInt(String str) {
        String temp = str.trim();
        int length = temp.length();
        long number = 0;
        boolean isNegativeNumber = false;
        for(int i = 0; i < length; i++){char c = temp.charAt(i);
            if(c == The '-' && i == 0){
                isNegativeNumber = true;
                continue;
            }
            if(c == '+' && i == 0){
                isNegativeNumber = false;
                continue;
            }
            if(c < '0' || c > '9') {if(i == 0 || (i == 1 && isNegativeNumber)){
                    return 0;
                }
                if(isNegativeNumber){
                    return (int) -number;
                }
                return (int) number;
            }
            number = number * 10 + Integer.valueOf(String.valueOf(c));
            if(isNegativeNumber){
                long tempNumber = -number;
                if(tempNumber < -(Math.pow(2.31))){
                    tempNumber = (long) -(Math.pow(2.31));
                    return (int) tempNumber; }}if(! isNegativeNumber && number > (Math.pow(2.31) - 1)){
                number = (long) (Math.pow(2.31) - 1);
                return (int) number; }}if(isNegativeNumber){
            return (int) -number;
        }
        return (int) number;
    }
Copy the code

O(n){O(n)}O(n). The trim() function is not used, so the space is O(1){O(1)}O(1).

public int strToInt(String str) {
        int res = 0, bndry = Integer.MAX_VALUE / 10;
        int i = 0, sign = 1, length = str.length();
        if(length == 0) return 0;
        while(str.charAt(i) == ' ')
            if(++i == length) return 0;
        if(str.charAt(i) == The '-') sign = -1;
        if(str.charAt(i) == The '-' || str.charAt(i) == '+') i++;
        for(int j = i; j < length; j++) {
            if(str.charAt(j) < '0' || str.charAt(j) > '9') break;
            if(res > bndry || res == bndry && str.charAt(j) > '7')
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            res = res * 10 + (str.charAt(j) - '0');
        }
        return sign * res;
    }
Copy the code

We can take a look at the method of STR. CharAt (j) > ‘7’, this must be inexplicable, actually this is related to the maximum of the last, seemingly clever, but like chicken ribs, because we can’t see the value, from the subject directly expressed in the subject to a maximum of, but we can learn from the official writing, Very simple.

conclusion

In order to reduce the space complexity to O(1){O(1)}O(1), trim() method can also be removed. Judge for yourself, but overall the effect is not significant.