[leetcode] 1536. Minimum Swaps to Arrange a Binary Grid

[leetcode] 1536. Minimum Swaps to Arrange a Binary Grid

Description

Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.

A grid is said to be valid if all the cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

Example 1:

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]Output: 3

Example 2:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]Output: -1Explanation: All rows are similar, swaps have no effect on the grid.

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,1]]Output: 0

Constraints:

n == grid.lengthn == grid[i].length1 <= n <= 200grid[i][j] is 0 or 1

分析

题目的意思是：给定nxn的二进制网格，现在可以交换网格的行，求最小的交换步骤使得网格的对角线全0.

用pos数组记录每行最有边为1的位置，遍历每一行求的。从上到下逐行确定，对于第 i 行，只要找到第 i…n−1 行中使得 pos[j]≤i 成立的最近的那一行 j，我们将这一行交换到第 i行即可，它对答案的贡献为 j-i。

代码

class Solution: def minSwaps(self, grid: List[List[int]]) -> int: n=len(grid) pos=[-1]*n for i in range(n): for j in range(n-1,-1,-1): if(grid[i][j]==1): pos[i]=j break res=0 for i in range(n): k=-1 for j in range(i,n): if(pos[j]<=i): res+=j-i k=j break if(k!=-1): for j in range(k,i,-1): pos[j],pos[j-1]=pos[j-1],pos[j] else: return -1 return res

参考文献

​​排布二进制网格的最少交换次数​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。