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

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

image.png

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

展开讨论

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

  • 分割平衡字符串
    由于原串已经是平衡的了,我们遍历原串,记录当前 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
展开全部 14 讨论