Weekly Contest 158

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

1221. Split a String in Balanced Strings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int balancedStringSplit(string s) {
        int l=0, r=0;
        int count = 0;
        for(auto i: s){
            if(i == 'L')
                l++;
            else
                r++;
            if(l == r && l!=0){
                count++;
                l = 0;
                r = 0;
            }
        }
        return count;
    }
};

1222. Queens That Can Attack the King

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
class Solution {
public:
    vector<vector<int>> ret;
    void helper(vector<vector<int>> &queens, int i, int j, int deli, int delj){
        if(i<0 || j<0 || i>=8 || j>=8)
            return;
        if(queens[i][j]){
            vector<int> ret1;
            ret1.push_back(i);
            ret1.push_back(j);
            ret.push_back(ret1);
            return;
        }
        helper(queens, i+deli, j+delj, deli, delj);
    }
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        vector<vector<int>> gh(10, vector<int>(10, 0));
        for(auto i: queens){
            gh[i[0]][i[1]] = 1;
        }
        helper(gh, king[0], king[1], -1, -1);
        helper(gh, king[0], king[1],  0, -1);
        helper(gh, king[0], king[1],  1, -1);
        helper(gh, king[0], king[1],  1,  0);
        helper(gh, king[0], king[1],  1,  1);
        helper(gh, king[0], king[1],  0,  1);
        helper(gh, king[0], king[1], -1,  1);
        helper(gh, king[0], king[1], -1,  0);
        return ret;
    }
};

1223. Dice Roll Simulation

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
class Solution {
public:
    typedef long long LL;
    LL dp[5002][16][6];
    LL mod = 1000000000 + 7;
    vector<int> rollMax;
    
    LL dfs(int k, int index, int n){
        if(n==0){
            return 1;
        }
        if(dp[n][k][index] != -1){
            return dp[n][k][index];
        }
        LL ans = 0;
        for(int i=0; i<6; i++){
            if(index != i){
                ans += dfs(1, i, n-1);
            }
            else if(k < rollMax[i]){
                ans += dfs(k+1, i, n-1);
            }
            else{
                
            }
        }
        return dp[n][k][index] = ans % mod;
    }
    
    int dieSimulator(int n, vector<int>& rollMax) {
        this->rollMax = rollMax;
        LL ans = 0;
        memset(dp, -1, sizeof(dp));
        return dfs(0, 0, n);
    }
};

1224. Maximum Equal Frequency

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
    map<int, int>count;
    map<int, int> m;
    bool check() const{
        
        if(m.size() == 1){//只出现一个数字
            return true;
        }
        
        //出现很多数字，但是都次数都是1
        if(count.size() == 1 && count.begin()->first == 1){
            return true;
        }
        
        if(count.size() != 2){
            return false;
        }
        
        auto one = count.begin();
        auto two = one;
        two++;
        
        //只有一个数字出现一次，其他都出现多次，且次数相等
        if(one->second == 1 && one->first ==1){
            return true;
        }
        if(two->second == 1 && two->first ==1){
            return true;
        }
        
        //所有数字都出现多次，但是大多数次数都相等，只有一个特殊多了一次
        if(one->second == 1 && one->first - 1 == two->first){
            return true;
        }
        if(two->second == 1 && two->first - 1 == one->first){
            return true;
        }
        
        return false;
    }
public:
    int maxEqualFreq(vector<int>& nums) {
        int ans = 1;
        for(int i=0;i<nums.size();i++){
            int old = m[nums[i]];
            m[nums[i]]++;
            
            //维护前缀
            if(count.find(old) != count.end()){
                count[old]--;
                if(count[old] == 0){
                    count.erase(old);
                }
            }
            count[m[nums[i]]]++;
            
            if(check()){
                ans = i + 1;
            }
        }
        
        return ans;
    }
};
Donate? comment?