第 283 场周赛题解 (opens new window)

Q1 2194. Excel 表中某个范围内的单元格 (opens new window)

理解题意就好，数字也是范围内，而不是第二列之后的从1开始... 这TestCase数据都是故意不给能够解释有可能造成歧义的地方，考察小聪明...

class SolutionA {
    fun cellsInRange(s: String): List<String> {
        val ans = ArrayList<String>()
        for (i in s[0]..s[3]) {
            for (j in s[1]..s[4]) {
                ans.add("$i$j")
            }
        }
        return ans
    }
}

Q2 6017. 向数组中追加 K 个整数 (opens new window)

先把K的数的和求出来，然后原数组排序（+去重），每遇到一个$<=k$的就把阈值增1，并总和要加一次当前阈值。

上来就暴力做来着，结果超时了，然后没加去重，又GG，最后WA了三次...

class SolutionB {
    fun minimalKSum(nums: IntArray, k: Int): Long {
        var ans = 1L * k * (k + 1) / 2
        val n = nums.distinct().sorted()
        var cur = k
        for (i in n.indices) {
            if (n[i] <= cur) {
                cur++
                ans -= n[i]
                ans += cur
            }
        }
        return ans
    }
}

Q3 6018. 根据描述创建二叉树 (opens new window)

正常构造即可，注意要查找仅出现在父节点一侧的值，返回这个Node。

class SolutionC {
    fun createBinaryTree(descriptions: Array<IntArray>): TreeNode? {
        val seen = HashMap<Int, TreeNode>()
        val p = IntArray(100005)
        descriptions.forEach {
            val parent = seen.getOrDefault(it[0], TreeNode(it[0]))
            val child = seen.getOrDefault(it[1], TreeNode(it[1]))
            if (it[2] == 1) {
                parent.left = child
            } else {
                parent.right = child
            }
            p[it[0]]++
            p[it[1]] = -10000
            seen[it[0]] = parent
            seen[it[1]] = child
        }
        for (i in p.indices) {
            if (p[i] > 0) {
                return seen[i]
            }
        }
        return null
    }
}

Q4 6019. 替换数组中的非互质数 (opens new window)

最开始用ArrayList进行removeAt和add操作，结果最后一个用例超时... 改成Stack处理就可以了... 吸取教训，注意基础数据结构的时间复杂度。

class SolutionD {
    fun replaceNonCoprimes(nums: IntArray): List<Int> {
        val ans = Stack<Int>()
        for (i in nums.indices) {
            ans.push(nums[i])
            while (ans.size >= 2) {
                val a = ans.pop()
                val b = ans.pop()
                if (gcd(a, b) > 1) {
                    ans.push(lcm(a, b))
                } else {
                    ans.push(b)
                    ans.push(a)
                    break
                }
            }
        }
        return ans
    }
}