第 273 场周赛题解

Q1 5963. 反转两次的数字 (opens new window)

不是0且没有后缀0。（我就直接暴力了...）

class SolutionA {
    fun isSameAfterReversals(num: Int): Boolean {
        return num.toString().reversed().toInt().toString().reversed().toInt() == num
    }
}

Q2 5964. 执行所有后缀指令 (opens new window)

双循环暴力。由于中间可能出圈，所以不方便用前缀和处理。

class SolutionB {
    fun executeInstructions(n: Int, startPos: IntArray, s: String): IntArray {
        val ans = IntArray(s.length)
        for (i in s.indices) {
            var (x, y) = startPos
            var step = 0
            for (j in i until s.length) {
                when (s[j]) {
                    'L' -> y--
                    'R' -> y++
                    'U' -> x--
                    'D' -> x++
                }
                if (x !in 0 until n) break
                if (y !in 0 until n) break
                step++
            }
            ans[i] = step
        }
        return ans
    }
}

Q3 5965. 相同元素的间隔之和 (opens new window)

记录相同数字的位置。从左到右，从右到左两次遍历即可。

class SolutionC {
    fun getDistances(arr: IntArray): LongArray {
        val map = HashMap<Int, ArrayList<Int>>()
        for (i in arr.indices) {
            map[arr[i]] = map.getOrDefault(arr[i], arrayListOf())
            map[arr[i]]!!.add(i)
        }
        val ans = LongArray(arr.size)
        map.forEach { t, u ->
            var left = 0L
            var c = 0L
            for (i in u.indices) {
                c++
                left += u[i]
                val tmp = u[i] * c - left
                ans[u[i]] += tmp
            }
            var right = 0L
            c = 0L
            for (i in u.indices.reversed()) {
                c++
                right += u[i]
                val tmp = u[i] * c - right
                ans[u[i]] -= tmp
            }
        }

        return ans
    }
}

Q4 5966. 还原原数组 (opens new window)

将数组拆分成两个数组，且每一位的差相同，即对于任意$i$都有$a[i] - b[i] == d$。

当构建数组成功后，原数组就是这两个数组的平均值。（使用双指针可以比Map判断更早中断）

class SolutionD {
    fun recoverArray(nums: IntArray): IntArray {
        nums.sort()
        for (k in nums.indices) {
            val map = HashMap<Int, Int>()
            // 等差数列的差
            val d = nums[k] - nums[0]
            if (d == 0 || d % 2 != 0) continue
            val left = ArrayList<Int>()
            val right = ArrayList<Int>()
            for (i in nums.indices) {
                val key = nums[i]
                val lk = nums[i] - d
                if (lk in map.keys) {
                    map[lk] = map.getOrDefault(lk, 0) - 1
                    right.add(key)
                    if (map[lk] == 0) {
                        map.remove(lk)
                    }
                } else {
                    map[key] = map.getOrDefault(key, 0) + 1
                    left.add(key)
                }
            }
            if (left.size == right.size) {
                val ans = IntArray(nums.size / 2)
                for (i in ans.indices) {
                    ans[i] = (left[i] + right[i]) / 2
                }
                return ans
            }
        }
        return intArrayOf()
    }
}