573. 松鼠模拟
现在有一棵树，一只松鼠和一些坚果。位置由二维网格的单元格表示。你的目标是找到松鼠收集所有坚果的最小路程，且坚果是一颗接一颗地被放在树下。松鼠一次最多只能携带一颗坚果，松鼠可以向上，向下，向左和向右四个方向移动到相邻的单元格。移动次数表示路程。
输入 1:
输入: 高度 : 5 宽度 : 7 树的位置 : [2,2] 松鼠 : [4,4] 坚果 : [[3,0], [2,5]] 输出: 12 解释:
注意:
原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 6.1 MB, 提交时间: 2023-10-21 23:03:28
import "math"
func abs(a int) int {
if a >= 0 {
return a
}
return -a
}
func max(a, b int) int {
if a < b {
return b
}
return a
}
func minDistance(height int, width int, tree []int, squirrel []int, nuts [][]int) int {
out, d := 0, math.MinInt64
for _, nut := range nuts {
dist := abs(tree[0]-nut[0]) + abs(tree[1]-nut[1])
out += dist * 2
d = max(d, dist-abs(squirrel[0]-nut[0])-abs(squirrel[1]-nut[1]))
}
return out - d
}
java 解法, 执行用时: 3 ms, 内存消耗: 43.7 MB, 提交时间: 2023-10-21 23:03:01
class Solution {
public int getDistance(int[] a, int[] b) {
return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
}
public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
int ans = (int) 1e9;
int sum_dis = 0;
for (int[] nut : nuts)
sum_dis += getDistance(nut, tree) * 2;
for (int[] first_nut : nuts) {
int cur = sum_dis - getDistance(first_nut, tree) + getDistance(first_nut, squirrel);
ans = Math.min(cur, ans);
}
return ans;
}
}
javascript 解法, 执行用时: 64 ms, 内存消耗: 43.3 MB, 提交时间: 2023-10-21 23:02:49
/**
* @param {number} height
* @param {number} width
* @param {number[]} tree
* @param {number[]} squirrel
* @param {number[][]} nuts
* @return {number}
*/
var getDistance = (a, b) => (Math.abs(a[0]-b[0])+Math.abs(a[1]-b[1]));
var minDistance = function(height, width, tree, squirrel, nuts) {
var ans = 1000000000, sum_dis = 0;
nuts.forEach((nut)=>{
sum_dis += getDistance(nut, tree) * 2;
})
nuts.forEach((first_nut) => {
var cur = sum_dis - getDistance(first_nut, tree) + getDistance(first_nut, squirrel);
ans = Math.min(ans,cur);
});
return ans;
};
cpp 解法, 执行用时: 24 ms, 内存消耗: 20.9 MB, 提交时间: 2023-10-21 23:02:35
class Solution {
int getDistance(vector<int>& a, vector<int>& b) {
return abs(a[0] - b[0]) + abs(a[1] - b[1]);
}
public:
int minDistance(int height, int width, vector<int>& tree, vector<int>& squirrel, vector<vector<int>>& nuts) {
int ans = 1e9;
int sum_dis = 0;
for (auto nut = nuts.begin(); nut != nuts.end(); ++nut)
sum_dis += getDistance(*nut, tree) * 2;
for (auto first_nut = nuts.begin(); first_nut != nuts.end(); ++first_nut) {
int cur = sum_dis - getDistance(*first_nut, tree) + getDistance(*first_nut, squirrel);
ans = min(cur, ans);
}
return ans;
}
};
python3 解法, 执行用时: 52 ms, 内存消耗: 16.8 MB, 提交时间: 2023-10-21 23:02:23
class Solution:
def getDistance(self, a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:
ans = int(1e9)
sum_dis = sum(self.getDistance(nut, tree) for nut in nuts) * 2
for first_nut in nuts:
cur = sum_dis - self.getDistance(first_nut, tree) + self.getDistance(first_nut, squirrel)
ans = min(cur, ans)
return ans