LeetCode 题解工作台
网格图中机器人回家的最小代价
给你一个 m x n 的网格图，其中 (0, 0) 是最左上角的格子， (m - 1, n - 1) 是最右下角的格子。给你一个整数数组 startPos ， startPos = [start row , start col ] 表示 初始 有一个 机器人 在格子 (start row , sta…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们不妨假设机器人的初始位置为 $(x_0, y_0)$，家所在的位置为 $(x_1, y_1)$。 如果 $x_0 < x_1$，那么机器人需要往下走，需要经过的行是 $[x_0 + 1, x_1]$，总代价为 $\sum_{i = x_0 + 1}^{x_1} rowCosts[i]$；如果 $x_0 > x_1$，那么机器人需要往上走，需要经过的行是 $[x_1, x_0 - 1]$，总代价…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个 m x n 的网格图，其中 (0, 0) 是最左上角的格子，(m - 1, n - 1) 是最右下角的格子。给你一个整数数组 startPos ，startPos = [startrow, startcol] 表示 初始 有一个 机器人 在格子 (startrow, startcol) 处。同时给你一个整数数组 homePos ，homePos = [homerow, homecol] 表示机器人的 家 在格子 (homerow, homecol) 处。
机器人需要回家。每一步它可以往四个方向移动：上，下，左，右，同时机器人不能移出边界。每一步移动都有一定代价。再给你两个下标从 0 开始的整数数组：长度为 m 的数组 rowCosts 和长度为 n 的数组 colCosts 。
- 如果机器人往 上 或者往 下 移动到第
r行 的格子，那么代价为rowCosts[r]。 - 如果机器人往 左 或者往 右 移动到第
c列 的格子，那么代价为colCosts[c]。
请你返回机器人回家需要的 最小总代价 。
示例 1：
输入：startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7] 输出：18 解释：一个最优路径为： 从 (1, 0) 开始 -> 往下走到 (2, 0) 。代价为 rowCosts[2] = 3 。 -> 往右走到 (2, 1) 。代价为 colCosts[1] = 2 。 -> 往右走到 (2, 2) 。代价为 colCosts[2] = 6 。 -> 往右走到 (2, 3) 。代价为 colCosts[3] = 7 。 总代价为 3 + 2 + 6 + 7 = 18
示例 2：
输入：startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26] 输出：0 解释：机器人已经在家了，所以不需要移动。总代价为 0 。
提示：
m == rowCosts.lengthn == colCosts.length1 <= m, n <= 1050 <= rowCosts[r], colCosts[c] <= 104startPos.length == 2homePos.length == 20 <= startrow, homerow < m0 <= startcol, homecol < n
解题思路
方法一：贪心
我们不妨假设机器人的初始位置为 ，家所在的位置为 。
如果 ，那么机器人需要往下走，需要经过的行是 ，总代价为 ；如果 ，那么机器人需要往上走，需要经过的行是 ，总代价为 ；如果 ，那么机器人不需要往上下走，总代价为 。
同理，如果 ，那么机器人需要往右走，需要经过的列是 ，总代价为 ；如果 ，那么机器人需要往左走，需要经过的列是 ，总代价为 ；如果 ，那么机器人不需要往左右走，总代价为 。
答案为上下走的总代价与左右走的总代价之和。
时间复杂度 ，其中 和 分别是 和 的长度。空间复杂度 。
class Solution:
def minCost(
self,
startPos: List[int],
homePos: List[int],
rowCosts: List[int],
colCosts: List[int],
) -> int:
x0, y0 = startPos
x1, y1 = homePos
dx = sum(rowCosts[x0 + 1 : x1 + 1]) if x0 < x1 else sum(rowCosts[x1:x0])
dy = sum(colCosts[y0 + 1 : y1 + 1]) if y0 < y1 else sum(colCosts[y1:y0])
return dx + dy
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding of greedy algorithms for pathfinding in grid-based problems.
- question_mark
Ability to identify edge cases and handle them efficiently.
- question_mark
Focus on optimizing space and time complexity in a problem involving traversal.
常见陷阱
外企场景- error
Failing to handle the case where startPos equals homePos, leading to unnecessary calculations.
- error
Not recognizing the grid structure and movement constraints, which may lead to overcomplicating the solution.
- error
Misunderstanding the problem as requiring a complex pathfinding algorithm when it's a simple greedy approach.
进阶变体
外企场景- arrow_right_alt
Consider a grid with additional constraints like obstacles or variable costs for each cell.
- arrow_right_alt
Extend the problem to a 3D grid with movement in three dimensions.
- arrow_right_alt
What if the robot could only move diagonally or had some restricted movement pattern?