初级系列：https://leetcode.cn/leetbook/detail/top-interview-questions-easy/
后续会持续更新leetcode思路、代码以及题解。不一定每个题都写，但是会写一些我认为需要记录的。
数组
买卖股票的最佳时机 II
题目：买卖股票，可以多次买入卖出，但是每次最多只能持有一只股票。给出一段时间内的股票价格，求最大收益。
思路：人类思维的第一反应是对这个数组分组，找到每次买入和卖出的时间。但是人类也能很快发现，这个分组的点不好找，问题在于你在[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数组，每次轮换即可。
旋转数组
题目：要求把一个数组向后移动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]再转回来就行，这样可以做到不开额外空间。