[LeetCode] 8. String to Integer (atoi)

轉自LeetCode

Implement atoi to convert a string to an integer.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

<Solution>

這題要注意幾點 (參考資料)

• int overflow 的問題

• 前綴空白

• sign符號的處理。這邊要特別注意幾種情況，"+-123"、"-+123、"++122、"--111"，都是回傳0

注意到上面幾點後，剩下就是把數字字元轉成數字相加

code 如下

C++

	class Solution {
	public:
	int myAtoi(string str) {
	if (str.length() == 0) {
	return 0;
	}
	int sign = 1, sum = 0, index = 0, len = str.length();
	const int INT_MAX_DEVIDE_10 = INT_MAX / 10;
	//> reach first non-whitespace char
	while(index < len && str[index] == ' ') {
	++index;
	}
	//> check positive or negative
	if (str[index] == '+' || str[index] == '-') {
	sign = (str[index++] == '+') ? 1 : -1;
	}
	//> 1. if there is one more '+' or '-', just return
	//> 2. only deal with digit chars
	while (index < len && str[index] >= '0' && str[index] <= '9') {
	//> overflow checking
	if (sum > INT_MAX_DEVIDE_10 || (sum == INT_MAX_DEVIDE_10 && str[index] - '0' > 7)) {
	return (sign == 1) ? INT_MAX : INT_MIN;
	}
	sum = 10 * sum + (str[index++] - '0');
	}
	return sum * sign;
	}
	};

view raw stringToInt.cpp hosted with ❤ by GitHub

Java

	public class Solution {
	public int myAtoi(String str) {
	long ans = 0;
	int sign = 1, index = 0;
	final int len = str.length();
	final long INT_MIN_ABS = Math.abs((long)Integer.MIN_VALUE);
	//>> ignore white spaces
	while(index < len && str.charAt(index) == ' ') {
	++index;
	}
	//>> check sign simbol
	if(index < len && (str.charAt(index) == '+' || str.charAt(index) == '-')) {
	sign = (str.charAt(index++) == '+') ? 1 : -1;
	}
	//>> covert string into int
	while(index < len && str.charAt(index) >= '0' && str.charAt(index) <= '9') {
	ans = ans * 10 + (long)(str.charAt(index++) - '0');
	if(sign == 1 && ans > Integer.MAX_VALUE) {
	return Integer.MAX_VALUE;
	}
	else if(sign == -1 && ans > INT_MIN_ABS) {
	return Integer.MIN_VALUE;
	}
	}
	return (int)(sign * ans);
	}
	}

view raw stringToInt.java hosted with ❤ by GitHub