【算法题】字符串转整数 (atoi)

深碍√TFBOYSˉ_ 2022-05-23 12:45 230阅读 0赞

题目：

实现 `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) 。

**思想：**

这道题其实比较容易就是遍历字符串中的每一个字符，然后提取中符合条件的数字，保存在数组中，最后将数组中的数字变为数字，但是这道题变态的地方在于编程者基本上很难一开始考虑到所有的限制条件，导致要一次一次提交才能知道自己错在哪里，需要改进那些地方。我在这里采用的笨方法，就是设置标志。

#include <iostream>
    #include <vector>
    #include <math.h>
    using namespace std;
    
    
    int myAtoi(string str) {
    	int len = str.length();
    	char num[100] = {'0'};
    	int cnt=0;
    	bool first_flag = false;//是否出现了第一个有意义的数字，比如000000001，那么1就是第一个有意义的数字，学术名是什么忘记了
    	bool black_flag = false;//第一个有意义的字符，可以是数字也可以是正负号，这个和上面的标志位都是为了能够跳过空格和无意义的0，但是不能合并，因为无意义的0可以出现在正负号后面
    	bool nega_flag = false;//整个数字是正数还是负数
        bool zero_flag = false ;//开头跳过的字符是否有零，如果有零则后面不能出现正负号
    	for(int i=0 ; i < len ; i++)//开始遍历
    	{
    		if((str[i] == ' '||str[i] == '0')&& black_flag == false)//如果是无意义的0或者空格跳过
    		{
    			if(str[i]=='0')//如果是无意义的零，则记录下来
    			{
    				zero_flag = true;
    			}
    			else if(zero_flag == true&&str[i] == ' ') return 0;//因为已经跳过了无意义的0，所以后面不能再跳过空格了
    			continue;
    		}
    		else if(str[i] != ' ' &&black_flag == false)//终于遇到一个有意义的字符了
    		{
    			
    			black_flag = true;
    			//下面就是正负号和数字都是可以接受的，这个字符作为数字的第一位
    			if((str[i]<= '9' && str[i] >= '0'))
    			{
    				first_flag = true;//找到第一个有意义的数字
    				num[cnt++] = str[i];
    			}
    			else if(str[i] == '-' &&zero_flag==false)
    			{
    
    				nega_flag = true;//设置该数字是正数还是负数
    			}
    			else if(str[i] == '+'&&zero_flag==false)
    			{
    
    				nega_flag = false;
    			}
    			else
    			{
    				break;
    			}
    		}
    		else if(str[i] !=' ' &&black_flag == true)//如果数字的第一位已经找到了，这里开始寻找后面的数字
    		{
    			
    			if(str[i] == '0'&&first_flag == false)//这里跳过无意义的0
    			{
    				//cout<<str[i]<<endl;
    				continue;
    			}
    			else if((str[i]<= '9' && str[i] >= '0'))//
    			{
    				    
    				    first_flag = true;//找到第一个有意义的数字，这里是重复设置了标志变量，但是无影响
    					num[cnt++] = str[i];//记录数字
    					if(cnt >10) { //如果数字的位数大于10位，则肯定超过了32位的有符号范围
    					      return 	nega_flag ? -2147483648 :2147483647;
    					}
    			}
    			else
    			{
    				break;
    			}
    		}
    		else
    		{
    			break;
    		}
    	}
    	if(cnt ==0)//如果没有记录任何数字，肯定不能转换
    	{
    		
    		return 0;
    	}
    	else if(cnt >10)//这里其实可要可不要
    	{
    		if(nega_flag == false)
    		{
    			return 2147483647;
    		}
    		else
    		{
    			return -2147483648;
    		}
    
    	}
    	else//接下来就是转换数字，记住高位是放在num数组中的前半部分，可以看成是大端模式
    	{
    	
    		int sum =0;
    		int max = nega_flag ? -2147483648 :2147483647;
    		num[cnt]='\0';
    		for(int j=cnt;j>0;j--)
    		{
    			if(cnt == 10){
    				if(nega_flag==false){
    					
    					if(strcmp(num,"2147483647") > 0) return max;
    					
    				}
    			  else
    			  {
    					if(strcmp(num,"2147483648") > 0) return max;
    			  }
    			}
    			sum+= pow(10,(cnt-j))*(num[j-1]-'0');
    		}
            
    		return nega_flag ?0-sum:sum;
    	}
    
    }
            
    
    
    int main()
    {
    	cout<<myAtoi("1095502006p8");
    	return 0;
    }