Monthly Archives: January 2016

LeetCode Longest Common Prefix

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


这题简单,找一系列字符串的最长公共前缀。先找出最短的字符串s,长度为sz,然后依次检查每个字符串的前sz个字符是否相同,只要有一个不相同就返回。
完整代码如下:

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。

LeetCode Roman to Integer

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


这一题是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

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


本题要求把一个阿拉伯数字转换为罗马数字。
首先要了解罗马数字的表示形式,具体看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

LeetCode Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) 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.


题意是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

LeetCode Decode Ways

LeetCode 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 an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.


动态规划题。设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

LeetCode Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S.
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).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.


这问题描述不清,题目想问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。

LeetCode Palindrome Partitioning II

LeetCode 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.
For example, given s = "aab",
Return 1 since 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,神速。

LeetCode Palindrome Number

LeetCode Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.

Some hints:Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.

这一题很有意思,要我们判断一个整数是否是回文数。
首先负数不是回文数,个位数是回文数。但是怎样判断大于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。

LeetCode String to Integer (atoi)

LeetCode String to Integer (atoi)
Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

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.

这题要求我们手动实现由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用户:-)

LeetCode Reverse Integer

LeetCode Reverse Integer
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321

Have you thought about this?Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
Update (2014-11-10):
Test cases had been added to test the overflow behavior.

题意就是要我们把整数逆序,需要注意当逆序之后超出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。