第 175 场周赛

Posted on | In , | |
Words count in article: 680 | Reading time ≈ 3

5332. 检查整数及其两倍数是否存在

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        for(int i=0; i<arr.size(); i++){
            for(int j=i+1; j<arr.size(); j++){
                if(arr[i] == arr[j]*2 || arr[j] == arr[i]*2)
                    return true;
            }
        }
        return false;
    }
};

5333. 制造字母异位词的最小步骤数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> mp1(26);
        vector<int> mp2(26);
        for(int i=0; i<s.size(); i++){
            mp1[s[i]-'a']++;
            mp2[t[i]-'a']++;
        }
        int count = 0;
        for(int i=0; i<26; i++){
            int cur = mp1[i]-mp2[i];
            if(cur > 0) count += cur;
        }
        return count;
    }
};

1348. 推文计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class TweetCounts {
public:
    unordered_map<string,set<int> > r;
    TweetCounts() {
        
    }
    void recordTweet(string tn, int time) {
        r[tn].insert(time);
    }
    vector<int> getTweetCountsPerFrequency(string freq, string tn, int st, int et) {
        int f;
        if(freq=="minute")f = 60;
        else if(freq=="hour")f = 3600;
        else f = 86400;
        vector<int> res((et-st+f)/f);
        for(auto t:r[tn]){
            if(t>=st&&t<=et){
                int it = (t-st)/f;
                res[it]++;
            }
        }
        return res;
    }
};

5335. 参加考试的最大学生数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    int maxStudents(vector<vector<char>>& seats) {
        int m=seats.size();
        int n=seats[0].size();
        vector<vector<int>> dp(m+1,vector<int>(1<<n));  //初始化

        for(int row=1;row<=m;row++){
            for(int s=0;s<(1<<n);s++){//遍历 2^n 个状态
                bitset<8> bs(s);//记录对应状态的bit位
                bool ok=true;
                for(int j=0;j<n;j++){
                    if((bs[j] && seats[row-1][j]=='#') || (j<n-1 && bs[j] && bs[j+1])){//不能坐在坏椅子上也不能在同一行相邻坐
                        ok=false;
                        break;
                    }
                }
                if(!ok){
                    dp[row][s]=-1;//说明坐在坏椅子上或相邻坐了，该状态舍弃
                    continue;
                }
                for(int last=0;last<(1<<n);last++){//找到一种当前行的可行状态后，遍历上一行的所有状态
                    if(dp[row-1][last]==-1)//上一行的状态被舍弃了，那就直接下一个状态
                        continue;
                    bitset<8> lbs(last);
                    bool flag=true;
                    for(int j=0;j<n;j++){
                        if(lbs[j] && ((j>0 && bs[j-1]) || (j<n-1 && bs[j+1]))){//如果找到的这个上一行状态的j位置坐了人，
                            flag=false;                                    //下一行的j+1位置或j-1位置也坐了人，那么该状态不合法，舍弃
                            break;
                        }
                    }
                    if(flag){//flag为真说明这个last状态的每个位置都合法
                        dp[row][s]=max(dp[row][s],dp[row-1][last]+(int)bs.count());//转移方程
                    }
                }

            }
        }
        int res=0;
        for(int i=0;i<(1<<n);i++){//在最后一行的所有状态中找出最大的
            if(dp[m][i]>res){
                res=dp[m][i];
            }
        }
        return res;
    }
};
Donate? comment?