Leetcode Weekly Contest Round 246

T1 5788. 字符串中的最大奇数

题目

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

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

示例 2：
输入：num = “4206”
输出：“”
解释：在 “4206” 中不存在奇数。

示例 3：
输入：num = “35427”
输出：“35427”
解释：“35427” 本身就是一个奇数。

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

题解

贪心，没啥悬念，找到最后一个奇数位，从头到这个位置能确保长度最大化，必为最大奇数

class Solution {
    public String largestOddNumber(String num) {
        int len = num.length();
        int flag = -1;
        for(int i = 0; i < len; i++){
            if((int)(num.charAt(i) - '0') % 2 == 1) flag = i;
        }
        if(flag == -1) return "";
        else return num.substring(0, flag + 1);
    }
}

一款新的在线电子游戏在近期发布，在该电子游戏中，以刻钟为周期规划若干时长为 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：
输入：startTime = “00:00”, finishTime = “23:59”
输出：95
解释：除最后一个小时你只完成了 3 个完整对局外，其余每个小时均完成了 4 场完整对局。

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

题解

基本思路：考虑将开始时刻修正为首轮开始的有效时刻，即00 15 30 45时刻，随后计算修正后的总时间，将总时间除以15即可得到有效场次

我们先计算修正前的时间，若 $res < 0$ 即 startTime 大于 finishTime，我们认为对局将跨越午夜，故加上 $24 * 60 min$ 即一天的时间。随后我们对开始时间进行修正，从总时间中扣除余量

在此需要注意两个操作的顺序，切勿颠倒

代码如下：

class Solution {
    public int numberOfRounds(String startTime, String finishTime) {
        int s_hour = Integer.parseInt(startTime.substring(0, 2));
        int s_minute = Integer.parseInt(startTime.substring(3, 5));
        int f_hour = Integer.parseInt(finishTime.substring(0, 2));
        int f_minute = Integer.parseInt(finishTime.substring(3, 5));
        int res = f_minute - s_minute + 60 * (f_hour - s_hour);
        if(res < 0) res += 24 * 60;
        if(s_minute == 0){
            
        }
        else if(s_minute <= 15){
            res -= 15 - s_minute;
        }
        else if(s_minute <= 30){
            res -= 30 - s_minute;
        }
        else if(s_minute <= 45){
            res -= 45 - s_minute;
        }
        else if(s_minute <= 60){
            res -= 60 - s_minute;
        }
        return res >= 0 ? res / 15: 0;
    }
}

T3 5791. 统计子岛屿

题目

给你两个 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 。

题解

非常常规的遍历，BFS和DFS在这道题目中都可以，全看阅读理解
grid2按块遍历，全部抹成0，过程中和grid1比较，如果grid1有0，这块就不算

代码如下：

class Solution {
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int rows = grid1.length;
        int cols = grid1[0].length;
        int cnt = 0;
        int[] dir = new int[]{-1, 0, 1, 0, -1};
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                boolean flag = true;
                if(grid2[i][j] == 1){
                    Queue<int[]> queue = new ArrayDeque<>();
                    queue.offer(new int[]{i, j});
                    grid2[i][j] = 0;
                    while(!queue.isEmpty()){
                        int[] cur = queue.poll();
                        int x = cur[0], y = cur[1];
                        if(grid1[x][y] != 1){
                            flag = false;
                        }
                        for(int t = 0; t < 4; t++){
                            int nx = x + dir[t], ny = y + dir[t + 1];
                            if(nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid2[nx][ny] == 1){
                                grid2[nx][ny] = 0;
                                queue.offer(new int[]{nx, ny});
                            }
                        }
                    }
                }
                else continue;
                if(flag) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

T4 5790. 查询差绝对值的最小值

题目

一个数组 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 <= 10^5
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 10^4
0 <= li < ri < nums.length

题解

这道题初看很吓人，关键点在于1 <= nums[i] <= 100，由此我们想到前缀和，创建一个数组new int[len][101]，在每个位置用一个100长度的数组 表示 100以内各个数字从头开始出现的个数，当我们要计算区间时，只需要抽出对应的两条100长度的数组相减即可获得 此区间内的各数出现次数
随后我们只需要在生成的100长度的数组中，计算非0元素间的最短距离

代码如下：

class Solution {
    public int[] minDifference(int[] nums, int[][] queries) {
        int len = nums.length;
        int[][] arr = new int[len][101];
        for(int i = 0; i < len; i++){
            for(int j = 0; j < 101; j++){
                arr[i][j] = (i > 0) ? arr[i - 1][j] : 0;
            }
            arr[i][nums[i]] = (i > 0 ? arr[i - 1][nums[i]] : 0) + 1;
        }
        int[] res = new int[queries.length];
        int a = 0;
        for(int[] query: queries){
            int[] tmp = new int[101];
            for(int i = 0; i < 101; i++){
                tmp[i] = arr[query[1]][i] - (query[0] == 0 ? 0 : (arr[query[0] - 1][i]));
            }
            int prev = -1;
            int min = Integer.MAX_VALUE;
            for(int i = 1; i <= 100; i++){
                if(tmp[i] != 0){
                    if(prev == -1){
                        prev = i;
                        continue;
                    }
                    else{
                        min = Math.min(min, i - prev);
                        prev = i;
                    }
                }
            }
            if(min == Integer.MAX_VALUE && prev != -1) res[a++] = -1;
            else res[a++] = min;
        }
        return res;
    }
}