Daily Archives: January 6, 2016

Best Time to Buy and Sell Stock with Cooldown

https://leetcode.com/problems/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]

Solution 1
t is quite similar to balloon burst problem. We build a 2-dimension dp[][]. dp[left][right] indicates the max profit we can get from prices[left] to prices[right]. Because there is one day cool down, we can get the basic formula dp[left][right] = dp[left][k-1] + dp[k+1][right]. It means when we sold at k-1 time, at most we can but at k+1 time.
sellstockcooldown1
Complete formula is sellstockcooldown2
This solution takes O(n^2) time and space, which was not able to pass leetcode.

Solution 2
We define sell[] and notsell[]. sell[i] is the max profit if we sell at i time. notsell[i] is the max profit if we don’t sell at i time.

For sell[i], If we sell at i time, at least we should add the gap value of prices[i] – price[i – 1]. It has 2 conditions. When i-1 time was sold, then buy at i-1 time again and sell it at i time.(or it equal we didn’t sell at i-1 time, we passed it). So we have sell[i] = sell[i – 1] + prices[i] – price[i – 1].
Another condition is that at i-1 time, we didn’t sell. We really bought at i-1 time and sell at i time. Because there is a cool down time. i-2 time shouldn’t sell neither. So for this condition we have notsell[i – 2] + prices[i] – price[i – 1].
For notsell[i], it is a easy one. notesell[i] = max(sell[i – 1], notsell[i – 1])

Totally, we have:
sell[i] = max(sell[i – 1] + prices[i] – price[i – 1], notsell[i – 1] + prices[i] – price[i – 1])
notesell[i] = max(sell[i – 1], notsell[i – 1])

In the end, we return max(sell[n – 1], notsell[n – 1]). Below is a calculation matrix for [1, 2, 3, 0, 2].sellstockcooldown3

check my code on github: link

Minimum height trees

https://leetcode.com/problems/minimum-height-trees/

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n – 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

0
|
1
/ \
2 3
return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

0 1 2
\ | /
3
|
4
|
5
return [3, 4]

Solution 1: Since this is a tree like graph. It means there is circle. One solution is to delete leaf nodes in the graph. In the new graph, delete the leaf node again. Do this until graph only has 1 or 2 nodes. The left 1, 2 node are the result. check my code on github: link

Solution 2: Find a random node. Treat this node as root. And find the diameter path. The middle 2 nodes will be the result. check my previous code for finding diameter in binary tree: link

Both of the solution has time complexity O(V), space complexity O(V).