# LeetCode House Robber III

LeetCode House Robber III The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the police. Example 1:

     3
/ \
2   3
\   \
3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7. Example 2:
     3
/ \
4   5
/ \   \
1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9. Credits: Special thanks to @dietpepsi for adding this problem and creating all test cases.

     1
/ \
2   3

# LeetCode House Robber II

213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),


Example 2:

Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).              Total amount you can rob = 1 + 3 = 4.

class Solution {
public:
int rob(vector<int>& nums)
{
if (nums.size() == 0)
return 0;
if (nums.size() == 1)
return nums[0];
int ans1 = 0, ans2 = 0;
vector<vector<int> > dp1(nums.size() + 1, vector<int>(2, 0)), dp2(nums.size() + 1, vector<int>(2, 0));
for (int i = 1; i < nums.size(); ++i) { // 不偷最后一家
dp1[i][0] = max(dp1[i – 1][0], dp1[i – 1][1]);
dp1[i][1] = dp1[i – 1][0] + nums[i – 1];
ans1 = max(ans1, max(dp1[i][0], dp1[i][1]));
}
for (int i = 2; i <= nums.size(); ++i) { // 不偷第一家
dp2[i][0] = max(dp2[i – 1][0], dp2[i – 1][1]);
dp2[i][1] = dp2[i – 1][0] + nums[i – 1];
ans2 = max(ans2, max(dp2[i][0], dp2[i][1]));
}
return max(ans1, ans2);
}
};

class Solution {
private:
int subrob(const vector<int>& nums, int left, int right)
{
int robsum = 0, norobsum = 0;
for (int i = left; i <= right; ++i) {
int nrs = max(robsum, norobsum);
int rs = norobsum + nums[i];
norobsum = nrs;
robsum = rs;
}
return max(robsum, norobsum);
}
public:
int rob(vector<int>& nums)
{
int n = nums.size();
if (n == 0)
return 0;
if (n == 1)
return nums[0];
return max(subrob(nums, 0, n – 2), subrob(nums, 1, n – 1));
}
};

class Solution {
private:
int rob_max(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
int ans = max(dp[0], dp[1]);
for (int i = 2; i < n; ++i) {
dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);
ans = max(ans, dp[i]);
}
return ans;
}
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0)return 0;
if (n == 1)return nums[0];
if (n == 2)return max(nums[0], nums[1]);
vector<int> money1(nums.begin(), nums.end() - 1), money2(nums.begin() + 1, nums.end());
return max(rob_max(money1), rob_max(money2));
}
};

# LeetCode Different Ways to Add Parentheses

241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +- and *.

Example 1:

Input: "2-1-1"
Output: [0, 2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2

Example 2:

Input: "2*3-4*5" Output: [-34, -14, -10, -10, 10] Explanation:  (2*(3-(4*5))) = -34  ((2*3)-(4*5)) = -14  ((2*(3-4))*5) = -10  (2*((3-4)*5)) = -10  (((2*3)-4)*5) = 10

class Solution {
private:
int operate(int a, int b, char c)
{
switch (c) {
case ‘+’:
return a + b;
case ‘-‘:
return a – b;
case ‘*’:
return a * b;
}
}
public:
vector<int> diffWaysToCompute(string input)
{
int n = input.size();
vector<int> ans;
bool found = false;
for (int i = 0; i < n; ++i) {
if (input[i] == ‘+’ || input[i] == ‘-‘ || input[i] == ‘*’) {
found = true;
vector<int> lefts = diffWaysToCompute(input.substr(0, i));
vector<int> rights = diffWaysToCompute(input.substr(i + 1));
for (int j = 0; j < lefts.size(); ++j) {
for (int k = 0; k < rights.size(); ++k) {
ans.push_back(operate(lefts[j], rights[k], input[i]));
}
}
}
}
if (!found)
return { atoi(input.c_str()) };
return ans;
}
};

# LeetCode Fraction Addition and Subtraction

LeetCode Fraction Addition and Subtraction Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1. Example 1:

Input:"-1/2+1/2"
Output: "0/1"

Example 2:
Input:"-1/2+1/2+1/3"
Output: "1/3"

Example 3:
Input:"1/3-1/2"
Output: "-1/6"

Example 4:
Input:"5/3+1/3"
Output: "2/1"

Note:
1. The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
2. Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
3. The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
4. The number of given fractions will be in the range [1,10].
5. The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.

# LeetCode Delete Operation for Two Strings

LeetCode Delete Operation for Two Strings Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string. Example 1:

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Note:
1. The length of given words won’t exceed 500.
2. Characters in given words can only be lower-case letters.

# LeetCode Combination Sum III

216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

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

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]


Example 2:

Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]]

class Solution {
private:
void dfs(vector<vector<int> >& ans, vector<int>& cand, int step, const int& k, int sum)
{
if (cand.size() == k && sum == 0) {
ans.push_back(cand);
return;
}
for (int i = step; i <= 9; ++i) {
if (i > sum)
break;
cand.push_back(i);
dfs(ans, cand, i + 1, k, sum – i);
cand.pop_back();
}
}
public:
vector<vector<int> > combinationSum3(int k, int n)
{
vector<vector<int> > ans;
vector<int> cand;
dfs(ans, cand, 1, k, n);
return ans;
}
};

class Solution {
void dfs(vector<vector<int>> &ans, vector<int> &cand, int k, int n, int &sum) {
if (cand.size() == k && sum == n) {
ans.push_back(cand);
return;
}
if (cand.size() >= k || sum >= n)return;
int start = 1;
if (!cand.empty())start = cand.back() + 1;
for (int i = start; i <= 9; ++i) {
cand.push_back(i);
sum += i;
dfs(ans, cand, k, n, sum);
sum -= i;
cand.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
if (k > 9 || n > 45)return { };
vector<vector<int>> ans;
vector<int> cand;
int sum = 0;
dfs(ans, cand, k, n, sum);
return ans;
}
};

# LeetCode Kth Smallest Element in a Sorted Matrix

378. Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
[ 1,  5,  9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

return 13.


Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

class Solution {
private:
struct Node {
int val, row, col;
Node(int v = 0, int r = 0, int c = 0)
: val(v)
, row(r)
, col(c){};
friend bool operator<(const Node& n1, const Node& n2) { return n1.val > n2.val; }
};
public:
int kthSmallest(vector<vector<int> >& matrix, int k)
{
int n = matrix.size();
priority_queue<Node> pn;
for (int i = 0; i < n; ++i)
pn.push(Node(matrix[i][0], i, 0));
Node t;
while (k–) {
t = pn.top();
pn.pop();
if (t.col < n – 1)
pn.push(Node(matrix[t.row][t.col + 1], t.row, t.col + 1));
}
return t.val;
}
};

class Solution {
public:
int kthSmallest(vector<vector<int> >& matrix, int k)
{
int n = matrix.size(), left = matrix[0][0], right = matrix[n – 1][n – 1];
while (left <= right) {
int mid = left + (right – left) / 2;
int cnt = 0;
for (int i = 0; i < n; ++i) {
cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) – matrix[i].begin();
}
if (cnt < k)
left = mid + 1;
else
right = mid – 1;
}
return left;
}
};

class Solution {
private:
int count_less_equal(vector<vector<int> >& matrix, int num)
{
int n = matrix.size(), i = n – 1, j = 0, cnt = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] <= num) {
cnt += i + 1;
++j;
}
else
–i;
}
return cnt;
}
public:
int kthSmallest(vector<vector<int> >& matrix, int k)
{
int n = matrix.size(), left = matrix[0][0], right = matrix[n – 1][n – 1];
while (left <= right) {
int mid = left + (right – left) / 2;
int cnt = count_less_equal(matrix, mid);
if (cnt < k)
left = mid + 1;
else
right = mid – 1;
}
return left;
}
};

# LeetCode Kill Process

LeetCode Kill Process Given n processes, each process has a unique PID (process id) and its PPID (parent process id). Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers. We use two list of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID. Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer. Example 1:

Input:
pid =  [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation:
3
/   \
1     5
/
10
Kill 5 will also kill 10.

Note:
1. The given kill id is guaranteed to be one of the given PIDs.
2. n >= 1.

# LeetCode Heaters

LeetCode Heaters Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses. Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters. So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters. Note:

1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
3. As long as a house is in the heaters’ warm radius range, it can be warmed.
Example 1:
Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:
Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

# LeetCode Permutation in String

LeetCode Permutation in String Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string. Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:
Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:
1. The input strings only contain lower case letters.
2. The length of both given strings is in range [1, 10,000].