leetcode-8-String-to-Integer-(atoi)

发表于   |  

描述

Implement atoi to convert a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

分析

大概是通过率最低的 Easy 类型的题目，因为边界情况太多了？

atoi 要求：

  1. 丢掉字符串前面的空格，可能有正负号，超过一个正负号就无法转换
  2. 字符串可以包括非数字字符，如果遇到非数字字符，只取非数字字符前的数字
  3. 如果第一个字符不是数字字符，不进行转换
  4. 不能转换，返回0，转换的值超过int，返回边界值（2147483647或-2147483648）

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int myAtoi(string str) {
        long long result = 0;
        char flag = '+';
        
        int len = str.length();
        int i = 0;
        
        while (str[i] == ' ' && i < len) {
            i++;
        }
        
        if(len < 1) {
            return result;
        }
        
        if(str[i] == '-') {
            flag = '-';
            i++;
        }else if(str[i] == '+') {
            flag = '+';
            i++;
        }
        
        for( ; i < len; i++) {
            if(str[i] < '0' || str[i] > '9') {
                break;
            }
            if(flag == '-') {
                result = result * 10 - (str[i]-'0');    
            }else if(flag == '+') {
                result = result * 10 + (str[i]-'0');    
            }
            
            if(result > INT_MAX) {
                return INT_MAX;
            }
        
            if(result < INT_MIN) {
                return INT_MIN;
            }
        }
        return result;
    }
};

解决方案2(Rust)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
pub struct Solution {}

impl Solution {
    pub fn my_atoi(str: String) -> i32 {
        let (i32_min, i32_max) = (-2_i64.pow(31), 2_i64.pow(31)-1);
        let mut result: i64 = 0;
        let mut flag = false;

        let mut num_matched = false;
        for ch in str.chars().into_iter() {
            if !num_matched {
                match ch {
                    ' ' => {},
                    '0'...'9' => {
                        num_matched = true;
                        result = result * 10 + ch.to_digit(10).unwrap() as i64;
                    },
                    '-' => {
                        num_matched = true;
                        flag = true;
                    },
                    '+' => { num_matched = true; }
                    _ => return 0
                }
            } else {
                match ch {
                    '0'...'9' => {
                        result = result * 10 + ch.to_digit(10).unwrap() as i64;
                        if result > i32_max {
                            break
                        }
                    },
                    _ => break
                }
            }
        }

        result = if flag { -result } else { result };
        if result > i32_max { return i32_max as i32; }
        if result < i32_min { return i32_min as i32; }
        return result as i32;
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_leetcode_8() {
        assert_eq!(Solution::my_atoi("42".to_string()), 42);
        assert_eq!(Solution::my_atoi("    -42".to_string()), -42);
        assert_eq!(Solution::my_atoi("4193 with words".to_string()), 4193);
        assert_eq!(Solution::my_atoi("words and 987".to_string()), 0);
        assert_eq!(Solution::my_atoi("-91283472332".to_string()), -2147483648);
    }
}

解决方案3（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func myAtoi(s string) int {
    newStr := strings.TrimSpace(s)
    if len(newStr) == 0 {
        return 0
    }
    
    var (
        sign int
        abs string
        result int
    )
    
    switch newStr[0] {
    case '-':
        sign, abs = -1, newStr[1:]
    case '+':
        sign, abs = 1, newStr[1:]
    default:
        sign, abs = 1, newStr
    }
    
    for i, ch := range abs {
        if ch < '0' || ch > '9' {
            abs = abs[:i]
            break
        }
    }
    
    for _, num := range abs {
        result = result * 10 + int(num-'0')
        switch {
        case sign == -1 && sign * result < -1<<31:
            return -1<<31
        case sign == 1 && result > 1 << 31-1:
            return 1<<31-1
        }
    }
    return result * sign
}

相关问题

题目来源