第 228 场周赛题解

Q1 5676. 生成交替二进制字符串的最少操作数 (opens new window)

根据题意，最终的字符串只可能是“010101...” or "101010..."。因此，我们直接用两种结果倒着推，看有多少字符不匹配的。直接使用异或运算可以减少一些代码行数。

class Solution5676 {
    fun minOperations(s: String): Int {
        fun dfs(ch: Char): Int {
            var ans = 0
            for (i in s.indices) {
                if ((i % 2 == 0) xor (s[i] == ch)) {
                    ans++
                }
            }
            return ans
        }
        return minOf(dfs('0'), dfs('1'))
    }
}

Q2 5677. 统计同构子字符串的数目 (opens new window)

遇到过很多次的经典题目，正常计算即可。有些算法需要注意结尾元素的处理。

class Solution5677 {
    fun countHomogenous(s: String): Int {
        val mod = 1000000007L
        var ans = 0L
        var left = s[0]
        var cnt = 0
        s.forEach {
            if (it == left) {
                cnt++
                ans += cnt
            } else {
                cnt = 1
                left = it
                ans++
            }
        }
        return (ans % mod).toInt()
    }
}

Q3 5678. 袋子里最少数目的球 (opens new window)

二分查找，与之前的坐船、运货等题目类似。基本上只要想到二分就很快能做出来了。

需要注意check函数的计算，对于可以整除的数字，操作会少一步（大佬们都用 (n - 1)/ mid来计算）。

class Solution5678 {
    fun minimumSize(nums: IntArray, maxOperations: Int): Int {
        fun check(mid: Int): Boolean {
            var ans = 0
            nums.forEach {
                if (it > mid) {
                    ans += it / mid
                    if (it % mid == 0) ans--
                }
            }
            return ans <= maxOperations
        }

        var left = 1
        var right = nums.max()!!
        while (left + 1 < right) {
            val mid = (left + right).ushr(1)
            when {
                check(mid) -> right = mid
                else -> left = mid
            }
        }
        return if (check(left)) {
            left
        } else {
            right
        }
    }
}

Q4 5679. 一个图中连通三元组的最小度数 (opens new window)

5分的Q4确实少见，比赛中直接硬暴力就过了。实际上可以用空间换时间，开二维的400*400的数组。能够快速查找到两个点是否有边。这样直接三重循环即可判断三个点是否互相连接。同时记录出3个点的总入度，它们的和减去3个点内部的6个入度即是答案。

class Solution5679 {
    fun minTrioDegree(n: Int, edges: Array<IntArray>): Int {
        val map = HashMap<Int, Int>()
        val matrix = Array<BooleanArray>(n + 1) { BooleanArray(n + 1) { false } }
        for (i in 1..n) map[i] = 0
        edges.forEach {
            map[it[0]] = map[it[0]]!! + 1
            map[it[1]] = map[it[1]]!! + 1
            matrix[it[0]][it[1]] = true
            matrix[it[1]][it[0]] = true
        }
        var ans = Int.MAX_VALUE
        for (i in 1..n - 2) {
            for (j in i + 1..n - 1) {
                if (matrix[i][j]) {
                    for (k in j + 1..n) {
                        if (matrix[i][k] && matrix[j][k])
                            ans = minOf(ans, map[i]!! + map[j]!! + map[k]!! - 6)
                    }
                }
            }
        }
        return if (ans == Int.MAX_VALUE) -1 else ans
    }
}