第 224 场周赛题解

Q1 1725. 可以形成最大正方形的矩形数目 (opens new window)

简单暴力，直接模拟就行。

class Solution5653 {
    fun countGoodRectangles(rectangles: Array<IntArray>): Int {
        val arr = rectangles.map { it.min()!! }
        val max = arr.max()!!
        return arr.count { it == max }
    }
}

Q2 1726. 同积元组 (opens new window)

这道题需要收集好题目给出的条件：

1. 数组中的正整数各不相同
2. 数据范围是[1, 1000]

因此，可以使用两重循环，把所有的积求出来。对于有元组可能的结果，一定有Product的size >= 2。因为$P = a * b = c * d$，所以对于每一个组合>1的P，都有$n * (n - 1) * 4$种元组。

class Solution5243 {
    fun tupleSameProduct(nums: IntArray): Int {
        val p = HashMap<Int, Int>()
        for (i in 0 until nums.lastIndex) {
            for (j in i + 1 until nums.size) {
                val key = nums[i] * nums[j]
                p[key] = p.getOrDefault(key, 0) + 1
            }
        }
        var ans = 0
        p.forEach {
            ans += (it.value * (it.value - 1)) * 4
        }
        return ans
    }
}

Q3 1727. 重新排列后的最大子矩阵 (opens new window)

首先，题意是列可以任意排序，保证行不变。

1. 我们先处理列的数据，将列上的数字映射为之前连续1的总次数。
2. 每一行根据列中该行的大小由高到低排序。
3. 动态查找出满足题意的最大值。

行的逆序排序，遇到每一个点时，之前点的1的高度都要大于等于当前点，因此可以使用宽度*当前点的值作为以当前点为右下角的矩形的面积。

class Solution5655 {
    fun largestSubmatrix(matrix: Array<IntArray>): Int {
        val n: Int = matrix.size
        val m: Int = matrix[0].size
        var res = 0
        for (i in 1 until n) {
            for (j in 0 until m) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] += matrix[i - 1][j]
                }
            }
        }
        for (i in 0 until n) {
            matrix[i].sortDescending()
            for (j in 0 until m) {
                val height = matrix[i][j]
                res = maxOf(res, height * (j + 1))
            }
        }
        return res
    }
}

Q4 1728. 猫和老鼠 II (opens new window)

经典的玩游戏题目，还有不少石子游戏之类的、Alice && Bob。问是否有必胜法。

这种题目一般数据规模不会很大，可以用硬DFS遍历所有的状态。我们只需要判断状态的结果并用记忆化递归优化即可。同时，还需要注意由于双方都采取最优策略，有以下效果：

1. 当老鼠移动时，哪一步能赢就走哪一步，即DFS中任一return true则整体可以return true
2. 当猫移动时，哪一步会让老鼠输就走哪一步，任一return false则整体return false
3. 由于row && col的范围是[1..8]，所以老鼠位置的状态最多64个，游戏不需要1000次步数都用完，100步内如果解决不了猫就算输了。（夸张点应该是128步，不过为达成追逐效果需要增加墙壁的位置，会减少状态数，经试验，测试数据的step最小为67）

class Solution5529 {
    fun canMouseWin(grid: Array<String>, catJump: Int, mouseJump: Int): Boolean {
        var cx = 0
        var cy = 0
        var mx = 0
        var my = 0
        var fx = 0
        var fy = 0
        for (i in grid.indices) {
            for (j in grid[0].indices) {
                when {
                    grid[i][j] == 'C' -> {
                        cx = i
                        cy = j
                    }
                    grid[i][j] == 'M' -> {
                        mx = i
                        my = j
                    }
                    grid[i][j] == 'F' -> {
                        fx = i
                        fy = j
                    }
                }
            }
        }

        val dr = intArrayOf(0, 1, 0, -1)
        val dc = intArrayOf(1, 0, -1, 0)

        val dp = Array<Array<Array<Array<Array<Boolean?>>>>>(8) {
            Array(8) { Array(8) { Array(8) { Array<Boolean?>(102) { null } } } }
        }

        fun dfs(cx: Int, cy: Int, mx: Int, my: Int, step: Int): Boolean {
            if (dp[cx][cy][mx][my][step] != null) {
                return dp[cx][cy][mx][my][step]!!
            }
            if (step > 100) return false
            if (cx == mx && cy == my) return false
            if (cx == fx && cy == fy) return false
            if (mx == fx && my == fy) return true

            if (step % 2 == 0) {
                // mouse move
                var res = false
                for (i in 0 until 4) {
                    for (j in 0..mouseJump) {
                        val nx: Int = mx + dr[i] * j
                        val ny: Int = my + dc[i] * j
                        if (nx !in grid.indices || ny !in grid[0].indices || grid[nx][ny] == '#') {
                            break
                        }
                        if (nx != mx || ny != my) {
                            if (dfs(cx, cy, nx, ny, step + 1)) {
                                return true.also {
                                    dp[cx][cy][mx][my][step] = it
                                }
                            }
                        }
                    }
                }
                return false.also {
                    dp[cx][cy][mx][my][step] = it
                }
            } else {
                // cat move
                for (i in 0 until 4) {
                    for (j in 0..catJump) {
                        val nx: Int = cx + dr[i] * j
                        val ny: Int = cy + dc[i] * j
                        if (nx !in grid.indices || ny !in grid[0].indices || grid[nx][ny] == '#') {
                            break
                        }
                        if (!dfs(nx, ny, mx, my, step + 1)) {
                            return false.also {
                                dp[cx][cy][mx][my][step] = it
                            }
                        }
                    }
                }
                return true.also {
                    dp[cx][cy][mx][my][step] = it
                }
            }
        }
        return dfs(cx, cy, mx, my, 0)
    }
}