67-把字符串转换成整数

题目描述

https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof

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

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

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

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

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

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

说明：

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

示例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 (−2^31) 。

思路分析

找出起始位和结束位置
找出符号位
从结束位置开始累加结果，中间判断结果是否大于最值

实现代码

csharp

public class Solution {
    public int StrToInt(string str) {
    	int start = 0;
    	int end = 0;
    	bool positive = true;
    	bool findSign = false;
    	int result = 0;
    	//处理空格
    	int index = 0;
    	while(str[index] == ' '){
    		index++;
    	}

        if(str[index] == '+' || str[index] == '-' || (str[index] > '0' && str[index] < '9')){
            start = index;
            if(str[index] == '+' || str[index] == '-'){
                index++;
                start++;
                positive = str[index] == '+';
            }
            while(index < str.Length){
                if(str[index] >= '0' && str[index] <= '9'){
                    end = index;
                }
                else{
                    break;
                }
                index++;
            }
            //Console.WriteLine("start{0},end{1}",start,end);

            int multi = 1;

            for(int i=end; i>=start; i--){
                int v = multi * (str[i] - '0');
                
                if(result > int.MaxValue - v){
                    if(positive){
                        return int.MaxValue;
                    }
                    else{
                        return int.MinValue;
                    }
                }

                result += v;
                multi *= 10;
            }
            if(!positive){
                result = -result;
            }
        }
    	return result;
    }
}

官方解法

两个地方优化了。

1个是判断最大值 int.MaxValue = 2147483647 去除最后一位取前面的位数，然后判断最后一位是否大于7即可 str[i] > '7' 这里处理很巧妙，判断 > '7' , 看似没有考虑 MIN, 但其实无论是 = '8' ,还是 >'8',返回的都是MIN。即 2147483647 返回的就是这个数 2147483647, 如果是 -2147483648 则直接返回也不会出错，因为它就是 int.MinValue，如果再大的数，也是返回 int.MinValue

2 是不需要从 end 一直往前加了相乘，而是从前面把结果相乘10然后加到后面的新数字，这样还可以判断前缀是否是大于 int.MaxValue

sign 用正负号表示，可以直接相乘返回即可

注意比较的时候要用 char '7'

梳理一下：

从前往后依次处理，使用 i =0 表示开始处理位置，初始化 res = 0 作为最后结果

处理开始空格，直接跳过，如果跳过后，发现i到最后一位了，返回0
处理正负号保存到 sign 变量中, sign 为 1 或者 -1，如果发现符号 i++
循环处理 for(int j=i 直到结束) 如果遇到非数字直接结束循环。如果是数字就加到 res 中去注意要将之前的 res 乘以 10，因为如果 42，先加了4，到加2的时候4要乘以10，后面一次类推另外在增加一个判断最大值的越界问题，使用 int.MaxValue / 10 作为boundary，左边的数 > boundary 或者等于 boundary 并且最后一位数 > '7' 说明越界了，根据符号返回对应的最大值，注意这里只需要判断7就可以了。

csharp

public class Solution{
	public int StrToInt(string str){
        if(str.Length == 0){
            return 0;
        }
		int res = 0;
		int boundry = int.MaxValue / 10;
		int i = 0;
		int sign = 1;
		int length = str.Length;
		while(str[i] == ' '){
			i++;
			if(i == length){
			 	return 0;
			}
		}
		if(str[i] == '-'){
			sign = -1;
		}
		if(str[i] == '-' || str[i] == '+'){
			i++;
		}

		for(int j=i; j<length; j++){
			if(str[j] < '0' || str[j] > '9'){
				break;
			}
			if(res > boundry || (res == boundry && str[j] > '7')){
				return sign == 1 ? int.MaxValue : int.MinValue;
			}
			res = res * 10 + (str[j] - '0');
		}
		return sign * res;
	}
}

复习:20220509

csharp

public class Solution {
    public int StrToInt(string str) {
        //去除开始的空格，如果一直到底就返回0
        //判断字符的符号
        //判断有效的字符，累加
        //判断是否越界 boundary = int.MaxValue / 10;
        if(str == ""){
            return 0;
        }
        int i=0; 
        int result = 0 ;
        int boundary = int.MaxValue / 10; //判断边界值
        int sign = 1; //符号
        while(str[i] == ' '){
            i++;
            if(i == str.Length){
                return 0;
            }
        }
        //判断符号
        if(str[i] == '-'){
            sign = -1;
        }
        if(str[i] == '-' || str[i] == '+'){
            i++;
        }
        //判断数字
        while(i < str.Length){
            //不合法停止判断
            if(str[i] < '0' || str[i] > '9'){
                break;
            }
            //判断是否越界
            if(result > boundary || result == boundary && str[i] > '7'){
                return sign == 1 ? int.MaxValue : int.MinValue;
            }

            result = result * 10 + str[i] - '0';
            i++;
        }

        return sign * result;

    }
}

67-把字符串转换成整数 #

题目描述 #

思路分析 #

实现代码 #

官方解法 #

复习:20220509 #

67-把字符串转换成整数

题目描述

思路分析

实现代码

官方解法

复习:20220509