本篇同步發布於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"));
		}
	}
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/1-99/8.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/1-99/8.cs

Reactions