【力扣】第260场周赛

周赛链接：https://s.heyiqi.cc/vx2

1.增量元素之间的最大差值

题目链接：https://s.heyiqi.cc/77z

给你一个下标从 0 开始的整数数组 nums ，该数组的大小为 n ，请你计算 nums[j] - nums[i] 能求得的 最大差值 ，其中 0 <= i < j < n 且 nums[i] < nums[j] 。
返回 最大差值 。如果不存在满足要求的 i 和 j ，返回 -1 。

示例 1：

输入：nums = [7,1,5,4]
输出：4
解释：
最大差值出现在 i = 1 且 j = 2 时，nums[j] - nums[i] = 5 - 1 = 4 。
注意，尽管 i = 1 且 j = 0 时 ，nums[j] - nums[i] = 7 - 1 = 6 > 4 ，但 i > j 不满足题面要求，所以 6 不是有效的答案。

示例 2：

输入：nums = [9,4,3,2]
输出：-1
解释：
不存在同时满足 i < j 和 nums[i] < nums[j] 这两个条件的 i, j 组合。

示例 3：

输入：nums = [1,5,2,10]
输出：9
解释：
最大差值出现在 i = 0 且 j = 3 时，nums[j] - nums[i] = 10 - 1 = 9 。

提示：

n == nums.length
2 <= n <= 1000
1 <= nums[i] <= 109

分析

签到题，数据范围较小，直接暴力

代码

class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int n = nums.size();
        int ans = -1;
        for(int i=n-1;i>-1;i--)
            for(int j=0;j<i;j++)
                if(nums[i]-nums[j]>ans)
                    ans = nums[i]>nums[j] ? nums[i]-nums[j] : ans;
        return ans;
    }
};

2.网格游戏

题目链接：https://s.heyiqi.cc/qxk

给你一个下标从 0 开始的二维数组 grid ，数组大小为 2 x n ，其中 grid[r][c] 表示矩阵中 (r, c) 位置上的点数。现在有两个机器人正在矩阵上参与一场游戏。

两个机器人初始位置都是 (0, 0) ，目标位置是 (1, n-1) 。每个机器人只会向右 ((r, c) 到 (r, c + 1)) 或向下 ((r, c) 到 (r + 1, c)) 。

游戏开始，第一个 机器人从 (0, 0) 移动到 (1, n-1) ，并收集路径上单元格的全部点数。对于路径上所有单元格 (r, c) ，途经后 grid[r][c] 会重置为 0 。然后，第二个 机器人从 (0, 0) 移动到 (1, n-1) ，同样收集路径上单元的全部点数。注意，它们的路径可能会存在相交的部分。

第一个 机器人想要打击竞争对手，使 第二个 机器人收集到的点数 最小化 。与此相对，第二个机器人想要 最大化 自己收集到的点数。两个机器人都发挥出自己的 最佳水平 的前提下，返回 第二个 机器人收集到的点数。

示例 1：

输入：grid = [[2,5,4],[1,5,1]]
输出：4
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 0 + 4 + 0 = 4 个点。

示例 2：

输入：grid = [[3,3,1],[8,5,2]]
输出：4
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。 
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 3 + 1 + 0 = 4 个点。

示例 3：

输入：grid = [[1,3,1,15],[1,3,3,1]]
输出：7
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 1 + 3 + 3 + 0 = 7 个点。

提示：

grid.length == 2
n == grid[r].length
1 <= n <= 5 * 104
1 <= grid[r][c] <= 105

分析

第一个机器人的目的是使第二个机器人得到的点数最小化，自己的获得的点数并非最大化，根据观察可以发现，第一个机器人可能走的路径为|____ 或 ￣￣| 或 ￣｜__，由于只能向右或者向下走，走完之后第二个机器人只能吃到第一行或第二行的剩余点数，因此只要找到第一个机器人向下走的那一列，使得第一行和第二行剩余点数较多的那一行尽可能的小，就能达成目标。
不难想到可以用前缀和，分别求出两行的前缀和，然后找到第一个机器人的转点，时间复杂度2n+n=O(n)，空间复杂度O(n)。

代码

class Solution {
    typedef long long ll;
public:
    long long gridGame(vector<vector<int>>& grid) {
        int n = grid[0].size();
        ll pre[2][n];
        pre[0][0] = grid[0][0];
        pre[1][0] = grid[1][0];
        for(int i=1;i<n;i++)pre[0][i]=pre[0][i-1]+grid[0][i];
        for(int i=1;i<n;i++)pre[1][i]=pre[1][i-1]+grid[1][i];
        ll left_min = LLONG_MAX;
        for(int i=0;i<n;i++){
            ll left_max = max(pre[0][n-1]-pre[0][i],i>0?pre[1][i-1]:0);
            left_min = left_max < left_min ? left_max : left_min;
        }
        return left_min;
    }
};

3.判断单词是否能放入填字游戏内

题目链接：https://s.heyiqi.cc/t6y

给你一个 m x n 的矩阵 board ，它代表一个填字游戏当前的状态。填字游戏格子中包含小写英文字母（已填入的单词），表示空格的 ' ' 和表示障碍格子的 '#' 。

如果满足以下条件，那么我们可以水平（从左到右或者从右到左）或竖直（从上到下或者从下到上）填入一个单词：

该单词不占据任何 '#' 对应的格子。
每个字母对应的格子要么是 ' ' （空格）要么与 board 中已有字母匹配。
如果单词是水平放置的，那么该单词左边和右边相邻格子不能为 ' ' 或小写英文字母。
如果单词是竖直放置的，那么该单词上边和下边相邻格子不能为 ' ' 或小写英文字母。
给你一个字符串 word ，如果 word 可以被放入 board 中，请你返回 true ，否则请返回 false 。

示例 1：

#	a	#
	b	#
#	c

1
2
3

输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc"
输出：true
解释：单词 "abc" 可以如上图放置（从上往下）。

示例 2：

	#	a
	#	c
	#	a

1
2
3

输入：board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac"
输出：false
解释：无法放置单词，因为放置该单词后上方或者下方相邻格会有空格。

示例 3：

#		#
		#
#	a	c

1
2
3

输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], word = "ca"
输出：true
解释：单词 "ca" 可以如上图放置（从右到左）。

提示：

m == board.length
n == board[i].length
1 <= m * n <= 2 * 10^5
board[i][j] 可能为 ' ' ，'#' 或者一个小写英文字母。
1 <= word.length <= max(m, n)
word 只包含小写英文字母。

分析

直接模拟，遍历每一个非'#'的格子，如果上方为墙尝试向下放，如果左方为墙尝试向右放，分别尝试正序和逆序，涵盖了所有情况。

代码

class Solution {
public:
    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        string word1 = word;
        reverse(word1.begin(),word1.end());
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j] != '#'){
                    //从上往下填充，例如abc
                    if(i==0 || (i>0&&board[i-1][j]=='#')){
                        // a 正序填充
                        // b
                        // c
                        int k=i;
                        for(;k<m && k-i<word.size();k++)
                            if(board[k][j]!=' ' && board[k][j]!=word[k-i])
                                break;
                        //判断是否填充成功
                        if(k-i==word.size() && (k==m || board[k][j]=='#'))
                            return true;
                        // c 逆序填充
                        // b
                        // a
                        k=i;
                        for(;k<m && k-i<word1.size();k++)
                            if(board[k][j]!=' ' && board[k][j]!=word1[k-i])break;
                        //判断是否填充成功
                        if(k-i==word1.size() && (k==m || board[k][j]=='#'))
                            return true;
                    }
                    //从左往右填充
                    if(j==0 || (j>0&&board[i][j-1]=='#')){
                        // a b c 正序填充
                        int k=j;
                        for(;k<n && k-j<word.size();k++)
                            if(board[i][k]!=' ' && board[i][k]!=word[k-j])
                                break;
                        //判断是否填充成功
                        if(k-j==word.size() && (k==n || board[i][k]=='#'))
                            return true;
                        // c b a 逆序填充
                        k=j;
                        for(;k<n && k-j<word1.size();k++)
                            if(board[i][k]!=' ' && board[i][k]!=word1[k-j])
                                break;
                        //判断是否填充成功
                        if(k-j==word1.size() && (k==n || board[i][k]=='#'))
                            return true;
                    }
                }
            }
        }
        return false;
    }
};

tip在外面增加一圈墙，无需判断边界情况

class Solution {
public:
    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        string word1 = word;
        reverse(word1.begin(),word1.end());
        vector<vector<char>> b1(m+2,vector<char>(n+2,'#'));
        for(int i=1;i<m+1;i++)
            for(int j=1;j<n+1;j++)
                b1[i][j]=board[i-1][j-1];
        m+=2;n+=2;
        for(int i=1;i<m-1;i++){
            for(int j=1;j<n-1;j++){
                if(b1[i][j]!='#'){
                    if(b1[i-1][j]=='#'){
                        int k=i;
                        for(;k-i<word.size()&&(b1[k][j]==' '||b1[k][j]==word[k-i]);k++);
                        if(k-i==word.size()&&b1[k][j]=='#')return 1;
                        k=i;
                        for(;k-i<word1.size()&&(b1[k][j]==' '||b1[k][j]==word1[k-i]);k++);
                        if(k-i==word1.size()&&b1[k][j]=='#')return 1;
                    }
                    if(b1[i][j-1]=='#'){
                        int k=j;
                        for(;k-j<word.size()&&(b1[i][k]==' '||b1[i][k]==word[k-j]);k++);
                        if(k-j==word.size()&&b1[i][k]=='#')return 1;
                        k=j;
                        for(;k-j<word1.size()&&(b1[i][k]==' '||b1[i][k]==word1[k-j]);k++);
                        if(k-j==word1.size()&&b1[i][k]=='#')return 1;
                    }
                }
            }
        }
        return 0;
    }
};

4.解出数学表达式的学生分数

题目链接：https://s.heyiqi.cc/ouj

给你一个字符串 s ，它只包含数字 0-9 ，加法运算符 '+' 和乘法运算符 '*' ，这个字符串表示一个合法的只含有 个位数数字 的数学表达式（比方说 3+5*2）。有 n 位小学生将计算这个数学表达式，并遵循如下 运算顺序 ：

按照 从左到右 的顺序计算乘法，然后
按照 从左到右 的顺序计算加法。

给你一个长度为 n 的整数数组 answers ，表示每位学生提交的答案。你的任务是给 answer 数组按照如下规则打分：

如果一位学生的答案等于表达式的正确结果，这位学生将得到 5 分。
否则，如果答案由 一处或多处错误的运算顺序 计算得到，那么这位学生能得到 2 分。
否则，这位学生将得到 0 分。

请你返回所有学生的分数和。

示例 1：

输入：s = "7+3*1*2", answers = [20,13,42]
输出：7
解释：如上图所示，正确答案为 13 ，因此有一位学生得分为 5 分：[20,13,42] 。
一位学生可能通过错误的运算顺序得到结果 20 ：7+3=10，10*1=10，10*2=20 。所以这位学生得分为 2 分：[20,13,42] 。
所有学生得分分别为：[2,5,0] 。所有得分之和为 2+5+0=7 。

示例 2：

输入：s = "3+5*2", answers = [13,0,10,13,13,16,16]
输出：19
解释：表达式的正确结果为 13 ，所以有 3 位学生得到 5 分：[13,0,10,13,13,16,16] 。
学生可能通过错误的运算顺序得到结果 16 ：3+5=8，8*2=16 。所以两位学生得到 2 分：[13,0,10,13,13,16,16] 。
所有学生得分分别为：[5,0,0,5,5,2,2] 。所有得分之和为 5+0+0+5+5+2+2=19 。

示例 3：

输入：s = "6+0*1", answers = [12,9,6,4,8,6]
输出：10
解释：表达式的正确结果为 6 。
如果一位学生通过错误的运算顺序计算该表达式，结果仍为 6 。
根据打分规则，运算顺序错误的学生也将得到 5 分（因为他们仍然得到了正确的结果），而不是 2 分。
所有学生得分分别为：[0,0,5,0,0,5] 。所有得分之和为 10 分。

提示：

3 <= s.length <= 31
s 表示一个只包含 0-9 ，'+' 和 '*' 的合法表达式。
表达式中所有整数运算数字都在闭区间 [0, 9] 以内。
1 <= 数学表达式中所有运算符数目（'+' 和 '*'） <= 15
测试数据保证正确表达式结果在范围 [0, 1000] 以内。
n == answers.length
1 <= n <= 104
0 <= answers[i] <= 1000

分析

代码

#题解 #力扣 #CPP #暴力 #动态规划 #模拟 #周赛

【力扣】第260场周赛

https://heyq.cc/2021/09/27/leetcode-weekly-contest-260/

作者

YiQi He

发布于

2021年9月27日

许可协议

【LGR-093】洛谷 10 月月赛 I & MCOI R6 Div.2 A&B 上一篇

【洛谷】P1002 [NOIP2002 普及组] 过河卒下一篇