leetcode周赛 255

https://leetcode-cn.com/contest/weekly-contest-225/

A：枚举，或者可以找规律

解法一：枚举

 1 class Solution {
 2 public:
 3     bool check(char * a,string& b){
 4         for(int i=0;i<5;i++){
 5             if(a[i]!=b[i]&&b[i]!='?')
 6                 return false;
 7         }
 8         return true;
 9     }
10     string maximumTime(string time) {
11         for(int i=23;i>=0;i--){
12             for(int j=59;j>=0;j--){
13                 char str[20];
14                 sprintf(str,"%02d:%02d",i,j);
15                 if(check(str,time)){
16                     return str; 
17                 }
18             }
19         }
20         return "";
21     }
22 };

解法二：找规律

 1 class Solution {
 2 public:
 3     string maximumTime(string time) {
 4         if(time[0]=='?'&&time[1]=='?'){
 5             time[0]='2';
 6             time[1]='3';
 7         }else if(time[0]!='?'&&time[1]=='?'){
 8             if(time[0]>='0'&&time[0]<='1'){
 9                 time[1]='9';
10             }else if(time[0]=='2'){
11                 time[1]='3';
12             }
13             
14         }else if(time[1]!='?'&&time[0]=='?'){
15             if(time[1]>='0'&&time[1]<='3')
16                 time[0]='2';
17             else if(time[1]>='4'&&time[1]<='9')
18                 time[0]='1';
19             
20         }
21         
22         if(time[3]=='?'&&time[4]=='?'){
23             time[3]='5';
24             time[4]='9';
25         }
26         if(time[3]!='?'&&time[4]=='?'){
27             time[4]='9';
28         }
29         if(time[3]=='?'&&time[4]!='?'){
30             time[3]='5';
31         }
32         return time;
33     }
34 };

B：枚举分界线

 1 class Solution {
 2 public:
 3     int cnta[26],cntb[26];
 4     int fun(int a[],int b[]){
 5         int res=INT_MAX;
 6         for(int i=1;i<25;i++){
 7             int t=0;
 8             for(int j=i+1;j<26;j++){
 9                 t+=a[j];
10             }
11             for(int j=i-1;j>=0;j--){
12                 t+=b[j];
13             }
14             t+=min(a[i],b[i]);
15             res=min(res,t);
16         } 
17         return res;
18     }
19     int minCharacters(string a, string b) {
20         for(auto x:a){
21             cnta[x-'a']++;
22         }
23         for(auto x:b){
24             cntb[x-'a']++;
25         }
26         int res=INT_MAX;
27         for(int i=0;i<26;i++){//条件三
28             int t=cnta[i]+cntb[i];
29             res=min(res,int(a.length()+b.length()-t));
30         }
31         res=min(res,fun(cnta,cntb));
32         res=min(res,fun(cntb,cnta));
33         return res;
34     }
35 };

C：模板题，容斥原理，二位前缀和

 1 class Solution {
 2 public:
 3     int kthLargestValue(vector<vector<int>>& matrix, int k) {
 4         vector<vector<int>> v;
 5         int n=matrix.size();
 6         int m=matrix[0].size();
 7         v.resize(n);
 8         for(int i=0;i<n;i++){
 9             v[i].resize(m);
10         }
11         vector<int> q;
12         for(int i=0;i<n;i++){
13             for(int j=0;j<m;j++){
14                 v[i][j]=matrix[i][j];
15                 if(i-1>=0)
16                     v[i][j]^=v[i-1][j];
17                 if(j-1>=0)
18                     v[i][j]^=v[i][j-1];
19                 if(i-1>=0&&j-1>=0)
20                     v[i][j]^=v[i-1][j-1];
21                 q.push_back(v[i][j]);
22             }
23         }
24         sort(q.begin(),q.end());
25         reverse(q.begin(),q.end());
26         return q[k-1];
27     }
28 };

D：思维题

第一层数目是 1

第二层数目是 1+2

第三层数目是1+2+3

首先找出层数 i ，满足sum<=n

对于多出来的，却又不够下一层的，可以发现最优策略是沿着对角线排成一行

因为如果排成一行的话，可放置的各自的数目为1+2+...+q，q为一行的数目

 1 class Solution {
 2 public:
 3     int minimumBoxes(int n) {
 4         int sum=0;
 5         int k=1,i=1;
 6         while(sum+k<=n){
 7             sum+=k;
 8             i++;
 9             k+=i;
10         }
11         int res=k-i;
12         k=1;
13         while(sum<n){
14             res++;
15             sum+=k;
16             k++;
17         }
18         return res;
19     }
20 };