今天作业巨 TM 多，刚刚写完三科作业，明天还有两科。来刷几道题。
DP
最大对角矩阵
今天继续研究最大子对角矩阵问题。
我们可以定义 $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)$ 依赖于：
- $f(i-1,j-1)$
- $i,j$ 左边 0 的数量
- $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++ 的条件。