hoho的日子

121. Best Time to Buy and Sell Stock 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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. Example 1: Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 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 In this case, no transaction is done, i.e. max profit = 0. 思路: O(n) 定義買點為目前最小值 並找出目前最大好處 buy = min( buy, i ) res  = max( res, i - buy) 122. Best Time to Buy and Sell Stock II ou may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 思路: O(n) 只要明天比今天的價更高 就值得投資. 掃一遍 prices 如果 prices[i+1]大於今天的值 累加...

Given a collection of candidate numbers ( C ) and a target number ( T ), find all unique combinations in  C  where the candidate numbers sums to  T . Each number in  C  may only be used  once  in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set  [10, 1, 2, 7, 6, 1, 5]  and target  8 , A solution set is:  [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] 思路: 這題跟 第39題 combination sum 小有差別 combination sum    可以想成 找零錢 然後手裡的零錢是無限的 請問有幾種找法? combination sum II可以想成 找零錢 然後手裡的零錢是 有 限的 請問有幾種找法? 我們可以在原本的 combination sum 上面做些改變: 1. 對candidates sort, 這可以讓我們之後輕易的判斷 candidate[i] == candidate[i-1] 是否一樣. 一樣的話直接跳過 (line 15) 2. 判斷path 是否在 res 出現過 (line 12) Time complexity: O(n!), n = element in the candidates Space complexity: O(m), the result of how many path we found class Solution(objec...