第一周刷题经验总结028

[Jerrydreamaker]

首先抱歉，好像有点晚了，向明天没精神工作的自己，公司和各位小伙伴。本周刷题重点突破了递归和 DP 两个点。

分别是 174 号的 dungeonGame 问题。哈哈哈，这题看这矩阵造型，求最优，必然是 DP 问题。接下来的问题是如何定义状态转移方程，哈哈，也很简单，骑士在矩阵的的任何一点，可以先下或向右移动，所以 i+1 ，或 j+1，然后选取两个的最小值。即 f(i,j)=max(1,min(f(i,j+1)-nums[i][j+1],f(i+1,j)-nums[i+1][j]))。如果骑士在边缘，则只能向下或向右。在调试过程中，记录骑士最开始并非是在 （0，0）可以想象成骑士在矩阵外，调到 （0，0）则减去 （0，0）处的矩阵值，其他同理。

然后就是 236 号的 lowest common ancestor 问题。说实话，问题是递归过程对递归函数的定义容易犯糊涂。
定义 find 函数：功能如下，在当前树下，找到左右子树找到的第一个 p 或者 q，如果没有则返回 null。如果左右都不为 null。则当前节点为最近父节点，退出递归，并且使用全局变量记录。如果一边为 null，则最近在另外一边。

其他问题：42 rain water 问题除了老师课堂上的解法。我自己构思了方法2：即找到数组中的最大值和第二大值，计算出其之间的雨水面积，等于 最低*宽度-中间元素高度之和。然后对左右数组进行递归。哈哈，下周一定实现。此处 flag。

接下啦是 同类型的条形图面积问题，想通了暴力解和如果不是最后以为，并且后面一位比其高，则放弃计算当前值。和使用minIndex 记录当前值往前的数组中的最小值，minIndex 前的数字使用 minIndex 一次计算。

额，之所以现在交作业，主要卡在一道自以为很简单的问题上。将数组向后移动 k 位。目前想法无法解决 k 大于数组长度问题。待突破。

其他软柿子就不提了哈。