Contest 158

本次竞赛四道题分别考察了栈、枚举、深度搜索以及数组统计。

1. 栈（1221. Split a String in Balanced Strings）

class Solution {
public:
    int balancedStringSplit(string s) {
        if(s.size()%2==1)   return 0;
        stack<char> st;
        int res = 0;
        for(char ele:s){
            if(st.empty()||ele==st.top())  st.push(ele);
            else st.pop();
            if(st.empty())
                res++;
        }
        return st.empty()? res:0;
    }
};

2. 枚举

3. 深度搜索（1223. Dice Roll Simulation）

class Solution {
public:
    long long cache[5002][16][6];
    const long long MOD  = 1000000000 + 7;
    vector<int> rollMax;
    int dieSimulator(int n, vector<int>& rollMax) {
        this->rollMax = rollMax;
        memset(cache, -1, sizeof(cache));
        return dfs(0, 0, n);
    }
    
    long long dfs(int k, int index, int n){
        if(n==0)    return 1;
        if(cache[n][k][index]!=-1)
            return cache[n][k][index];
        long long res = 0;
        for(int i=0; i<6; i++){
            if(index!=i)
                res += dfs(1, i, n-1);
            else if(k<rollMax[i])
                res += dfs(k+1, index, n-1);
        }
        return cache[n][k][index] = res%MOD;
    }
};

4.数组统计（1224. Maximum Equal Frequency）

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        map<int,int> cnt, fre;
        int max_app = 0;
        int res=0;
        for(int i=0; i<nums.size(); i++){
            ++cnt[nums[i]];
            ++fre[cnt[nums[i]]];
            max_app = max(max_app, cnt[nums[i]]);
            if((fre[max_app]==1 && fre[max_app-1]*(max_app-1)+1==i+1)||fre[max_app]*max_app+1==i+1)
                res=i+1;
        }
        return max_app == 1? nums.size():res;
    }
};