fenghaolw

Given n, generate all structurally unique BST's (binary search trees) that store values 1, ... , n. Solution: The idea is exactly the same with  Unique Binary Search Trees . Notes: we need to use TreeNode *root = new TreeNode(i) to initialize a new struct and pointer. The following code passes LeetCode online large judge.

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 as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again). Solution: The maximum profit is always achieved by buying at the lowest points and selling at the highest points. In other words, we will buy the stock before the price increases, and sell the stock before the price decreases. This could be easily implemented by traversing the array. The following code passes LeetCode online large judge. Notes: the complexity is O(n). In this code we need to check the last element in the array. In the for loop we only sell the stock before the price decreases; however, it is possible that the price never goes down. So in the last element, we will sell the stock if

Given n, how many structurally unique BST's (binary search trees) that store values 1, ... , n? For example, Given n = 3, there are a total of 5 unique BST's. Solution: If root is 1 or n, then the left (or right) subtree is empty; another subtree stores n - 1 values If root is between 2 and n - 1, i.e., 1 < i < n, then the left subtree stores i - 1 values (1, ... , i - 1), the right subtree stores n - i values (i + 1, ... , n) Suppose the number of unique BST's that store values 1, ... , n is T(n), then T(n) = 2 * T(n - 1) + sum^{n - 1}_{i = 2} T(i - 1) * T(n - i) This number is also known as Catalan number The following code passes LeetCode online large judge Or, we can define T(0) = 1, then T(n) = sum^{n-1}_{i=0} T(i) T(n-1-i). Java version:

Say you have an array for which the i-th  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. Solution:  cannot use max - min since we have to buy the stock before sell... cannot find min first then find the max after min, since the maximum gap might be another one, for example, min might be the last element exhaustive search costs O(n^2)  divide and conquer: find the min of the first half and the max of the last half. compare the gap, and the gaps in each half. T(n) = 2T(n/2) + O(n) = O(nlogn) The following code passes LeetCode online large judge  class Solution { public : int maxProfit(vector < int > & prices) { // Start typing your C/C++ solution below // DO NOT write int main() function int s = prices.size(); if (s < 2 ) return 0 ; if (s ==