# LeetCode Lowest Common Ancestor of a Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree:  root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.


Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.


Note:

• All of the nodes’ values will be unique.
• p and q are different and both values will exist in the BST.

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
if (p->val > q->val)
swap(p, q);
if (p->val <= root->val && q->val >= root->val)
return root;
if (p->val < root->val && q->val < root->val)
return lowestCommonAncestor(root->left, p, q);
if (p->val > root->val && q->val > root->val)
return lowestCommonAncestor(root->right, p, q);
}
};

class Solution {
void BSTSearch(TreeNode* root, TreeNode* p, vector<TreeNode*>& ancestors) {
while (root->val != p->val) {
ancestors.push_back(root);
if (p->val > root->val)root = root->right;
else root = root->left;
}
ancestors.push_back(root);
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> pa, qa;
BSTSearch(root, p, pa);
BSTSearch(root, q, qa);
int i = 0;
for (; i < pa.size() && i < qa.size(); ++i) {
if (pa[i] != qa[i])break;
}
return pa[i - 1];
}
};

# LeetCode Insert Delete GetRandom O(1) – Duplicates allowed

LeetCode Insert Delete GetRandom O(1) – Duplicates allowed Design a data structure that supports all following operations in average O(1) time. Note: Duplicate elements are allowed.

1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
Example:
// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();
// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);
// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);
// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);
// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();
// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);
// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

• 10:[0,1]
• 20:[2,3]
• 30:[4,5]

• 10:[0]
• 20:[2,3]
• 30:[4,1]

• 10:[]
• 20:[2,3]
• 30:[4,0]

# LeetCode Insert Delete GetRandom O(1)

LeetCode Insert Delete GetRandom O(1) Design a data structure that supports all following operations in average O(1) time.

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();
// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);
// Returns false as 2 does not exist in the set.
randomSet.remove(2);
// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);
// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();
// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);
// 2 was already in the set, so return false.
randomSet.insert(2);
// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

# LeetCode Best Time to Buy and Sell Stock with Cooldown

LeetCode Best Time to Buy and Sell Stock with Cooldown Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

1. 第i天卖出的收益=max(第i-1天买入+第i天卖出的收益，第i-1天卖出~但反悔了~改为第i天卖出)
2. 第i天买入的收益=max(第i-2天卖出~第i-1天冷却~第i天买入的负收益，第i-1天买入~但反悔了~改为第i天买入)

1. 第i-1天卖出后反悔，改为第i天卖出 等价于 第i-1天持有股票，第i天再卖出
2. 第i-1天买入后反悔，改为第i天买入 等价于 第i-1天没有股票，第i天再买入

# LeetCode Best Time to Buy and Sell Stock IV

188. Best Time to Buy and Sell Stock IV

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.


Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

1. mustSell[i][j]=max(globalBest[i-1][j-1]+profit, mustSell[i-1][j]+profit)
2. globalBest[i][j]=max(globalBest[i-1][j], mustSell[i][j])

class Solution {
public:
int maxProfit(int k, vector<int>& prices)
{
int days = prices.size();
if (days < 2)
return 0;
if (k >= days / 2) {
int ans = 0;
for (int i = 1; i < days; ++i) {
if (prices[i] > prices[i – 1])
ans += (prices[i] – prices[i – 1]);
}
return ans;
}
vector<vector<int> > mustSell(days, vector<int>(k + 1, 0)), globalBest(days, vector<int>(k + 1, 0));
for (int i = 1; i < days; ++i) {
int profit = prices[i] – prices[i – 1];
for (int j = 1; j <= k; ++j) {
mustSell[i][j] = max(globalBest[i – 1][j – 1] + profit, mustSell[i – 1][j] + profit);
globalBest[i][j] = max(globalBest[i – 1][j], mustSell[i][j]);
}
}
return globalBest[days – 1][k];
}
};

# LeetCode Best Time to Buy and Sell Stock III

123. Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.


Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

class Solution {
public:
int maxProfit(vector<int>& prices)
{
int n = prices.size();
if (n < 2)
return 0;
vector<int> minprice(n), maxprice(n);
for (int i = 0; i < n; ++i) {
minprice[i] = i == 0 ? INT_MAX : min(minprice[i – 1], prices[i – 1]);
maxprice[n – i – 1] = i == 0 ? INT_MIN : max(maxprice[n – i], prices[n – i]);
}
vector<int> profit1(n), profit2(n);
for (int i = 0; i < n; ++i) {
profit1[i] = i == 0 ? 0 : max(profit1[i – 1], prices[i] – minprice[i]);
profit2[n – i – 1] = i == 0 ? 0 : max(profit2[n – i], maxprice[n – i – 1] – prices[n – i – 1]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, profit1[i] + profit2[i]);
}
return ans;
}
};

class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0 || n == 1)return 0;
vector<int> cur_min(n, INT_MAX), cur_max(n, INT_MIN);
cur_min[0] = prices[0];
cur_max[n - 1] = prices[n - 1];
for (int i = 1; i < n; ++i) {
cur_min[i] = min(cur_min[i - 1], prices[i]);
cur_max[n - i - 1] = max(cur_max[n - i], prices[n - i - 1]);
}
for (int i = 1; i < n; ++i) {
dp_sell[i] = max(dp_sell[i - 1], prices[i] - cur_min[i]);
dp_buy[n - i - 1] = max(dp_buy[n - i], cur_max[n - i - 1] - prices[n - i - 1]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, dp_sell[i] + dp_buy[i]);
}
return ans;
}
};

# LeetCode Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.


Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.


Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

class Solution {
public:
int maxProfit(vector<int>& prices)
{
int ans = 0;
for (int i = 1; i < prices.size(); ++i) {
if (prices[i] > prices[i – 1])
ans += (prices[i] – prices[i – 1]);
}
return ans;
}
};

# LeetCode Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.


Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

class Solution {
public:
int maxProfit(vector<int>& prices)
{
if (prices.size() < 2)
return 0;
vector<int> diff(prices.size() – 1);
for (int i = 1; i < prices.size(); ++i) {
diff[i – 1] = prices[i] – prices[i – 1];
}
vector<int> dp(diff.size());
int ans = 0;
for (int i = 0; i < diff.size(); ++i) {
if (i == 0 || dp[i – 1] < 0)
dp[i] = diff[i];
else
dp[i] = dp[i – 1] + diff[i];
ans = max(ans, dp[i]);
}
return ans;
}
};

class Solution {
public:
int maxProfit(vector<int>& prices)
{
if (prices.size() < 2)
return 0;
vector<int> dp(prices.size());
int min_so_far = prices[0], ans = 0;
for (int i = 1; i < prices.size(); ++i) {
dp[i] = prices[i] – min_so_far;
min_so_far = min(min_so_far, prices[i]);
ans = max(ans, dp[i]);
}
return ans;
}
};

class Solution {
public:
int maxProfit(vector<int>& prices)
{
int n = prices.size();
if (n < 2)
return 0;
vector<int> minprice(n), maxprice(n);
int ans = 0;
for (int i = 0; i < n; ++i) {
minprice[i] = (i == 0 ? prices[0] : min(minprice[i – 1], prices[i]));
maxprice[n – i – 1] = (i == 0 ? prices[n – 1] : max(maxprice[n – i], prices[n – i – 1]));
}
for (int i = 0; i < n; ++i) {
ans = max(ans, maxprice[i] – minprice[i]);
}
return ans;
}
};

# LeetCode Search in Rotated Sorted Array II

81. Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true


Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

• This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
• Would this affect the run-time complexity? How and why?

class Solution {
public:
bool search(vector<int>& nums, int target)
{
int l = 0, r = nums.size() – 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target)
return true;
if (nums[mid] < nums[r]) {
if (target > nums[mid] && target <= nums[r]) {
l = mid + 1;
}
else {
r = mid – 1;
}
}
else if (nums[mid] > nums[r]) {
if (target >= nums[l] && target < nums[mid]) {
r = mid – 1;
}
else {
l = mid + 1;
}
}
else {
–r;
}
}
return false;
}
};

class Solution {
public:
bool SearchRange(vector<int>& nums, int l, int r, int target) {
if (l > r)return false;
if (l == r)return nums[l] == target;

int mid = l + (r - l) / 2;
if (nums[mid] == target)return true;

if (nums[l] < nums[mid]){
if (target >= nums[l] && target < nums[mid])return SearchRange(nums, l, mid - 1, target);
else return SearchRange(nums, mid + 1, r, target);
}
else if (nums[l] > nums[mid]) {
if (target > nums[mid] && target <= nums[r])return SearchRange(nums, mid + 1, r, target);
else return SearchRange(nums, l, mid - 1, target);
}
else {
++l;
return SearchRange(nums, l, r, target);
}
}
bool search(vector<int>& nums, int target) {
return SearchRange(nums, 0, nums.size() - 1, target);
}
};

# LeetCode Search in Rotated Sorted Array

33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4


Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

class Solution {
public:
int search(vector<int>& nums, int target)
{
int l = 0, r = nums.size() – 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] < nums[r]) {
if (target > nums[mid] && target <= nums[r]) {
l = mid + 1;
}
else {
r = mid – 1;
}
}
else {
if (target >= nums[l] && target < nums[mid]) {
r = mid – 1;
}
else {
l = mid + 1;
}
}
}
return -1;
}
};

class Solution {
public:
int BinarySearch(vector<int>& nums, int target, int left, int right) {
if (left > right)return -1;
if (left == right) {
if (nums[left] == target)return left;
else return -1;
}
if (nums[left] < nums[right]) {
if (target >= nums[left] && target <= nums[right]) {
int mid = left + (right - left) / 2;
if (nums[mid] == target)return mid;
else if (nums[mid] < target)return BinarySearch(nums, target, mid + 1, right);
else return BinarySearch(nums, target, left, mid - 1);
}
else {
return -1;
}
}
else {
int mid = left + (right - left) / 2;
int lans = BinarySearch(nums, target, left, mid);
int rans = BinarySearch(nums, target, mid + 1, right);
if (lans != -1)return lans;
if (rans != -1)return rans;
return -1;
}
}
int search(vector<int>& nums, int target) {
return BinarySearch(nums, target, 0, nums.size() - 1);
}
};


class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l <= r) {
int m = l + (r - l) / 2;
if(nums[m] == target) return m;

if(l == m || nums[l] < nums[m]) { // l == m 左边只有一个元素，左边也是有序的
if(target >= nums[l] && target < nums[m]) r = m - 1;
else l = m + 1;
} else {
if(target > nums[m] && target <= nums[r]) l = m + 1;
else r = m - 1;
}
}

return -1;
}
};