LeetCode第225场周赛

2021-01-24

5661. 替换隐藏数字得到的最晚时间

题意:
给你一个字符串 time ,格式为 hh:mm(小时:分钟),其中某几位数字被隐藏(用 ? 表示)。

有效的时间为 00:00 到 23:59 之间的所有时间,包括 00:00 和 23:59 。

替换 time 中隐藏的数字,返回你可以得到的最晚有效时间。

思路:
简单直接判断即可

代码

class Solution {
    public String maximumTime(String time) {
        String ans="";
        if(time.charAt(0)=='?') {
            if(time.charAt(1)=='?')ans+='2';
            else if(time.charAt(1)<='3')ans+='2';
            else ans+='1';
        }
        else ans+=time.charAt(0);
        if(time.charAt(1)=='?') {
            if(ans.charAt(0)=='2') ans+='3';
            else ans+='9';  
        }
        else ans+=time.charAt(1);
        ans+=':';
        if(time.charAt(3)=='?') {
            ans+='5';
        }
        else ans+=time.charAt(3);
        if(time.charAt(4)=='?') {
            ans+='9';
        }
        else ans+=time.charAt(4);
        return ans;
    }
}

5662. 满足三条件之一需改变的最少字符数

题意:
给你两个字符串 a 和 b ,二者均由小写字母组成。一步操作中,你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。

操作的最终目标是满足下列三个条件 之一 :

a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。
b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。
a 和 b 都 由 同一个 字母组成。
返回达成目标所需的 最少 操作数。

思路
确定划分字符,因为均是小写字符'a'~'z',所以对于字符 x 有两种情况

  1. a 字符串全部小于等于 x,b 字符串全部大于 x
  2. a 字符串全部大于 x,b 字符串全部小于等于 x

代码

class Solution {
public:
    int minCharacters(string a, string b) {
        
        int lena=a.length();
        int lenb=b.length();
        
        map<char,int>mpa;
        map<char,int>mpb;
        
        for(int i=0;i<lena;i++) {
            mpa[a[i]]++;
        }
        for(int j=0;j<lenb;j++) {
            mpb[b[j]]++;
        }
        
        int ans=0x3f3f3f3f;
        
        //全变成同一字符
        for(char i='a';i<='z';i++) {
            ans=min(ans,lena+lenb-mpa[i]-mpb[i]);
        }
        
        //找出比a全部字符x小的 b全部字符大于x的
        int sum1=0,sum2=0;
        for(char i='a';i<='y';i++) {
            sum1+=mpa[i];
            sum2+=mpb[i];
            //a全部小于等于 i b大于i
            ans=min(ans,lena-sum1+sum2);
            
            //a全部大于i,b小于等于i
            if(i<'z') ans=min(ans,lenb-sum2+sum1);
            
           // if(ans==1) cout<<i<<'\n';
        }
       
        return ans;
    }
};

坑点在于对于字符 z 是不需要判断的,因为不可能有比 z 还大的

5663. 找出第 K 大的异或坐标值

题意
给你一个二维矩阵 matrix 和一个整数 k ,矩阵大小为 m x n 由非负整数组成。

矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j](下标从 0 开始计数)执行异或运算得到。

请你找出 matrix 的所有坐标中第 k 大的值(k 的值从 1 开始计数)。

思路
维护一个 l[]数组表示从第一行到当前行,这一列的异或值为多少即可。边扫描边记录异或值即可。最后按照数据范围进行查找第 k 大即可。

代码

class Solution {
    int []a=new int [1000010];
    int []l=new int [1005];
    public int kthLargestValue(int[][] matrix, int k) {

        int x=0;
        for(int i=0;i<matrix[0].length;i++) {
            x^=matrix[0][i];
            l[i]=matrix[0][i];
            a[x]++;
        }
        /*
        for(int i=0;i<100;i++) {
           if(a[i]!=0) {
               System.out.println(i+"  "+a[i]+"  ");
           }
        }
        */
        x=0;
        for(int i=1;i<matrix.length;i++) {
            x=0;
            for(int j=0;j<matrix[0].length;j++) {
                l[j]^=matrix[i][j];
                x^=l[j];
                //if(j>0) x^=l[j-1];
                
                a[x]++;
            }
        }
        /*
        for(int i=0;i<100;i++) {
           if(a[i]!=0) {
               System.out.println(i+"  "+a[i]+"  ");
           }
        }
        */
       // System.out.println();
        int ans=1000000;
        for(int i=1000000;i>=0;i--) {
            if(a[i]!=0) k-=a[i];
            if(k<=0) {
                //cout<<i<<'\n';
             //   System.out.println(i);
                ans=i;
                break;
            }
        }
        /*
        for(int j=0;j<matrix[0].length;j++) {
            System.out.printf(l[j]+"  ");
        }
        */
        return ans;
    }
}
/*
[[3,10,9,5,5,7],[0,1,7,3,8,1],[9,3,0,6,1,6],[10,2,9,10,10,7]]
18
*/

标题:LeetCode第225场周赛
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2021/01/24/1611475041527.html