【剑指offer】

面试题67：字符串转成整数

LeedCode：LCR 192. 把字符串转换成整数 (atoi)

测试atoi的功能和异常效果

#include <iostream>
#include <cstdlib>using namespace std;
//测试atoi的各项功能
//atoi：将数字字符串转换成int类型的整数
void test_atoi(const char *str,int expectd)
{int ret = atoi(str);if(ret == expectd){cout<<"Test passed:atoi("<<str<<") = "<<ret<<endl;}else{cout<<"Test failed:atoi("<<str<<") = "<<ret<<endl;}
}int main()
{//正数 负数 0test_atoi("123",123);test_atoi("-123",-123);test_atoi("0",0);//边界test_atoi("2147483647",2147483647); //INT_MAXtest_atoi("-2147483648",-2147483648); //INT_MIN//非法输入test_atoi("",0);test_atoi("abc",0);test_atoi("123abc",123);test_atoi("abc123",0);//混合输入test_atoi("123 ",123);test_atoi(" 123",123);test_atoi(" -123",-123);test_atoi("-123 ",-123);//溢出 --有符号的上溢和下溢test_atoi("2147483656",21474836456);test_atoi("-2147483660",-2147483660);system("pause");return 0;
}

运行效果：

溢出这里atoi函数的操作和LeedCode上的要求不一样，LeedCode上简化了要求，如果上溢那就输出最大的正整数，如果下溢那就输出最小的负整数，具体的计算机溢出可以参照这篇文章：整数溢出详解

计算机中有 4 种溢出情况，以 32 位整数为例。

① 无符号上溢：无符号数 0xffffffff 加 1 会变成 0。

② 无符号下溢：无符号数 0 减去 1 会变成 0xffffffff,即-1。

③ 有符号上溢：有符号正数 0x7fffffff 加 1 变成 0x80000000, 即从 2147483647 变成了-2147483648。

④ 有符号下溢：有符号负数 0x80000000 减去 1 变成 0x7fffffff,即从-2147483648 变成了 2147483647。

因此实现把一个字符串转换成整数这个问题，需要考虑以下几点

1. ““和” “和"0”，三种情况输出的都是0，实际上是有区别的，按照书上说的，atoi是通过全局变量来区分的，如果是非法输入，返回0并把这个全局变量设为一个特殊标记，如果输入是"0”，则返回0，不会设置全局变量，可以通过检查全局变量来查看是非法输入还是字符串"0"
2. 正负号的判断，正负号占一个位置，并且正负号后应当紧接着就是数字，否则也是非法输入，相当于还是识别到了" "
3. 溢出，int类型是4字节，取值范围是INT_MAX：2147483647 INT_MIN：-2147483648，这个宏定义在<limits.h>这个头文件里，可以包含然后直接用

这里提供了满足LeedCode上要求的代码，其实还有合法非法，以及溢出问题没有考虑到
下面是用C++实现的代码，

class Solution {
public:int myAtoi(string str) {int res = 0,bndry = INT_MAX/10;int i = 0,sign = 1,len = str.size();if(len == 0) return 0; //空字符串while(str[i] == ' '){if(++i == len) return 0; //空格后面全是空格}if(str[i] == '-') sign = -1; //负号if(str[i] == '+' || str[i] == '-') i++; //正号或负号for(int j = i;j<len;j++){if(str[j] <'0' || str[j] >'9') break; //非数字字符//int类型：INT_MAX：2147483647 INT_MIN：-2147483648，尾数为7和8if(res > bndry || res == bndry && str[j] >'7'){return sign == 1 ? INT_MAX : INT_MIN; //溢出}res = res*10 + (str[j]-'0');}return sign*res; }
};

用C实现的代码：

int myAtoi(char* str) {assert(str); //空指针判断if (*str == '\0') //空串判断return 0;while (isspace(*str)) { //清除空格str++;}int sign = 1; //判断正负号if (*str == '-')sign = -1;if (*str == '+' || *str == '-')str++;int ret = 0, bon = INT_MAX / 10;while (*str != '\0') {if (*str < '0' || *str > '9')break;if (ret > bon || ret == bon && *str > '7') { //溢出判断return sign == 1 ? INT_MAX : INT_MIN;}ret = ret * 10 + (*str - '0');str++;}return sign * ret;
}

书上的代码：

面试题1：赋值运算符函数

class CMyString
{
public:CMyString(char* pData = nullptr);CMyString(const CMyString& str);~CMyString(void);
private:char* m_pData;
};

面试题3：数组中重复的数字

LeedCode：442. 数组中重复的数据