第 260 场周赛题解

Q1 2016. 增量元素之间的最大差值 (opens new window)

一个大小没注意... 结果WA了一发0...

class Solution5881 {
    fun maximumDifference(nums: IntArray): Int {
        var ans = -1
        for (i in 0 until nums.lastIndex) {
            for (j in i + 1 until nums.size) {
                if (nums[j] > nums[i])
                    ans = maxOf(ans, nums[j] - nums[i])
            }
        }
        return ans
    }
}

Q2 2017. 网格游戏 (opens new window)

要注意题目写明数组大小为$2 * n$，所以第二个机器人拿的是第二行开始部分 or 第一行结束部分。直接前缀和即可。

class Solution5882 {
    fun gridGame(grid: Array<IntArray>): Long {
        val m = grid[0].size
        val a = LongArray(m)
        for (i in 0 until m)
            a[i] = (if (i != 0) a[i - 1] else 0) + grid[1][i]
        val b = LongArray(m)
        for (i in m - 1 downTo 0)
            b[i] = (if (i != m - 1) b[i + 1] else 0) + grid[0][i]
        var ans = Long.MAX_VALUE / 2
        for (i in 0 until m) {
            ans = minOf(
                ans, maxOf(
                    a.getOrElse(i - 1) { 0L },
                    b.getOrElse(i + 1) { 0L }
                )
            )
        }
        return ans
    }
}

Q3 2018. 判断单词是否能放入填字游戏内 (opens new window)

按顺序遍历，合法的头需要左侧&上侧需要连接‘#’或边缘。从水平、垂直两个方向单独讨论即可。要注意字符串可以逆序填写... 这也吃了一发WA。

class Solution5883 {
    fun placeWordInCrossword(board: Array<CharArray>, word: String): Boolean {
        fun check(str: String, i: Int, j: Int, hor: Boolean): Boolean {
            var x = i
            var y = j
            var step = 0
            while (x in board.indices && y in board[0].indices) {
                if (step == str.length) {
                    return board[x][y] == '#'
                }
                if (board[x][y] != ' ' && board[x][y] != str[step]) return false
                step++
                if (hor) y++
                else x++
            }
            return step == str.length
        }
        for (i in board.indices) {
            for (j in board[0].indices) {
                if (board[i][j] != '#') {
                    if (i == 0 || board[i - 1][j] == '#') {
                        if (check(word, i, j, false)) return true
                        if (check(word.reversed(), i, j, false)) return true
                    }
                    if (j == 0 || board[i][j - 1] == '#') {
                        if (check(word, i, j, true)) return true
                        if (check(word.reversed(), i, j, true)) return true
                    }
                }
            }
        }
        return false
    }
}

Q4 2019. 解出数学表达式的学生分数 (opens new window)

真正逻辑顺序结果计算出来，再把所有可能性计算出来，最后$map$出分数即可。注意范围是$[0..1000]$，因此可以对于范围外的结果提前剪枝。全部结果的计算与241. 为运算表达式设计优先级 (opens new window)相同。

class Solution5884 {
    fun scoreOfStudents(s: String, answers: IntArray): Int {
        val real = eval(s)
        val seen = HashMap<String, HashSet<Int>>()
        fun dfs(l: Int, r: Int): HashSet<Int> {
            val key = "$l,$r"
            if (key in seen) return seen[key]!!
            if (r - l == 1)
                return hashSetOf(s.substring(l, r).toInt()).also {
                    seen[key] = it
                }
            val set = HashSet<Int>()
            // i按顺序选中每个符号
            for (i in l + 1..r - 1 step 2) {
                val left = dfs(l, i)
                val right = dfs(i + 1, r)
                left.forEach { a ->
                    right.forEach { b ->
                        if (s[i] == '+') {
                            if (a + b <= 1000)
                                set.add(a + b)
                        } else {
                            if (a * b <= 1000)
                                set.add(a * b)
                        }
                    }
                }
            }
            return set.also {
                seen[key] = it
            }
        }

        val set = dfs(0, s.length)
        return answers.map {
            when (it) {
                real -> 5
                in set -> 2
                else -> 0
            }
        }.sum()
    }
}

// 支持 +-*/ 并符合运算规律，先计算*/再计算+-
// todo 增加括号的支持
fun eval(expression: String): Int {
    val stn = Stack<Int>()
    val op = Stack<Char>()
    expression.forEach {
        if (it in '0'..'9') {
            stn.push(it - '0')
            if (op.isNotEmpty() && op.peek() in arrayOf('*', '/')) {
                val a = stn.pop()
                val b = stn.pop()
                when (op.pop()) {
                    '*' -> stn.push(a * b)
                    '/' -> stn.push(b / a)
                }
            }
        } else {
            op.push(it)
        }
    }
    while (op.isNotEmpty()) {
        val a = stn.pop()
        val b = stn.pop()
        when (op.pop()) {
            '+' -> stn.push(a + b)
            '-' -> stn.push(b - a)
        }
    }
    return stn.pop()
}