Skip to content

Latest commit

 

History

History
201 lines (163 loc) · 7.05 KB

README.md

File metadata and controls

201 lines (163 loc) · 7.05 KB
Raw
comments difficulty edit_url rating source tags
true
中等
1743
第 66 场双周赛 Q3
贪心
数组

2087. 网格图中机器人回家的最小代价

English Version

题目描述

给你一个 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.length
  • n == colCosts.length
  • 1 <= m, n <= 105
  • 0 <= rowCosts[r], colCosts[c] <= 104
  • startPos.length == 2
  • homePos.length == 2
  • 0 <= startrow, homerow < m
  • 0 <= startcol, homecol < n

解法

方法一：贪心

设机器人当前位置为 $(i, j)$，目标位置为 $(x, y)$。

  • 如果 $i \lt x$，则机器人往下移动，代价为 $rowCosts[i + 1] + rowCosts[i + 2] + \cdots + rowCosts[x]$。
  • 如果 $i \gt x$，则机器人往上移动，代价为 $rowCosts[x] + rowCosts[x + 1] + \cdots + rowCosts[i - 1]$。
  • 如果 $j \lt y$，则机器人往右移动，代价为 $colCosts[j + 1] + colCosts[j + 2] + \cdots + colCosts[y]$。
  • 如果 $j \gt y$，则机器人往左移动，代价为 $colCosts[y] + colCosts[y + 1] + \cdots + colCosts[j - 1]$。

时间复杂度 $O(m + n)$，空间复杂度 $O(1)$。其中 $m$ 和 $n$ 分别为 $rowCosts$ 和 $colCosts$ 的长度。

Python3

class Solution:
    def minCost(
        self,
        startPos: List[int],
        homePos: List[int],
        rowCosts: List[int],
        colCosts: List[int],
    ) -> int:
        i, j = startPos
        x, y = homePos
        ans = 0
        if i < x:
            ans += sum(rowCosts[i + 1 : x + 1])
        else:
            ans += sum(rowCosts[x:i])
        if j < y:
            ans += sum(colCosts[j + 1 : y + 1])
        else:
            ans += sum(colCosts[y:j])
        return ans

Java

class Solution {
    public int minCost(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
        int i = startPos[0], j = startPos[1];
        int x = homePos[0], y = homePos[1];
        int ans = 0;
        if (i < x) {
            for (int k = i + 1; k <= x; ++k) {
                ans += rowCosts[k];
            }
        } else {
            for (int k = x; k < i; ++k) {
                ans += rowCosts[k];
            }
        }
        if (j < y) {
            for (int k = j + 1; k <= y; ++k) {
                ans += colCosts[k];
            }
        } else {
            for (int k = y; k < j; ++k) {
                ans += colCosts[k];
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {
        int i = startPos[0], j = startPos[1];
        int x = homePos[0], y = homePos[1];
        int ans = 0;
        if (i < x) {
            ans += accumulate(rowCosts.begin() + i + 1, rowCosts.begin() + x + 1, 0);
        } else {
            ans += accumulate(rowCosts.begin() + x, rowCosts.begin() + i, 0);
        }
        if (j < y) {
            ans += accumulate(colCosts.begin() + j + 1, colCosts.begin() + y + 1, 0);
        } else {
            ans += accumulate(colCosts.begin() + y, colCosts.begin() + j, 0);
        }
        return ans;
    }
};

Go

func minCost(startPos []int, homePos []int, rowCosts []int, colCosts []int) (ans int) {
	i, j := startPos[0], startPos[1]
	x, y := homePos[0], homePos[1]
	if i < x {
		ans += sum(rowCosts, i+1, x+1)
	} else {
		ans += sum(rowCosts, x, i)
	}
	if j < y {
		ans += sum(colCosts, j+1, y+1)
	} else {
		ans += sum(colCosts, y, j)
	}
	return
}

func sum(nums []int, i, j int) (s int) {
	for k := i; k < j; k++ {
		s += nums[k]
	}
	return
}