Monthly Archives: August 2016

LeetCode Maximum Subarray

LeetCode Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

click to show more practice.

More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.


求最大连续子数组和,这是一道非常经典的题目,从本科时候就开始做了。有两种解法。
动态规划法
用dp数组存储到当前元素的最大子数组和,如dp[i-1]表示包含第i-1个元素的最大子数组和,则dp[i]表示包含第i个元素的最大子数组和。如果dp[i-1]>0,则dp[i]=dp[i-1]+nums[i];否则dp[i]=nums[i]。完整代码如下:

class Solution {
public:
	int maxSubArray(vector<int>& nums) {
		vector<int> dp(nums.size(), 0);
		dp[0] = nums[0];
		int ans = nums[0];
		for (int i = 1; i < nums.size(); i++) {
			if (dp[i - 1] > 0)dp[i] = dp[i - 1] + nums[i];
			else dp[i] = nums[i];
			if (dp[i] > ans)ans = dp[i];
		}
		return ans;
	}
};

本代码只用扫描一遍数组,所以时间复杂度为O(n)。本代码提交AC,用时12MS。
分治法
将数组一分为二,比如数组[a,b]分为[a,m-1]和[m+1,b],递归求解[a,m-1]和[m+1,b]的最大连续子数组和lmax和rmax,但是[a,b]的最大连续子数组和还可能是跨过中点m的,所以还应该从m往前和往后求一个包含m的最大连续子数组和mmax,然后再求lmax,rmax,mmax的最大值。完整代码如下:

class Solution {
public:
	int divide(vector<int>& nums, int left, int right) {
		if (left == right)return nums[left];
		if (left == right - 1)return max(nums[left] + nums[right], max(nums[left], nums[right]));
		int mid = (left + right) / 2;
		int lmax = divide(nums, left, mid - 1);
		int rmax = divide(nums, mid + 1, right);
		int mmax = nums[mid], tmp = nums[mid];
		for (int i = mid - 1; i >= left; i--) {
			tmp += nums[i];
			if (tmp > mmax)mmax = tmp;
		}
		tmp = mmax;
		for (int i = mid + 1; i <= right; i++) {
			tmp += nums[i];
			if (tmp > mmax)mmax = tmp;
		}
		return max(mmax, max(lmax, rmax));
	}
	int maxSubArray(vector<int>& nums) {
		return divide(nums, 0, nums.size() - 1);
	}
};

本代码可以类比平面上求最近点对的例子,需要考虑跨界的问题,时间复杂度为O(nlgn)。本代码提交AC,用时也是12MS。
综合来看,还是动态规划法更漂亮。

LeetCode Plus One

LeetCode Plus One
Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.


用一个数组表示一个数,然后对这个数加1,输出新的数组。很简单的题,注意一下进位即可。
完整代码如下:

class Solution {
public:
	vector<int> plusOne(vector<int>& digits) {
		vector<int> ans;
		int n = digits.size() - 1;
		digits[n]++;
		while (digits[n] >= 10 && n > 0) {
			digits[n] -= 10;
			digits[n - 1]++;
			n--;
		}
		if (n == 0 && digits[n] >= 10) {
			ans.push_back(1);
			digits[n] -= 10;
		}
		ans.insert(ans.end(), digits.begin(), digits.end());
		return ans;
	}
};

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

LeetCode Combination Sum II

LeetCode Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

这题和之前的LeetCode Combination Sum很类似,但是要求同一个数字不能重复选,不过candidates里面可能会有重复的数字。所以策略就是在一个for循环里面判断数字是否重复,注意不能在递归里面判断所选数字是否重复,因为递归的时候是可以选相同数字的,比如样例的[1,1,6]。同时递归的时候传入当前下标的下一个下标。
完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& candidates, int idx, vector<int>& sol, int target) {
		if (target == 0) {
			ans.push_back(sol);
		}
		else {
			for (int i = idx; i < candidates.size(); i++) {
				if (candidates[i] > target)break;
				if (i != idx && candidates[i] == candidates[i - 1])continue; // i != idx
				sol.push_back(candidates[i]);
				work(ans, candidates, i + 1, sol, target - candidates[i]); // i + 1
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, 0, sol, target);
		return ans;
	}
};

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

LeetCode Combination Sum

LeetCode Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

本题要从一个集合中取出一些数,使得和为某个特定的数target,输出所有的这种组合。注意不能有重复的组合,比如[2,2,3]和[3,2,2]算是重复的。
这是很常见的组合问题,使用递归的思路求解。比如样例,要求和为7,则每个加数必须小于等于7,所以依次尝试2,3,6,7,如果是2,则还差7-2=5,所以递归的在[2,3,6,7]里面找和为5的组合。如此递归,直到差为0。但是这样有一个问题,比如你这一次尝试的是2,则可能得到[2,2,3]的组合,下一次尝试3,则可能得到[3,2,2]的组合,但是这两个组合是相同的。我一开始的想法是对组合排序,然后用set去重。代码如下:

class Solution {
public:
	void work(set<vector<int>>& ans, vector<int>& candidates, vector<int>& sol, int target) {
		if (target == 0) {
			vector<int> tmp = sol;
			sort(tmp.begin(), tmp.end());
			ans.insert(tmp);
		}
		else {
			for (int i = 0; i < candidates.size(); i++) {
				if (candidates[i] > target)break;
				sol.push_back(candidates[i]);
				work(ans, candidates, sol, target - candidates[i]);
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		set<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, sol, target);
		return vector<vector<int>>(ans.begin(), ans.end());
	}
};

本代码提交AC,但是用时145MS,只击败了4.5%的人,所以肯定还有更优的方案。
上述方案的一个费时的地方就是要对每个组合排序,然后用set去重,如果能省掉这个环节,速度会快很多。
网上查看题解之后,恍然大悟,每次只选不小于上一次选过的数,这样得到的组合就不会有重复,不需要排序,也不需要set去重。比如上面的例子,在选到3时,差7-3=4,此时再从[2,3,6,7]里面选时,只选大于等于3的数,也就是3,6,7,不再考虑2了。但是6,7都大于4,不行;3的话,剩余4-3=1也无解。所以搜3的时候,就不会得到[3,2,2]的结果,也就无需去重。
完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& candidates, vector<int>& sol, int target) {
		if (target == 0) {
			ans.push_back(sol);
		}
		else {
			for (int i = 0; i < candidates.size(); i++) {
				if (candidates[i] > target || (sol.size() > 0 && candidates[i] < sol[sol.size() - 1]))continue;
				sol.push_back(candidates[i]);
				work(ans, candidates, sol, target - candidates[i]);
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, sol, target);
		return ans;
	}
};

本代码提交AC,用时20MS,速度快了好多。
后来我发现这个版本的代码还可以优化,因为candidates已经排好序了,如果这次取了i号元素,下一次只要取i及以后的元素即可,所以在递归的时候多传入一个下标值,也能提速。完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& candidates, int idx, vector<int>& sol, int target) {
		if (target == 0) {
			ans.push_back(sol);
		}
		else {
			for (int i = idx; i < candidates.size(); i++) {
				if (candidates[i] > target)break;
				sol.push_back(candidates[i]);
				work(ans, candidates, i, sol, target - candidates[i]);
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, 0, sol, target);
		return ans;
	}
};

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

LeetCode Happy Number

LeetCode Happy Number
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number

  • 12 + 92 = 82
  • 82 + 22 = 68
  • 62 + 82 = 100
  • 12 + 02 + 02 = 1

本题要判断一个数是否是Happy Number,过程是:不断对数的每个digit求平方和,如果平方和等于1,则是Happy Number;如果造成无限循环了,则不是Happy Number。
代码很简单,直接按题意做就是,使用set判断是否出现重复循环了。完整代码如下:

class Solution {
public:
	bool isHappy(int n) {
		set<int> nums;
		while (true) {
			if (nums.find(n) != nums.end())return false;
			nums.insert(n);
			int sum = 0;
			while (n != 0) {
				int q = n % 10;
				sum += q*q;
				n = n / 10;
			}
			if (sum == 1)return true;
			else n = sum;
		}
	}
};

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

LeetCode Next Permutation

LeetCode Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1


本题要求一个序列的下一个更大的序列,比如1,2,3 → 1,3,2,如果一个序列是最大的序列,如3,2,1,则返回其最小序列1,2,3。
算法从后往前扫描序列,如果从后往前看一直是上升的,如3,2,1,则说明这是最大的序列,直接将其逆序即可。
否则直到找到一个下降的转折点,比如4876543,找到48是下降的,这样我们就可以把4换成更大的数,但又不能太大,Next Permutation必须是紧跟在原序列后面的一个序列,所以我们从4的后面找比4大的最小的数,这里就是5。然后交换4和5,得到5876443,此时5后面仍然是有序的,而且是最大的,所以还要把5后面的序列逆序一下,得到5344678。
完整代码如下:

class Solution {
public:
	void nextPermutation(vector<int>& nums) { // 4876543
		for (int i = nums.size() - 1; i > 0; i--) {
			if (nums[i] > nums[i - 1]) { // 8 > 4
				int min_idx = i, min_val = INT_MAX;
				for (int j = nums.size() - 1; j > i; j--) {
					if (nums[j] > nums[i - 1] && nums[j] < min_val) { // 5 > 4
						min_idx = j;
						min_val = nums[j];
					}
				}
				swap(nums[i - 1], nums[min_idx]); // 5876443
				reverse(nums.begin() + i, nums.end()); // 5344678
				return;
			}
		}
		reverse(nums.begin(), nums.end());
	}
};

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

LeetCode Rotate Image

LeetCode Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?


本题要求将一个矩阵顺时针旋转90度,且不使用多余的数组保存中间结果。看似很简单,其实有很多点需要注意。

如上图所示,旋转的时候,其实每次都只有四个元素互相交换,如上图的黑色方框和红色方框。每次旋转时,先保存最上面那个元素,比如黑框,先把2保存下来,然后把9填到2的位置,把15填到9的位置...最后把2填到8的位置,这样整个旋转过程只使用了1个临时变量,达到了in-place的目的。
每次换框的时候,比如由黑框换到红框,x--,y++。在旋转的时候,需要充分利用方框四周的4个三角形是全等三角形,求出4个顶点的坐标。自己摸索一下就能找到里面的关系。
完整代码如下:

class Solution {
public:
	void rotate(vector<vector<int>>& matrix) {
		int offset = matrix.size() - 1, max_y = matrix.size() - 1;
		for (int i = 0; i < matrix.size() / 2; i++) {
			int x = offset, y = 0;
			for (int j = i; j < max_y; j++) {
				int tmp = matrix[i][j];
				matrix[i][j] = matrix[i + x][j - y];
				matrix[i + x][j - y] = matrix[i + x + y][j - y + x];
				matrix[i + x + y][j - y + x] = matrix[i + y][j + x];
				matrix[i + y][j + x] = tmp;
				x--;
				y++;
			}
			offset -= 2;
			max_y--;
		}
	}
};

本代码提交AC,用时4MS。
二刷。更简单,更安全的做法是先对行逆序,就是第一行和最后一行互换,第二行和倒数第二行互换...然后对对称元素互换。详细过程参考讨论区:https://discuss.leetcode.com/topic/6796/a-common-method-to-rotate-the-image。完整代码如下:

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        reverse(matrix.begin(), matrix.end());
        for(int i = 0; i < matrix.size(); ++i) {
            for(int j = i + 1; j < matrix[0].size(); ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

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

LeetCode Permutations II

LeetCode Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

这道题和之前的Permutations很像,只不过此时包含有重复元素。 在Permutations里,我使用了一个一个往里加的思路,今天我使用另一个思路。
为了得到一个序列的所有排列,可以采用每个元素和当前第一个元素交换的思路。比如要得到1,2,3的所有排列,第一轮每个元素和第一个元素交换得到

  • 1,2,3
  • 2,1,3
  • 3,2,1

此时每个元素都有打头的序列出现,再对每一个序列,除掉第一个元素,循环交换。比如对于1,2,3,此时把2,3作为一个新的序列,和此时的第一个元素2交换,得到序列:

  • 2,3
  • 3,2

然后再和之前的元素1拼接起来,得到以1开头的所有排列:

  • 1,2,3
  • 1,3,2

同理能得到以2,3打头的所有排列。用这种思路也可以求解Permutations这个题。当遇到有重复元素时,可以先对数组排序,在交换的时候,如果当前元素和前一个元素相同,则不再交换。最后再用set去重,完整代码如下:

class Solution {
public:
	void work(set<vector<int>>& ans, vector<int>& nums, int start) {
		if (start == nums.size()) {
			ans.insert(nums);
		}
		else {
			for (int i = start; i < nums.size(); i++) {
				if (i != start&&nums[i] == nums[i - 1])continue;
				swap(nums[i], nums[start]);
				work(ans, nums, start + 1);
				swap(nums[i], nums[start]);
			}
		}
	}
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		set<vector<int>> ans;
		work(ans, nums, 0);
		return vector<vector<int>>(ans.begin(),ans.end());
	}
};

本代码提交AC,用时48ms。速度比较慢,应该还有其他更优的算法。


新方法,使用和Permutations类似的dfs递归方法,只不过在递归的时候,判断一下,保证这次递归的元素不能和上一次相同。比如数组是[1,1,2],第一次从第一个1开始递归,那么在这层循环中,下一次递归就不能从第二个1开始了,但是下一层循环中还是应该可以选第二个1的。理解起来有点绕,假设我们把求[1,1,2]的全排列想象成从[1,1,2]中无放回的取数字,依先后顺序扔到3个格子中,每个格子只能放一个数字。那么第一次拿的数可能是1,1,2,则第一次拿第一个1和第二个1产生的全排列应该是完全一样的。
代码如下。第11行:用last记录本次循环中上一个递归的数,那么本次循环不再对同一个数递归了。因为先对数组排序了,所以所有相同的数字都会聚到一起,而且这样产生的全排列是按大小顺序排列的。

class Solution {
private:
	void dfs(const vector<int>& nums, vector<vector<int>>& ans, vector<int>& cand, vector<int> &visited) {
		if (cand.size() == nums.size()) {
			ans.push_back(cand);
			return;
		}
		int last = INT_MAX;
		for (int i = 0; i < nums.size(); ++i) {
			if (visited[i] == 0) {
				if (i != 0 && nums[i] == last)continue; // 不能和上一次递归的元素相同,否则产生冗余排列
				cand.push_back(nums[i]);
				last = nums[i];
				visited[i] = 1;
				dfs(nums, ans, cand, visited);
				visited[i] = 0;
				cand.pop_back();
			}
		}
	}
public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		vector<vector<int>> ans;
		vector<int> cand, visited(nums.size(), 0);
		dfs(nums, ans, cand, visited);
		return ans;
	}
};

本代码提交AC,用时23MS,比前一种方法快,省掉了set去重。
二刷。上述解法固然正确,但是用INT_MAX来初始化last还是有风险的,万一数组中有INT_MAX呢。
更好的方法其实是,不用last记录上一次递归的值,二刷直接在内层if判断,如果i!=0且nums[i]==nums[i-1],说明这个数和上一个数相同,但是此时还不能continue,万一有[1,1,2]这种情况,在外层递归第二个1时,第一个1在上一轮是已经恢复了visited[0]=0的,所以这里可以加上一个visited[i-1]==0。完整代码如下:

class Solution {
private:
	void dfs(const vector<int>& nums, vector<vector<int>>& ans, vector<int>& cand, vector<int> &visited) {
		if (cand.size() == nums.size()) {
			ans.push_back(cand);
			return;
		}
		for (int i = 0; i < nums.size(); ++i) {
			if (visited[i] == 0) {
                if(i != 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) continue;
				cand.push_back(nums[i]);
				visited[i] = 1;
				dfs(nums, ans, cand, visited);
				visited[i] = 0;
				cand.pop_back();
			}
		}
	}
public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		vector<vector<int>> ans;
		vector<int> cand, visited(nums.size(), 0);
		dfs(nums, ans, cand, visited);
		return ans;
	}
};

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

LeetCode Length of Last Word

LeetCode Length of Last Word
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World",
return 5.


本题要求一个字符串中最后一个单词的长度,比如"Hello World",则返回5。需要注意结尾包含空格的情况,比如"Hello World ",还是要返回5。所以需要先删除尾部空格,然后再从后往前查找第一个空格,返回空格到结尾的长度。
完整代码如下:

class Solution {
public:
	int lengthOfLastWord(string s) {
		int e = s.size() - 1;
		while (e >= 0 && s[e] == ' ') {
			e--;
		}
		if (e < s.size() - 1) {
			s = s.substr(0, e + 1);
		}
		size_t tPos = s.find_last_of(' ');
		if (tPos == string::npos)return s.size();
		return s.size() - tPos - 1;
	}
};

本代码提交AC,用时4MS。
二刷。上述代码也过于复杂,还有字符串的substr,下面是更简洁的版本:

class Solution {
public:
    int lengthOfLastWord(string s) {
        int i = s.size() - 1;
        while(i >= 0 && s[i] == ' ') --i;
        if(i < 0) return 0;
        int j = i - 1;
        while(j >= 0 && s[j] != ' ') --j;
        return i - j;
    }
};

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

LeetCode Permutations

LeetCode Permutations
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

这道题要产生一个数组的所有排列情况,可以使用递归的思想,一个一个元素往里加,直到达到个数要求。使用flag来标记是否添加过。和我最近在做的蛋白质搜索引擎中加修饰的情况很类似,实现如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& tmp, vector<int>& nums, vector<int>& flag) {
		if (tmp.size() == nums.size()) {
			ans.push_back(tmp);
		}
		else {
			for (int i = 0; i < flag.size(); i++) {
				if (flag[i] == 1) {
					vector<int> next = tmp;
					next.push_back(nums[i]);
					flag[i] = 0;
					work(ans, next, nums, flag);
					flag[i] = 1;
				}
			}
		}
	}
	vector<vector<int>> permute(vector<int>& nums) {
		vector<int> flag(nums.size(), 1);
		vector<vector<int>> ans;
		vector<int> tmp;
		work(ans, tmp, nums, flag);
		return ans;
	}
};

本代码提交AC,用时21MS。
二刷。其实上述代码中不需要复制一个next数组的,代码如下:

class Solution {
private:
    void DFS(const vector<int>& nums, vector<int>& visited, vector<int>& candidate, vector<vector<int>>& ans) {
        if(candidate.size() == nums.size()) {
            ans.push_back(candidate);
            return;
        }
        for(int i = 0; i < nums.size(); ++i) {
            if(visited[i] == 0) {
                visited[i] = 1;
                candidate.push_back(nums[i]);
                DFS(nums, visited, candidate, ans);
                visited[i] = 0;
                candidate.pop_back();
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> visited(nums.size(), 0), candidate;
        vector<vector<int>> ans;
        DFS(nums, visited, candidate, ans);
        return ans;
    }
};

本代码提交AC,用时9MS,击败79%。
还可以不需要visited和candidate数组,用交换的思路,代码如下:

class Solution {
private:
    void DFS(vector<int>& nums, vector<vector<int>>& ans, int start) {
        if(start == nums.size()) {
            ans.push_back(nums);
            return;
        }
        for(int i = start; i < nums.size(); ++i) {
            swap(nums[i], nums[start]);
            DFS(nums, ans, start + 1);
            swap(nums[i], nums[start]);
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        DFS(nums, ans, 0);
        return ans;
    }
};

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