[Leetcode系列]初級演算法
初級系列： http://leetcode.cn/leetbook/detail/top-interview-questions-easy/
後續會持續更新leetcode思路、程式碼以及題解。不一定每個題都寫，但是會寫一些我認為需要記錄的。
陣列
題目：買賣股票，可以多次買入賣出，但是每次最多隻能持有一隻股票。給出一段時間內的股票價格，求最大收益。
思路：人類思維的第一反應是對這個陣列分組，找到每次買入和賣出的時間。但是人類也能很快發現，這個分組的點不好找，問題在於你在[A,B]選擇買賣時，無論是A還是B都不好列舉。因此，重新審題，發現：1. 如果我把買入和賣出的時間看成k個[A,B]的區間，那麼如果我想在總的1-n天最優，那麼一定存在一個區間集合set([Ai,Bi])中每個區間都是最優的，且從中按順序抽出一段也是最優的，這就是最優化原理。2. 第i+1天的結果只與第i天的狀態+動作有關，第i天的狀態是對前i-1天策略的總結，這就是滿足無後效性。滿足無後效性+最優化原理，就可以進行DP了。
考慮每個時刻的狀態：只有持有股票和未持有股票兩種狀態，即f[i][0]為第i時刻未持有股票的狀態，f[i][1]為第i時刻持有股票的狀態。f[i][0] = max(f[i-1][1] + price[i], f[i-1][0]), f[i][1] = max(f[i-1][0] – price[i], f[i-1][1]) 發現f[i][x]只與f[i-1][x]有關，用一個變數代替f陣列，每次輪換即可。
程式碼： http://leetcode.cn/submissions/detail/355898476/
題目：要求把一個數組向後移動k位，出界的元素自動回到陣列開頭，並且繼續向後移動。如[1,2,3]移動1位是[3,1,2]。題目希望給出儘量多的思路。
思路：我想了幾個思路：
首先先把k對陣列長度取模，別重複轉了。
- 新建一個臨時陣列，原陣列i位置的元素應該放在(i+k)%n的位置
- 把原陣列複製兩遍，從第k個位置開始截就行。這種迴圈的題都可以用複製兩遍解。
- 先reverse整個陣列，然後reverse[0,k-1]再reverse[k, n-1]。這種做法比較巧妙。證明：[n-k,n-1]位置的元素應該跑到[0, k-1]，並且需要平移過去。如果使用reverse，雖然會把[n-k,n-1]放到[0, k-1]但是方向是反的，這時候只要再轉一下即可。最後吧[k, n-1]再轉回來就行，這樣可以做到不開額外空間。