# # Leetcode 第260场周赛题解

## # Problem A - 增量元素之间的最大差值 (opens new window)

### # 方法一：前缀和

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(1)$

class Solution {
public:
int maximumDifference(vector<int>& nums) {
int ans = -1, lo = INT_MAX;
for (int num : nums) {
if (num > lo)
ans = max(ans, num - lo);
lo = min(lo, num);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12

## # Problem B - 网格游戏 (opens new window)

### # 方法一：前缀和

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(1)$

class Solution {
public:
long long gridGame(vector<vector<int>>& grid) {
int n = grid[0].size();
long long left = 0, right = 0;
for (int i = 1; i < n; ++i)
right += grid[0][i];
long long ans = right;
for (int i = 1; i < n; ++i) {
left += grid[1][i - 1], right -= grid[0][i];
ans = min(ans, max(left, right));
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

## # Problem C - 判断单词是否能放入填字游戏内 (opens new window)

### # 方法一：动态规划预处理+枚举+旋转

• 左侧为边界或障碍
• 从它开始连续$K$个格子非障碍，再下一个格子为边界或障碍

• 时间复杂度$\mathcal{O}(NM)$
• 空间复杂度$\mathcal{O}(NM)$

bool check(vector<vector<char>> &board, string word) {
int n = board.size(), m = board[0].size(), k = word.size();

for (int i = 0; i < n; ++i) {
vector<int> acc(m);
for (int j = m - 1; j >= 0; --j) {
if (board[i][j] == '#')
acc[j] = 0;
else
acc[j] = (j == m - 1) ? 1 : acc[j + 1] + 1;
}

for (int j = 0; j < m; ++j) {
if (acc[j] == k && (j == 0 || board[i][j - 1] == '#')) {
bool good = true;
for (int p = 0; p < k; ++p) {
if (board[i][j + p] != word[p] && board[i][j + p] != ' ') {
good = false;
break;
}
}
if (good)
return true;
}
}
}

return false;
}

class Solution {
public:
bool placeWordInCrossword(vector<vector<char>>& board, string word) {
int n = board.size(), m = board[0].size(), k = word.size();

if (check(board, word))
return true;

vector<vector<char>> b1(board);
for (int i = 0; i < n; ++i)
reverse(b1[i].begin(), b1[i].end());

if (check(b1, word))
return true;

vector<vector<char>> b2(m);
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
b2[i].emplace_back(board[j][i]);

if (check(b2, word))
return true;

vector<vector<char>> b3(b2);
for (int i = 0; i < m; ++i)
reverse(b3[i].begin(), b3[i].end());

return check(b3, word);
}
};

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

## # Problem D - 解出数学表达式的学生分数 (opens new window)

### # 方法一：表达式求值+动态规划

1. 求出表达式的正确值
2. 求出表达式所有可能的值
3. 计算学生的得分

using ll = long long;

unordered_map<char, int> order = {{'#', -1}, {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'$', 0}, {'(', 0}}; // Leetcode 224: Basic Calculator class Calculator { string trim(string s) { string t; for (char c : s) if (c != ' ') t.push_back(c); return t; } ll calc(ll a, ll b, char c) { switch(c) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; default: return a; } } public: int calculate(string s) { s = trim(s); stack<ll> val; stack<char> op; op.push('#'); bool is_num = false, is_negative = false; ll num = 0; s += '$';
auto work = [&](){
ll b = val.top();
val.pop();
ll a = val.top();
val.pop();
val.push(calc(a, b, op.top()));
op.pop();
};
for (int i = 0; i < s.size(); ++i) {
char c = s[i];
ll delta = c - '0';
if (delta >= 0 && delta <= 9) {
num = num * 10 + delta;
is_num = true;
}
else {
if (is_num) {
val.push(is_negative ? -num : num);
is_num = false;
is_negative = false;
} else {
if (c == '-' && (i == 0 || s[i - 1] != ')')) {
is_negative = true;
continue;
}
}

// Special case: "-(...)" => "-1*(...)"
if (is_negative) {
val.push(-1);
while (order[op.top()] >= order['*'])
work();
op.push('*');
is_negative = false;
}

num = 0;
if (c == ')')
while (op.top() != '(')
work();
else if (c != '(')
while (order[op.top()] >= order[c])
work();
if (c == ')')
op.pop();
else
op.push(c);
}
}
return val.top();
}
};

class Solution {
public:
int scoreOfStudents(string s, vector<int>& answers) {
vector<int> nums;
vector<char> ops;
for (char ch : s) {
if (ch == '+' || ch == '*')
ops.emplace_back(ch);
else
nums.emplace_back(ch - '0');
}

int n = nums.size();

Calculator calculator;
ll correct = calculator.calculate(s);

vector<vector<unordered_set<int>>> dp(n, vector<unordered_set<int>>(n));
for (int i = 0; i < n; ++i)
dp[i][i].emplace(nums[i]);
for (int len = 2; len <= n; ++len) {
for (int i = 0; i + len - 1 < n; ++i) {
int j = i + len - 1;
for (int k = i; k < j; ++k) {
for (int x : dp[i][k])
for (int y : dp[k + 1][j]) {
if (ops[k] == '+' && x + y <= 1000)
dp[i][j].emplace(x + y);
else if (ops[k] == '*' && x * y <= 1000)
dp[i][j].emplace(x * y);
}
}
}
}

int ans = 0;
ans += 5;
ans += 2;
}

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138