面试题 17.24. 最大子矩阵

面试题 17.24. 最大子矩阵

思路:

本题是最大连续子数组的二维follow up.

一维情况下,可以直接使用多种算法求解:

  1. 累加数组+二维搜索左右边界, $O(N^2)$

  2. 二维搜索左右边界同时累加数字,$O(N^2)$

  3. 分治算法,把问题maxarr(i, j)分解为maxarr(i, mid)maxarr(mid + 1, j)。其中子数组可能在左右两端数组中或者横跨两个段,所以从中间向两边搜索最大连续数组和Sum1,如此解决了一个基本问题,并且递归的将小问题解决,获取总的问题的解。$O(NLogN)$

  4. 线段树做法,同样也是分治的思想,但是考虑的更多。maxarr(i, j)分解为maxarr(i, mid)maxarr(mid + 1, j)。基本问题是arr(i, j)中的sumlsumr, sumisumm,分别代表从左边开始的子数组的和,从右边开始的子数组的和,在中间扩展的子数组的和,和整个数组的和。而我们要大问题的sumi就是所要求的值,巧妙的地方在于问题的分解,sumi可以就是子数组的sumi和左子段的sumr与右子段的suml之和最大值。其他同理。

  5. DP做法,以dp[i]arr[i]为结尾的和最大的连续子数组的和。状态更新方程为
    $$
    dp[i] = max(dp[i - 1] + arr[i], arr[i])
    $$

这很有趣,实际上就是舍弃掉可能为负数的dp[i - 1], 另外在舍弃时也可以记录下数组起点。更进一步的观察,空间可以优化到O(1)

二维情况下,虽然非常相似,但是解法一时想不到直接扩展到二维。但是问题可以化解为一维。

在确定了矩阵行数据,或者首先遍历矩阵的上下界后,顺道求出该矩阵的在各各列的和。之后便可以用一维的做法求出连续列的最大和。

复杂$O(N^3)$。

Read more

312. Burst Balloons

312. Burst Balloons

思路:

Hard题做了才有收获啊!lc上题库里几道经典的具有锻炼思维和思考能力的题。

  1. 拿到手,首先映入脑海里明显应该是贪心或者分治算法:仔细思考一下,贪心发现没有依据,也没有例子;分治算法把考虑把求取问题dp(l, r)——开区间的(l,r)一组气球全部戳爆以后,可以获取最大金币数量。如果第一选取k个气球戳爆,则有子问题(l,k)(k,r),但是可以发现两个子问题是相互依赖的。也就是说一个问题解的选择会影响另一个问题的解的选择。所以这个思路也不行。

  2. Amazing的是,我们可以反过来考虑问题!我们把整个过程逆序,把戳爆存在的气球,变成从一个气球都不存在,添加一个个不存在的气球。dp(l, r)问题就是在寻找,把(l, r)中的所有位置填满气球,可以获得最大金币数量。思考一下如何分解为子问题:
    $$
    dp(l, r) = max_{i = l + 1}^{r - 1}[dp(l , i) + dp(i, r) + nums[i] * nums[l] * nums[r]]
    $$
    具体计算可以用记忆化搜索和DP计算。

看了下大神的解法,居然还有用启发式搜索的!太顶了!

Read more

124. Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum

思路:

这题有意思在DP。但算不上hard。

树上的最大路径之和可以转化为一个节点上的左右子树连起来的路径,而左右路径的最大长度分别可以通过左右子树的路径的一部分求得。考虑到子树路径之和小于0的情况,有当前节点和左右子树路径的最大长度为:DP[i] = max(max(DP[i * 2],0), max(DP[i * 2 + 1],0) + val 。同时可以求出,当前节点最长路径,pathsum = max(DP[i * 2],0) + max(DP[i * 2 + 1],0) + val

Read more

213. House Robber II

213. House Robber II

思路:

首和尾的数字元素不能同时选择的。那么直接把列表拆分成两个$[0,…., n - 2]$和$[1,…..,n-1]$,分开DP就行了。

使用$dp[i]$表示数组在元素$i$上所能获得的最大金钱。

当然也可进行动作拆分。

Read more

309. Best Time to Buy and Sell Stock with Cooldown

309. Best Time to Buy and Sell Stock with Cooldown

思路:

无限购买,每个prices都可以设置为一个购买点。把状态按照已经购买状态$f[i][0]$、处于冷冻状态的刚卖出$f[i][1]$和不处于冷冻期的卖出状态$f[i][2]$,分成三个部分,可以写出dp转移方程:
$$
\begin{split}
f[i][0] &= max(f[i - 1][0], f[i - 1][2] - prices[i]) \\
f[i][1] &= f[i - 1][0] + prices[i]\\
f[i][2] &= max(f[i - 1][1], f[i - 1][2]) \
\end{split}
$$
初始化$f[0][0]= -prices[0]$,最后取结果$max(f[n-1])[1], f[n-1][2])$。

DP状态方程巧妙在把一个状态拆分成不同的并行状态,同时在不同状态可以相互转移,自然的添加了一次购买,一次卖出,一次等待的限制。

Read more