讨论/题目交流/🏆 第 158 场力扣周赛/
🏆 第 158 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

分割平衡字符串
可以攻击国王的皇后
掷骰子模拟
最大相等频率

展开讨论
共 14 个讨论

先占坑,题解稍晚来,比赛还没结束就不说太明白了~:

  • 分割平衡字符串
    由于原串已经是平衡的了,我们遍历原串,记录当前 LLRR 的数量差,如果数量差为 00 就表示可以以当前位置作为一个分割点。

  • 可以攻击国王的皇后
    从国王的位置沿 88 个方向搜索,每个碰到第一个王后的位置就停止并记录结果,因为再靠后的位置会被挡住。

  • 掷骰子模拟
    dp[i][j]dp[i][j] 表示丢 ii 次,最后一次的数字是 jj 的方法总数,那么我们可以枚举这一次丢的数字 kk 和次数 ll,对应的转移到新状态 dp[i+l][k]dp[i+l][k]。时间复杂度为 O(66n15)O(6*6*n*15)
    PS:上述复杂度可以通过题目,但是该题有非常多的优化空间,详细题解我们再来讨论。

  • 最大相等频率
    维护两个dict,第一个dict记录每个数字的频次,第二个count_dict记录每个频次的数量,然后遍历原数组,维护这两个dict。在第 ii 位遍历完以后,如果存在以下情况之一,则前 ii 位是一个合法的要求前缀。

    1. len(count_dict) == 1 且该频次出现次数为 1 或者频次值为 1。对应多个数出现一次或者一个数出现多次的情况。
    2. len(count_dict) == 2 且大频次正好是小频次 -1,且大频次数量正好是 1。对应比如所有数都出现 2 次,只有一个数出现 3 次,这个时候我们可以删去一个数来保持所有数频次一致。
      时间复杂度为O(n)。
    3. (感谢@sunsky提醒) len(count_dict) == 2 且小频次数量为 1 时,我们可以通过删去小频次数来满足题目要求。
14

第三题纠结了好久,终于理解了。

class Solution:
    def dieSimulator(self, n: int, rollMax):
        MOD = 10 ** 9 + 7
        nums = [[[0 for _ in range(16)] for _ in range(6)] for _ in range(n)]
        for i in range(6):
            nums[0][i][1] = 1
        for i in range(1,n): # 第i次掷骰子,0-start
            for j in range(6): # 第i次掷出j点,j=0~5表示1-6点
                for k in range(6): # 第i-1掷出k点,k=0~5表示1-6点
                    if j!=k: # 若i次与i-1次点数不同,无需考虑重复问题,因为每个数字至少可连续出现一次(rollMax>=1)
                        nums[i][j][1] += sum(nums[i-1][k]) % MOD # 对第i-1次掷出k点的情况,无论是连续的第几次,都求和;此处暗含两次求和,一个是数组第三维由sum()求和,另一个是随着k的循环,不断累加得出nums[i][j][1]的值
                    else:
                        for m in range(2,rollMax[j-1]+1): # 若k与j相同,即当前点数与上一次点数相同,则需考察连续次数小于rollMax[j-1]的情况;在第i次连续掷出j点m次的序列数等于在第i-1次连续掷出j点m-1次的序列数量。
                            nums[i][j][m] = nums[i-1][j][m-1]
        ans = [0,0,0,0,0,0]
        for j in range(6):
            ans[j] = sum(nums[-1][j]) % MOD
        return sum(ans) % MOD
2

5224. 掷骰子模拟

原题链接

dp[i][j][k] 表示第 i 轮掷骰子掷出数字 jj 连续出现 k 次的组合数量。

那么有状态转移如下:

j 并非在连续出现时(即 k == 1 时):

// j 出现 1 次的组合数等于上一轮投出非数字 j 的所有情况和
dp[i][j][1] = sum(dp[i - 1][other != j][:])

j 连续出现 k(k > 1) 次时:

if k <= rollMax[j]:
    // 本轮投出连续出现 k 次数字 j 的情况数量等于:上一轮连续投掷出 k - 1 次 j 的情况数量
    dp[i][j][k] = dp[i - 1][j][k - 1]

ps:很多同学说测试用例是错的,可能是因为理解错题意了,题目说的是 连续 掷出数字 i 的次数不能超过 rollMax[i],而不是数字的投掷总数。

具体实现:

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[[0 for _ in range(16)] for _ in range(7)] for _ in range(n + 1)]
        mod = 10**9 + 7
                
        for i in range(1, n + 1):
            # 投掷的数
            for j in range(1, 7):
                # 第一次投掷
                if i == 1:
                    dp[i][j][1] = 1
                    continue
                
                # 数字 j 连续出现 k 次
                for k in range(2, rollMax[j - 1] + 1):
                    dp[i][j][k] = dp[i - 1][j][k - 1]
                    
                # 前一次投出的数不是 j
                s = 0
                for l in range(1, 7):
                    if l == j:
                        continue
                    for k in range(1, 16):
                        s += dp[i - 1][l][k]
                        s %= mod
                dp[i][j][1] = s
        
        res = 0
        for j in range(1, 7):
            for k in range(1, 16):
                # 求投掷 n 次时所有组合总和
                res += dp[n][j][k]
                res %= mod
                
        return res
2

第 158 场力扣周赛
有没有小伙伴解释一下第一题如果输入是"RRLRRLRLLLRL",输出为什么是2?
我的代码如下:
class Solution {
public:
int count(string s, int n)
{
if(!n)
return 0;
if(n==1)
return 0;
if(s[n-2] == s[n-1])
return count(s, n-1);
else
return count(s, n-2) + 1;

}
int balancedStringSplit(string s) {
    int result=0;
    result = count(s,s.length());
    return result;
}

};
没有想明白

1

最后一题,考虑三种情况:
1、前缀数组中所有数字的频率只有两种,设为A和B,其中A=B+1,且只有一个数字频率为A;
2、前缀数组中所有数字的频率只有两种,其中只有一个数字的频率为1,其他数字的频率都大于1且相等;
3、整个数组的数字的频率都是1。

对应的处理:
1、把前缀数组中频率为A的数字删去1个即可;
2、把前缀数组中频率为1的数字删去即可;
3、整个数组删去任意一个数字都可。

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

第三题,扔色子.
我的思路很简单,用一个三维数组表示的话。v[k][i][j]表示第k轮扔出i点的骰子,并且这个点数已经连续出现j次时的序列的个数。
如果下一轮的点数和这一轮最后的点数不同的时候:v[k+1][c][1] += v[k][i][j]
如果下一轮的点数和这一轮最后的点数相同并且依然不超过这个点最大的可连续限制的时候:v[k+1][i][j+1] += v[k][i][j]
当然,别忘记取模。
而且由于强迫症,不喜欢开三维的数组,所以用了两维的数组只记录一轮的结果。

class Solution {
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        vector<vector<int> > ve(6, vector<int>(16, 0));
        int mo = 1000000007;
        for(int i=0; i<6; i++)
        {
            ve[i][1] = 1;
        }
        for(int k=2; k<=n; k++)
        {
            vector<vector<int> > t(6, vector<int>(16, 0));
            for(int i=0; i<6; i++)
            {
                for(int j=1; j<ve[i].size()&&j<k; j++)
                {
                    for(int c=0; c<6; c++)
                    {
                        if(c!=i)
                            t[c][1] = (t[c][1] + ve[i][j])%mo;
                        else if(j<rollMax[i])
                            t[c][j+1] = (t[c][j+1] + ve[i][j])%mo;
                    }
                }
            }
            ve.clear();
            ve = t;
        }
        int res = 0;
        for(int i=0; i<6; i++)
        {
            for(int j=0; j<ve[i].size(); j++)
            {
                res = (res + ve[i][j])%mo;
            }
        }
        return res;
    }
};
1

image.png
????

我的思路比较笨,想和大家交流学习下:
第一题我用遍历做的,比较l,r次数等不等就好;
第二题用国王从八个方向去找皇后,如果找到一个就停止该方向寻找;
第三题没想出来,想用排列组合来做,但是感觉去重太麻烦;
第四题用了两个数组分别存储某个数字出现的次数,和出现某次的数字个数,然后在遍历过程中判断即可,判断条件稍微麻烦些。

第三题答案少了两个。。哪位大佬帮忙看下错误在哪?image.png

掷色子问题
我用的是dfs 调试挺长时间不知道问题出在哪里了 测试用例三 总是166个 不是181个

class Solution {
public:
    int tn;
    long long MAXN=1e9+7;
    long long ret;
    vector<int> rol;
    void dfs(int times,vector<int>& tmp){
        if(times==tn){ ret++; ret=ret%MAXN; return;}
        for(int i=0;i<6;i++){
            if(tmp[i]>=rol[i]) continue;
            tmp[i]++;
            dfs(times+1,tmp);
            tmp[i]--;
        }
        
    }
    int dieSimulator(int n, vector<int>& rollMax) {
        tn = n;
        rol = rollMax;
        vector<int> tmp(6,0);
        dfs(0,tmp);
        return ret;
    }
};