【剑指offer】

剑指offer

• • 面试题67：字符串转成整数
  • 面试题1：赋值运算符函数
  • 面试题3：数组中重复的数字

面试题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()
{
    //正数 负数 0
    test_atoi("123",123);
    test_atoi("-123",-123);
    test_atoi("0",0);

    //边界
    test_atoi("2147483647",2147483647); //INT_MAX
    test_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和8
            if(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. 数组中重复的数据