Leetcode Weekly Contest 246（详细解析）

题目链接： Leetcode Weekly Contest 246

写在前面：

本次周赛没有参加，在赛后进行了模拟。

1、1903. Largest Odd Number in String

难度：Easy

题目大意：

给出一个字符串，该字符串由数字组成，返回字串所能表示的最大奇数。

思路：

找到最后一位奇数所在的位置即可。

代码

class Solution {
    public String largestOddNumber(String num) {
        int n=num.length();
        char[] arr=num.toCharArray();
        int lastOdd=n-1;//最后一位奇数的位置
        while(lastOdd>=0&&(arr[lastOdd]-'0')%2==0){
            lastOdd--;
        }
        if(lastOdd<0){
            return "";
        }
        else{
            return num.substring(0,lastOdd+1);
        }
    }
}
           

2、1904. The Number of Full Rounds You Have Played

难度：Medium

题目大意：

详见题意。

思路：

把开始时间向后移到整数个15分钟的时间点，把结束时间向后移到整数个15分钟的时间点，计算开始时间和结束时间之间共有多少个15分钟。注意一些细节，比如满60分钟要进位，开始时间如果晚于结束时间要将结束时间后移一天。

代码

class Solution {
    public int numberOfRounds(String startTime, String finishTime) {
        int startH=(startTime.charAt(0)-'0')*10+startTime.charAt(1)-'0';
        int startM=(startTime.charAt(3)-'0')*10+startTime.charAt(4)-'0';
        int finishH=(finishTime.charAt(0)-'0')*10+finishTime.charAt(1)-'0';
        int finishM=(finishTime.charAt(3)-'0')*10+finishTime.charAt(4)-'0';
        if(startH>finishH||startH==finishH&&startM>finishM){
            finishH+=24;
        }
        if(startM%15!=0){
            startM=((startM/15+1)*15);
            if(startM==60){//满60分钟进位
                startM=0;
                startH++;
            }
        }
        if(finishM%15!=0){
            finishM=((finishM/15)*15)%60;
        }
        int minute=finishH*60+finishM-(startH*60+startM);
        if(minute<0){
            return 0;
        }
        return minute/15;
    }
}

           

3、1905. Count Sub Islands

难度：Medium

题目大意：

详见题目。

思路：

参考高赞回答，用DFS求解。这道题与Leetcode 200. Number of Islands类似。

代码

class Solution {
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int m=grid1.length;
        int n=grid1[0].length;
        int count=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid2[i][j]==1){
                    count+=dfs(grid1,grid2,i,j);
                }
            }
        }
        return count;
    }
    public int dfs(int[][] grid1,int[][] grid2,int i,int j){
        int m=grid1.length;
        int n=grid1[0].length;
        int res=1;
        if(i<0||i>=m||j<0||j>=n||grid2[i][j]==0){
            return 1;
        }
        grid2[i][j]=0;
        res&=dfs(grid1,grid2,i-1,j);
        res&=dfs(grid1,grid2,i+1,j);
        res&=dfs(grid1,grid2,i,j-1);
        res&=dfs(grid1,grid2,i,j+1);
        return res&grid1[i][j];
    }
}
           

4、1906. Minimum Absolute Difference Queries

难度：Medium

题目大意：

详见题目。

思路

数组中的元素

1 <= nums[i] <= 100

，用前缀和

prefix[i+1][j]

表示

nums[0...i]

中

j

出现的次数。给出某个区间后，依次遍历1~100,判断这些数字在这个区间中出现的次数是否大于0，然后求这个区间内各个元素的的最小差值。

代码

class Solution {
    public int[] minDifference(int[] nums, int[][] queries) {
        int n=nums.length;
        int[] cnt=new int [101];
        int[][] prefix=new int[n+1][101];
        //prefix[i+1][j]表示nums[0…i]中j出现的次数
        for(int i=0;i<n;i++){
            cnt[nums[i]]++;
            for(int j=1;j<=100;j++){
                prefix[i+1][j]=cnt[j];
            }
        }
        int[] res=new int[queries.length];
        for(int i=0;i<queries.length;i++){
            int L=queries[i][0],R=queries[i][1];
            int prev=-1;//前一个出现的数
            int minDiff=Integer.MAX_VALUE;
            for(int j=1;j<=100;j++){
                if(prefix[R+1][j]-prefix[L][j]>0){
                    if(prev!=-1){
                        minDiff=Math.min(minDiff,j-prev);
                    }
                    prev=j;
                }
            }
            if(minDiff==Integer.MAX_VALUE){
                res[i]=-1;
            }
            else{
                res[i]=minDiff;
            }
        }
        return res;
    }
}