剑指 Offer 67: 把字符串转换成整数

[songyy5517]

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明： 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: "42"
输出: 42

示例 2:

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3:

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

示例 4:

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。

示例 5:

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

分析 这道题考察的是字符串与整数之间的转换。因此，我们可以基于数字的性质，对字符串中的字符依次进行判断，包括正负号，数字，其他字符等等。因为要考虑越界问题，一旦当数字越界，我们就无需继续遍历字符串了，因此每次遍历时计算数字，并判断是否越界，从而提前剪枝。

[songyy5517]

思路：字符串遍历，累加和

1. 异常处理；
2. 字符串剪枝：去掉前面多余的空格；判断剪枝后的字符串是否为空；
3. 定义相关变量：符号位sign（int），字符串的数字结果res （long）；
4. 遍历字符串：
   • 首字符为+/-符号，则进入下一个循环；
   • 若当前字符为数字，则计算结果res = res * 10 + char - '0'；否则跳出循环；
   • 通过当前结果res，判断字符串是否越界。
5. 返回最终结果：res * sign。

复杂度分析

• 时间复杂度： $O(N)$ ， $N$ 为字符串长度，字符串剪枝和计算结果需要遍历字符串，使用 $O(N)$ 大小的时间；
• 空间复杂度： $O(1)$ ，额外定义了常数大小的变量。

[songyy5517]

import java.util.*;
public class Solution {
    public int StrToInt (String s) {
        // write code here
        // 分析：这道题类似于之前判断字符串是否为数值的题目，需要进行分类讨论。

        // 1. 异常处理
        if (s == null || s.length() == 0)
            return 0;

        // 2. 字符串预处理
        s = s.trim();
        if (s.length() == 0)
            return 0;

        // 3. 定义相关变量：符号位，字符串的数字结果
        int sign = s.charAt(0) == '-' ? -1 : 1;
        long res = 0;    // int -> long

        // 3. 遍历
        for (int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            // 首字符判断
            if (i == 0 && (cur == '+' || cur == '-'))
                continue;

            // 判断当前字符，累加结果
            if (cur >= '0' && cur <= '9')
                res = res * 10 + (cur - '0');  
            else
                break;

            // 越界判断
           if (res * sign > Integer.MAX_VALUE || res * sign < Integer.MIN_VALUE){
                return sign == -1 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
           }
        }

        return (int)res * sign;
    }
}

[songyy5517]

Key points:

1. 将数字字符串转换成数字：先左移再加数字;
2. int越界；

[songyy5517]

2023/12/2 2024/3/25

1. 剪枝：逐步计算当前字符串对应的数字，并判断是否越界。