leetcode 1536. Minimum Swaps to Arrange a Binary Grid 贪心冒泡排序

题目

https://leetcode.com/contest/weekly-contest-200/problems/minimum-swaps-to-arrange-a-binary-grid/
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

思路

排序问题,把行数据转换为右边连续的0的个数,而后进行冒泡排序,但是改为贪心策略,对应位置需要的数为 n,n-1,n-2…3,2,1,0 从最高位开始如果该位置的数>=对应的要求,则跳过,如果小于,则向后寻找第一个满足该目标的数,冒泡交换到该位置,记录交换次数,如果找不到则返回-1
基于这样一个思想

当前位置所需要的数一定是最大的,所以向后寻找时第一个满足的数即使是剩余目标中的最大数也是符合预期的,而最近保证了交换次数最小

源码

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        vector<int> nums;
        for(auto p:grid){
            int count = 0;
            for(int i = p.size()-1;i>=0;--i){
                if(p[i]==0){
                    count++;
                }else break;
            }
            nums.push_back(count);
        }
        int res = 0;
        for(int i = 0;i < nums.size();++i){
            if(nums[i] < nums.size()-i-1){
                bool f = true;
                for(int j = i+1;j < nums.size();++j){
                    if(nums[j]>=nums.size()-i-1){
                        int t = nums[j];
                        nums.erase(nums.begin()+j);
                        nums.insert(nums.begin()+i,t);
                        res += j-i;
                        f = false;
                        break;
                    }
                }
                if(f)return -1;
            }
        }
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注