文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個(gè) n x n 的二進(jìn)制網(wǎng)格 grid，每一次操作中，你可以選擇網(wǎng)格的 相鄰兩行 進(jìn)行交換。

一個(gè)符合要求的網(wǎng)格需要滿足主對角線以上的格子全部都是 0 。

請你返回使網(wǎng)格滿足要求的最少操作次數(shù)，如果無法使網(wǎng)格符合要求，請你返回 -1 。

主對角線指的是從 (1, 1) 到 (n, n) 的這些格子。

輸入：grid = [[0,0,1],[1,1,0],[1,0,0]] 輸出：3

輸入：grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]] 輸出：-1 解釋：所有行都是一樣的，交換相鄰行無法使網(wǎng)格符合要求。

輸入：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 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-swaps-to-arrange-a-binary-grid
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 找出每行末尾連續(xù)的0的個(gè)數(shù)
• 檢查每行0的個(gè)數(shù)是否滿足。不滿足，往下找到第一個(gè)滿足的，挪上去

class Solution { public:int minSwaps(vector<vector<int>>& grid) {int i, j, sum = 0, n = grid.size(), ans = 0;vector<int> num;for(i = 0; i < n; ++i){sum = 0;for(j = n-1; j>=0 && grid[i][j]==0 ; --j)sum++;num.push_back(sum);//末尾連續(xù)0的個(gè)數(shù)}for(i = 0; i < n; ++i){if(num[i] >= n-i-1)continue;//0的個(gè)數(shù)夠了，不動(dòng)j = i;while(j < n && num[j] < n-i-1){ //往下找到一個(gè)0夠多的j++;}if(j == n)//沒找到，返回-1return -1;while(num[i] < n-i-1){ //找到了，往上挪swap(num[j], num[j-1]);ans++;j--;}}return ans;} };

168 ms 25.9 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1536. 排布二进制网格的最少交换次数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。