第 261 场周赛题解

Q1 2027. 转换字符串的最少操作次数 (opens new window)

贪心着改，遇到一个就相当于把这个和后两个都一起改了。

class Solution5890 {
    fun minimumMoves(s: String): Int {
        val arr = s.toCharArray()
        var ans = 0
        for (i in arr.indices) {
            if (arr[i] != 'O') {
                arr[i] = 'O'
                if (i + 1 in arr.indices)
                    arr[i + 1] = 'O'
                if (i + 2 in arr.indices)
                    arr[i + 2] = 'O'
                ans++
            }
        }
        return ans
    }
}

Q2 2028. 找出缺失的观测数据 (opens new window)

一层一层放，直到放没即可。

class Solution5891 {
    fun missingRolls(rolls: IntArray, mean: Int, n: Int): IntArray {
        val left = (rolls.size + n) * mean - rolls.sum()
        if (left.toDouble() / n > 6.0 || left.toDouble() / n < 1.0) {
            return intArrayOf()
        }
        val ans = IntArray(n)
        for (i in 0 until left) {
            ans[i % n]++
        }
        return ans
    }
}

Q3 2029. 石子游戏 IX (opens new window)

恶心的石子游戏又来了！

解法一：正向考虑，Alice如何必胜 or 必败。

1. 首先都是3的倍数，Alice无可选，直接输
2. 0是偶数，则对方选0我方也选0，约掉不用考虑。我方选1，对方只能选1（选0我们也选0）。之后对方选几我们就选互补值，最后对方没得选。
3. 0是奇数，我方选1，对方可以选0，然后我方选1 or 对方选1我方选0，这时消耗两个1，重新转回上述Case2的状态。

这种方法有点乱... 代码出错不易发现，可以使用下面方法二来无视逻辑，只跟规则走。

class Solution5892 {
    fun stoneGameIX(stones: IntArray): Boolean {
        val arr = IntArray(3)
        for (x in stones)
            arr[x % 3] += 1
        // Alice 先手，无石子可选
        if (arr[1] == 0 && arr[2] == 0) return false
        if (arr[0] % 2 == 0) {
            // Alice 先手，选1必胜
            if (arr[1] != 0 && arr[1] - 1 < arr[2]) return true
            // Alice 先手，选2必胜
            if (arr[2] != 0 && arr[2] - 1 < arr[1]) return true
        } else {
            // Alice 先手，选1必胜（过渡回上述状态）
            if (arr[1] != 0 && arr[2] < arr[1] - 2) return true
            if (arr[2] != 0 && arr[1] < arr[2] - 2) return true
        }
        return false
    }
}

解法二：DFS硬搜

按照规则来处理，简化Alice与Bob的判断，在所有的可能性中进行搜索。

三个数字可以进行简化，0直接%2即可。对于1与2，需要让他们减少至最小值>=1。若本身存在0，则无需简化。

这种判断不用太过思考内部逻辑，只需要处理好数据剪枝即可。

class Solution5892 {
    fun stoneGameIX(stones: IntArray): Boolean {
        val arr = IntArray(3)
        stones.forEach {
            arr[it % 3]++
        }
        if (arr[1] == 0 && arr[2] == 0) return false
        if (arr[1] != 0 || arr[2] != 0) arr[0] %= 2

        val div = 2
        val min = minOf(arr[1] / div, arr[2] / div)
        if (min != 0) {
            arr[1] -= (min - 1) * div
            arr[2] -= (min - 1) * div
        }

        val seen = HashMap<String, Boolean>()
        fun dfs(cur: Int, left: IntArray, alice: Boolean): Boolean {
            val key = "$cur, ${left.joinToString()} $alice"
            if (key in seen) return seen[key]!!

            if (cur > 0 && cur % 3 == 0) {
                return alice
            }
            if (left.sum() == 0) {
                return false
            }
            if (!alice) {
                // Bob走让Alice输的步骤
                // ans 使用 and
                var ans = true
                for (i in 0 until 3) {
                    if (left[i] == 0) continue
                    val next = left.clone() as IntArray
                    next[i]--
                    ans = ans and dfs(cur + i, next, !alice)
                }
                return ans
            }
            // Alice走能让自己赢的步骤
            // ans 使用 or
            var ans = false
            for (i in 0 until 3) {
                if (left[i] == 0) continue
                val next = left.clone() as IntArray
                next[i]--
                ans = ans or dfs((cur + i) % 3 + 3, next, !alice)
            }
            return ans.also {
                seen[key] = it
            }
        }
        return dfs(0, arr, true)
    }
}

Q4 2030. 含特定字母的最小子序列 (opens new window)

使用单调栈处理。需要计算当前栈内含有letter的字符数，以及剩余内容还有letter的总数。若总数足够，弹栈的时候才可以弹letter，否则不能弹letter。其次，要保证当前栈空余部分都塞入letter可以满足repetition。

该题目比Q3要简单，只是Q3花费时间太多，导致这题思考时间不够了。

// 单调栈
class Solution5893 {
    fun smallestSubsequence(s: String, k: Int, letter: Char, repetition: Int): String {
        val st = Stack<Char>()
        // 剩余letter
        var lst = s.count { it == letter }
        // 当前持有letter
        var cur = 0
        for (i in s.indices) {
            // 1. 满足总长度k
            // 2. 满足字符重复repetition
            while (st.isNotEmpty() && s[i] < st.peek() && st.size + s.length - i > k) {
                if (st.peek() == letter) {
                    if (cur + lst > repetition) {
                        cur--
                        st.pop()
                    } else {
                        break
                    }
                } else {
                    st.pop()
                }
            }

            st.push(s[i])
            if (s[i] == letter) {
                cur++
                lst--
            }
            if (st.size > k) {
                if (st.peek() == letter) cur--
                st.pop()
            }
            // 腾出足够的位置给letter
            while (st.isNotEmpty() && k - st.size < repetition - cur) {
                if (st.peek() == letter) cur--
                st.pop()
            }
        }
        return st.joinToString("")
    }
}