第 245 场周赛题解

Q1 1897. 重新分配字符使所有字符串都相等 (opens new window)

看每一个字母是否能被整除。

class Solution1897 {
    fun makeEqual(words: Array<String>): Boolean {
        val n = words.size
        val cur = IntArray(26)
        words.forEach {
            it.forEach {
                cur[it - 'a']++
            }
        }
        return cur.all { it % n == 0 }
    }
}

Q2 1898. 可移除字符的最大数目 (opens new window)

上来就想到用二分，但是一直超时... 最后发现是生生的用$ArrayList$的$removeAt$操作，改为用$StringBuilder$的$setCharAt$或直接用数组记录$index$，在子序列判断过程中跳过这些即可。要吸取教训啊！

class Solution1898 {
    fun maximumRemovals(s: String, p: String, removable: IntArray): Int {
        fun check(k: Int): Boolean {
            // 教训：String操作要用StringBuilder
            val str = StringBuilder(s)
            removable.take(k).forEach {
                str.setCharAt(it, ' ')
            }
            return p.isSubSeqOf(str.toString())
        }

        var left = 0
        var right = removable.size
        while (left + 1 < right) {
            val mid = (left + right).ushr(1)
            when {
                check(mid) -> left = mid
                else -> right = mid
            }
        }
        return if (check(right)) {
            right
        } else {
            left
        }
    }
}

fun String.isSubSeqOf(target: String): Boolean {
    var x = 0
    var y = 0
    while (x < this.length && y < target.length) {
        if (this[x] == target[y]) {
            x++
            y++
        } else {
            y++
        }
    }
    return x == this.length
}

Q3 1899. 合并若干三元组以形成目标三元组 (opens new window)

一句就行，只取三元组三者数据都小于等于$target$，再判断它们当中的最大值能否满足实现$target$。

class Solution1899 {
    fun mergeTriplets(triplets: Array<IntArray>, target: IntArray): Boolean {
        return triplets.filter { it[0] <= target[0] && it[1] <= target[1] && it[2] <= target[2] }.let {
            it.any { it[0] == target[0] } && it.any { it[1] == target[1] } && it.any { it[2] == target[2] }
        }
    }
}

Q4 1900. 最佳运动员的比拼回合 (opens new window)

硬$DFS$暴力即可。队伍最多$20$个，且比赛只能最左和最右比，因此状态数很有限，递归足够满足时间复杂度。两侧的参数分别是，当前轮次还未比完的队伍 和 比赛完进入下一轮的队伍。其他的按照题意模拟即可。

class Solution5787 {
    fun earliestAndLatest(n: Int, firstPlayer: Int, secondPlayer: Int): IntArray {
        val arr = ArrayList<Int>()
        for (i in 1..n) arr.add(i)

        fun dfs(left: ArrayList<Int>, right: ArrayList<Int>, step: Int): Pair<Int, Int> {
            if (left.isEmpty()) {
                return dfs(ArrayList(right.sorted()), arrayListOf(), step + 1)
            }
            if (left.size == 1) {
                right.add(left[0])
                return dfs(ArrayList(right.sorted()), arrayListOf(), step + 1)
            }
            val a = left.removeAt(0)
            val b = left.removeAt(left.lastIndex)
            if (a == firstPlayer && b == secondPlayer) {
                return Pair(step, step)
            } else if (a == firstPlayer || a == secondPlayer) {
                right.add(a)
                return dfs(ArrayList(left), ArrayList(right), step)
            } else if (b == firstPlayer || b == secondPlayer) {
                right.add(b)
                return dfs(ArrayList(left), ArrayList(right), step)
            } else {
                right.add(a)
                val x = dfs(ArrayList(left), ArrayList(right), step)
                right.remove(a)
                right.add(b)
                val y = dfs(ArrayList(left), ArrayList(right), step)
                return Pair(minOf(x.first, y.first), maxOf(x.second, y.second))
            }
        }
        return dfs(arr, arrayListOf<Int>(), 1).toList().toIntArray()
    }
}