贪心-限制操作方式的重排问题

字数统计: 1.5k字 | 阅读时长: 6分

2020-10-26

摘要: 带限制操作方式的重排问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章贪心：不限操作方式的重排问题中，我们讨论了几种给数组重新排序的场景，需要满足一些给定的要求，或者最大化某个指标。共同点是都可以用贪心来解决，也就是说枚举重拍后的每个位置，在选择该位置要填那个元素的时候，选择的策略是贪心的。

本文我们继续看几个在数组上重新排序，满足一些约束性要求或最大化某个指标。但是重排的操作方式是有限制的，比如只能交换相邻元素、选择非空子数组翻转或升序、与另一数组交换任意一组元素对。

$1 交换相邻元素

1505. 最多 K 次交换相邻数位后得到的最小整数

题解参考：力扣1505-最多K次交换相邻数位后得到的最小整数。

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

给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的相邻两行进行交换。

一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。

请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1 。

主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。

提示：

n == grid.length
n == grid[i].length
1 <= n <= 200
grid[i][j] 要么是 0 要么是 1 。

示例 1：
输入：
1
2
3
grid = [[0,0,1]
       ,[1,1,0]
       ,[1,0,0]]
输出：3

示例 2：
输入：
1
2
3
4
grid = [[0,1,1,0]
       ,[0,1,1,0]
       ,[0,1,1,0]
       ,[0,1,1,0]]
输出：-1
解释：所有行都是一样的，交换相邻行无法使网格符合要求。

示例 3：
输入：
1
2
3
grid = [[1,0,0]
       ,[1,1,0]
       ,[1,1,1]]
输出：0

算法：贪心

预处理：

1	idxs[i] := [i..n-1]均为0的行下标

有解条件：

1	idxs[i].size() >= i , i = 1,2,...,n-1

从高往低处理行，维护 move[i] 表示第 i 行是否往前移动过：

枚举行号 i (0,1,...,n-1):
    j = idxs[i] 中从左往右第一个没有移动过的
    j 是原位置，但之前的迭代中 j 可能后移了，后移次数为 [j+1..n-1] 中有多少个往前移动过
    ans = j - i + 后移次数
    标记 move[j] = true

代码 (C++)

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> idxs(n);
        // idxs[i] := [i,..,n-1] 均为 0 的行下标
        for(int i = 0; i < n; ++i) // O(N)
        {
            int j = left_1(grid[i]); // O(N)
            if(j < n)
            {
                for(int k = j; k < n; ++k)
                    idxs[k].push_back(i); // O(N^2)
            }
        }
        for(int i = 1; i < n; ++i)
            if((int)idxs[i].size() < i)
                return -1;
        vector<bool> moved(n, false); // move[i] := 第 i 行是否往前移动过了
        int ans = 0;
        for(int i = 0; i < n - 1; ++i)
        {
            // [i+1..n-1] 都是 0 的最小行号
            int j;
            for(int jj: idxs[i + 1]) // O(N^2)
            {
                if(moved[jj])
                    continue;
                j = jj;
                break;
            }
            int moved_cnt = 0; // [j+1,..n-1] 有多少移动过
            for(int jj = j + 1; jj < n; ++jj) // O(N^2)
                moved_cnt += moved[jj];
            ans += j - i + moved_cnt;
            moved[j] = true;
        }
        return ans;
    }

private:
    int left_1(const vector<int>& row)
    {
        int n = row.size();
        for(int i = n - 1; i >= 0; --i)
            if(row[i] == 1)
                return i + 1;
        return 0;
    }
};

$2 选择非空子数组进行翻转

1460. 通过翻转子数组使两个数组相等

给你两个长度相同的整数数组 target 和 arr 。每一步中，你可以选择 arr 的任意非空子数组并将它翻转。你可以执行此过程任意次。

如果你能让 arr 变得与 target 相同，返回 True；否则，返回 False 。

提示：

target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000

示例 1：
输入：target = [1,2,3,4], arr = [2,4,1,3]
输出：true
解释：你可以按照如下步骤使 arr 变成 target：
1- 翻转子数组 [2,4,1] ，arr 变成 [1,4,2,3]
2- 翻转子数组 [4,2] ，arr 变成 [1,2,4,3]
3- 翻转子数组 [4,3] ，arr 变成 [1,2,3,4]
上述方法并不是唯一的，还存在多种将 arr 变成 target 的方法。

示例 2：
输入：target = [7], arr = [7]
输出：true
解释：arr 不需要做任何翻转已经与 target 相等。

示例 3：
输入：target = [3,7,9], arr = [3,7,11]
输出：false
解释：arr 没有数字 9 ，所以无论如何也无法变成 target 。

算法：贪心、排序

将 arr 与 target 分别排序，如果所得结果相同，则可以通过对 arr 的操作变为 target。

代码 (C++)

class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        int n = target.size(), m = arr.size();
        if(n != m) return false;
        sort(target.begin(), target.end());
        sort(arr.begin(), arr.end());
        for(int i = 0; i < n; ++i)
            if(arr[i] != target[i])
                return false;
        return true;
    }
};