|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- 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: -1
- Explanation: 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.length
- n == grid[i].length
- 1 <= n <= 200
- grid[i][j] is 0 or 1
复制代码
- class Solution:
- def minSwaps(self, grid: List[List[int]]) -> int:
- zeros = [0 for _ in grid]
- result = 0
- for i in range(len(grid)):
- count = 0
- for j in range(len(grid[i]) - 1, -1, -1):
- if grid[i][j] != 0:
- break
- count += 1
- zeros[i] = count
-
- n = len(grid)
- for i in range(len(grid)):
- target = n - i - 1
- for j in range(i, len(grid) + 1):
-
- if j < n and zeros[j] >= target:
- break
- if j == n:
- return -1
- result += j - i
- temp = zeros[j]
- for k in range(j, i, -1):
- zeros[k] = zeros[k - 1]
- zeros[i] = temp
- return result
复制代码 |
|