Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode String to Integer (atoi)

Leetcode algorithms 第 8 题:String to Integer (atoi) 。

题目

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

解答

atoi的基本思想就是从高位到低位逐个遍历源字符串的每一位,把它加到目标变量中,最终得到的即为答案。但这里重要的是对细节的处理,而不仅仅是能够完成最基本的功能,于是需要考虑以下的若干方面。

  • 空串,直接返回0。
  • 正负号,处理正负数情况。
  • 非法字符,这里遇到非法字符即停止。
  • 前后空格,首先忽略前导空格,把后面空格当做非法字符。
  • 溢出,分别有正溢出和负溢出,,这里溢出时返回对应的最值。

注意,这里判断溢出时也需要注意表达式的溢出。例如,当前答案为ans,添加新的一位x时,判断溢出时需要考虑正负情况:

  • 正数,当ans * 10 + x > INT_MAX时溢出,但不能这样写,需要写出ans > (INT_MAX – x) / 10
  • 负数,当-ans * 10 – x < INT_MIN时溢出,但不能这样写,需要写出-ans < (INT_MIN + x) / 10

具体代码如下:

class Solution {
public:
    int atoi(const char *str) {
        if (!str || !*str) return 0; //空
        
        while (isspace(*str)) str++; //前导空格
        
        int flag = 1; //正负号
        if (*str == '+') str++;
        else if(*str == '-') flag = -1, str++;
        
        int ans = 0;
        for (; isdigit(*str); str++) //非法字符
        {
            int x = *str - '0';
            if (flag == 1 && ans > (INT_MAX - x) / 10)       //正溢出
                return INT_MAX;
            else if(flag == -1 && -ans < (INT_MIN + x) / 10) //负溢出
                return INT_MIN;
            else
                ans = ans * 10 + x;
        }
        
        return flag * ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论