LeetCode笔记：Weekly Contest 261

• LeetCode笔记：Weekly Contest 261
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四

给出题目一的试题链接如下：

• 2027. Minimum Moves to Convert String

这一题我们用贪婪算法即可求解。

我们从左向右遍历，如果发现一个X，就需要进行一次变换，此时无论后方字母是啥，后续两个字符都会被修正，因此我们只需要继续从i+3个位置开始考察即可。

给出python代码实现如下：

class Solution:
    def minimumMoves(self, s: str) -> int:
        i, n = 0, len(s)
        res = 0
        while i < n:
            if s[i] == "O":
                i += 1
            else:
                res += 1
                i += 3
        return res

提交代码评测得到：耗时32ms，占用内存14.1MB。

给出题目二的试题链接如下：

• 2028. Find Missing Observations

这一题我们很容易就能够计算出剩余没有出现的n个元素的总和，记为s，显然，如果 s > 6 n s > 6n s>6n或者 s < n s < n s

对于剩下的情况，我们总可以给出一种构造方式为a个6，c个1以及剩下一个元素b。

此时我们可以给出条件如下：
{ 6 a + b + c = s a + 1 + c = n left{ begin{aligned} 6a + b + c & = s \ a + 1 + c & = n end{aligned} right. {6a+b+ca+1+c​=s=n​

此时我们计算即可得到abc的结果。

给出python代码实现如下：

class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
        m = len(rolls)
        s = (n+m) * mean - sum(rolls)
        if s > 6 * n or s < n:
            return []
        elif s == 6*n:
            return [6] * n
        a = (s-n) // 5
        c = n -1 - a
        b = s - 6*a - c
        return [6] * a + [b] + [1] * c

提交代码评测得到：耗时1492ms，占用内存25.2MB。

给出题目三的试题链接如下：

• 2029. Stone Game IX

这一题考察的其实就是一个必胜策略。

由于我们考虑的是和对于3的余数，因此，我们事实上只要考虑所有数字对于3的余数，然后进行数目统计即可。

要想使得游戏继续，刨除掉余数为0的情况，可能的序列只有两种：

1. 1121212121212……
2. 2212121212121……

我们分别考虑先取1或者先取2的情况，而对于每一种情况。

我们首先考虑先取1的情况，此时又需要考虑余数为0的情况，如果其数量模2为0，那么就可以直接忽略，因为无论如何Alice都可以将情况恢复至变换之前，因此，Alice要取的永远都是2，我们只需要2的数目多于剩余的1的数目即可；反之，如果模为1，那么情况就会反转，Alice要取的数会变成1，此时我们要求1的数目至少需要比2的数目多2。

同理，我们可以分析得到先取2时的情况。

给出python代码实现如下：

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        cnt = defaultdict(int)
        for k in stones:
            cnt[k % 3] += 1
        
        if cnt[1] > 0:
            if cnt[0] % 2 == 0:
                if cnt[2] > cnt[1]-1:
                    return True
            else:
                if cnt[1]-2 > cnt[2]:
                    return True
        if cnt[2] > 0:
            if cnt[0] % 2 == 0:
                if cnt[1] > cnt[2]-1:
                    return True
            else:
                if cnt[2]-2 > cnt[1]:
                    return True
        
        return False

提交代码评测得到：耗时1903ms，占用内存28MB。

给出题目四的试题链接如下：

• 2030. Smallest K-Length Subsequence With Occurrences of a Letter

pass

这一题不想看了，算是休息一下吧。