算法拾珠（二）

不知怎么的把算法拾珠（一）发到公众号上去了，底稿也删了，所以算法拾珠（一）只能见公众号文章了。

本文记录了三种算法问题的基本问题和一系列扩展问题（followup），可供深入理解这几类问题的解法。

这三类问题包括：

X sum问题：一个序列中取X个数字，使它们的和凑成定值。

股票买卖问题：一段连续天数，股票有价格可以买卖，问最大获利。

链表环问题：链表有环的条件，检测和分析。

X sum 问题

1) Two Sum, LeetCode #1

我当初的解法：排序，二分法

最优解法：一边遍历，一边插入、查询hashmap，O(n)复杂度，O(n)空间

2) 3Sum, LeetCode #15

我的解法：排序，从左到右枚举，然后用双指针往中间移动

最优解法：目前看到的最优解法如上，O(n^2logn)时间，O(1)空间

3) 3Sum Cloest, LeetCode #16

解法：类似3Sum那样去找，只是每次记录一下与target的差距，最后取一个最小值。O(n2logn)时间，O(1)空间

4) 4Sum, LeetCode #18

解法: 还是双指针的思想，只不过比3Sum多一层而已。O(n^3)时间，O(1)空间

*5) 4Sum II, LeetCode #454

解法：首先A,B,C,D都排序，枚举A，B的元素，然后还是双指针的思想，一个指针在C从左往右，一个指针在D从右往左。

这题比较偏了，不属于常规kSum，不做重点考虑。

由此可得，k-Sum问题当k==2时可以用hashmap的额外空间以O(n)的复杂度解决。而当k>2时可以用递归以及双指针法来解决。

// kSum通用代码
void kSum(const vector<int>& nums, int k, int target, int from, int end, vector<int>& cur, vector<vector<int> >& result) {
        if (k < 2) return;
        if (k == 2) {
            int l = from, r = end;
            while (l < r) {
                if (nums[l] + nums[r] == target) {
                    vector<int> tmp(cur);
                    tmp.push_back(nums[l]);
                    tmp.push_back(nums[r]);
                    result.push_back(tmp);
                    while (l < r && nums[l] == nums[l+1]) l++;
                    while (l < r && nums[r] == nums[r-1]) r--;
                    l++, r--;
                }
                else if (nums[l] + nums[r] > target)
                    r--;
                else
                    l++;
            }
        }
        else {
            for (int i=from;i<=end-k+1;i++) {
                if (i > from && nums[i] == nums[i-1]) continue;
                cur.push_back(nums[i]);
                kSum(nums, k-1, target-nums[i], i+1, end, cur, result);
                cur.pop_back();
            }
        }
    }

股票买卖问题

给定n天的股票价格数据，n天内，买卖股票一次或多次，获得最大收益。

1) Best Time to Buy and Sell Stock, LeetCode #121

要求买卖一次股票，获得最大收益。

解法：贪心，即可，可以把股价看做折线图，只能买卖一次，所以我们只需找最低的波谷和最高的波峰，相减即得。当然要保证波峰在波谷之后。

具体的，从左往右扫描，维护当前最小值，每次用当天的股价减去目前最小股价（保证波峰在波谷之后），求得一个max值，即为答案。

复杂度O(n), O(1)，已经最优了。

2) Best Time to Buy and Sell Stock II, LeetCode #122

可以买卖任意次，获得最大收益。

解法：还是把股价波动看成折线图，既然可以无线买，那么我们肯定是贪心地，每个上升斜坡的钱都要挣到。

所以，具体的，只要price[i] > price[i+1]，一定可以挣这份钱。最大收益就是这样的钱的累加。

复杂度O(n), O(1)，也是最优。

3) Best Time to Buy and Sell Stock III, LeetCode #123

至多买卖两次。

我的解法：类似前面的思路，无非是要找最多两个不重叠的波谷-波峰对，我们枚举分界点，求出分界点左边的最优波谷-波峰和右边的最优波谷-波峰，相加为答案。

具体的，用O(n)的空间存储前缀的最优波谷-波峰，同样用O(n)的空间存储后缀的最优波谷-波峰，最后枚举分界点，两个利润一相加为答案。

此解法复杂度为O(n), O(n)，需要一定空间来存储。

更优解法：

动态规划的思想。

每天只可能是种状态之一：持有第一支，卖出第一支，持有第二支，卖出第二支。

dp[i][state]表示到第i天，状态为state所获的最大收益。

则

dp[i][sell2] = max(dp[i-1][sell2], dp[i-1][hold2]+i)
dp[i][hold2] = max(dp[i-1][hold2], dp[i-1][sell1]-i)
dp[i][sell1] = max(dp[i-1][sell1], dp[i-1][hold1]+i)
dp[i][hold1] = max(dp[i-1][hold1], 0-i)

return dp[n][sell2]

由于dp[i][states]只与dp[i-1][states]有关，所以可以直接用一个变量表示每种状态，所以可以做到O(n), O(1)。

4) Best Time to Buy and Sell Stock IV, LeetCode #188

至多买卖k次。

类似上题的思想，动态规划法，只是4种状态变成2k种状态而已。

dp[i][k][h]表示到第i天，目前操作股票（持有/卖出）是第k支，操作状态为h（h=0:持有，h=1:卖出）。

则有如下转移方程：

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k][0]+prices[i]);
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k-1][1]-prices[i]);

同样，由于第一维(i)只与i-1有关，所以该存储也可省去。

复杂度O(kn)，空间O(k)。

这题要注意的是，当k>=n/2时，实际上等价于没有次数限制的情况。对应题(2)。

3) Best Time to Buy and Sell Stock with Cooldown, LeetCode #309

可以无限次买卖，但是每次卖出后都需要隔一天才能再次买入。

解法：

动态规划求解，由于不限买卖次数，只是需要隔一天。

我们令每天只有两种状态：持有(hold)，套现(cash)，其中持有包括不买卖和买入。

cash[i]表示第i天，最大现金流，有两个子问题：一是之前就已经套现，而是之前持有，今天套现。去这两者的最大值为今天最大现金流。持有类似。

那么有如下方程：

// 套现取 |之前套现| 与 |之前持有，今天套现| 二者的最大值，后者要减去一定的手续费。
cash[i] = max(cash[i-1], hold[i-1]+prices[i]-fee)
// 持有取 |之前持有| 与 |前天及之前套现，今天买入| 二者的最大值。
hold[i] = max(hold[i-1], cash[i-2]-prices[i])

4) Best Time to Buy and Sell Stock with Transaction Fee, LeetCode #714

可以无限次买卖，但是每次卖出操作都有手续费fee，求最大收益。

解法：

动态规划求解，由于不像限制买卖次数的题，我们不能去照样维护一个dp[k][2]，因为不知道k是多少，我们也无需考虑这次买卖是第几支，因为不限制随便买。

当然，也可以令k为n/2，但此时我们用另一种方法求解。

我们令每天只有两种状态：持有(hold)，套现(cash)，其中持有包括不买卖和买入。

那么有如下方程：

// 套现取 |之前套现| 与 |之前持有，今天套现| 二者的最大值，后者要减去一定的手续费。
cash[i] = max(cash[i-1], hold[i-1]+prices[i]-fee)
// 持有取 |之前持有| 与 |之前套现，今天买入| 二者的最大值。
hold[i] = max(hold[i-1], cash[i-1]-prices[i])

总而言之，解决股票类问题，如果简单的话，可以直接贪心思想来做，当然该贪心方法也是动态规划的特例。 如果稍微复杂一点，那么可以用动态规划来做。 只要把握好每天的状态，就好定制状态转移方程了。

链表环问题

链表环问题是比较常问的一类问题。我们系统梳理一下。

1) 判断单链表是否有环

解法：解法已经烂大街了，设置两个指针p1, p2，一个每次走一步，一个每次走两步，最后如果 p1 == p2，说明有环，如果其中一个为NULL，则没有环。

2) 证明这样做的正确性

• 如果没有环，走得快的那个一定会率先走到NULL，结束。
• 如果有环，那么需证明，p1, p2 一定会相遇，从而得出有环的结论。
  考虑 p1, p2 的距离，因为如果有环，最后 p1, p2 都会进入环，如果进入环的时候他们的距离为d，由于 p2 比 p1 快一步，所以他们的距离每次都会缩短1，所以他们的距离会呈现 d,d-1,d-2,…1,0 这样的趋势，最终距离为 0，相等判环。
  且由于d < r（环长），所以，相遇的时候，p1绝对还没有绕环一圈。

3) 求有环单链表的环长

解法：我们走到相遇点以后，从相遇点出发，一直走，总会走回到相遇点，这时走的步数就是环长。

另一种比较绕的思路：从相遇点开始 p1 和 p2 继续按照原来的方式向前走，直到二者再次相遇，此时经过的步数就是环上节点的个数。

因为 p1 == p2，可以看成他们初始距离为r（环长），此后每步初始距离减1，减到0，走的步数就是环长。

4) 如果存在环，找出环的入口点

假设链表总长为 L，head 到入口节点距离为 a，入口节点到相遇点距离为x，则环长 $r = L - a$

假设当 p1, p2 第一次相遇时，p1 走了 s 步，则 p2 走了 2s 步。即 $s = a+x$。

由于此时相遇，则有 $s + nr = 2s, n \ge 1$。

则有 $nr = a+x$，$a = nr - x = (n-1)r + r - x = (n-1)r + L - a - x$。

也就是说，我们从起点 head 走到入口节点，和从相遇点走 0 圈或多圈到达入口节点的距离是一样的。

所以，一个指针 p3 从 head 出发，一个 p4 从相遇点出发，p3==p4 时，到达入口节点。

5) 求有环单链表的链表长

入口节点知道了，则距离 a 知道了，环长 r 也知道了，所以 a + r = L。

6) 如果存在环，求出环上距离任意一个节点最远的点（对面节点）

其实这题相当于求链表的中间点，仍可以用一快一慢双指针解决。一个走一步，一个走两步。

7) 为什么快慢指针步长为2，为3, 4, 5…行不行？

可以。下面证明在有环链表中，步长$k=3,4,5…$的时候依然存在一个相遇点，检测出环。

即要证明存在 s, $X_s == X_{2s}$。

设 s 是第一个大于 a 的且是 r 的倍数的数。且 $X_{2s}$ 可被看做 s 多走了 $(k-1)s$ 步到达的地点。

即 $X_{2s} = X_s + ((k-1)s \% r)$，又 s 是 r 的倍数，所以后项等于 0。所以有 $X_s == X_{2s}$。

所以无论对于多大的 k (k > 1)，都存在一个 s，使得两指针相遇，判断出环。

8) 步长改成3会不会变快？不能，为什么？相遇所经过的步数与环和步长有什么关系？

仍然设 head 到相遇点距离为 s，设步长为 k，则有 $s + nr = ks$。

即有：$nr = (k-1)s \to s = nr / (k-1)$。

这就是相遇所经过的步数与环和步长的关系。

那么 $s = nr / (k-1)$，最好的情况是，$s = r$ 即 $n / (k-1) = 1 \to k = n+1$。

又因为，$n \ge 1$，因为快指针至少比慢指针多走一圈（不绕一圈无法相遇）。

所以 $k >= 2$，由于快指针走得复杂度是 $O(nk)$，所以 k 越小越好，为 2 最佳。慢指针复杂度是 $O(n)$。

9) 会不会在多点相遇？

会，但是考虑这个无意义了，因为只要相遇，环已经检测出来了。

总的来说，遇到链表环问题，基本上用双指针来做，快的指针步长为2是有道理的，能够使得相遇前快指针走的步数最少，也即时间复杂度最小。当然，任意的k>1都能够作为快指针的步长。