第 259 场周赛题解

Q1 2011. 执行操作后的变量值 (opens new window)

简单判断+即可。

class Solution5875 {
    fun finalValueAfterOperations(operations: Array<String>): Int {
        var ans = 0
        operations.forEach {
            if ("+" in it) ans++
            else ans--
        }
        return ans
    }
}

Q2 2012. 数组美丽值求和 (opens new window)

前缀最大值，后缀最小值，再次遍历数组看是否符合即可。

class Solution5876 {
    fun sumOfBeauties(nums: IntArray): Int {
        val maxArr = IntArray(nums.size)
        for (i in 1 until nums.size) {
            maxArr[i] = maxOf(maxArr[i - 1], nums[i - 1])
        }
        val minArr = IntArray(nums.size) { Int.MAX_VALUE }
        for (i in nums.lastIndex - 1 downTo 0) {
            minArr[i] = minOf(minArr[i + 1], nums[i + 1])
        }
        var ans = 0
        for (i in 1..nums.size - 2) {
            if (nums[i] > maxArr[i] && nums[i] < minArr[i]) {
                ans += 2
            } else if (nums[i] > nums[i - 1] && nums[i] < nums[i + 1]) {
                ans++
            }
        }
        return ans
    }
}

Q3 2013. 检测正方形 (opens new window)

正常按逻辑模拟，通过与查询点相同的$x$值，寻找另一个点，确认边长，之后再次确认其余两个点的值。

看成长方形WA了N次... 要仔细读题啊！

class DetectSquares() {

    val mapX = HashMap<Int, ArrayList<Int>>()
    val mapY = HashMap<Int, ArrayList<Int>>()

    fun add(point: IntArray) {
        val x = point[0]
        val y = point[1]
        mapX[x] = mapX.getOrDefault(x, arrayListOf())
        mapX[x]!!.add(y)
        mapY[y] = mapY.getOrDefault(y, arrayListOf())
        mapY[y]!!.add(x)
    }

    fun count(point: IntArray): Int {
        var ans = 0
        val x = point[0]
        val y = point[1]
        // 选择X相同，Y不同的点
        for (ny in mapX.getOrDefault(x, arrayListOf())) {
            if (ny == y) continue
            // 边长diff
            val diff = abs(ny - y)
            ans += mapX.getOrDefault(x + diff, arrayListOf()).let {
                it.count { it == y } * it.count { it == ny }
            }
            ans += mapX.getOrDefault(x - diff, arrayListOf()).let {
                it.count { it == y } * it.count { it == ny }
            }
        }
        return ans
    }

}

Q4 2014. 重复 K 次的最长子序列 (opens new window)

由于条件有$2 <= n < k * 8$，则子序列的长度不超过7。遍历其可能性的组合，将每种组合进行一次子序列的搜索即可。

class Solution5878 {
    fun longestSubsequenceRepeatedK(s: String, k: Int): String {
        fun check(str: String): Boolean {
            var c = 0
            var i = 0
            s.forEach {
                if (it == str[i]) {
                    i++
                }
                if (i == str.length) {
                    i = 0
                    c++
                    if (c == k) return true
                }
            }
            return false
        }

        val dp = Array(8) { ArrayList<String>() }
        dp[0].add("")
        for (i in 0 until 7) {
            for (str in dp[i]) {
                for (c in 'a'..'z') {
                    val t = str + c
                    if (check(t)) dp[i + 1].add(t)
                }
            }
        }
        for (i in 7 downTo 0) {
            return dp[i].maxOrNull() ?: continue
        }
        return ""
    }
}