Straight forward C++ 12ms solution (Updated)


  • 0

    First version

        int myAtoi(string str) {
            if(str.size()==0)
            return 0;
            
            int res=0;
            
            string num="+-0123456789";
             
            //Skip the ' '
            for(int i=0;i<str.size();){
                if(str[i]==' ')
                str.erase(str.begin()+i);
                else break;
            }
            
            //Find valid string.
            //When come across first invalid character, break, discard the tail
            for(int i=0;i<str.size();){
                //'+' or '-' appears in the middle of string is invalid
                if((str[i]=='+'||str[i]=='-')&&i!=0){
                    str=str.assign(str.begin(),str.begin()+i);
                    break;
                }
               //Other invalid characters
                if(num.find(str[i])==-1){
                str=str.assign(str.begin(),str.begin()+i);
                break;
                }
                else
                i++;
            }
          
            //Check whether string is NULL.
            if(str.size()==0) return 0;
            
            int base=1;    //1,10,100,1000...
            int digit=0;   //The length of the number
            
            //The first digit is tricky
            //It could be '+' or '-' or number, so we deal with it later
            //Calculate the res until only the first digit was left
            for(int i=str.size()-1;i>0;){
                res=res+base*(str[i]-'0');
                base=base*10;
                i--;
                digit++;
            }
        
            //digit>10, overflow, set result to INT_MAX or -INT_MAX-1 
            if(digit>10){
                if(str[0]!='-')
                return INT_MAX;
                
                if(str[0]=='-')
                return -INT_MAX-1;
            }
            
            //If the first digit is not a '+' or '-', it overflows for sure
            if(digit==10&&str[0]!='-'&&str[0]!='+')
            return INT_MAX;
            
            //Deal with the first digit
            if(str[0]=='-') 
            res=-res;
            else if(str[0]=='+')
            //Do nothing
            ;
            else res+=base*(str[0]-'0');
            
            //When added the first digits to the result, overflow could happen again
            //if first digit is not '-' and result is negetive, overflows
            if(str[0]!='-'&&res<0)
            res=INT_MAX;
            //if first digit is '-' and result is positive, overflows
            if(str[0]=='-'&&res>0)
            res=-INT_MAX-1;
            
            return res;
            
        }
    

    Update(08/09/2017): Make it clean.
    May not seems clean enough, but considering so many 'strange' TCs like ‘+-2’, we have to exclude these circumstances...
    Any suggestions are welcomed.

        int myAtoi(string str) {
            if(str.size() == 0) return 0;
            int cur = 0;
            while(cur < str.size() && str[cur] == ' ') cur++;
            if(cur == str.size() || (!isdigit(str[cur]) && str[cur] != '+' && str[cur] != '-' )) return 0;
            int end = cur+1;
            while(isdigit(str[end])) end++;
            string s = str.substr(cur, end - cur);
            int num = 0;
            int base = 1;
            for(int i = s.size() - 1; i >= 0; i--){
                if(s[i] == '+' || s[i] == '-') break;
                int add = base * (s[i] - '0');
                if(INT_MAX - num < add || (s.size() - i > 10 && s[i] != '0')) 
                   return s[0] == '-' ? INT_MIN : INT_MAX;
                num += add;
                base *= 10;
            }
            if(s[0] == '-') num = -num;
            return num;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.