題目： LeetCode - 1536. Minimum Swaps to Arrange a Binary Grid

題目說明

給一個二維陣列，代表一個正方形，裡面的值只有 0 或 1。題目要求第 n 行需要有 邊長 - n - 1 個 0 在最右邊，每次可以選擇一行與鄰近的行互換，求最少的交換次數，若題目無法達成要求的話回傳 - 1。

解題思路

使用一個陣列紀錄每行右邊 0 的個數，之後找到要搬移的行進行搬移並紀錄次數即可。

參考解法

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
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size(), target = n - 1, count = 0;
        vector<int> zeroes(n);
        for(int i = 0; i < n; ++i)
            for(int j = n - 1; j >= 0; --j)
            {
                if(grid[i][j] == 1)
                    break;
                ++zeroes[i];
            }
        for(int i = 0; i < n; ++i, --target)
        {
            int j = i;
            while(j < n && target > zeroes[j])
                ++j;
            if(j == n)
                return -1;
            zeroes.insert(zeroes.begin() + i, zeroes[j]);
            zeroes.erase(zeroes.begin() + j + 1);
            count += j - i;
        }
        return count;
    }
};

2020-09-01 重寫

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
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size(), target = n - 1, count = 0;
        vector<int> zeroes(n);
        for(int i = 0; i < n; ++i) for(int j = n - 1; j >= 0 && !grid[i][j]; ++zeroes[i], --j);
        for(int i = 0; i < n; ++i, --target)
        {
            int j = i;
            while(j < n && target > zeroes[j]) ++j;
            if(j == n) return -1;
            zeroes.insert(zeroes.begin() + i, zeroes[j]);
            zeroes.erase(zeroes.begin() + j + 1);
            count += j - i;
        }
        return count;
    }
};