网格游戏

2017. 网格游戏

给你一个下标从 0 开始的二维数组 grid ，数组大小为 2 x n ，其中 grid[r][c] 表示矩阵中 (r, c) 位置上的点数。现在有两个机器人正在矩阵上参与一场游戏。

两个机器人初始位置都是 (0, 0) ，目标位置是 (1, n-1) 。每个机器人只会向右 ((r, c) 到 (r, c + 1)) 或向下 ((r, c) 到 (r + 1, c)) 。

游戏开始，第一个 机器人从 (0, 0) 移动到 (1, n-1) ，并收集路径上单元格的全部点数。对于路径上所有单元格 (r, c) ，途经后 grid[r][c] 会重置为 0 。然后，第二个 机器人从 (0, 0) 移动到 (1, n-1) ，同样收集路径上单元的全部点数。注意，它们的路径可能会存在相交的部分。

第一个 机器人想要打击竞争对手，使 第二个 机器人收集到的点数 最小化 。与此相对，第二个 机器人想要 最大化 自己收集到的点数。两个机器人都发挥出自己的 最佳水平 的前提下，返回 第二个 机器人收集到的点数。

示例 1：

输入：grid = [[2,5,4],[1,5,1]]
输出：4
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 0 + 4 + 0 = 4 个点。

示例 2：

输入：grid = [[3,3,1],[8,5,2]]
输出：4
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。 
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 3 + 1 + 0 = 4 个点。

示例 3：

输入：grid = [[1,3,1,15],[1,3,3,1]]
输出：7
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 1 + 3 + 3 + 0 = 7 个点。

提示：

grid.length == 2
n == grid[r].length
1 <= n <= 5 * 10⁴
1 <= grid[r][c] <= 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: long long gridGame(vector<vector<int>>& grid) { } };

java 解法, 执行用时: 4 ms, 内存消耗: 55.7 MB, 提交时间: 2023-09-14 01:12:49

class Solution {
    public long gridGame(int[][] grid) {
        int n = grid[0].length;
        long[][] p = new long[2][n + 1];
        for(int i = 1; i <= n; i++) {
            p[0][i] = p[0][i - 1] + grid[0][i - 1];
            p[1][i] = p[1][i - 1] + grid[1][i - 1];
        }
        long ans = Long.MAX_VALUE;
        for(int i = 1; i <= n; i++) {
            ans = Math.min(ans, Math.max(p[0][n] - p[0][i], p[1][i - 1]));
        }
        return ans;
    }
}

python3 解法, 执行用时: 212 ms, 内存消耗: 28.3 MB, 提交时间: 2023-09-14 01:12:22

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        n = len(grid[0])
        r1,r2 = [0]*n,[0]*n
        for i in range(n-1,0,-1):r1[i-1] = r1[i]+grid[0][i]
        for i in range(n-1):r2[i+1] = r2[i]+grid[1][i]
        res = float('inf')
        for i in range(n):res = min(res,max(r1[i],r2[i]))
        return res

cpp 解法, 执行用时: 128 ms, 内存消耗: 61.9 MB, 提交时间: 2023-09-14 01:11:52

class Solution {
public:
    typedef long long LL;
    long long gridGame(vector<vector<int>>& grid) {
        LL res = (1ll << 62) - 1;
        LL left0 = accumulate(grid[0].begin(),grid[0].end(),0ll);
        LL left1 = 0;
        for(int i = 0;i < grid[0].size();i++){
            left0 -= (LL)grid[0][i];
            res = min(res,max(left0,left1));
            left1 += (LL)grid[1][i];
        }
        return res;
    }
};

golang 解法, 执行用时: 128 ms, 内存消耗: 8.6 MB, 提交时间: 2023-09-14 01:11:34

func gridGame(grid [][]int) int64 {
	ans := math.MaxInt64
	left0 := 0
	for _, v := range grid[0] {
		left0 += v
	}
	left1 := 0
	for j, v := range grid[0] { // 枚举第一个机器人在哪拐弯
		left0 -= v
		ans = min(ans, max(left0, left1)) // 第二个机器人只能取上下剩余部分中的最大值
		left1 += grid[1][j]
	}
	return int64(ans)
}

func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a < b { return b }; return a }

上一题

下一题

详情