LeetCode - 8 String to Integer (atoi)

本篇同步发布於Blog:[解题] LeetCode - 8 String to Integer (atoi)

平台：

LeetCode

题号：

8 - String to Integer (atoi)

题目连结：

https://leetcode.com/problems/valid-palindrome/

题目说明：

给1个字串s，实作atoi函式，将此字串转成整数。字串里可能包含多个非数字字元，像是+号、-号、空白、非数字等。前面遇到空白都略过，直到第一个非空白字元。接着有可选的+号字元或者-号，後面可能接着数字或者其他字元。

在数字之後的其他字元就都排除不理。

如果在空白字元之後的字串，没有合理的数字或者是空字串或者只有空白，则回传0。

解析後的数字如果超出32位元整数的上限/下限，则回传32位元整数的上限/下限。

比如范例输入s = " -42"，回传-42

s = "4193 with words"，4193後出现非数字字元，所以只需解析前面的数字，回传4193

s = "words and 987"，一开始出现非数字字元，属於非合理的数字，回传0

s = "-91283472332"，低於32位元整数的下限，所以回传32位元整数的下限-2147483648

解题方法：

　有2阶段的处理流程，第1阶段是解析该字串前面是否有无效的整数规则，如下图1的解析流程。

图1

第2阶段是前面得知是正数或负数，用64位元变数做进位计算，直到字串读到结尾或者非数字。再判断long变数有无超出32位元整数的上限/下限。最後回传转型32位元整数。

难度为Medium

程序码 (C++ 与 C#)：

#include <iostream>
#include <cstdlib>
using namespace std;

class Solution {
public:
    int myAtoi(string s) {
        int n = s.length();
        bool isPositive = true;
        int i;
        for(i = 0 ; i < n;++i){
            if(s[i] != ' ' && s[i] != '+' && s[i] != '-' && !isdigit(s[i])){
                return 0;
            }
            else if(s[i] == ' '){
                continue;
            }
            else if(s[i] == '+'){
                ++i;
                break;
            }
            else if(s[i] == '-'){
                ++i;
                isPositive = false;
                break;
            }
            else{
                break;
            }
        }

        long long ans = 0;
        for(int j = i; j < n;++j){
            if(!isdigit(s[j])){
                break;
            }

            ans = ans * 10 + (isPositive ? (s[j] - '0') : -(s[j] - '0'));

            if(ans > INT_MAX){
                return INT_MAX;
            }
            else if(ans < INT_MIN){
                return INT_MIN;
            }
        }

        return (int) ans;
    }
};

int main()
{
    Solution sol;
    cout << sol.myAtoi("   -42") << endl;
    cout << sol.myAtoi("4193 with words") << endl;
    cout << sol.myAtoi("words and 987") << endl;
    cout << sol.myAtoi("-91283472332") << endl;
    return 0;
}

using System;

namespace LeetCode8
{
	public class Solution {
	    public int MyAtoi(string s) {
	        int n = s.Length;
	        bool isPositive = true;
	        int i;
	        for(i = 0 ; i < n;++i){
	            if(s[i] != ' ' && s[i] != '+' && s[i] != '-' && !Char.IsDigit(s[i])){
	                return 0;
	            }
	            else if(s[i] == ' '){
	                continue;
	            }
	            else if(s[i] == '+'){
	                ++i;
	                break;
	            }
	            else if(s[i] == '-'){
	                ++i;
	                isPositive = false;
	                break;
	            }
	            else{
	                break;
	            }
	        }
	        
	        long ans = 0;
	        for(int j = i; j < n;++j){
	            if(!Char.IsDigit(s[j])){
	                break;
	            }
	            
	            ans = ans * 10 + (isPositive ? (s[j] - '0') : -(s[j] - '0'));
	            
	            if(ans > Int32.MaxValue){
	                return Int32.MaxValue;
	            }
	            else if(ans < Int32.MinValue){
	                return Int32.MinValue;
	            }
	        }
	        
	        return (int) ans;
	    }
	}
	public class Program
	{
		public static void Main()
		{
			Solution sol = new Solution();
			Console.WriteLine(sol.MyAtoi("   -42"));
		    Console.WriteLine(sol.MyAtoi("4193 with words"));
		    Console.WriteLine(sol.MyAtoi("words and 987"));
		    Console.WriteLine(sol.MyAtoi("-91283472332"));
		}
	}
}