# # Leetcode 第196场周赛题解

## # Problem A - 判断能否形成等差数列 (opens new window)

class Solution {
public:
bool canMakeArithmeticProgression(vector<int>& arr) {
sort(arr.begin(), arr.end());
int d = arr[1] - arr[0];
for (int i = 1; i + 1 < arr.size(); ++i)
if (arr[i + 1] - arr[i] != d)
return false;
return true;
}
};

1
2
3
4
5
6
7
8
9
10
11

## # Problem B - 所有蚂蚁掉下来前的最后一刻 (opens new window)

class Solution:
def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
return max(0 if len(left) == 0 else max(left), 0 if len(right) == 0 else n - min(right))

1
2
3

## # Problem C - 统计全 1 子矩形 (opens new window)

$dp[i][j][k]$表示右下角为$(i,j)$，高度为$k$的矩形的数目。显然，$dp[i][j][k]$可以由$dp[i][j-1][k]$递推得到。

int dp[155][155][155];

class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
int ans = 0;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (mat[i - 1][j - 1] == 0)
continue;
for (int k = 1; k <= i; ++k) {
if (mat[i - k][j - 1] == 0)
break;
dp[i][j][k] = 1 + dp[i][j - 1][k];
ans += dp[i][j][k];
}
}
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

$f[i][j]$表示以$(i,j)$为结尾的最长连续1串的长度，显然可以通过递推在$O(nm)$时间内求出。

class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
vector<vector<int>> f(n + 2, vector<int>(m + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (mat[i - 1][j - 1] == 1)
f[i][j] = f[i][j - 1] + 1;
}
int ans = 0;
for (int j = 1; j <= m; ++j) {
stack<pair<int, int>> st;
for (int i = 1; i <= n + 1; ++i) {
int pos = i;
while (!st.empty() && st.top().first > f[i][j]) {
auto [h, left] = st.top();
st.pop();
int last = st.empty() ? 0 : st.top().first;
int h0 = max(last, f[i][j]);
int len = i - left;
ans += (h - h0) * len * (len + 1) / 2;
pos = left;
}
if (st.empty() || st.top().first < f[i][j])
st.push({f[i][j], pos});
}
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

## # Problem D - 最多 K 次交换相邻数位后得到的最小整数 (opens new window)

class Solution {
int n;
vector<int> a;
int lowbit(int x) {
return x & (-x);
}
void update(int idx, int delta) {
for (; idx <= n; idx += lowbit(idx))
a[idx] += delta;
}
int query(int idx) {
int ans = 0;
for (; idx > 0; idx -= lowbit(idx))
ans += a[idx];
return ans;
}
public:
string minInteger(string num, int k) {
vector<set<int>> s(10);
n = num.size();
string ans;
a = vector<int>(n + 1);
for (int i = 0; i < n; ++i)
s[num[i] - '0'].insert(i);
int idx = 0, left = 0;
vector<bool> vis(n);
while (idx < n) {
int curr = num[idx] - '0';
int m = idx;
for (int j = 0; j < curr; ++j) {
if (s[j].empty())
continue;
int p = *s[j].begin();
int d = (p + query(p + 1)) - (idx + query(idx + 1));
if (d > k)
continue;
else {
m = p;
k -= d;
break;
}
}
if (m != idx) {
vis[m] = true;
left++;
update(idx + 1, 1);
update(m + 1, -1);
} else {
vis[idx] = true;
while (idx < n && vis[idx])
idx++;
}
ans.push_back(num[m]);
s[num[m] - '0'].erase(m);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58