第246场周赛

比赛说明

本场竞赛由「蔚来 & 力扣」联合主办

【工作机会奖励】

排名第 1 ~ 300 名的参赛者可获「 NIO 蔚来」简历内推机会。

【实物奖励】

排名第 1 名的参赛者可获 NIO 蔚来 ES8 - 1:18 合金车模（天蓝）x 1
排名第 2 名的参赛者可获 NIO 蔚来 ES6 - 1:18 合金车模（星云紫）x 1
排名第 3 ~ 4 名的参赛者可获 NIO 蔚来Blue Sky 保温杯（蓝绿）x 1
排名第 5 ~ 10 名的参赛者可获 NIO 蔚来 NIOLIFE环保软木笔 5支装 x 1
排名第 166、266、366、466、566、666 名的参赛者可获 NIO 蔚来的纪念礼品 x 1

题目列表

题目	难度	得分
1.字符串中的最大奇数	简单	3
2.你完成的完整对局数	中等	4
3.统计子岛屿	中等	5
4.查询差绝对值的最小值	中等	5

字符串中的最大奇数

题目描述：

给你一个字符串 num ，表示一个大整数。请你在字符串 num 的所有 非空子字符串 中找出 值最大的奇数 ，并以字符串形式返回。如果不存在奇数，则返回一个空字符串 "" 。

子字符串 是字符串中的一个连续的字符序列。

示例1：

1
2
3

输入：num = "52"
输出："5"
解释：非空子字符串仅有 "5"、"2" 和 "52" 。"5" 是其中唯一的奇数。

示例2：

1
2
3

输入：num = "4206"
输出：""
解释：在 "4206" 中不存在奇数。

示例3：

1
2
3

输入：num = "35427"
输出："35427"
解释："35427" 本身就是一个奇数。

提示：

1 <= num.length <=$10^5$
num 仅由数字组成且不含前导零

思路：

倒序遍历字符串num，如果当前字符对应数字是奇数，返回从头到当前字符的子串。

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

class Solution {
public:
    string largestOddNumber(string num) {
        if(num[num.size()-1]%2==1){
            return num;
        }
        for(int i=num.size()-2;i>=0;i--){
            if(num[i]%2==1){
                num.erase(i+1,num.size()-1-i);
                return num; 
            }
        }
        return "";

    }
};

你完成的完整对局数

题目描述：

一款新的在线电子游戏在近期发布，在该电子游戏中，以刻钟为周期规划若干时长为 15 分钟 的游戏对局。这意味着，在 HH:00、HH:15、HH:30 和 HH:45 ，将会开始一个新的对局，其中 HH 用一个从 00 到 23 的整数表示。游戏中使用 24 小时制的时钟 ，所以一天中最早的时间是 00:00 ，最晚的时间是 23:59 。

给你两个字符串 startTime 和 finishTime ，均符合 "HH:MM" 格式，分别表示你进入和退出游戏的确切时间，请计算在整个游戏会话期间，你完成的 完整对局的对局数 。

例如，如果 startTime = "05:20" 且 finishTime = "05:59" ，这意味着你仅仅完成从 05:30 到 05:45 这一个完整对局。而你没有完成从 05:15 到 05:30 的完整对局，因为你是在对局开始后进入的游戏；同时，你也没有完成从 05:45 到 06:00 的完整对局，因为你是在对局结束前退出的游戏。

如果 finishTime 早于 startTime ，这表示你玩了个通宵（也就是从 startTime 到午夜，再从午夜到 finishTime）。

假设你是从 startTime 进入游戏，并在 finishTime 退出游戏，请计算并返回你完成的 完整对局的对局数 。

子字符串 是字符串中的一个连续的字符序列。

示例1：

输入：startTime = "12:01", finishTime = "12:44"
输出：1
解释：你完成了从 12:15 到 12:30 的一个完整对局。
你没有完成从 12:00 到 12:15 的完整对局，因为你是在对局开始后的 12:01 进入的游戏。
你没有完成从 12:30 到 12:45 的完整对局，因为你是在对局结束前的 12:44 退出的游戏。

示例2：

输入：startTime = "20:00", finishTime = "06:00"
输出：40
解释：你完成了从 20:00 到 00:00 的 16 个完整的对局，以及从 00:00 到 06:00 的 24 个完整的对局。
16 + 24 = 40

示例3：

1
2
3

输入：startTime = "00:00", finishTime = "23:59"
输出：95
解释：除最后一个小时你只完成了 3 个完整对局外，其余每个小时均完成了 4 场完整对局。

提示：

startTime 和 finishTime 的格式为 HH:MM
00 <= HH <= 23
00 <= MM <= 59
startTime 和 finishTime 不相等

思路：

先把startTime和finishTime都转成分钟数，然后判断开始时间点是否小于结束时间，如果大于，则证明玩了个通宵，结束时间要加上24个小时，然后计算玩的这段时间有多少个刻钟，最后判断开始时间点是否是刻钟起点（15的倍数），如果不是最终结果要减去1。

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

class Solution {
public:
    int numberOfRounds(string startTime, string finishTime) {
        int result=0;
        //cout<<startTime.substr(0,2)<<endl;
        int start_hour=stoi(startTime.substr(0,2));
        int start_min=stoi(startTime.substr(3,2));
        int end_hour=stoi(finishTime.substr(0,2));
        int end_min=stoi(finishTime.substr(3,2));
        //字符串转int不能直接强转吗
        //int end_min=int(finishTime.substr(3,2));
        int start=start_hour*60+start_min;
        int end=end_hour*60+end_min;
        if(start>end){
            end+=24*60;
        }
        result=end/15-start/15;
        if(start%15!=0){
            result-=1;
        }
        return result;
    }
};

统计子岛屿

题目描述：

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个岛屿是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

如果 grid2 的一个岛屿，被 grid1 的一个岛屿完全包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。

请你返回 grid2 中 子岛屿 的数目。

示例1：

输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
输出：3
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。

示例2：

输入：grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
输出：2 
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 2 个子岛屿。

提示：

m == grid1.length == grid2.length
n == grid1[i].length == grid2[i].length
1 <= m, n <= 500
grid1[i][j] 和 grid2[i][j] 都要么是 0 要么是 1 。

思路：

觉得这道题和之前做过的一道题类似，应该是要用递归，不过比赛时没做。。。

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

class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {

    }
};

查询差绝对值的最小值

题目描述：

一个数组 a 的 差绝对值的最小值 定义为：0 <= i < j < a.length 且 a[i] != a[j] 的 |a[i] - a[j]| 的 最小值。如果 a 中所有元素都相同，那么差绝对值的最小值为 -1 。

比方说，数组 [5,**2**,**3**,7,2] 差绝对值的最小值是 |2 - 3| = 1 。注意答案不为 0 ，因为 a[i] 和 a[j] 必须不相等。

给你一个整数数组 nums 和查询数组 queries ，其中 queries[i] = [li, ri] 。对于每个查询 i ，计算 子数组 nums[li...ri] 中 差绝对值的最小值 ，子数组 nums[li...ri] 包含 nums 数组（下标从 0 开始）中下标在 li 和 ri 之间的所有元素（包含 li 和 ri 在内）。

请你返回 ans 数组，其中 ans[i] 是第 i 个查询的答案。

子数组 是一个数组中连续的一段元素。

|x| 的值定义为：

如果 x >= 0 ，那么值为 x 。
如果 x < 0 ，那么值为 -x 。

示例1：

输入：nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
输出：[2,1,4,1]
解释：查询结果如下：
- queries[0] = [0,1]：子数组是 [1,3] ，差绝对值的最小值为 |1-3| = 2 。
- queries[1] = [1,2]：子数组是 [3,4] ，差绝对值的最小值为 |3-4| = 1 。
- queries[2] = [2,3]：子数组是 [4,8] ，差绝对值的最小值为 |4-8| = 4 。
- queries[3] = [0,3]：子数组是 [1,3,4,8] ，差的绝对值的最小值为 |3-4| = 1 。

示例2：

输入：nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
输出：[-1,1,1,3]
解释：查询结果如下：
- queries[0] = [2,3]：子数组是 [2,2] ，差绝对值的最小值为 -1 ，因为所有元素相等。
- queries[1] = [0,2]：子数组是 [4,5,2] ，差绝对值的最小值为 |4-5| = 1 。
- queries[2] = [0,5]：子数组是 [4,5,2,2,7,10] ，差绝对值的最小值为 |4-5| = 1 。
- queries[3] = [3,5]：子数组是 [2,7,10] ，差绝对值的最小值为 |7-10| = 3 。

提示：

2 <= nums.length <= 105
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 104
0 <= li < ri < nums.length

思路：

按照queries中的元素取出nums中的子数组，然后计算差绝对值的最小值，这里是关键，我采用了sort排序，效率太低超时了。。。

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

class Solution {
public:
    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> result;
        int m=queries.size();
        int n=queries[0].size();
        for(int i=0;i<m;i++){
            //取出子数组
            vector<int> sub_nums;
            sub_nums.assign(nums.begin()+queries[i][0],nums.begin()+queries[i][1]+1);
            //计算子数组差绝对值最小值
            //对子数组从小到大排序
            sort(sub_nums.begin(),sub_nums.end());
            int min=INT_MAX;
            for(int j=1;j<sub_nums.size();j++){ 
                if((sub_nums[j]!=sub_nums[j-1]) && (min>sub_nums[j]-sub_nums[j-1])){     
                    min=sub_nums[j]-sub_nums[j-1]; 
                }
            }
            if(min==INT_MAX){
                min=-1;
            }
            result.emplace_back(min);
        }
        return result;

    }
};

总结

很久没做LeetCode题了，从这周开始坚持参加周赛，然后写写博客，平常刷LeetCode题也不再每道题都写博客了，加油。