第 270 场周赛题解

Q1 2094. 找出 3 位偶数 (opens new window)

签到。

class Solution2094 {
    fun findEvenNumbers(digits: IntArray): IntArray {
        val set = HashSet<Int>()
        for (i in 0 until digits.size - 2) {
            for (j in i + 1 until digits.size - 1) {
                for (k in j + 1 until digits.size) {
                    val a = digits[i]
                    val b = digits[j]
                    val c = digits[k]
                    set.add(a * 100 + b * 10 + c)
                    set.add(a * 100 + c * 10 + b)
                    set.add(b * 100 + a * 10 + c)
                    set.add(b * 100 + c * 10 + a)
                    set.add(c * 100 + a * 10 + b)
                    set.add(c * 100 + b * 10 + a)
                }
            }
        }
        return set.sorted().filter { it >= 100 && it % 2 == 0 }.toIntArray()
    }
}

Q2 2095. 删除链表的中间节点 (opens new window)

链表题，都先转成线性表~

class Solution2095 {
    fun deleteMiddle(head: ListNode?): ListNode? {
        val l = head.toIntArray().toArrayList()
        if (l.size == 0 || l.size == 1) return null
        l.removeAt(l.size / 2)
        return l.toIntArray().toListNode()
    }
}

Q3 2096. 从二叉树一个节点到另一个节点每一步的方向 (opens new window)

先找到根节点到两个节点的路径，公共祖先部分可以舍弃，剩下的就是第一个节点都是UP，再拼接第二个节点的路径。

class Solution2096 {
    fun getDirections(root: TreeNode?, startValue: Int, destValue: Int): String {
        var sl = ""
        var sr = ""
        fun dfs(node: TreeNode?, sb: ArrayList<Char>) {
            if (node == null) return
            if (node.`val` == startValue) {
                sl = sb.joinToString("")
            }
            if (node.`val` == destValue) {
                sr = sb.joinToString("")
            }
            sb.add('L')
            dfs(node.left, sb)
            sb.removeAt(sb.lastIndex)
            sb.add('R')
            dfs(node.right, sb)
            sb.removeAt(sb.lastIndex)
        }
        dfs(root, ArrayList())
        var start = 0
        while (start in sl.indices && start in sr.indices) {
            if (sl[start] == sr[start]) {
                start++
                continue
            }
            break
        }

        return sl.substring(start, sl.length).map { "U" }.joinToString("") + sr.substring(start, sr.length)
    }
}

Q4 2097. 合法重新排列数对 (opens new window)

欧拉通路，技巧就是先DFS每一个next，再add到结果中，这样就可以保证每个环都会走到。

class Solution2097 {
    fun validArrangement(pairs: Array<IntArray>): Array<IntArray> {
        val map = HashMap<Int, Stack<IntArray>>()
        val deg = HashMap<Int, Int>()
        pairs.forEach {
            map[it[0]] = map.getOrDefault(it[0], Stack())
            map[it[0]]!!.push(it)
            deg[it[0]] = deg.getOrDefault(it[0], 0) - 1
            deg[it[1]] = deg.getOrDefault(it[1], 0) + 1
        }

        var start = pairs[0][0]
        for (key in deg.keys) {
            // 入度比出度大1，则以该点为起始点
            if (deg[key] == -1) {
                start = key
                break
            }
        }

        val ans = ArrayList<IntArray>()
        fun dfs(cur: Int, arr: ArrayList<IntArray>) {
            while (map[cur]?.isNotEmpty() == true) {
                val next = map[cur]?.pop() ?: return
                dfs(next[1], arr)
                arr.add(next)
            }
        }
        dfs(start, ans)
        return ans.reversed().toTypedArray()
    }
}