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){ // [;, 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-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code