# LeetCode Merge Sorted Array

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

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

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[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

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2
Output:
[
[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;
}
};

class Solution {
public:
void dfs(vector<vector<int>> &ans, vector<int> &cand, int n, int k) {

if (cand.size() == k) {
ans.push_back(cand);
return;
}
if (n == 0)return;

cand.push_back(n);
dfs(ans, cand, n - 1, k);
cand.pop_back();

dfs(ans, cand, n - 1, k);
}
vector<vector<int>> combine(int n, int k) {
vector<int> cand;
vector<vector<int>> ans;
dfs(ans, cand, n, k);
return ans;
}
};

# LeetCode Simplify Path

Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.

In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level.

Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.

Example 1:

Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.


Example 2:

Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.


Example 3:

Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.


Example 4:

Input: "/a/./b/../../c/"
Output: "/c"


Example 5:

Input: "/a/../../b/../c//.//"
Output: "/c"


Example 6:

Input: "/a//b////c/d//././/.."
Output: "/a/b/c"

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

class Solution {
public:
string simplifyPath(string path) {
stack<string> stk;
int n = path.size();
int i = 0, j = 0;
while (i < n) {
while (i < n&&path[i] == '/')++i;
if (i >= n)break;
j = i + 1;
while (j < n&&path[j] != '/')++j;
string name = path.substr(i, j - i);
if (name == ".." && !stk.empty())stk.pop();
if (name != "."&&name != "..")stk.push(name);
i = j;
}
string ans = "";
while (!stk.empty()) {
ans = "/" + stk.top() + ans;
stk.pop();
}
if (ans == "")return "/";
else return ans;
}
};

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

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps


Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

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

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place 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.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

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

class Solution {
public:
void sortColors(vector<int>& nums)
{
int zero = 0, second = nums.size() - 1;
int i = 0;
while (i <= second) {
while (i < second && nums[i] == 2) {
swap(nums[i], nums[second--]);
}
while (i > zero && nums[i] == 0) {
swap(nums[i], nums[zero++]);
}
++i;
}
}
};


# LeetCode Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
/ \       / \
2   3     2   3

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

Output: true


Example 2:

Input:     1         1
/           \
2             2

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

Output: false


Example 3:

Input:     1         1
/ \       / \
2   1     1   2

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

Output: false

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

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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
/ \
9  20
/  \
15   7

return its minimum depth = 2.

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

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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
/ \
9  20
/  \
15   7

return its depth = 3.

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

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"


Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9.
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

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

class Solution {
public:
string SingleMultiply(string s, char c) {
string ans = "";
int vc = c - '0';
int carry = 0;
for (int i = s.size() - 1; i >= 0; --i) {
int vs = s[i] - '0';
int prod = vc * vs + carry;
ans.push_back('0' + (prod % 10));
carry = prod / 10;
}
if (carry > 0)ans.push_back(carry + '0');
return ans;
}
string multiply(string num1, string num2) {
int n1 = num1.size(), n2 = num2.size();
if (n1 > n2)return multiply(num2, num1);
if (num1 == "0")return "0";
vector<string> prods;
int max_len = 0;
for (int i = n1 - 1; i >= 0; --i) {
string prod = string(n1 - i - 1, '0') + SingleMultiply(num2, num1[i]);
max_len = prod.size() > max_len ? prod.size() : max_len;
prods.push_back(prod);
}
string ans = "";
int carry = 0;
for (int i = 0; i < max_len; ++i) {
int val = 0;
for (int j = 0; j < prods.size(); ++j) {
if (i < prods[j].size())val += (prods[j][i] - '0');
}
val += carry;
ans.push_back('0' + (val % 10));
carry = val / 10;
}
if (carry > 0)ans.push_back('0' + carry);
reverse(ans.begin(), ans.end());
return ans;
}
};