第212场周赛

比赛地址

比赛说明

本场竞赛由「猿辅导」&「力扣」联合主办

【工作机会奖励】

• 排名第 1 ~ 1000 名参赛者可获「猿辅导」社招简历内推机会。

【实物周边奖励】

• 排名第 1 ~ 10 名的参赛者可获「2020 猿辅导鼠年纪念币」；
• 排名第 11 ~ 30 名的参赛者可获「小猿手办」；
• 排名第 99、199、299 名的参赛者可获「幸运奖」；

重要提示

1. 请注意，每个错误提交的惩罚时间已经从 10分钟 改变为了 5分钟 。

2. 力扣一向非常重视竞赛的公平，为了保障每一位用户的权益，如有用户被检查出竞赛中存在违规行为（如抄袭、作弊等），我们会坚持以 零容忍 的态度维护竞赛的公平、公正。

3. 以下被判定为竞赛中的违规行为

   • 一人使用多账号提交（英文站 LCUS 的账号 和 中文站 LCCN 的账号属于两个账号）

   • 通过不正当的方式将部分或全部测试用例的答案直接贴到代码里的

   • 多账号提交雷同代码（抄袭）
   • 使用不正当手段影响他人竞赛的
   • 竞赛结束前在讨论区发布答案的

4. 如被发现违规行为，我们将会严格按照以下处罚规则执行：

   • 第一次违规：账号内的所有积分清零，账号冻结 1 个月

   • 第二次违规：永久封号

5. 同时我们也鼓励大家共同维护竞赛的公平和公正，我们会给与举报成功的用户额外的奖励：

   • 被认定为违规账号的前 10 名举报者，每人可获得 20 积分奖励

   • 每人每场最高可获得举报成功的 100 积分奖励

题目列表

题目	难度	得分
1.按键持续时间最长的键	简单	3
2.等差子数组	中等	4
3.最小体力消耗路径	中等	5
4.矩阵转换后的秩	困难	7

按键持续时间最长的键

题目描述：

LeetCode 设计了一款新式键盘，正在测试其可用性。测试人员将会点击一系列键（总计 n 个），每次一个。

给你一个长度为 n 的字符串 keysPressed ，其中 keysPressed[i] 表示测试序列中第 i 个被按下的键。releaseTimes 是一个升序排列的列表，其中 releaseTimes[i] 表示松开第 i 个键的时间。字符串和数组的 下标都从 0 开始 。第 0 个键在时间为 0 时被按下，接下来每个键都 恰好 在前一个键松开时被按下。

测试人员想要找出按键 持续时间最长 的键。第 i 次按键的持续时间为 releaseTimes[i] - releaseTimes[i - 1] ，第 0 次按键的持续时间为 releaseTimes[0] 。

注意，测试期间，同一个键可以在不同时刻被多次按下，而每次的持续时间都可能不同。

请返回按键 持续时间最长 的键，如果有多个这样的键，则返回 按字母顺序排列最大 的那个键。

示例1：

输入：releaseTimes = [9,29,49,50], keysPressed = "cbcd"
输出："c"
解释：按键顺序和持续时间如下：
按下 'c' ，持续时间 9（时间 0 按下，时间 9 松开）
按下 'b' ，持续时间 29 - 9 = 20（松开上一个键的时间 9 按下，时间 29 松开）
按下 'c' ，持续时间 49 - 29 = 20（松开上一个键的时间 29 按下，时间 49 松开）
按下 'd' ，持续时间 50 - 49 = 1（松开上一个键的时间 49 按下，时间 50 松开）
按键持续时间最长的键是 'b' 和 'c'（第二次按下时），持续时间都是 20
'c' 按字母顺序排列比 'b' 大，所以答案是 'c'

示例2：

输入：releaseTimes = [12,23,36,46,62], keysPressed = "spuda"
输出："a"
解释：按键顺序和持续时间如下：
按下 's' ，持续时间 12
按下 'p' ，持续时间 23 - 12 = 11
按下 'u' ，持续时间 36 - 23 = 13
按下 'd' ，持续时间 46 - 36 = 10
按下 'a' ，持续时间 62 - 46 = 16
按键持续时间最长的键是 'a' ，持续时间 16

提示：

• releaseTimes.length == n
• keysPressed.length == n
• 2 <= n <= 1000
• 0 <= releaseTimes[i] <= 109
• releaseTimes[i] < releaseTimes[i+1]
• keysPressed 仅由小写英文字母组成

思路：

用一个变量存储最长的持续时间，然后依次遍历releaseTimes计算每个键的持续时间（第1个键特殊处理），比较持续时间若相同比较字母顺序。

提交的代码：（运行时间16ms，内存消耗10.7M）

class Solution {
public:
    char slowestKey(vector<int>& releaseTimes, string keysPressed) {
        //先把releaseTimes转换成每个键的持续时间，从后面开始
        int key_time=0;
        char c;
        for(int i=releaseTimes.size()-1;i>=0;i--){
            //计算持续时间，第一个键例外
            if(i!=0){
                releaseTimes[i]=releaseTimes[i]-releaseTimes[i-1];
            }
            if(releaseTimes[i]>key_time){
                //持续时间最长的键
                key_time=releaseTimes[i];
                c=keysPressed[i];
            }else if(releaseTimes[i]==key_time){
                //相同持续时间比较字母顺序
                if(keysPressed[i]>c){
                    c=keysPressed[i];
                }
            }
        }
    return c;
    }
};

等差子数组

题目描述：

如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是 等差数列 。更正式地，数列 s 是等差数列，只需要满足：对于每个有效的 i ， s[i+1] - s[i] == s[1] - s[0] 都成立。

例如，下面这些都是 等差数列 ：

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

下面的数列 不是等差数列 ：

1, 1, 2, 5, 7

给你一个由 n 个整数组成的数组 nums，和两个由 m 个整数组成的数组 l 和 r，后两个数组表示 m 组范围查询，其中第 i 个查询对应范围 [l[i], r[i]] 。所有数组的下标都是 从 0 开始 的。

返回 boolean 元素构成的答案列表 answer 。如果子数组 nums[l[i]], nums[l[i]+1], ... , nums[r[i]] 可以 重新排列 形成 等差数列 ，answer[i] 的值就是 true；否则answer[i] 的值就是 false 。

示例1：

输入：nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]
输出：[true,false,true]
解释：
第 0 个查询，对应子数组 [4,6,5] 。可以重新排列为等差数列 [6,5,4] 。
第 1 个查询，对应子数组 [4,6,5,9] 。无法重新排列形成等差数列。
第 2 个查询，对应子数组 [5,9,3,7] 。可以重新排列为等差数列 [3,5,7,9] 。

示例2：

输入：nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]
输出：[false,true,false,false,true,true]

提示：

• n == nums.length
• m == l.length
• m == r.length
• 2 <= n <= 500
• 1 <= m <= 500
• 0 <= l[i] < r[i] < n
• -105 <= nums[i] <= 105

思路：

用vector容器存储返回结果，默认值为true。m次循环（m是数组l的长度），在每次循环中得到相对应的范围数组，然后判断数组是否是等差数列，如果不是则修改结果容器对应元素为false

代码：（执行用时204ms，击败47.38%，内存20.9M，击败83.18%）

class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        //定义布尔类型返回向量容器，默认值是true
        vector<bool> result(l.size(),true);
        vector<int> tmp;
        int d=0;
        int j=0;
        //得到结果
        for(int i=0;i<l.size();i++){
            //数组元素清空
            tmp.clear();
            for(j=l[i];j<=r[i];j++){
                //存储获取到的范围数组
                tmp.push_back(nums[j]);
            }
            //重新排序
            sort(tmp.begin(),tmp.end());
            //判断子数组是否是等差数组
            for(j=0;j<tmp.size()-1;j++){
                    //求公差
                    if(j==0){
                        d=tmp[j+1]-tmp[j];
                    }else{
                        //差不等于公差d
                        if(tmp[j+1]-tmp[j]!=d){
                            result[i]=false;
                        }
                    }
            }
            tmp.clear();
        }
        return result;
    }
};

最小体力消耗路径

题目描述：

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

示例1：

输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路劲差值最大值为 3 。

示例2：

输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

示例3：

输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出：0
解释：上图所示路径不需要消耗任何体力。

提示：

• rows == heights.length
• columns == heights[i].length
• 1 <= rows, columns <= 100
• 1 <= heights[i][j] <= 106

思路：

没什么好的想法，直观的解法就是遍历所有的走法，从（0,0）到（row-1，columns-1），不对好像也不行，因为还有往回查的。

代码：

矩阵转换后的秩

题目描述：

给你一个 m x n 的矩阵 matrix ，请你返回一个新的矩阵 answer ，其中 answer[row][col] 是 matrix[row][col] 的秩。

每个元素的 秩 是一个整数，表示这个元素相对于其他元素的大小关系，它按照如下规则计算：

• 如果一个元素是它所在行和列的最小值，那么它的 秩 为 1。
• 如果两个元素 p 和 q 在 同一行 或者 同一列 ，那么：
• • 如果 p < q ，那么 rank(p) < rank(q)
  • 如果 p == q ，那么 rank(p) == rank(q)
  • 如果 p > q ，那么 rank(p) > rank(q)
• 秩 需要越 小 越好。

题目保证按照上面规则 answer 数组是唯一的。

示例1：

输入：matrix = [[1,2],[3,4]]
输出：[[1,2],[2,3]]
解释：
matrix[0][0] 的秩为 1 ，因为它是所在行和列的最小整数。
matrix[0][1] 的秩为 2 ，因为 matrix[0][1] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。
matrix[1][0] 的秩为 2 ，因为 matrix[1][0] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。
matrix[1][1] 的秩为 3 ，因为 matrix[1][1] > matrix[0][1]， matrix[1][1] > matrix[1][0] 且 matrix[0][1] 和 matrix[1][0] 的秩都为 2 。

示例2：

输入：matrix = [[7,7],[7,7]]
输出：[[1,1],[1,1]]

示例3：

输入：matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
输出：[[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

示例4：

输入：matrix = [[7,3,6],[1,4,5],[9,8,2]]
输出：[[5,1,4],[1,2,3],[6,3,1]]

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 500
• -109 <= matrix[row][col] <= 109

思路：

这道属于难题，我都没看，上一道中等题我都没做出来，还是先算了

代码：

总结

第一次参加LeetCode周赛，只提交了一道题，排名好像几千名吧，这么看参加的人还不少哇，不过第二道题挺可惜的提交了以后超出时间限制😥也没时间改了，后来复盘发现存储范围数组的tmp容器排序代码我放到了for循环中，应该放到外面也就是说要全部获取到tmp元素后再调用sort函数排序，不能放入一个元素就排一下序，没必要。其实参加周赛的时候心神不定，不专注，有心事。或许是因为没信心吧，所以做的慢了些，效率不高，下次加油吧。

啊好懵，本科学的算法和数据结构都忘了（也可能没学会）🤣。决定还是先刷简单题吧，这周赛我觉得我现在水平不太行，题解要写好久，等到刷了一定数量的简单题有了一定的水平之后再来完成这些周赛的题解吧，不过我一定会回来的🤔