今天作业巨 TM 多,刚刚写完三科作业,明天还有两科。来刷几道题。

DP

最大对角矩阵

今天继续研究最大子对角矩阵问题。

image-20211120223341924

我们可以定义 $f (i,j)$ 表示 $[i,j]$ 处最大对角矩阵的大小。则当 $i=5,j=3$ 的情况,可以知道 $f (i-1,j-1)$ 是 3,而还需要往上、往左搜索第一个 1 的位置。上面搜索到正上方 $i=3,j=3$ 处有一个 1,距离为 2,左边没有搜索到 1,距离取 3-(-1)=4,因此对于 $f (i,j)|_{i=5,j=3} = \min (3 + 1,2, 4) = 2$

即 $f (i,j)$ 依赖于:

  1. $f(i-1,j-1)$
  2. $i,j$ 左边 0 的数量
  3. $i,j$ 上边 0 的数量

优化:可以 dp 改成结构体,里面同时记录 1,2,3.

https://youtu.be/tW0zwL2ar7s?t=4254

221. 最大正方形

刷题

最长和谐子数组

思路是 DP 或者 滑动窗口,不过 DP 的话可能时间复杂度太高。

记录窗口内的最大最小值。

3 4 9 1 2 1 2 1 2 9 5 3  ok len maxlen
[3] 4 9 1 2 1 2 1 2 9 5 3 v	1	1
[3 4] 9 1 2 1 2 1 2 9 5 3 v	2	2
[3 4 9] 1 2 1 2 1 2 9 5 3 x	3	3
3 [4 9] 1 2 1 2 1 2 9 5 3 x	2	3
3 4 [9] 1 2 1 2 1 2 9 5 3 x	1	3
3 4 9[] 1 2 1 2 1 2 9 5 3 x	0	3
3 4 9 [1] 2 1 2 1 2 9 5 3 v	1	3
3 4 9 [1 2] 1 2 1 2 9 5 3 v	2	3
3 4 9 [1 2 1] 2 1 2 9 5 3 v	3	3
3 4 9 [1 2 1 2] 1 2 9 5 3 v	4	4
3 4 9 [1 2 1 2 1] 2 9 5 3 v	5	5
3 4 9 [1 2 1 2 1 2] 9 5 3 v	6	6
3 4 9 [1 2 1 2 1 2 9] 5 3 x	7	6
3 4 9 1 [2 1 2 1 2 9] 5 3 v	6	6
3 4 9 1 2 [1 2 1 2 9] 5 3 v	5	6
3 4 9 1 2 1 [2 1 2 9] 5 3 v	4	6
3 4 9 1 2 1 2 [1 2 9] 5 3 v	3	6
3 4 9 1 2 1 2 1 [2 9] 5 3 v	2	6
3 4 9 1 2 1 2 1 2 [9] 5 3 v	1	6
3 4 9 1 2 1 2 1 2 9[] 5 3 v	0	6
3 4 9 1 2 1 2 1 2 9 [5] 3 v	1	6
3 4 9 1 2 1 2 1 2 9 5[] 3 v	0	6
3 4 9 1 2 1 2 1 2 9 5 [3] v	1	6
ret = 7

发现左边回退太慢,还可优化:

3 4 9 1 2 1 2 1 2 9 5 3  ok len maxlen
[3] 4 9 1 2 1 2 1 2 9 5 3 v	1	1
[3 4] 9 1 2 1 2 1 2 9 5 3 v	2	2
[3 4 9] 1 2 1 2 1 2 9 5 3 x	3	3
3 4 [9] 1 2 1 2 1 2 9 5 3 v	1	3 // 一旦出界,就重置 l 到 r-1
3 4 [9 1] 2 1 2 1 2 9 5 3 x	0	3
3 4 9 [1] 2 1 2 1 2 9 5 3 v	1	3
3 4 9 [1 2] 1 2 1 2 9 5 3 v	2	3
3 4 9 [1 2 1] 2 1 2 9 5 3 v	3	3
3 4 9 [1 2 1 2] 1 2 9 5 3 v	4	4
3 4 9 [1 2 1 2 1] 2 9 5 3 v	5	5
3 4 9 [1 2 1 2 1 2] 9 5 3 v	6	6
3 4 9 [1 2 1 2 1 2 9] 5 3 x	6	6
3 4 9 1 2 1 2 1 2 [9] 5 3 v	1	6 // 一旦出界,就重置 l 到 r-1
3 4 9 1 2 1 2 1 2 [9 5] 3 x	1	6
3 4 9 1 2 1 2 1 2 9 [5] 3 v	0	6
3 4 9 1 2 1 2 1 2 9 5 [3] v	1	6
ret = 7

其中 ok = v [i_max]-v [i_min]<=1 len=i_max-i_min+1

#include <debug.h>

class Solution {
public:
  int findLHS(vector<int> &v) {
    int n = v.size();
    bool ok = true;
    int maxlen = 0, l = 0, r = 0;
    int i_min = 0, i_max = 0;
    while (l <= r && r < n) {
      ok = v[i_max] - v[i_min] == 1;
      if (ok) {
        maxlen = max(maxlen, r - l + 1);
        printf("l = %d\n", l);
        printf("r = %d\n", r);
        print_vec_part(v, l, r + 1);
        r++;
        if (r < n) {
          i_min = v[r] < v[i_min] ? r : i_min;
          i_max = v[r] > v[i_max] ? r : i_max;
        }
      } else {
        l = r;
        i_min = l;
        i_max = l;
      }
    }
    return maxlen;
  }
};
int main(int argc, char const *argv[]) {
  Solution s;
  std::vector<int> v = {1, 3, 2, 2, 5, 2, 3, 7};
  cout << s.findLHS(v) << endl;
  return 0;
}

594. 最长和谐子序列

子序列则不用连续。我们可以统计每一个数后面有多少个与它差值 1 的。

class Solution {
public:
  int find(std::vector<int> &v, int from, int offset) {
    int maxv = v[from];
    int minv = v[from];
    int len = 0;
    for (int i = from; i < v.size(); i++) {
      if (v[from] == v[i] || v[from] == v[i] + offset) {
        len++;
        maxv = max(maxv, v[i]);
        minv = min(minv, v[i]);
      }
    }
    if (maxv - minv != 1) {
      return 0;
    }
    return len;
  }
  int findLHS(vector<int> &v) {
    int maxlen = 0;
    for (int i = 0; i < v.size(); i++) {
      maxlen = max (maxlen, find (v, i, 1)); // 统计 x, x+1 子序列
      maxlen = max (maxlen, find (v, i, -1)); // 统计 x, x-1 子序列
    }
    return maxlen;
  }
};

结果:超时。

改进自然是想办法记忆状态,避免重复运算。

比如对于

{1, 3, 2, 2, 5, 2, 3, 7};
    |
    此时我们想知道后面有多少个等于 3 或 4 的,多少个等于 3 或 2 的

但我发现这样很难得到递推方程。偷瞄答案了,原来要排个序。然后就能很容易得到答案。

{1, 3, 2, 2, 5, 2, 3, 7};
-->
{1, 2, 2, 2, 3, 3, 5, 7}
    [           ]
class Solution {
public:
  int findLHS(vector<int> &v) {
    sort(v.begin(), v.end());
    int l = 0, r = 1, maxlen = 0, n = v.size();
    while (l < r && r < n) {
      while (l < r && v[r] - v[l] > 1) {
        l++;
      }
      if (v[r] - v[l] == 1) {
        maxlen = max(maxlen, r - l + 1);
      }
      r++;
    }
    return maxlen;
  }
};

需要注意的是 l++r++ 的条件。