Monthly Archives: January 2016

LeetCode Longest Common Prefix

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        if (strs.size() == 0)
            return "";
        int max_common = INT_MAX;
        string longest_common = "";
        for (int i = 0; i < strs.size(); i++)
            if (strs[i].size() < max_common)
                max_common = strs[i].size();
        for (int i = 0; i < max_common; i++) {
            for (int j = 1; j < strs.size(); j++) {
                if (strs[j][i] != strs[0][i])
                    return longest_common;
            }
            longest_common += strs[0][i];
        }
        return longest_common;
    }
};

本代码提交AC,用时4MS。

二刷。简洁版代码如下:

class Solution {
public:
	string longestCommonPrefix(vector<string>& strs) {
		int n = strs.size(), i = 0;
		if (n == 0)return "";
		while (true) {
			bool valid = true;
			for (int j = 0; j < n; ++j) {
				if (i >= strs[j].size() || strs[j][i] != strs[0][i]) {
					valid = false;
					break;
				}
			}
			if (!valid)break;
			else ++i;
		}
		return strs[0].substr(0, i);
	}
};

本代码提交AC,用时4MS。

LeetCode Roman to Integer

13. Roman to Integer

Roman numerals are represented by seven different symbols: IVXLCD and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9. 
  • X can be placed before L (50) and C (100) to make 40 and 90. 
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

这一题是LeetCode Integer to Roman的姊妹篇,只需从左往右依次解析字符串即可,优雅版本如下:

class Solution {
public:
    int romanToInt(string s)
    {
        vector<int> nums = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };
        vector<string> symbol = { "I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M" };
        int ans = 0;
        for (int i = nums.size() – 1; i >= 0; i–) {
            int sz = symbol[i].size();
            while (s.size() >= sz && s.substr(0, sz) == symbol[i]) {
                ans += nums[i];
                s = s.substr(sz);
            }
        }
        return ans;
    }
};

本代码提交AC,用时68MS。

LeetCode Integer to Roman

12. Integer to Roman

Roman numerals are represented by seven different symbols: IVXLCD and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9. 
  • X can be placed before L (50) and C (100) to make 40 and 90. 
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: 3
Output: "III"

Example 2:

Input: 4
Output: "IV"

Example 3:

Input: 9
Output: "IX"

Example 4:

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

本题要求把一个阿拉伯数字转换为罗马数字。 首先要了解罗马数字的表示形式,具体看Roman numerals WIKI。 罗马数字由上左图的7个基本字母组成,直接递归很容易求解。但是会有一些特殊情况,比如4,如果递归求解就是IIII,为了简便,采用5-1也就是IV的形式。上面右图就是基本的特殊情况。考虑特殊情况之后的递归代码如下:

class Solution {
public:
    string work(int num, string cur)
    {
        if (num >= 1000)
            return work(num – 1000, cur + "M");
        if (num >= 500) {
            if (num >= 900)
                return work(num – 900, cur + "CM");
            return work(num – 500, cur + "D");
        }
        if (num >= 100) {
            if (num >= 400)
                return work(num – 400, cur + "CD");
            return work(num – 100, cur + "C");
        }
        if (num >= 50) {
            if (num >= 90)
                return work(num – 90, cur + "XC");
            return work(num – 50, cur + "L");
        }
        if (num >= 10) {
            if (num >= 40)
                return work(num – 40, cur + "XL");
            return work(num – 10, cur + "X");
        }
        if (num >= 5) {
            if (num >= 9)
                return work(num – 9, cur + "IX");
            return work(num – 5, cur + "V");
        }
        if (num < 5) {
            if (num >= 4)
                return work(num – 4, cur + "IV");
            while (num > 0) {
                cur += "I";
                num–;
            }
            return cur;
        }
    }
    string intToRoman(int num) { return work(num, ""); }
};

本代码提交AC,用时32MS,这么多if语句,真是不够优雅。后来看到网上一种解法,简洁漂亮许多,贴出来学习一下:

class Solution {
public:
    string intToRoman(int num)
    {
        vector<int> nums = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };
        vector<string> symbol = { "I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M" };
        string ans = "";
        for (int i = nums.size() – 1; i >= 0; i--) {
            while (num >= nums[i]) {
                ans += symbol[i];
                num -= nums[i];
            }
        }
        return ans;
    }
};

本代码提交AC,用时56MS,比上一版稍慢,不够这版更好看。

LeetCode Container With Most Water

11. Container With Most Water

Given n non-negative integers a1a2, …, a, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

题意是x轴上立着一堆线段,从这些线段中找两根和x轴构成一个木桶,问哪个木桶能装最多的水。 暴力枚举的话,是$O(n^2)$的。我们可以用贪心的思路来解决:要使木桶装更多的水,短板越长越好,且两根线之间的距离越长也越好。 设置首尾指针i,j,计算由i,j夹到的木桶的体积(这里简单点,面积即可),如果height[i]<height[j],则i++,因为短板越长越好,所以这相当于抛弃了height[i],保留height[j],底板减1。
完整代码如下:

class Solution {
public:
    int maxArea(vector<int>& height)
    {
        int mA = 0, i = 0, j = height.size() – 1;
        while (i != j) {
            int cur = min(height[i], height[j]) * (j – i);
            if (cur > mA)
                mA = cur;
            if (height[i] < height[j])
                i++;
            else
                j--;
        }
        return mA;
    }
};

本代码提交AC,用时24MS。
二刷。
证明贪心方法的正确性一般用反证法,推出矛盾即可,证明过程见讨论区:https://discuss.leetcode.com/topic/503/anyone-who-has-a-o-n-algorithm

三刷。反证法过程:刚开始的时候l=0,r=n-1,假设此时height[l]<height[r],则此时的组合对l来说是它能形成最大面积的情况。因为x轴长度最大,当r往左边走的时候,x肯定会变小;如果r往左走遇到比l更短的y,则总的y变短,面积变小;如果r往左走遇到比l更长的y,则依然是l作为y,但因为x已经变小了,所以面积依然变小。总之,每一次组合,都是对更短的那个柱子的最大面积,而更长的柱子还有可能和其他柱子组成更大的面积,所以我们每次丢掉短柱子,保留长柱子。

LeetCode Decode Ways

91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

动态规划题。设s为加密字符串,dp[i]表示s[1,…,i]解密的方案数。如果$s[i]\in [1,9]$,则s[i]可以单独解密,有dp[i]+=dp[i-1];如果$s[i-1]s[i]\in [10,26]$,则s[i]可以和s[i-1]拼起来一起解密,有dp[i]+=dp[i-2]。
DP转移公式如下:
$$\begin{cases}dp[i] += dp[i-1] & \text{if $s[i] \in [1,9]$}\\dp[i] += dp[i-2] & \text{if $s[i-1]s[i] \in [10,26]$}\\\end{cases}$$
注意如果0出现在首位则无法解密。
完整代码如下:

class Solution {
public:
    int numDecodings(string s)
    {
        if (s == "" || s[0] == ‘0’)
            return 0;
        s = "^" + s;
        int n = s.size();
        vector<int> dp(n, 0);
        dp[0] = dp[1] = 1;
        for (int i = 2; i < n; i++) {
            if (s[i] >= ‘1’ && s[i] <= ‘9’)
                dp[i] += dp[i – 1];
            if ((s[i – 1] == ‘1’ && s[i] >= ‘0’ && s[i] <= ‘9’) || (s[i – 1] == ‘2’ && s[i] >= ‘0’ && s[i] <= ‘6’))
                dp[i] += dp[i – 2];
        }
        return dp[n – 1];
    }
};

本代码提交AC,用时8MS。

LeetCode Distinct Subsequences

115. Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

It’s guaranteed the answer fits on a 32-bit signed integer.

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

这问题描述不清,题目想问S中有多少个不同的subsequence等于T,这里的不同是指形成subsequence的方法不同,比如样例中,rabbbit可以去掉中间任意一个b都能形成T,所以不同的方法有3种。 这是典型的动态规划问题。假设dp[i][j]表示由S[1,…,i]变到T[1,…,j]有多少种subsequence方法。此时我们有两种选择,如果S[i]!=T[j],则等价于由S[1,…,i-1]变到T[1,…,j],所以dp[i][j]=dp[i-1][j];如果S[i]==T[j],则还可以由S[1,…,i-1]变到T[1,…,j-1],所以dp[i][j]+=dp[i-1][j-1]。
DP转移公式如下:
$$dp[i][j]=\begin{cases}dp[i-1][j] & \text{if $S[i]\neq T[j]$}\\dp[i-1][j]+dp[i-1][j-1] & \text{if $S[i]=T[j]$}\\\end{cases}$$
为了便于理解,我们先在s和t的开头添加一个哨兵字符’^’,初始值dp[i][0]=1,因为由任意字符串转换为空字符串只有一种方法,就是把s中的字符全删了;dp[0][j]=0,因为空字符串的subsequence不可能是是某个非空字符串。
完整代码如下:

class Solution {
public:
    int numDistinct(string s, string t)
    {
        if (s == "")
            return 0;
        if (t == "")
            return 1;
        s = "^" + s;
        t = "^" + t;
        int n = s.size(), m = t.size();
        vector<vector<int> > dp(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++)
            dp[i][0] = 1; // ‘*’ -> ” 1 sub
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = dp[i – 1][j];
                if (s[i] == t[j])
                    dp[i][j] += dp[i – 1][j – 1];
            }
        }
        return dp[n – 1][m – 1];
    }
};

本代码提交AC,用时20MS。

二刷。不添加哨兵,vector增加1也是可以的,代码如下:

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        if(n > m) return 0;
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));
        for(int i = 0; i < m; ++i) dp[i][0] = 1;
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[m][n];
    }
};

本代码提交AC,用时20MS。

LeetCode Palindrome Partitioning II

132. Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

动态规划题目,类似于矩阵链相乘。设dp[i][j]表示s[i,…,j]是否为回文串,cut[j]表示s[1,…,j]需要多少刀才能切成回文串。动态规划运行到最后返回cut[n]。
对于cut[j],切第一刀的时候,我们尝试前面j个切割位点,比如我们尝试切第i点,则s[1,…,j]被分成了s[1,…,i-1]和s[i,…,j],如果s[i,…,j]为回文串,则s[i,…,j]不需要再切了,又因为cut[i-1]我们之前已经算过了,所以在i处切一刀,有cut[j]=cut[i-1]+1。尝试所有的切割位点i,找最小的cut[j]。
如果发现i=1的时候s[i,…,j]为回文串,则s[1,…,j]不需要再切了,所以cut[j]=0。
完整代码如下:

class Solution {
public:
    int minCut(string s)
    {
        int n = s.size();
        vector<vector<bool> > dp(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++)
            dp[i][i] = true;
        vector<int> cut(n, 0); // # of cut for s[0,j]
        for (int j = 0; j < n; j++) {
            cut[j] = j; // set maximum # of cut
            for (int i = 0; i <= j; i++) {
                if (s[i] == s[j] && (j – i <= 1 || dp[i + 1][j – 1])) {
                    dp[i][j] = true;
                    if (i > 0) // if need to cut, add 1 to the previous cut[i-1]
                        cut[j] = min(cut[j], cut[i – 1] + 1);
                    else // if [0…j] is palindrome, no need to cut cut[j] = 0;
                }
            }
        }
        return cut[n – 1];
    }
};

本代码提交AC,用时84MS。

二刷。参考讨论区一个大神的做法:https://discuss.leetcode.com/topic/2840/my-solution-does-not-need-a-table-for-palindrome-is-it-right-it-uses-only-o-n-space。这种方法不需要上面的做法的dp数组,效率也会高很多。

还是需要cuts数组,cuts[i]表示前i个字符切成回文子串,最少的刀数。对于每一个字符,我们枚举以该字符为中心,能够扩展到的最长的回文子串的长度,比如下图,以b为中心扩展,扩展到aba是一个回文子串,那么要把Y切成回文子串,需要的刀数不超过把X切成回文子串需要的刀数加1,也就是cuts[Y]=min(cuts[Y],cuts[X]+1)。
注意,扩展的时候,需要考虑到以b为中心的回文子串的长度是奇数还是偶数。

.......aba...
|<-X->| ^
|<---Y-->|

通过枚举每一个回文中心点,我们可以算到所有的cuts,最后返回cuts[n]。完整代码如下:

class Solution {
public:
    int minCut(string s)
    {
        int n = s.size();
        vector<int> cuts(n + 1, 0); // cuts[i] 表示前i个字符切成回文子串,最少的刀数
        for (int i = 0; i <= n; ++i)
            cuts[i] = i – 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; i – j >= 0 && i + j < n && s[i – j] == s[i + j]; ++j) // 最后一个是奇数长回文子串
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i – j] + 1);
            for (int j = 1; i – j + 1 >= 0 && i + j < n && s[i – j + 1] == s[i + j]; ++j) // 最后一个是偶数长回文子串
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i – j + 1] + 1);
        }
        return cuts[n];
    }
};

本代码提交AC,用时6MS,神速。

三刷。两个DP,第一个DP求解出任意两个位置的子串[i:j]是否为回文。第二个DP2,DP2[j]表示前j长的字符串,需要的最小cut数,对于第j个字符,它可以自己独立成为一个回文,所以DP2[j]=DP2[j-1]+1;还可以遍历j前面的字符i,如果[i:j]能形成回文的话,则DP2[j]=DP2[i-1]+1。完整代码如下:

class Solution {
public:
	void preprocess(const string &s, vector<vector<int>> &dp) {
		int n = s.size();
		for (int i = 0; i < n; ++i)dp[i][i] = 1;
		for (int len = 2; len <= n; ++len) {
			for (int i = 0; i < n; ++i) {
				int j = i + len - 1;
				if (j < n && s[i] == s[j] && (len == 2 || dp[i + 1][j - 1] == 1)) {
					dp[i][j] = 1;
				}
			}
		}
	}
	int minCut(string s) {
		int n = s.size();
		if (n == 0 || n == 1)return 0;
		vector<vector<int>> dp(n, vector<int>(n, 0));
		preprocess(s, dp);
		vector<int> dp2(n, 0);
		for (int j = 1; j < n; ++j) {
			dp2[j] = dp2[j - 1] + 1;
			for (int i = j - 1; i >= 0; --i) {
				if (dp[i][j] == 1) {
					int pre_cut = i > 0 ? dp2[i - 1] + 1 : 0;
					dp2[j] = min(dp2[j], pre_cut);
				}
			}
		}
		return dp2[n - 1];
	}
};

本代码提交AC,用时44MS。

LeetCode Palindrome Number

9. Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?


这一题很有意思,要我们判断一个整数是否是回文数。 首先负数不是回文数,个位数是回文数。但是怎样判断大于9的整数是否是回文数呢? 首先想到的是把int转换为string表示,这样就很方便判断了,但是题目要求不能用额外的存储空间,也就是不能用和x位数线性以上的存储空间,当然几个常数空间是可以的。 后来想依次取出数字的首尾数字,判断是否相等。但是中间有0出现时会有问题,比如1000021,去掉首尾1之后只剩int x=2了,导致判断错误。 还有一个办法是将x转换为x的逆序x’,然后依次判断x和x’的末尾是否相等,但是x’可能超出int表示范围,又作罢。 后来观察发现,回文数字765567在转换为逆序数的过程中,肯定有某个状态,x==x’,比如765=765,而这时x’肯定不会超出int的表示范围。所以我们可以在边逆序的时候边判断。 完整代码如下:

class Solution {
public:
    bool isPalindrome(int x)
    {
        if (x < 10)
            return x >= 0;
        if (x % 10 == 0)
            return false;
        int y = 0;
        while (x > y) {
            y = y * 10 + x % 10;
            if (x == y) //76567
                return true;
            x /= 10;
            if (x == y) //765567
                return true;
        }
        return false;
    }
};

本代码提交AC,用时76MS。

二刷。常规解法,取出每一位数字进行判断:

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        if(x == 0) return true;
        if(x % 10 == 0) return false;
        
        vector<int> digits;
        while(x != 0) {
            digits.push_back(x % 10);
            x /= 10;
        }
        int l = 0, r = digits.size() - 1;
        while(l < r) {
            if(digits[l] != digits[r]) return false;
            ++l;
            --r;
        }
        return true;
    }
};

本代码提交AC,用时52MS。

LeetCode String to Integer (atoi)

8. String to Integer (atoi)

Implement atoi which converts a string to an integer.

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.

Note:

  • Only the space character ' ' is considered as whitespace character.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

Input: "42"
Output: 42

Example 2:

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

这题要求我们手动实现由string转换为int的atoi函数。当然有很多细节需要考虑,不过你可以一步一步来,先实现常见的case,然后看看出错样例,再逐步完善自己的算法。 错了几次之后,我看了atoi函数的介绍,上面并没有说明如果数值超过int的表示范围应该怎么处理:

If the converted value would be out of the range of representable values by an int, it causes undefined behavior. Seestrtol for a more robust cross-platform alternative when this is a possibility.

不过strtol函数提到如果超出long表示范围则返回最大值或最小值,所以在实现atoi时我也是这么做的。 算法过程是:首先去除前导空白字符(如空格),如果剩余字符串长度为0或者1,则特殊处理;判断有无符号位;然后对字符依次处理,直到遇到一个非数字字符,break;最后检查是否超出int范围以及符号位。 完整代码如下:

class Solution {
public:
    int myAtoi(string str)
    {
        int i = 0;
        while (i < str.size() && str[i] == ‘ ‘)
            i++;
        string tmp = str.substr(i);
        if (tmp.size() == 0 || (tmp.size() == 1 && (tmp[0] < ‘0’ || tmp[0] > ‘9’)))
            return 0;
        string digits = (tmp[0] == ‘-‘ || tmp[0] == ‘+’) ? tmp.substr(1) : tmp;
        double ans = 0;
        for (int i = 0; i < digits.size(); i++)
            if (digits[i] < ‘0’ || digits[i] > ‘9’)
                break;
            else
                ans = ans * 10 + (digits[i] – ‘0’);
        ans = (tmp[0] == ‘-‘) ? -ans : ans;
        if (ans > INT_MAX)
            return INT_MAX;
        else if (ans < INT_MIN)
            return INT_MIN;
        else
            return ans;
    }
};

本代码提交AC,用时8MS,居然击败了75%的CPP用户:-)

二刷。如果不用double存储结果的话,可以和LeetCode Reverse Integer类似处理,即在转换的过程中判断是否超过int表示范围。不过有点奇怪的是,如果字符串表示的值就是INT_MAX的话,ans=ans*10+digit会运行时错误,大概意思是说ans是int,无法存储INT_MAX?挺奇怪的,所以把>7改成>=7。

class Solution {
public:
	bool isDigit(char c) {
		return c >= '0'&&c <= '9';
	}
	int myAtoi(string str) {
		int ans = 0;
		bool neg = false;
		int i = 0, n = str.size();
		while (str[i] == ' '&&i < n)++i;
		if (i < n) {
			if (str[i] == '-') {
				neg = true;
				++i;
			} else if (str[i] == '+')++i;
			while (i < n&&isDigit(str[i])) {
				int digit = str[i] - '0';
				if (!neg && (ans > INT_MAX / 10 || (ans == INT_MAX / 10 && digit >= 7)))return INT_MAX;
				if (neg && (-ans < INT_MIN / 10 || (-ans == INT_MIN / 10 && digit >= 8)))return INT_MIN;
				ans = ans * 10 + digit;
				++i;
			}
		}
		if (neg)ans = -ans;
		return ans;
	}
};

本代码提交AC,用时4MS。

LeetCode Reverse Integer

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.


题意就是要我们把整数逆序,需要注意当逆序之后超出int表示范围时,返回0。所以我们用double来保存逆序之后的整数,将其和INT_MAX比较,如果大于INT_MAX,则输出0。 完整代码如下:

class Solution {
public:
    int reverse(int x)
    {
        unsigned int y = (x > 0) ? x : -x;
        double ans = 0;
        while (y) {
            ans = ans * 10 + (y % 10);
            y = y / 10;
        }
        if (ans > INT_MAX)
            return 0;
        return x < 0 ? -ans : ans;
    }
};

本代码提交AC,用时8MS。

二刷。如果不用double存储的话,该怎么办?难就难在如何处理越界的问题。我们可以在计算y的过程中判断y是否越界,代码如下。

如果tmp=y*10+reminder>INT_MAX,有两种情况。一种情况是y*10本身就已经>INT_MAX了,此时即y>INT_MAX/10。另一种情况是y*10没>INT_MAX,是加上reminder之后大于的,由于INT_MAX=2147483647,所以如果reminder>7的话,y*10+reminder就会大于INT_MAX。INT_MIN的情况类似。另外,负数的余数也是负数,所以正负数的情况可以合并考虑。

class Solution {
public:
	int reverse(int x) {

		int y = 0;
		while (x != 0) {
			int reminder = x % 10;
			x /= 10;
			if (y > INT_MAX / 10 || (y == INT_MAX / 10 && reminder > 7))return 0;
			if (y < INT_MIN / 10 || (y == INT_MIN / 10 && reminder < -8))return 0;
			y = y * 10 + reminder;
			
		}
		return y;
	}
};

本代码提交AC,用时4MS。