leetcode 第 260 场算法比赛

这次比赛题比较简单,可惜十一调休要上班,我没参加。


零、背景

这次比赛的题比较简单,不多说了,直接看题解吧。

一、增量元素之间的最大差值

题意:给一个数组,一个元素与之后位置的元素有一个差值,求最大差值。

思路:从后到前求最值,然后求差值,更新最优答案即可。

二、网格游戏

题意:给一个 2*N 的方格,两个机器人进行博弈。

机器人只能向左与向下行动。

第一个机器人经过的路径,会把方格的积分设置为0。

第二个机器人会尽量使得自己的积分最大。

问第一个机器人如何走,才能使得第二个机器人的积分最小。

思路:典型的最大值中的最小值。

不管第一个机器人如何走,第二个机器人都会尽量使自己当前的积分最大。

枚举第一个机器人的所有走法,取第二个机器人最差的那个最大积分即可(最大值中的最小值)。

由于方格只有 2 行,当第一个机器人走之后,第二个机器人有两个局部最优策略。

一个是把第一行剩余的积分全部获得,可以通过后缀和O(1)得到。
一个是把第二行剩余的积分全部获得,可以通过前缀和O(1)得到。

所以这道题的方法也就出来了。

1、预处理出第一行的后缀和与第二行的前缀和。

2、枚举第一个机器人的所有策略,求当前策略第二个机器人的最大积分。

3、第二个机器人的所有最大积分中,取最小积分即可。

三、判断单词是否能放入填字游戏内

题意:给一个方格,有三种字符:空白、障碍物、字母。

现在空白的地方可以填充字母,问是否可以填充出一个水平或者垂直的连续字符串,等于目标字符串。

连续字符串定义:两端不能有空白,必须是边界或者障碍物。

思路:由于连续字符串边界不能有空白,那直接暴力枚举即可。

复杂度:O(n^2)

小技巧:字符串可以从上到下、从下到上、从左到右、从右到左,分四种情况。

可以通过翻转目标字符串,从而代替从右到左。

对方格的访问进行封装,从而可以把从下到上转化为从左到右。

char Get(int i, int j, int flag){    if(flag) {        return board[j][i];    } else {        return board[i][j];    }}
if(CheckHorizontally(n, m, 0) || CheckHorizontally(m, n, 1)){ return true;}
reverse(word.begin(), word.end());
if(CheckHorizontally(n, m, 0) || CheckHorizontally(m, n, 1)){ return true;}return false;

四、解出数学表达式的学生分数

题意:给一个包含加法与乘法的字符串公式。

运算符之间可以任意加括号,问可以算出 1000 以内的哪些正整数。

字符串长度最大为 31,字符串内数字只有一位。

思路:由于可以任意加括号,那就需要进行枚举,将字符串分成两部分,然后两部分得到的值集进行合并运算,得到当前字符串的所有值集。

优化:由于题目只需要求 1000 以内的答案,所以大于 1000 的就不需要计算了。

PS:第一次做的时候,我保留了一个大于 1000 的最小数字,写题解的时候,发现不保留依旧可以通过。

优化后复杂度:O(15 * 15 * 1000 * 1000)

unordered_set<ll> dp[32][32];
void Dfs(int l, int r){ // [l, r) if(dp[l][r].size() > 0) return;
auto& ans = dp[l][r]; if(l + 1 == r) { ans.insert(s[l] - '0'); return; }
int maxVal = -1;
for(int i = l + 1; i < r; i += 2) { // Dfs(l, i); Dfs(i+1, r);
for(auto a: dp[l][i]) { for(auto b: dp[i+1][r]) { ll v = 0; if(s[i] == '+') { v = a + b; } else { v = a * b; } if(v <= 1000) { ans.insert(v); } } } }}

五、最后

这次比赛整体都不难。

对于第三题,我有一个想法:去掉两端必须是边界或障碍物的限制时,又该如何做呢?

小提示:把空白与字符串连接起来,空白当做任意匹配符,就是一个正则表达式了。

加油,算法人。

《完》

-EOF-

题图:来自朋友圈。

leetcode 第 260 场算法比赛

上篇文章:leetcode 秋季编程大赛(2021团队赛)

推荐:leetcode 第 259 场算法比赛

长按二维码,一起成长学习


leetcode 第 260 场算法比赛

leetcode 第 260 场算法比赛

▲ 长按关注,天天成长

觉得有帮助可以点击好看与转发,谢谢!

Click to rate this post!
[Total: 0 Average: 0]

人已赞赏
Dfinity名家说小白百科每日优选

NNS Dapp对用户层次的重要性

2021-9-30 20:13:25

Rust开发名家说每日优选

《 RustMagazine 中文精选 》2021年第九期正式发布

2021-10-1 23:22:51

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
有新消息 消息中心
搜索