第 264 场周赛题解

Q1 5906. 句子中的有效单词数 (opens new window)

模拟。这Q1恶心的想吐。

class Solution5906 {
    fun countValidWords(sentence: String): Int {
        fun check(str: String): Boolean {
            var ans = true
            if (str.isEmpty()) {
                ans = false
            }
            if (('0'..'9').any { n -> n in str }) {
                ans = false
            }
            if ('-' in str) {
                if (str.count { it == '-' } > 1) ans = false
                else {
                    val index = str.indexOf('-')
                    if (index == 0 || index == str.lastIndex) ans = false
                    else {
                        if (!str[index - 1].isLetter()
                            || str[index - 1].isUpperCase()
                            || str[index + 1].isUpperCase()
                            || !str[index + 1].isLetter()
                        ) {
                            ans = false
                        }
                    }
                }
            }
            val arr = arrayOf('!', '.', ',')
            if (str.count { it in arr } > 1) {
                ans = false
            } else if (str.count { it in arr } == 1) {
                if (str.last() !in arr) {
                    ans = false
                }
            }
            return ans
        }
        return sentence.split(" ").count {
            check(it)
        }
    }
}

Q2 5907. 下一个更大的数值平衡数 (opens new window)

可以用i++的暴力处理，也可以先将所有可能的值计算处理，二分查找。

class Solution5907 {
    fun nextBeautifulNumber(n: Int): Int {
        val ts = TreeSet<Int>()

        val list = ArrayList<ArrayList<Int>>()
        for (i in 1..6) {
            val cur = arrayListOf<Int>()
            repeat(i) {
                cur.add(i)
            }
            list.add(cur)
        }
        for (mask in 1 until (1 shl 6)) {
            val state = ArrayList<Int>()
            for (i in 0 until 6) {
                if (mask and (1 shl i) != 0) {
                    state.addAll(list[i])
                }
            }
            if (state.size <= 7) {
                state.toIntArray().permuteUnique().forEach {
                    ts.add(it.joinToString("").toInt())
                }
            }
        }

        return ts.ceiling(n + 1)!!
    }
}

Q3 2049. 统计最高分的节点数目 (opens new window)

构造树之后，直接计算左子树和右子树的结点数目，DFS遍历即可。

class Solution5908 {
    fun countHighestScoreNodes(parents: IntArray): Int {
        val n = parents.size
        val root = TreeNode(0)

        val map = HashMap<Int, ArrayList<Int>>()
        for (i in parents.indices) {
            map[parents[i]] = map.getOrDefault(parents[i], arrayListOf())
            map[parents[i]]!!.add(i)
        }

        // 通过parents数组，构建二叉树
        val queue: Queue<Pair<Int, TreeNode>> = LinkedList<Pair<Int, TreeNode>>()
        queue.add(Pair(0, root))
        while (queue.isNotEmpty()) {
            val size = queue.size
            for (k in 0 until size) {
                val item = queue.poll()
                val node = item.second

                map[item.first]?.forEach {
                    val next = TreeNode(it)
                    if (node.left == null) node.left = next
                    else if (node.right == null) node.right = next
                    queue.offer(Pair(it, next))
                }
            }
        }

        // 获取所有节点的儿子数（包含自己）
        val seen = HashMap<TreeNode, Int>()
        fun TreeNode?.count(): Int = if (this == null) {
            0
        } else if (this in seen) {
            seen[this]!!
        } else {
            (1 + this.left.count() + this.right.count()).also {
                seen[this] = it
            }
        }

        var max = -1L
        var ans = 0
        fun dfs(node: TreeNode?) {
            if (node == null) return

            var left = node.left.count()
            var right = node.right.count()
            var top = n - left - right - 1
            if (left == 0) left = 1
            if (right == 0) right = 1
            if (top == 0) top = 1
            val cur = top.toLong() * left * right
            if (cur > max) {
                max = cur
                ans = 1
            } else if (cur == max) {
                ans++
            }

            dfs(node.left)
            dfs(node.right)
        }

        dfs(root)
        return ans
    }
}

Q4 2050. 并行课程 III (opens new window)

Q4反而是本场比赛最简单的一道题... 没有任何花样，直接DFS遍历即可。

class Solution5909 {
    fun minimumTime(n: Int, relations: Array<IntArray>, time: IntArray): Int {
        val edges = HashMap<Int, ArrayList<Int>>()
        relations.forEach {
            edges[it[1]] = edges.getOrDefault(it[1], arrayListOf())
            edges[it[1]]!!.add(it[0])
        }

        val seen = IntArray(n + 1)

        fun dfs(cur: Int): Int {
            if (seen[cur] != 0) return seen[cur]

            var max = 0
            edges.getOrDefault(cur, arrayListOf()).forEach {
                max = maxOf(max, dfs(it))
            }
            max += time[cur - 1]
            return max.also {
                seen[cur] = max
            }
        }

        for (i in 1..n) {
            dfs(i)
        }

//        seen.print()
//        return seen.max()!!
        return seen.maxOrNull()!!
    }
}