leetcode solution

Buy and Sell Stock 121 Best Time to Buy and Sell Stock Base Case:         int minPrice = prices[0];         int maxProfit = 0; Formula:         for (auto i = 0; i < prices.size(); i++) {             minPrice = min(minPrice, prices[i]);             maxProfit = max(maxProfit, prices[i] - minPrice);         } 122. Best Time to Buy and Sell Stock II Greedily Add all the prices[i] - prices[i - 1] delta to the total profit if it is greater than zero (since we can complete as much transactions as we want and there is no transaction fees) A slightly improvement is that, in a inner while loop, first record j = i as the starting price, while (i < N - 1 && prices[i] < prices[i +1]) we keep increase i, until it...

169 Majority Element Here low = 0, high = nums.size(); initially (super end) solve(vector<int>& nums, int low, int high) Base case: 1 == high - low return nums[low] Otherwise, get mid = low + (high - mid) / 2; int leftMod = solve(nums, low, mid); int rightMod = solve(nums, mid, high); if (leftMod == rightMod)     return leftMod; Otherwise count the leftMod and rightMod frequency in the whole array. return the bigger one. 53 Maximum Subarray Get the maximum of (1) maximum sub-array in the left half (2) maximum in the right half (3) and the maximum sub-array that accross the right half and right half. globalMax = max(solve(nums, left, mid), solve(nums, mid, right)); return  max(globalMax, leftMax + rightMax); 241 Different Ways to Add Parentheses  Get the different ways to add parentheses  (1) in the left half (2) in the right half (3) and the different combinations in the left half and right half using different operat...

Lecture 1: To do: (117? 199) Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree . In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. numerical_limits<int>::min()   <==> INT_MIN

It’s only impossible if you don’t compete.   Space complexity is a measure of the amount of working storage an algorithm needs. That means how much memory, in the worst case , is needed at any point in the algorithm .

Start at 2018.07.03 End at  Base Knowledge:   回溯算法的定义：回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就 退回一步重新选择 ，这种走不通就退回再走的技术为回溯法。适用于求解组合数较大的问题。 对于回溯问题，总结出一个递归函数模板，包括以下三点 递归函数的开头写好跳出条件，满足条件才将当前结果加入总结果中 已经拿过的数不再拿 if(s.contains(num)){continue;} 遍历过当前节点后，为了回溯到上一步，要去掉已经加入到结果list中的当前节点。 针对不同的题目采用不同的跳出条件或判断条件。 下面通过几个例子来说明对上述模板的使用 https://www.codetd.com/article/1054326   77 Combinations     套用模板 1. 退出条件： out.size（） == k 2. 已经拿过的数处理： pos = pos + 1 when recursion 3. 回溯：out.push_back(i) before recursion, and out.pop_back() after recursion backtracking(n, k, pos + 1, out, res);   39 Combination Sum   (similar 77)   套用模板   1. 退出条件： target cut down to zero  2. 已经拿过的数处理：  allow use the same number multiple times，pos = pos  3. 回溯：out.push_back(i) b...