第 258 场周赛题解

Q1 2000. 反转单词前缀 (opens new window)

模拟，需要注意$subString$是左闭右开区间。

class Solution5867 {
    fun reversePrefix(word: String, ch: Char): String {
        val index = word.indexOf(ch)
        if (index < 0) return word
        return word.substring(0, index + 1).reversed() + word.substring(index + 1, word.length)
    }
}

Q2 2001. 可互换矩形的组数 (opens new window)

很多类似题目，结果还是被$Int$坑了一把... 以后能用$Long$就用$Long$。

class Solution5868 {
    fun interchangeableRectangles(rectangles: Array<IntArray>): Long {
        val map = HashMap<Double, Long>()
        rectangles.forEach {
            val cur = it[0].toDouble() / it[1].toDouble()
            map[cur] = map.getOrDefault(cur, 0) + 1L
        }
        var ans = 0L
        map.forEach { t, u ->
            ans += u * (u - 1)
        }
        return ans / 2
    }
}

Q3 2002. 两个回文子序列长度的最大乘积 (opens new window)

枚举全部状态，计算其中最大值即可。

class Solution5869 {
    fun maxProduct(s: String): Int {
        var ans = 1
        fun dfs(i: Int, l: String, r: String) {
            if (i == s.length) {
                if (l.isPalindrome() && r.isPalindrome())
                    ans = maxOf(ans, l.length * r.length)
                return
            }
            dfs(i + 1, l + s[i], r)
            dfs(i + 1, l, r + s[i])
            dfs(i + 1, l, r)
        }
        dfs(0, "", "")
        return ans
    }
}

Q4 2003. 每棵子树内缺失的最小基因值 (opens new window)

启发式搜索... 就是集合合并时，将小的$add$到大的里，这样执行的操作会少一些... 就差个这玩意，没$A$... 讨厌这种细节...

class Solution5870 {
    fun smallestMissingValueSubtree(parents: IntArray, nums: IntArray): IntArray {
        val n = parents.size
        val nodeList = Array<NTreeNode>(n) { i -> NTreeNode(nums[i], i) }

        for (i in parents.indices) {
            if (parents[i] != -1) {
                nodeList[parents[i]].children.add(nodeList[i])
                nodeList[i].parent = nodeList[parents[i]]
            }
        }

        val ans = IntArray(n) { 1 }
        fun dfs(root: NTreeNode): Pair<HashSet<Int>, Int> {
            var cur = HashSet<Int>()
            var tmp = HashSet<Int>()
            var max = 1
            root.children.forEach {
                dfs(it).also {
                    tmp = it.first
                    if (cur.size >= tmp.size) {
                        cur.addAll(tmp)
                    } else {
                        tmp.addAll(cur)
                        cur = tmp
                    }
                    max = maxOf(max, it.second)
                }
            }
            cur.add(root.`val`)
            while (max in cur) {
                max++
            }
            ans[root.index] = max
            return Pair(cur, max)
        }
        dfs(nodeList[0])
        return ans
    }
}