# # Leetcode 第34场双周赛题解

## # Problem A - 矩阵对角线元素的和 (opens new window)

class Solution:
def diagonalSum(self, mat: List[List[int]]) -> int:
ans = 0
n = len(mat)
for i in range(n):
ans += mat[i][i]
if i != n - i - 1:
ans += mat[i][n - i - 1]
return ans

1
2
3
4
5
6
7
8
9

## # Problem B - 分割字符串的方案数 (opens new window)

typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
int numWays(string s) {
vector<int> a;
int n = s.size();
for (int i = 0; i < n; ++i)
if (s[i] == '1')
a.emplace_back(i);
int m = a.size();
if (m % 3 != 0)
return 0;
if (a.empty())
return (ll)(n - 1) * (n - 2) / 2 % MOD;
int t = m / 3;
int d1 = a[t] - a[t - 1], d2 = a[t * 2] - a[t * 2 - 1];
return (ll)d1 * d2 % MOD;
}
};

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

## # Problem C - 删除最短的子数组使剩余数组有序 (opens new window)

class Solution {
public:
int findLengthOfShortestSubarray(vector<int>& arr) {
int n = arr.size();
int l = 0;
while (l + 1 < n && arr[l] <= arr[l + 1])
l++;
if (l == n - 1)
return 0;
vector<int> v = {-1};
v.insert(v.end(), arr.begin(), arr.end());
v.emplace_back(1e9);
int ans = 0, r = n + 1;
for (int i = l + 1; i >= -1; --i) {
while (v[r - 1] <= v[r] && v[r - 1] >= v[i] && r - 1 > i)
r--;
ans = max(ans, i + n + 1 - r);
}
return n - ans;
}
};

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

## # Problem D - 统计所有可行路径 (opens new window)

typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
int n = locations.size();
vector<vector<ll>> dp(n, vector<ll>(fuel + 1, 0));
dp[start][0] = 1;
for (int f = 0; f < fuel; ++f)
for (int i = 0; i < n; ++i) {
if (dp[i][f] == 0)
continue;
for (int j = 0; j < n; ++j) {
if (j == i)
continue;
ll cost = abs(locations[i] - locations[j]);
if (f + cost <= fuel)
dp[j][f + cost] = (dp[j][f + cost] + dp[i][f]) % MOD;
}
}
ll ans = 0;
for (int i = 0; i <= fuel; ++i)
ans = (ans + dp[finish][i]) % MOD;
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