# 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.

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];
}
}
};


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--;
}
}
}
};


# 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:

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

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;
}
};


# 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],
]

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;
}
};


# 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".

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;
}
};


# 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?

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;
}
};


# 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?

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;
}
};


# 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;
}
};


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);
}
};


# 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.

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);
}
}; 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);
}
};


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);
}
};


#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;
} 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;
}
};


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;
}
};


# 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);
}
};


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;
}
};


# 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.

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;
}
}; 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;
}
};