# # Leetcode 第207场周赛题解

## # Problem A - 重新排列单词间的空格 (opens new window)

class Solution {
public:
string reorderSpaces(string text) {
vector<string> words;
int spaces = 0;
string curr;
for (char c : text) {
if (c == ' ') {
if (!curr.empty())
words.emplace_back(curr);
spaces++;
curr.clear();
} else
curr.push_back(c);
}
if (!curr.empty())
words.emplace_back(curr);
int n = words.size();
string ans;
if (n == 1) {
ans = words[0];
for (int i = 0; i < spaces; ++i)
ans.push_back(' ');
} else {
int c = spaces / (n - 1);
for (int i = 0; i < n; ++i) {
ans += words[i];
if (i < n - 1)
for (int j = 0; j < c; ++j)
ans.push_back(' ');
}
for (int j = 0; j < spaces % (n - 1); ++j)
ans.push_back(' ');
}
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

## # Problem B - 拆分字符串使唯一子字符串的数目最大 (opens new window)

class Solution {
public:
int maxUniqueSplit(string s) {
int n = s.size();
int ans = 1;
for (int i = 0; i < (1 << n); ++i) {
vector<bool> v(n);
for (int j = 0; j < n; ++j)
v[j] = (i & (1 << j)) > 0;
int hi = 0;
for (int j = 1; j < n; ++j)
if (v[j] != v[j - 1])
hi++;
hi++;
if (hi <= ans)
continue;
int l = 0;
unordered_set<string> st;
bool ok = true;
for (int j = 1; j < n; ++j) {
if (v[j] != v[j - 1]) {
string sub = s.substr(l, j - 1 - l + 1);
if (st.count(sub)) {
ok = false;
break;
}
st.insert(sub);
l = j;
}
}
if (!ok)
continue;
string sub = s.substr(l, n - l);
if (st.count(sub))
ok = false;
st.insert(sub);
if (ok)
ans = max(ans, (int)st.size());
}
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

class Solution {
int n, ans = 0;
unordered_set<string> st;
void dfs(string &s, int pos) {
if (pos == n)
ans = max(ans, (int)st.size());
int rest = n - pos;
if (st.size() + rest <= ans)
return;
for (int i = pos; i < n; ++i) {
string sub = s.substr(pos, i - pos + 1);
if (st.count(sub))
continue;
st.insert(sub);
dfs(s, i + 1);
st.erase(sub);
}
}
public:
int maxUniqueSplit(string s) {
n = s.size();
dfs(s, 0);
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

## # Problem C - 矩阵的最大非负积 (opens new window)

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1ll << 60;

class Solution {
public:
int maxProductPath(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<ll>> f(n, vector<ll>(m, INF)), g(n, vector<ll>(m, INF));
if (grid[0][0] >= 0)
f[0][0] = grid[0][0];
if (grid[0][0] <= 0)
g[0][0] = grid[0][0];
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
if (i > 0) {
if (f[i - 1][j] != INF) {
if (grid[i][j] >= 0) {
if (f[i][j] == INF)
f[i][j] = f[i - 1][j] * grid[i][j];
else
f[i][j] = max(f[i][j], f[i - 1][j] * grid[i][j]);
}
if (grid[i][j] <= 0)
g[i][j] = min(g[i][j], f[i - 1][j] * grid[i][j]);
}
if (g[i - 1][j] != INF) {
if (grid[i][j] <= 0) {
if (f[i][j] == INF)
f[i][j] = g[i - 1][j] * grid[i][j];
else
f[i][j] = max(f[i][j], g[i - 1][j] * grid[i][j]);
}
if (grid[i][j] >= 0)
g[i][j] = min(g[i][j], g[i - 1][j] * grid[i][j]);
}
}
if (j > 0) {
if (f[i][j - 1] != INF) {
if (grid[i][j] >= 0) {
if (f[i][j] == INF)
f[i][j] = f[i][j - 1] * grid[i][j];
else
f[i][j] = max(f[i][j], f[i][j - 1] * grid[i][j]);
}
if (grid[i][j] <= 0)
g[i][j] = min(g[i][j], f[i][j - 1] * grid[i][j]);
}
if (g[i][j - 1] != INF) {
if (grid[i][j] <= 0) {
if (f[i][j] == INF)
f[i][j] = g[i][j - 1] * grid[i][j];
else
f[i][j] = max(f[i][j], g[i][j - 1] * grid[i][j]);
}
if (grid[i][j] >= 0)
g[i][j] = min(g[i][j], g[i][j - 1] * grid[i][j]);
}
}
}
if (f[n - 1][m - 1] == INF)
return -1;
return f[n - 1][m - 1] % MOD;
}
};
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
59
60
61
62
63
64
65

## # Problem D - 连通两组点的最小成本 (opens new window)

const int INF = 0x3f3f3f3f;

class Solution {
public:
int connectTwoGroups(vector<vector<int>>& cost) {
int n = cost.size(), m = cost[0].size();
vector<int> dp(1 << m, INF);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
vector<int> ndp(1 << m, INF);
for (int last = 0; last < (1 << m); ++last) {
if (dp[last] == INF)
continue;
for (int j = 0; j < m; ++j) {
int nxt = last | (1 << j);
ndp[nxt] = min(ndp[nxt], dp[last] + cost[i][j]);
}
int v = (1 << m) - 1 - last;
if (v > 0) {
for (int j = v; j > 0; j = v & (j - 1)) {
int c = 0;
for (int k = 0; k < m; ++k)
if (j & (1 << k))
c += cost[i][k];
int nxt = last | j;
ndp[nxt] = min(ndp[nxt], dp[last] + c);
}
}
}
dp = move(ndp);
}
return dp.back();
}
};
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