Monthly Archives: September 2016

LeetCode Merge Sorted Array

LeetCode Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.


把两个已排序数组合并成一个有序数组。注意是保存到nums1中。我一开始理解的是在合并过程中不能借助额外空间,所以用两个指针i,j指向两个数组,然后每次从nums2中找第一个小于nums1[i]的数,然后交换nums1[i]和nums2[j],再调整nums2使有序。如此下去,nums1就是合并有序数组中的较小数组部分。
这个版本的完整代码如下:

class Solution {
public:
	void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		if (n == 0)return;
		int i = 0;
		while (i < m) {
			int j = 0;
			while (nums1[i] <= nums2[j] && i < m)i++;
			if (i >= m)break;
			swap(nums1[i], nums2[j]);
			while (j<n - 1 && nums2[j]>nums2[j + 1]) {
				swap(nums2[j], nums2[j + 1]);
				j++;
			}
			i++;
		}
		for (int j = 0; j < n; j++) {
			nums1[i++] = nums2[j];
		}
	}
};

本代码提交AC,用时6MS。
但是只击败了15%的人,仔细看看算法实现,最坏复杂度是O(n*m),因为如果nums1={6,7,8,9,10},nums2={1,2,3,4,5},则nums1[i]每和nums2[0]交换一次,nums2调整时都要交换n-1次,所以最坏复杂度是O(n*m)。所以应该还有更好的算法。
看题解,发现我没有很好利用nums1的数组大小至少是n+m这个信息,这说明合并之后的整个数组,最大下标只能是n+m-1,所以我们可以对nums1和nums2从后往前比较,把更大的元素依次在nums1[n+m-1]往前放,这样共3个指针,他们之间不会有overlap。此算法的复杂度只有O(max(n,m))
完整代码如下:

class Solution {
public:
	void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		if (n == 0)return;
		int i = m - 1, j = n - 1, k = m + n - 1;
		while (i >= 0 || j >= 0) {
			int a = i >= 0 ? nums1[i] : INT_MIN;
			int b = j >= 0 ? nums2[j] : INT_MIN;
			if (a > b) {
				nums1[k--] = a;
				i--;
			}
			else {
				nums1[k--] = b;
				j--;
			}
		}
	}
};

本代码提交AC,用时3MS,果然快多了。

LeetCode Subsets

LeetCode Subsets
Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:

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

求一个集合的所有子集,高中就知道所有子集个数为2^n个,包括空集和它本身。
算法思路和LeetCode Combinations几乎一样,只不过成功条件不再是candidate中有k个数了,而是每添加一个元素都算成功一个。
完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& cand, vector<int>& nums, int step) {
		ans.push_back(cand);
		for (int i = step; i < nums.size(); i++) {
			cand.push_back(nums[i]);
			work(ans, cand, nums, i + 1);
			cand.pop_back();
		}
	}
	vector<vector<int>> subsets(vector<int>& nums) {
		vector<vector<int>> ans;
		vector<int> cand;
		work(ans, cand, nums, 0);
		return ans;
	}
};

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

LeetCode Combinations

LeetCode Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:

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

求1~n的所有k组合数,和求排列数有点类似。当然也是递归的思路,每个数都有取和不取两种情况,分别递归。唯一需要注意的是递归遍历的时候不走回头路,这样才不会重复。比如求1,2,3,4的两数组合,第一个取1,第二个可以取2,3,4;当第一个取2时,就不再回过头来测试1了,因为之前测试1时,已经产生了{1,2}这个组合,现在测试2时,只需要往前测试3,4了。
完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& candidate, int step, int& n, int& k) {
		if (candidate.size() == k) {
			ans.push_back(candidate);
		}
		else {
			for (int i = step; i <= n; i++) { // 从第step步开始
				candidate.push_back(i);
				work(ans, candidate, i + 1, n, k); // 下一步从i+1步开始
				candidate.pop_back();
			}
		}
	}
	vector<vector<int>> combine(int n, int k) {
		vector<vector<int>> ans;
		vector<int> cand;
		work(ans, cand, 1, n, k);
		return ans;
	}
};

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

LeetCode Simplify Path

LeetCode Simplify Path
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

  • Did you consider the case where path = "/../"?
    In this case, you should return "/".
  • Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
    In this case, you should ignore redundant slashes and return "/home/foo".

简化Unix路径字符串。使用栈数据结构,扫描字符串,获取/之前的字符串,如果是一点.则保持当前路径,什么也不做;如果是两点..则弹栈,否则把字符串压栈。
需要注意的是/../,/.,/...等情况,三个点应该认为一个合法的路径字符串,虽然在Windows上并不合法。所以我们在进行算法之前,不管原始字符串末尾是否包含/,我们都在末尾添加上斜杠/,以便后续统一处理。
扫描完一次字符串之后,把栈内字符串依次弹出并组合成一个简化的路径。
完整代码如下:

class Solution {
public:
	string simplifyPath(string path) {
		path += "/";
		stack<string> sPath;
		string p1 = "";
		for (int i = 0; i < path.size(); i++) {
			if (path[i] == '/') {
				if (p1 == "" || p1 == ".") {
				}
				else if (p1 == "..") {
					if (!sPath.empty())
						sPath.pop();
				}
				else {
					sPath.push(p1);
				}
				p1 = "";
			}
			else p1 += path[i];
		}
		if (sPath.empty())return "/";
		string ans = "";
		while (!sPath.empty()) {
			ans = "/" + sPath.top() + ans;
			sPath.pop();
		}
		return ans;
	}
};

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

LeetCode Climbing Stairs

LeetCode Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?


虽然是easy模式,但是是很好的一道题。问爬一个有n个台阶的楼梯,每次只能跨1步或者2步,共有多少种方案。
使用DP解决,假设前n个台阶共有dp[n]种方案,来了一个新台阶第n+1个台阶,那么这个台阶可以单独1步跨,则方案数为dp[n];也可以和第n个台阶合在一起一次性跨2步,则还剩n-1个台阶,所以方案数为dp[n-1]。综合起来就是dp[n+1]=dp[n]+dp[n-1],这其实就是斐波那契数列。
求斐波那契数列的第n项是一个经典问题,如果使用原始的递归求解,则会有很多重复计算,导致超时:

class Solution {
public:
	int climbStairs(int n) {
		if (n == 1)return 1;
		if (n == 2)return 2;
		return climbStairs(n - 1) + climbStairs(n - 2);
	}
};

但是每次我们只需要前两项的数值,所以可以优化为:

class Solution {
public:
	int climbStairs(int n) {
		if (n == 1)return 1;
		if (n == 2)return 2;
		int a1 = 1, a2 = 2, tmp;
		for (int i = 3; i <= n; i++) {
			tmp = a1 + a2;
			swap(a1, a2);
			swap(a2, tmp);
		}
		return a2;
	}
};

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

LeetCode Sort Colors

LeetCode Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?


这道题有意思。实质是要把由0,1,2组成的数组从小到大排序,本来用计数排序,分别统计一下0,1,2这3个数字各有多少个,然后重新构造一个排好序的数组即可,但是Follow up里提到不能使用two-pass算法,并且只能使用常数空间复杂度。
我稍加思考,想到一个可行的算法。因为数组中只有3个数字,那么排好序的数组开头肯定是0(如果有0的话),结尾肯定是2(如果有2的话)。所以我们只需一遍遍历,遇到0则放到开头,遇到2则放到结尾,遇到1的话,就先统计一下1的数目。最后把1重新赋值到所有0的后面,1的个数在前面已经统计过了,所以正好。
完整代码如下:

class Solution {
public:
	void sortColors(vector<int>& nums) {
		int p0 = 0, p2 = nums.size() - 1; // p0和p2分别代表下一个0和2应该填入的位置
		int n1 = 0; // 1的数量
		for (int i = 0; i <= p2; i++) {
			if (nums[i] == 0)nums[p0++] = nums[i];
			else if (nums[i] == 1)n1++;
			else {
				swap(nums[i], nums[p2]);
				p2--;
				i--;
			}
		}
		for (int i = 0; i < n1; i++)
			nums[p0++] = 1;
	}
};

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

LeetCode Same Tree

LeetCode Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.


判断两棵二叉树是否相同。我第一想到的是对两棵树都先序遍历一下,然后看看遍历出来的序列是否一致,如果一致则树是一样的。

class Solution {
public:
	void preOrderTraverse(TreeNode *t, vector<int>& res) {
		if (t != NULL) {
			res.push_back(t->val);
			preOrderTraverse(t->left, res);
			preOrderTraverse(t->right, res);
		}
	}
	bool isSameTree(TreeNode* p, TreeNode* q) {
		vector<int> pRes, qRes;
		preOrderTraverse(p, pRes);
		preOrderTraverse(q, qRes);
		if (pRes.size() != qRes.size())return false;
		for (int i = 0; i < pRes.size(); i++) {
			if (pRes[i] != qRes[i])return false;
		}
		return true;
	}
};

但是这样做居然是错的!请注意,虽然两棵树的遍历结果是一样的,并不代表这两棵树的结构是一样的。比如[10,5,15]和[10,5,null,null,15],虽然先序遍历的结果都是10,5,15,但是这两棵树的结构是不一样的。所以不能只看遍历的结果,在遍历的时候就要判断是否相同。如果在同一个位置上,一颗节点为空,另一棵上有值,结构就不一样了。要么两个节点都为空或者有值且相等。
完整代码如下:

class Solution {
public:
	bool isSameTree(TreeNode* p, TreeNode* q) {
		if (p == NULL&&q == NULL)return true;
		if (p == NULL || q == NULL)return false;
		if (p->val != q->val)return false;
		return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
	}
};

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

LeetCode Minimum Depth of Binary Tree

LeetCode Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.


求一棵二叉树的最小深度,类似于LeetCode Maximum Depth of Binary Tree求最大深度,但是稍微难一点。
请注意,不能直接把求最大深度的大于号改为小于号:

class Solution {
public:
	int dfs(TreeNode* root, int nDepth) {
		if (root == NULL)return nDepth;
		int left = dfs(root->left, nDepth + 1);
		int right = dfs(root->right, nDepth + 1);
		return left < right ? left : right;
	}
	int minDepth(TreeNode* root) {
		return dfs(root, 0);
	}
};

因为如下图所示,当走到A点时,没有右孩子,导致int right = dfs(root->right, nDepth + 1);会得到A点的高度2,比左孩子的高度低,即最小高度为2了。但是最小高度显然是4。所以需要稍加修改,使得如果某个孩子为空时,不在该孩子深搜了,只有当两个孩子都为空时(即是叶子节点时),才得到一个合法的深度,去和其他深度做比较。

深度搜索的完整代码如下:

class Solution {
public:
	int dfs(TreeNode* root, int nDepth) {
		if (root == NULL)return nDepth;
		if (root->left == NULL&&root->right == NULL)return nDepth + 1;
		int left = root->left == NULL ? INT_MAX : dfs(root->left, nDepth + 1);
		int right = root->right == NULL ? INT_MAX : dfs(root->right, nDepth + 1);
		return left < right ? left : right;
	}
	int minDepth(TreeNode* root) {
		return dfs(root, 0);
	}
};

本代码提交AC,用时9MS。
但是DFS必须走到所有叶子节点才能得到最小深度,而如果采用广度优先搜索BFS时,遇到的第一个叶子节点的深度就是最小深度了,就可以返回了。所以理论上,BFS的性能会更优。
BFS的完整代码如下:

struct NewTreeNode {
	TreeNode* tn;
	int depth;
};
class Solution {
public:
	int bfs(TreeNode* root) {
		queue<NewTreeNode*> qTree;
		NewTreeNode* ntn = new NewTreeNode;
		ntn->tn = root;
		ntn->depth = 0;
		qTree.push(ntn);
		NewTreeNode* top = new NewTreeNode;
		while (!qTree.empty()) {
			top = qTree.front();
			qTree.pop();
			if (top->tn == NULL)return top->depth;
			if (top->tn->left == NULL&&top->tn->right == NULL)return top->depth + 1;
			if (top->tn->left != NULL) {
				NewTreeNode* tmp = new NewTreeNode;
				tmp->tn = top->tn->left;
				tmp->depth = top->depth + 1;
				qTree.push(tmp);
			}
			if (top->tn->right != NULL) {
				NewTreeNode* tmp = new NewTreeNode;
				tmp->tn = top->tn->right;
				tmp->depth = top->depth + 1;
				qTree.push(tmp);
			}
		}
		return -1;
	}
	int minDepth(TreeNode* root) {
		return bfs(root);
	}
};

本代码提交AC,用时也是9MS。
我看Leetcode上有很多关于树的题,为了方便测试,自己写了一个由数组构造树结构的函数,如下:

#include<vector>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* genTree(vector<int>& vi, int id) {
	if (vi.size() == 0)return NULL;
	TreeNode* root = new TreeNode(vi[id]);
	if (2 * id + 1 < vi.size() && vi[2 * id + 1] != -1) { root->left = genTree(vi, 2 * id + 1);
	}
	if (2 * id + 2 < vi.size() && vi[2 * id + 2] != -1) { root->right = genTree(vi, 2 * id + 2);
	}
	return root;
}
int main() {
	vector<int> vTree = { 1,2,3,4,5 };
	TreeNode* root = genTree(vTree, 0);
	return 0;
}

使用时只要传入数组和0,返回的就是一个建好的树。用数组存树,一般第i号节点的左右孩子下标分别为2i+1和2i+2。存好之后恰好是一棵树的层次遍历结果。
如果要构建的不是一棵完全树,比如下面的左图,则先需要转换为完全图,也就是用-1代替一个不存在的节点,此时传入的数组应该是[1,-1,2,-1,-1,3,-1],genTree函数遇到-1会自动跳过不创建节点。当然如果你的树中本来就有-1这个值,也可以把-1换成其他数。

二刷。BFS的代码还可以写得更简洁漂亮一些,类似于层次遍历,遍历到某一层有叶子节点时,层数就是最小深度,代码如下:

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            ++depth;
            int n = q.size();
            while(n--) {
                TreeNode *cur = q.front();
                q.pop();
                if(cur->left == NULL && cur->right == NULL) return depth;
                if(cur->left != NULL) q.push(cur->left);
                if(cur->right != NULL) q.push(cur->right);
            }
        }
        return depth;
    }
};

本代码提交AC,用时9MS。
DFS的代码也可以写得更漂亮一些:

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL) return 0;
        if(root->left == NULL) return minDepth(root->right) + 1;
        if(root->right == NULL) return minDepth(root->left) + 1;
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

本代码提交AC,用时13MS,比BFS慢。

LeetCode Maximum Depth of Binary Tree

LeetCode Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.


计算出二叉树的最大深度,简单题,直接深搜即可。。。
完整代码如下:

class Solution {
public:
	int dfs(TreeNode* root, int nDepth) {
		if (root == NULL)return nDepth;
		int left = dfs(root->left, nDepth + 1);
		int right = dfs(root->right, nDepth + 1);
		return left > right ? left : right;
	}
	int maxDepth(TreeNode* root) {
		return dfs(root, 0);
	}
};

本代码提交AC,用时13MS。
二刷。还可以更简洁一些:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        if(root->left == NULL && root->right == NULL) return 1;
        int left_depth = maxDepth(root->left), right_depth = maxDepth(root->right);
        return max(left_depth, right_depth) + 1;
    }
};

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

LeetCode Multiply Strings

LeetCode Multiply Strings
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note:

  • The numbers can be arbitrarily large and are non-negative.
  • Converting the input string to integer is NOT allowed.
  • You should NOT use internal library such as BigInteger.

把两个以字符串形式存储的非负整数相乘起来,输出字符串结果。很考验基本功的一个题目,使用小学学过的乘法来做,一位一位相乘,然后把每一位相乘的结果加起来得到最终结果。
比如35*423,先调个位置423*35,确保num2长度短于num1,然后我们循环num2的每一位,比如首先5*423=2115,然后3*423=1269,但是加起来的时候要注意,1269要往前缩进一位成12690。最终结果为2115+12690=14805。
所以整个过程需要实现两个辅助函数,两个字符串相加,以及一个字符和字符串相乘的函数。完整代码如下:

class Solution {
public:
	string add(string num1, string num2) {
		int i = num1.size() - 1, j = num2.size() - 1;
		string ans = "";
		bool carry = false;
		while (i >= 0 || j >= 0) {
			int sum = (i >= 0 ? (num1[i] - '0') : 0) + (j >= 0 ? (num2[j] - '0') : 0);
			sum += carry ? 1 : 0;
			if (sum >= 10) {
				ans.push_back(sum - 10 + '0');
				carry = true;
			}
			else {
				ans.push_back(sum + '0');
				carry = false;
			}
			i--; j--;
		}
		if (carry)ans.push_back('1');
		reverse(ans.begin(), ans.end());
		return ans;
	}
	string multiply(string num1, char c) {
		if (c == '0')return "0";
		if (c == '1')return num1;
		string ans = "";
		int i = num1.size() - 1;
		int carry = 0;
		while (i >= 0) {
			int prod = (num1[i] - '0')*(c - '0');
			prod += carry;
			if (prod >= 10) {
				ans.push_back(prod % 10 + '0');
				carry = prod / 10;
			}
			else {
				ans.push_back(prod + '0');
				carry = 0;
			}
			i--;
		}
		if (carry > 0)ans.push_back(carry + '0');
		reverse(ans.begin(), ans.end());
		return ans;
	}
	string multiply(string num1, string num2) {
		if (num1.size() < num2.size()) { // 确保num1长于num2
			string tmp = num2;
			num2 = num1;
			num1 = tmp;
		}
		string ans = "0";
		int j = num2.size() - 1, k = 0; // k:缩进的位数
		while (j >= 0) {
			string p = multiply(num1, num2[j]);
			for (int i = 0; i < k; i++)
				p.push_back('0');
			ans = add(ans, p);
			j--; k++;
		}
		return ans;
	}
};

本代码提交AC,用时26MS。
二刷。上述解法不够简洁,讨论区有一种很漂亮的解法:https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation/60,图片解释如下:

也就是可以算出来两个digit相乘的结果在最终结果中的下标位置,比如上图中123*45,num1的2乘以num2的4的结果是8,对应的下标分别是num1的i=1和num2的j=0,两个digit相乘结果最多可以占两位,这两位在最终结果中的下标是i+j和i+j+1,这个例子就是i+j=1,j+j+1=2,相乘结果08正好叠加在最终结果的第1和2位。
完整代码如下:

class Solution {
public:
	string multiply(string num1, string num2) {
		int n1 = num1.size(), n2 = num2.size();
		vector<int> ans(n1 + n2, 0);
		for (int i = n1 - 1; i >= 0; --i) {
			for (int j = n2 - 1; j >= 0; --j) {
				int mul = (num1[i] - '0') * (num2[j] - '0');
				int p1 = i + j, p2 = i + j + 1;
				int sum = mul + ans[p2];
				ans[p1] += sum / 10;
				ans[p2] = sum % 10;
			}
		}
		string ret = "";
		int i = 0;
		while (i < n1 + n2 && ans[i] == 0)++i;
		if (i >= n1 + n2) return "0";
		while (i < n1 + n2) {
			ret.push_back('0' + ans[i]);
			++i;
		}
		return ret;
	}
};

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