跳转至

3189. 得到一个和平棋盘的最少步骤 🔒

题目描述

给定一个长度为 n 的二维数组 rooks，其中 rooks[i] = [xi, yi] 表示 n x n 棋盘上一个车的位置。你的任务是每次在垂直或水平方向上移动 1 格 车（到一个相邻的格子）使得棋盘变得 和平。

如果每行每列都 只有 一个车，那么这块棋盘就是和平的。

返回获得和平棋盘所需的 最少 步数。

注意 任何时刻 两个车都不能在同一个格子。

 

示例 1：

输入：rooks = [[0,0],[1,0],[1,1]]

输出：3

解释：

示例 2：

输入：rooks = [[0,0],[0,1],[0,2],[0,3]]

输出：6

解释：

 

提示：

  • 1 <= n == rooks.length <= 500
  • 0 <= xi, yi <= n - 1
  • 输入保证没有两个车在相同的格子。

解法

方法一：贪心

我们可以将所有的车按照横坐标排序，然后将车按顺序分配给每一行，计算每个车到目标位置的距离之和。然后将所有的车按照纵坐标排序，按照同样的方法计算每个车到目标位置的距离之和。最后将两个距离之和相加即为答案。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为车的数量。

1
2
3
4
5
6
7
class Solution:
    def minMoves(self, rooks: List[List[int]]) -> int:
        rooks.sort()
        ans = sum(abs(x - i) for i, (x, _) in enumerate(rooks))
        rooks.sort(key=lambda x: x[1])
        ans += sum(abs(y - j) for j, (_, y) in enumerate(rooks))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int minMoves(int[][] rooks) {
        Arrays.sort(rooks, (a, b) -> a[0] - b[0]);
        int ans = 0;
        int n = rooks.length;
        for (int i = 0; i < n; ++i) {
            ans += Math.abs(rooks[i][0] - i);
        }
        Arrays.sort(rooks, (a, b) -> a[1] - b[1]);
        for (int j = 0; j < n; ++j) {
            ans += Math.abs(rooks[j][1] - j);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minMoves(vector<vector<int>>& rooks) {
        sort(rooks.begin(), rooks.end());
        int ans = 0;
        int n = rooks.size();
        for (int i = 0; i < n; ++i) {
            ans += abs(rooks[i][0] - i);
        }
        sort(rooks.begin(), rooks.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        for (int j = 0; j < n; ++j) {
            ans += abs(rooks[j][1] - j);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func minMoves(rooks [][]int) (ans int) {
    sort.Slice(rooks, func(i, j int) bool { return rooks[i][0] < rooks[j][0] })
    for i, row := range rooks {
        ans += int(math.Abs(float64(row[0] - i)))
    }
    sort.Slice(rooks, func(i, j int) bool { return rooks[i][1] < rooks[j][1] })
    for j, col := range rooks {
        ans += int(math.Abs(float64(col[1] - j)))
    }
    return
}

1
2
3
4
5
6
7
function minMoves(rooks: number[][]): number {
    rooks.sort((a, b) => a[0] - b[0]);
    let ans = rooks.reduce((sum, rook, i) => sum + Math.abs(rook[0] - i), 0);
    rooks.sort((a, b) => a[1] - b[1]);
    ans += rooks.reduce((sum, rook, j) => sum + Math.abs(rook[1] - j), 0);
    return ans;
}

评论