题目简介：
给你一个 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.lengthn == grid[i].length1 <= n <= 200grid[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:
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;
}
};
|
