第 249 场周赛题解

Q1 1929. 数组串联 (opens new window)

生拼，之前都不知道$IntArray$的这种操作，又涨知识了！

class Solution1929 {
    fun getConcatenation(nums: IntArray): IntArray {
        return nums + nums
    }
}

Q2 1930. 长度为 3 的不同回文子序列 (opens new window)

寻找的只是长度为3的，那么直接遍历$a..z$，寻找以相同字母最开头和最结尾的中间包含多少个不同的字母，每种字母则可凑成一个长度为3的回文。

class Solution1930 {
    fun countPalindromicSubsequence(s: String): Int {
        var ans = 0
        for (i in 'a'..'z') {
            var c = 0
            var start = false
            val cur = BooleanArray(26)
            s.forEach {
                if (it == i) {
                    if (!start) {
                        start = true
                    } else {
                        c = cur.count { it }
                        cur[it - 'a'] = true
                    }
                } else {
                    if (start) cur[it - 'a'] = true
                }
            }
            ans += c
        }
        return ans
    }
}

Q3 1931. 用三种不同颜色为网格涂色 (opens new window)

被之前的题欺骗了，一直在推到公式，结果$1h$过去了，推的头都大了。

直接$DFS$暴力做即可，把所有可能的字符串展示出来，每一层对应的下一层有几种也直接暴力计算。

注意$memo$的Key用层级和当前字符串，减少时间复杂度。

class Solution1931 {
    fun colorTheGrid(m: Int, n: Int): Int {
        val mod = 1000000007L

        var set = hashSetOf<String>("1", "2", "3")
        repeat(m - 1) {
            val next = hashSetOf<String>()
            for (i in '1'..'3') {
                set.forEach {
                    if (it.last() != i) {
                        next.add("$it$i")
                    }
                }
            }
            set = next
        }

        val map = HashMap<String, ArrayList<String>>()
        set.forEach { a ->
            map[a] = arrayListOf()
            set.forEach { b ->
                if ((0 until m).all { a[it] != b[it] }) {
                    map[a]!!.add(b)
                }
            }
        }

        var ans = 0L
        val seen = HashMap<String, Long>()
        fun dfs(cur: String, level: Int): Long {
            val key = "${cur}_$level"
            if (key in seen) {
                return seen[key]!!
            }
            if (level == n) return 1L
            var ans = 0L
            map[cur]!!.forEach {
                ans += dfs(it, level + 1)
                ans %= mod
            }
            return ans.also {
                seen[key] = it
            }
        }
        set.forEach {
            ans += dfs(it, 1)
            ans %= mod
        }
        return (ans % mod).toInt()
    }
}

Q4 1932. 合并多棵二叉搜索树 (opens new window)

首先，明确合成的二叉搜索树是严格大于小于，因此合成后的树一定每个节点的值不同。且题意中有说每个根节点不同，则可以确认除了$n - 1$个连接用的点，其他的点的$value$都不会重复。

确认了点不会重复，那么可以确认根节点，然后通过$DFS$尝试将所有可连接的树都连接在一起，只会有一种拼接方法。拼接完成后，看拼接后的树的总节点数是不是拼接前的总结点数 + n - 1。若是，再检查下这个新树是否是$BST$即可。

class Solution1932 {
    fun canMerge(trees: List<TreeNode>): TreeNode? {
        val arr = IntArray(50005)
        val totalCount = trees.sumBy {
            it.count()
        }
        val mapRoot = hashMapOf<Int, TreeNode>()
        val set = hashSetOf<Int>()
        trees.forEach {
            set.add(it.`val`)
            mapRoot[it.`val`] = it
            arr[it.`val`]++
            it.left?.let {
                set.add(it.`val`)
                arr[it.`val`]--
            }
            it.right?.let {
                set.add(it.`val`)
                arr[it.`val`]--
            }
        }

        if (totalCount - trees.size + 1 != set.size) return null

        if (arr.count { it == 1 } != 1) return null
        val start = arr.indexOfFirst { it == 1 }
        val root = mapRoot[start]

        // Start Merge
        fun dfs(root: TreeNode?) {
            if (root == null) return
            dfs(mapRoot[root.left?.`val`])
            dfs(mapRoot[root.right?.`val`])

            if (mapRoot[root.left?.`val`] != null)
                root.left = mapRoot[root.left?.`val`]
            if (mapRoot[root.right?.`val`] != null)
                root.right = mapRoot[root.right?.`val`]
        }

        dfs(root)
        return if (root.isBST() && root.count() == set.size) root
        else null
    }
}

fun TreeNode?.count(): Int = if (this == null) {
    0
} else {
    1 + this.left.count() + this.right.count()
}

/**
 * 判断二叉树是否为二叉搜索树
 * 严格大于小于（禁止等于）
 * */
fun TreeNode?.isBST(): Boolean {
    if (this == null) return false
    fun dfs(node: TreeNode?, up: Int, down: Int): Boolean {
        if (node == null) return true
        // println("${node.`val`} in $down..$up")
        if (node.`val` <= down || node.`val` >= up) return false
        return dfs(node.left, minOf(up, node.`val`), down) && dfs(node.right, up, maxOf(down, node.`val`))
    }
    return dfs(this.left, this.`val`, Int.MIN_VALUE) && dfs(this.right, Int.MAX_VALUE, this.`val`)
}