[周赛传送门]https://leetcode-cn.com/contest/weekly-contest-260/
2016. 增量元素之间的最大差值
思路：暴力枚举
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
先说最直白的方法，枚举所有下标对
(
i
,
j
)
(i,j)
(i,j)，判断
n
u
m
s
i
nums_i
numsi? 与
n
u
m
s
j
nums_j
numsj? 的大小关系并更新答案。
class Solution {
public:
int maximumDifference(vector<int>& nums) {
int anw = -1;
for (int i = 0; i < nums.size(); i++) {
for (int j = i+1; j < nums.size(); j++) {
if (nums[i] < nums[j]) {
anw = max(anw, nums[j] - nums[i]);
}
}
}
return anw;
}
};
思路：预处理最小值
时间复杂度：
O
(
n
)
O(n)
O(n)
设有长度为
n
n
n 的一维数组
o
p
t
opt
opt，
o
p
t
i
opt_i
opti? 表示在前
i
i
i 个元素中的最小值。那么对于每个
n
u
m
s
i
，
i
≥
1
nums_i，i \ge 1
numsi?，i≥1，所能贡献的最大差值为 :
- 当
o
p
t
i
?
1
≤
n
u
m
s
i
opt_{i-1} \le nums_i
opti?1?≤numsi? 时，为
n
u
m
s
i
?
o
p
t
i
?
1
nums_i - opt_{i-1}
numsi??opti?1?
- 反之为 -1。
整体实现上，可以先
O
(
n
)
O(n)
O(n) 的预处理
o
p
t
opt
opt。然后再
O
(
n
)
O(n)
O(n) 的求出每个
n
u
m
s
i
nums_i
numsi? 的最大差值，其中最大的即为答案。
class Solution {
public:
int maximumDifference(vector<int>& nums) {
int anw = -1;
for (int i = 1, opt = nums[0]; i < nums.size(); i++) {
if(opt < nums[i]) {
anw = max(anw, nums[i] - opt);
}
opt = min(opt, nums[i]);
}
return anw;
}
};
2017. 网格游戏
思路：贪心
时间复杂度：
O
(
n
)
O(n)
O(n)
不难发现，先手必定走过
n
+
1
n+1
n+1 个格子。先手有
n
n
n 种走法，选择一个 位置
p
p
p，
p
∈
[
0
,
n
)
p\in[0,n)
p∈[0,n)，先手会走过第一排的
[
0
，
p
]
[0，p]
[0，p] ，以及第二排的
[
p
,
n
)
[p, n)
[p,n)。
后手有以下两种方案：
-
(
0
,
0
)
→
(
0
,
n
?
1
)
→
(
1
,
n
?
1
)
(0,0)→(0,n-1)→(1,n-1)
(0,0)→(0,n?1)→(1,n?1)，得分为第一排的
(
p
,
n
)
(p,n)
(p,n) 格子的和。
-
(
0
,
0
)
→
(
1
,
n
?
1
)
→
(
1
,
n
?
1
)
(0,0)→(1,n-1)→(1,n-1)
(0,0)→(1,n?1)→(1,n?1)，得分为第二排的
[
0
,
p
)
[0,p)
[0,p) 格子的和。
不难得出先手的策略，选择一个
p
p
p，使得第一排
(
p
,
n
)
(p,n)
(p,n) 和 第二排
[
0
,
p
)
[0,p)
[0,p) 中的最大值最小。
class Solution {
public:
long long gridGame(vector<vector<int>>& grid) {
int64_t sum[2] = {0};
int n = grid[0].size();
for (int i = 0; i < n; i++) {
sum[0] += grid[0][i];
sum[1] += grid[1][i];
}
int64_t pre[100000] = {grid[0][0]};
for (int i = 1; i < n; i++) {
pre[i] = pre[i-1] + grid[0][i];
}
int64_t anw = sum[0] + sum[1];
int suf = 0;
for (int i = n-1; i >= 0; i--) {
suf += grid[1][i];
int opt = max(sum[0] - pre[i], sum[1] - suf);
anw = min(anw, opt);
}
return anw;
}
};
2018. 判断单词是否能放入填字游戏内
思路 暴力枚举
时间复杂度：
O
(
(
n
m
)
3
/
2
)
O((nm)^{3/2})
O((nm)3/2)
枚举坐标
(
i
,
j
)
(i,j)
(i,j)，检查四个方向：
-
(
i
,
j
)
→
(
i
+
k
?
1
,
j
)
(i,j) → (i+k-1,j)
(i,j)→(i+k?1,j)
-
(
i
,
j
)
→
(
i
?
k
+
1
,
j
)
(i,j) → (i-k+1,j)
(i,j)→(i?k+1,j)
-
(
i
,
j
)
→
(
i
,
j
+
k
?
1
)
(i,j) → (i,j+k-1)
(i,j)→(i,j+k?1)
-
(
i
,
j
)
→
(
i
,
j
?
k
+
1
)
(i,j) → (i,j-k+1)
(i,j)→(i,j?k+1)
是否存在一个方向能放下
w
o
r
d
s
words
words，其中
k
k
k 为
w
o
r
d
s
words
words 的长度。
另外，还需检查对应的边界是否符合要求。
整体上的时间复杂度为
O
(
n
m
k
)
O(nmk)
O(nmk)，考虑到
k
k
k的取值不超过
(
n
,
m
)
\sqrt{(n,m)}
(n,m)
? ，因此时间复杂度可简化为
O
(
(
n
m
)
3
/
2
)
O((nm)^{3/2})
O((nm)3/2)。
class Solution {
public:
bool check(int x, int y, const vector<vector<char>> &board, int n, int m) {
if (0 <= x && x < n && 0 <= y && y < m && board[x][y] == '#') {
return true;
}
if (-1 == x || x == n || -1 == y || y == m) {
return true;
}
return false;
}
bool placeWordInCrossword(vector<vector<char>>& board, string word) {
int n = board.size();
int m = board[0].size();
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0 , 0, 1,-1};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int d = 0; d < 4; d++) {
int sx = i - dx[d];
int sy = j - dy[d];
if (!check(sx, sy, board, n, m)) {
continue;
}
int ex = i + (word.size())*dx[d];
int ey = j + (word.size())*dy[d];
if (!check(ex, ey, board, n, m)) {
continue;
}
bool flag = true;
for (int k = 0, x = i, y = j; k < word.size() && flag; k++, x += dx[d], y += dy[d]) {
if (!(board[x][y] == ' ' || board[x][y] == word[k])) {
flag = false;
}
}
if (flag) { return flag; }
}
}
}
return false;
}
};
2019. 解出数学表达式的学生分数
思路：动态规划
时间复杂度：
O
(
n
2
?
m
2
+
k
)
O(n^2*m^2 + k)
O(n2?m2+k)。
n
n
n 为 字符串的长度。
m
m
m 为取值上限，本题为 1000。
k
k
k 为提交的答案数。
计算正确值的思路比较简单，可以借助栈来实现先乘后加。
int getCorrect(const std::string &s) {
stack<int> st;
st.push(s[0]-'0');
for (int i = 1; i < s.size(); i += 2) {
if (s[i] == '*') {
st.top() *= s[i+1]-'0';
} else {
st.push(s[i+1]-'0');
}
}
int sum = 0;
while (!st.empty()) {
sum += st.top();
st.pop();
}
return sum;
}
乱序执行的结果，可用动态规划求解。设有二维数组
d
p
dp
dp。
d
p
l
,
r
dp_{l,r}
dpl,r? 是一个集合，表示表达式
s
l
,
r
s_{l,r}
sl,r? 乱序执行结果的集合。
通过枚举运算符将表达式一分为二，比如有
s
l
,
r
s_{l,r}
sl,r?，以及运算符
s
p
s_p
sp?, 则将表达式分为
s
l
,
p
?
1
s_{l,p-1}
sl,p?1? 以及
s
p
+
1
,
r
s_{p+1,r}
sp+1,r?。
不难想到状态转移方程：
- 当
l
=
r
l = r
l=r 时：
d
p
l
,
r
=
s
l
dp_{l,r} = s_l
dpl,r?=sl? - 当
l
≠
r
l\ne r
l?=r时：
d
p
l
,
r
=
x
?
y
,
x
∈
d
p
l
,
p
?
1
,
y
∈
d
p
p
+
1
,
r
dp_{l,r} = x · y, x\in dp_{l,p-1}, y\in dp_{p+1,r}
dpl,r?=x?y,x∈dpl,p?1?,y∈dpp+1,r?
因此，可在
O
(
n
2
?
m
2
)
O(n^2*m^2)
O(n2?m2) 时间复杂度内求出所有的
d
p
l
,
r
dp_{l,r}
dpl,r?。
n
n
n 为 字符串的长度。
m
m
m 为取值上限，本题为 1000。
最后，枚举提交的答案，求解总分数即可。
class Solution {
public:
int getCorrect(const std::string &s) {
stack<int> st;
st.push(s[0]-'0');
for (int i = 1; i < s.size(); i += 2) {
if (s[i] == '*') {
st.top() *= s[i+1]-'0';
} else {
st.push(s[i+1]-'0');
}
}
int sum = 0;
while (!st.empty()) {
sum += st.top();
st.pop();
}
return sum;
}
unordered_set<int> dp[32][32];
void getPossible(const std::string &s, int l, int r) {
if (dp[l][r].size()) {
return;
}
if (l == r) {
dp[l][r].insert(s[l]-'0');
return;
}
for (int i = l+1; i < r; i += 2) {
getPossible(s, l, i-1);
getPossible(s, i+1, r);
for (auto vl : dp[l][i-1]) {
for (auto vr : dp[i+1][r]) {
auto v = ((s[i] == '+') ? (vl + vr) : (vl * vr));
if (v <= 1000) {
dp[l][r].insert(v);
}
}
}
}
}
int scoreOfStudents(string s, vector<int>& answers) {
int correct = getCorrect(s);
int n = s.size()-1;
getPossible(s, 0, n);
int anw = 0;
for (auto a : answers) {
if (a == correct) {
anw +=5;
} else if(dp[0][n].count(a) == 1) {
anw += 2;
}
}
return anw;
}
};
|