Keshawn_lu's Blog

Leetcode 5477. 排布二进制网格的最少交换次数

字数统计: 595阅读时长: 2 min
2020/08/02 Share

题目简介:

给你一个 n x n 的二进制网格 grid,每一次操作中,你可以选择网格的 相邻两行 进行交换。

一个符合要求的网格需要满足主对角线以上的格子全部都是 0

请你返回使网格满足要求的最少操作次数,如果无法使网格符合要求,请你返回 -1

主对角线指的是从 (1, 1)(n, n) 的这些格子。

示例 1:

1
2
输入:grid = [[0,0,1],[1,1,0],[1,0,0]]
输出:3

示例 2:

1
2
3
输入:grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
输出:-1
解释:所有行都是一样的,交换相邻行无法使网格符合要求。

示例 3:

1
2
输入:grid = [[1,0,0],[1,1,0],[1,1,1]]
输出:0

提示:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 200
  • grid[i][j] 要么是 0 要么是 1

思路:

周赛的第三题,做出来有点小开心。

首先统计每行后缀连续0的个数。

i行若要满足要求,其后缀0的个数必>= grid[i].size() - (i + 1)。若不满足,则往下遍历最近的一行j,并将第j行逐渐向上移动,在此过程中改变相应行的count值(并非交换两行)。

若向下遍历完后,仍没有满足要求的行,则此矩阵不满足题设,返回-1

tip:

  • 每次遍历需要将flag置为0
  • 只要前grid.size() - 1行满足要求即可,最后一行不用管。
  • 将第j行移动至第i行,需要花费j - i次。(并非两行交换)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:

//统计后缀0个数
int count_0(vector<vector<int>>& grid, int row){

int sum = 0;

for(int i = grid[row].size() - 1; i >= 0; i--){

if(grid[row][i] == 0)
sum++;
else
return sum;
}

return sum;
}

int minSwaps(vector<vector<int>>& grid) {

int sum = 0;

int flag = 0;

vector<int> count(grid.size(), 0);

for(int i = 0; i < grid.size(); i++){

count[i] = count_0(grid, i);
}

for(int i = 0; i < grid.size() - 1; i++){

flag = 0;
if(count[i] < grid[i].size() - (i + 1)){

for(int j = i + 1; j < grid.size(); j++){

if(count[j] >= grid[i].size() - (i + 1)){

sum += j - i;

//相应行往下移动
for(int k = j; k > i; k--){

count[k] = count[k - 1];
}

flag = 1;

break;
}

}

if(flag == 0)
return -1;
}
}

return sum;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: