力扣00008.字符串转换整数(atoi)

发表于 分类于 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 9 分钟
字符串转换整数(atoi)、字符串、中等

题目描述

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
  3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  4. 将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
  5. 如果整数数超过 32 位有符号整数范围 [$−2^{31}, 2^{31} − 1$] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 $−2^{31}$ 的整数应该被固定为 $−2^{31}$ ，大于 $2^{31} − 1$ 的整数应该被固定为 $2^{31} − 1$ 。
  6. 返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ‘ ‘ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：

输入：s = “42”
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步：”42”（当前没有读入字符，因为没有前导空格）
第 2 步：”42”（当前没有读入字符，因为这里不存在 ‘-‘ 或者 ‘+’）
第 3 步：”42”（读入 “42”）
解析得到整数 42 。
由于 “42” 在范围 [$−2^{31}, 2^{31} − 1$] 内，最终结果为 42 。

示例 2：

输入：s = “   -42”
输出：-42
解释：
第 1 步：”   -42”（读入前导空格，但忽视掉）
第 2 步：”   -42”（读入 ‘-‘ 字符，所以结果应该是负数）
第 3 步：”   -42”（读入 “42”）
解析得到整数 -42 。
由于 “-42” 在范围 [$−2^{31}, 2^{31} − 1$] 内，最终结果为 -42 。

示例 3：

输入：s = “4193 with words”
输出：4193
解释：
第 1 步：”4193 with words”（当前没有读入字符，因为没有前导空格）
第 2 步：”4193 with words”（当前没有读入字符，因为这里不存在 ‘-‘ 或者 ‘+’）
第 3 步：”4193 with words”（读入 “4193”；由于下一个字符不是一个数字，所以读入停止）
解析得到整数 4193 。
由于 “4193” 在范围 [$−2^{31}, 2^{31} − 1$] 内，最终结果为 4193 。

提示：

  • 0 <= s.length <= 200
  • s 由英文字母（大写和小写）、数字（0-9）、’ ‘、’+’、’-‘ 和 ‘.’ 组成

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int myAtoi(string s) {
        s.erase(0, s.find_first_not_of(' '));
        if (s.empty())
            return 0;
        int sign = 1;
        size_t i = 0;
        if (s[i] == '+' || s[i] == '-') {
            sign = (s[i++] == '-') ? -1 : 1;
        }
        long result = 0;
        while (i < s.length() && isdigit(s[i])) {
            result = result * 10 + (s[i++] - '0');
            if (result * sign >= INT_MAX)
                return INT_MAX;
            else if (result * sign <= INT_MIN)
                return INT_MIN;
        }
        return result * sign;
    }
};

结果

执行用时 : 0 ms, 击败 100.00% 使用 C++ 的用户

内存消耗 : 6.43 MB, 击败 68.82% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int myAtoi(String s) {
        s = s.trim();
        if (s.isEmpty())
            return 0;
        int sign = 1;
        int i = 0;
        if (s.charAt(i) == '+' || s.charAt(i) == '-') {
            sign = (s.charAt(i++) == '-') ? -1 : 1;
        }
        long result = 0;
        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            result = result * 10 + (s.charAt(i++) - '0');
            if (result * sign >= Integer.MAX_VALUE)
                return Integer.MAX_VALUE;
            else if (result * sign <= Integer.MIN_VALUE)
                return Integer.MIN_VALUE;
        }
        return (int) (result * sign);
    }
}

结果

执行用时 : 1 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 41.44 MB, 击败 6.90% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def myAtoi(self, s):
        s = s.strip()
        if not s:
            return 0
        sign = 1
        i = 0
        if s[i] == '+' or s[i] == '-':
            sign = -1 if s[i] == '-' else 1
            i += 1
        result = 0
        while i < len(s) and s[i].isdigit():
            result = result * 10 + int(s[i])
            i += 1
            if result * sign >= 2**31 - 1:
                return 2**31 - 1
            elif result * sign <= -2**31:
                return -2**31
        return result * sign

结果

执行用时 : 24 ms, 击败 82.57% 使用 Python 的用户

内存消耗 : 13.01 MB, 击败 77.81% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def myAtoi(self, s: str) -> int:
        s = s.strip()
        if not s:
            return 0
        sign = 1
        i = 0
        if s[i] == '+' or s[i] == '-':
            sign = -1 if s[i] == '-' else 1
            i += 1
        result = 0
        while i < len(s) and s[i].isdigit():
            result = result * 10 + int(s[i])
            i += 1
            if result * sign >= 2**31 - 1:
                return 2**31 - 1
            elif result * sign <= -2**31:
                return -2**31
        return result * sign

结果

执行用时 : 44 ms, 击败 76.98% 使用 Python3 的用户

内存消耗 : 16.98 MB, 击败 5.10% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int myAtoi(char* s) {
    if (s == NULL) return 0;
    while (*s && isspace(*s)) {
        s++;
    }
    int sign = 1;
    if (*s == '-' || *s == '+') {
        sign = (*s == '-') ? -1 : 1;
        s++;
    }
    long result = 0;
    while (*s && isdigit(*s)) {
        result = result * 10 + (*s - '0');
        if (result * sign >= INT_MAX) {
            return INT_MAX;
        } else if (result * sign <= INT_MIN) {
            return INT_MIN;
        }
        s++;
    }
    return (int)(result * sign);
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 C 的用户

内存消耗 : 6.07 MB, 击败 98.05% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int MyAtoi(string s) {
        if (string.IsNullOrWhiteSpace(s))
            return 0;
        s = s.Trim();
        int sign = 1;
        int i = 0;
        if (s[i] == '+' || s[i] == '-') {
            sign = (s[i++] == '-') ? -1 : 1;
        }
        long result = 0;
        while (i < s.Length && char.IsDigit(s[i])) {
            result = result * 10 + (s[i++] - '0');
            if (result * sign >= int.MaxValue)
                return int.MaxValue;
            else if (result * sign <= int.MinValue)
                return int.MinValue;
        }
        return (int)(result * sign);
    }
}

结果

执行用时 : 52 ms, 击败 93.48% 使用 C# 的用户

内存消耗 : 38.67 MB, 击败 23.48% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(s) {
    s = s.trim();
    if (!s)
        return 0;
    let sign = 1;
    let i = 0;
    if (s[i] === '+' || s[i] === '-') {
        sign = (s[i++] === '-') ? -1 : 1;
    }
    let result = 0;
    while (i < s.length && !isNaN(parseInt(s[i]))) {
        result = result * 10 + parseInt(s[i++]);
        if (result * sign >= Math.pow(2, 31) - 1) {
            return Math.pow(2, 31) - 1;
        } else if (result * sign <= -Math.pow(2, 31)) {
            return -Math.pow(2, 31);
        }
    }
    return result * sign;
};

结果

执行用时 : 76 ms, 击败 58.19% 使用 JavaScript 的用户

内存消耗 : 43.27 MB, 击败 48.14% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function myAtoi(s: string): number {
    s = s.trim();
    if (!s)
        return 0;
    let sign = 1;
    let i = 0;
    if (s[i] === '+' || s[i] === '-') {
        sign = (s[i++] === '-') ? -1 : 1;
    }
    let result = 0;
    while (i < s.length && !isNaN(parseInt(s[i]))) {
        result = result * 10 + parseInt(s[i++]);
        if (result * sign >= Math.pow(2, 31) - 1) {
            return Math.pow(2, 31) - 1;
        } else if (result * sign <= -Math.pow(2, 31)) {
            return -Math.pow(2, 31);
        }
    }
    return result * sign;
}

结果

执行用时 : 88 ms, 击败 24.75% 使用 TypeScript 的用户

内存消耗 : 44.51 MB, 击败 64.64% 使用 TypeScript 的用户

PHP

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
class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function myAtoi($s) {
        $s = trim($s);
        if ($s === '')
            return 0;
        $sign = 1;
        $i = 0;
        if ($s[$i] === '+' || $s[$i] === '-') {
            $sign = ($s[$i++] === '-') ? -1 : 1;
        }
        $result = 0;
        while ($i < strlen($s) && is_numeric($s[$i])) {
            $result = $result * 10 + (int)($s[$i++]);
            if ($result * $sign >= pow(2, 31) - 1) {
                return pow(2, 31) - 1;
            } else if ($result * $sign <= -pow(2, 31)) {
                return -pow(2, 31);
            }
        }
        return $result * $sign;
    }
}

结果

执行用时 : 12 ms, 击败 26.09% 使用 PHP 的用户

内存消耗 : 19.36 MB, 击败 8.70% 使用 PHP 的用户

Swift

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
class Solution {
    func myAtoi(_ s: String) -> Int {
        let trimmed = s.trimmingCharacters(in: .whitespaces)
        if trimmed.isEmpty {
            return 0
        }
        var sign = 1
        var i = trimmed.startIndex
        if trimmed[i] == "+" || trimmed[i] == "-" {
            sign = trimmed[i] == "-" ? -1 : 1
            i = trimmed.index(after: i)
        }
        var result = 0
        while i < trimmed.endIndex && trimmed[i].isNumber {
            if let digit = Int(String(trimmed[i])) {
                result = result * 10 + digit
                if result * sign >= Int32.max {
                    return Int(Int32.max)
                } else if result * sign <= Int32.min {
                    return Int(Int32.min)
                }
            }
            i = trimmed.index(after: i)
        }
        return result * sign
    }
}

结果

执行用时 : 12 ms, 击败 27.50% 使用 Swift 的用户

内存消耗 : 16.10 MB, 击败 5.00% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    fun myAtoi(s: String): Int {
        var trimmed = s.trim()
        if (trimmed.isEmpty())
            return 0
        var sign = 1
        var i = 0
        if (trimmed[i] == '+' || trimmed[i] == '-') {
            sign = if (trimmed[i] == '-') -1 else 1
            i++
        }
        var result = 0L
        while (i < trimmed.length && trimmed[i].isDigit()) {
            result = result * 10 + (trimmed[i] - '0')
            if (result * sign >= Int.MAX_VALUE) {
                return Int.MAX_VALUE
            } else if (result * sign <= Int.MIN_VALUE) {
                return Int.MIN_VALUE
            }
            i++
        }
        return (result * sign).toInt()
    }
}

结果

执行用时 : 208 ms, 击败 16.22% 使用 Kotlin 的用户

内存消耗 : 36.90 MB, 击败 29.73% 使用 Kotlin 的用户

Dart

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
class Solution {
  int myAtoi(String s) {
    s = s.trim();
    int sign = 1;
    int result = 0;
    final maxVal = (1 << 31) - 1;
    final minVal = -(1 << 31);
    if (s.isEmpty) return 0;
    int i = 0;
    if (s[i] == '-') {
        sign = -1;
        i++;
    } else if (s[i] == '+') {
        i++;
    }
    while (i < s.length && s[i].compareTo('0') >= 0 && s[i].compareTo('9') <= 0) {
        int digit = s.codeUnitAt(i) - '0'.codeUnitAt(0);
        if (result > (maxVal - digit) ~/ 10) {
        return sign == 1 ? maxVal : minVal;
        }
        result = result * 10 + digit;
        i++;
    }
    return result * sign;
  }
}

结果

执行用时 : 340 ms, 击败 50.00% 使用 Dart 的用户

内存消耗 : 143.98 MB, 击败 100.00% 使用 Dart 的用户

Go

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
func myAtoi(s string) int {
    s = strings.TrimSpace(s)
    if s == "" {
        return 0
    }
    sign := 1
    result := 0
    maxVal := int(math.Pow(2, 31)) - 1
    minVal := -int(math.Pow(2, 31))
    i := 0
    if s[i] == '-' {
        sign = -1
        i++
    } else if s[i] == '+' {
        i++
    }
    for i < len(s) && unicode.IsDigit(rune(s[i])) {
        digit := int(s[i] - '0')
        if result > (maxVal-digit)/10 {
            if sign == 1 {
                return maxVal
            }
            return minVal
        }
        result = result*10 + digit
        i++
    }
    return result * sign
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 2.02 MB, 击败 100.00% 使用 Go 的用户

Ruby

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
# @param {String} s
# @return {Integer}
def my_atoi(s)
    s = s.strip
    return 0 if s.empty?
    sign = 1
    result = 0
    max_val = 2**31 - 1
    min_val = -(2**31)
    i = 0
    if s[i] == '-'
        sign = -1
        i += 1
    elsif s[i] == '+'
        i += 1
    end
    while i < s.length && s[i].match?(/\d/)
        digit = s[i].to_i
        if result > (max_val - digit) / 10
            return sign == 1 ? max_val : min_val
        end
        result = result * 10 + digit
        i += 1
    end
    result * sign
end

结果

执行用时 : 68 ms, 击败 -% 使用 Ruby 的用户

内存消耗 : 206.60 MB, 击败 33.33% 使用 Ruby 的用户

Scala

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
object Solution {
  def myAtoi(s: String): Int = {
    val trimmed = s.trim
    if (trimmed.isEmpty) return 0
    var sign = 1
    var result = 0
    val maxVal = Int.MaxValue
    val minVal = Int.MinValue
    var i = 0
    if (trimmed(i) == '-') {
      sign = -1
      i += 1
    } else if (trimmed(i) == '+') {
      i += 1
    }
    while (i < trimmed.length && trimmed(i).isDigit) {
      val digit = trimmed(i).asDigit
      if (result > (maxVal - digit) / 10) {
        return if (sign == 1) maxVal else minVal
      }
      result = result * 10 + digit
      i += 1
    }
    result * sign
  }
}

结果

执行用时 : 480 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 54.23 MB, 击败 100.00% 使用 Scala 的用户

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
impl Solution {
    pub fn my_atoi(s: String) -> i32 {
        let trimmed = s.trim();
        if trimmed.is_empty() {
            return 0;
        }
        let mut sign = 1;
        let mut result: i64 = 0;
        let max_val = i32::MAX as i64;
        let min_val = i32::MIN as i64;
        let mut i = 0;
        if trimmed.as_bytes()[i] as char == '-' {
            sign = -1;
            i += 1;
        } else if trimmed.as_bytes()[i] as char == '+' {
            i += 1;
        }
        while i < trimmed.len() && (trimmed.as_bytes()[i] as char).is_digit(10) {
            let digit = trimmed.as_bytes()[i] as char;
            result = result * 10 + digit.to_digit(10).unwrap() as i64;
            if result * sign >= max_val {
                return i32::MAX;
            } else if result * sign <= min_val {
                return i32::MIN;
            }
            i += 1;
        }
        result as i32 * sign as i32
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.01 MB, 击败 59.21% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

1
2
3
4
5
6
7
8
9
10
11
12
13
-spec my_atoi(S :: unicode:unicode_binary()) -> integer().
my_atoi(S) ->
    Str = unicode:characters_to_list(S),
    Str2 = string:strip(Str),
    case string:to_integer(Str2) of
        {Num, _} when is_integer(Num) ->
            case {Num < -2147483648, Num > 2147483647} of
                {true, false} -> -2147483648;
                {false, true} -> 2147483647;
                {false, false} -> Num
            end;
        _ -> 0
    end.

结果

执行用时 : 288 ms, 击败 100.00% 使用 Erlang 的用户

内存消耗 : 59.31 MB, 击败 100.00% 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户