贪心：不限操作方式的重排问题

字数统计: 4.8k字 | 阅读时长: 21分

2020-09-28

摘要: 几个用贪心解决的重排问题场景

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

对于一个数组来说，对其元素重新排序是最重要的操作。如果排序的依据就是从小到大，那么就是常规的排序算法。还有很多重排的问题，其要求不像从小到大这么严格，而是满足一些要求即可。比如文章奇数位置元素排在偶数位置元素之前中讨论的是一种简单的情况，要求是使得奇数位置元素排在偶数位置元素之前。

本文我们讨论三类稍微复杂的重排问题，对数组 A 重新排序，使得：

(1) A 中相邻 k 个元素互不相同。
(2) $A[i] > B[i]$ 的数目最大化（田忌赛马）。
(3) A 上的某种权值或指标最大。

它们的共同点都是对给定数组 $A$ 重新排序，满足给定的要求即可，对排序过程的具体操作也没有要求。

$1 要求相邻 k 个元素互不相同

358. K 距离间隔重排字符串

给你一个非空的字符串 s 和一个整数 k ，你要将这个字符串 s 中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离至少为 k 。如果无法做到，请返回一个空字符串 “”。

提示：

1
2
3

1 <= s.length <= 3e5
s 仅由小写英文字母组成
0 <= k <= s.length

示例 1：
输入: s = “aabbcc”, k = 3
输出: “abcabc”
解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。

示例 2:
输入: s = “aaabc”, k = 3
输出: “”
解释: 没有办法找到可能的重排结果。

示例 3:
输入: s = “aaadbbcc”, k = 2
输出: “abacabcd”
解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。

算法：贪心、堆

预处理信息：vector<int> char_cnts(26) 记录每个字符的出现次数，在预处理过程中遇到不合法的情况直接返回空串。

从前到后枚举答案的每个位置 i，从所有字符中选一个，这个选择是贪心的，即选择当前频数最大的那个，此外被选字符的上一次插入的位置必须 <= i-k。

被选择为当前位置的答案的那个字符频数减一，之后还要参与竞选，但减一之后不一定就是频数最大的了，因此频数需要用堆动态地维护起来。

更新答案时，可以用 vector<int> prev_idx(26, -n) 动态维护字符上一次插入的位置；也可以用 buffer 一次捞 k 个，就不用看上次的位置了。

代码 (C++)

用 vector<int> prev_idx(26, -n) 动态维护字符上一次插入的位置。

class Solution {
public:
    string rearrangeString(string s, int k) {
        int n = s.size();
        if(n == 1 || k == 0) return s;
        // 有解的条件，n / k 商 p 余 q
        // 最多有 q 个 char 的 cnt == p + 1, 其余均需要 <= p
        int p = n / k, q = n % k;

        vector<int> char_cnt(26, 0);
        int M = 0; // cnt == p + 1 的个数
        for(int i = 0; i < n; ++i)
        {
            int cur = s[i] - 'a';
            ++char_cnt[cur];
            if(char_cnt[cur] > p + 1)
                return "";
            if(char_cnt[cur] == p + 1)
            {
                ++M;
                if(M > q)
                    return "";
            }
        }
        // 在循环中没有退出说明有解

        using PII = pair<int, int>; // (频数，字符)
        priority_queue<PII> pq;
        for(int i = 0; i < 26; ++i)
        {
            if(char_cnt[i] > 0)
                pq.push(PII(char_cnt[i], i));
        }

        // 更新答案
        vector<int> prev_idx(26, -n);
        vector<PII> buffer(26);
        string result(n, ' ');
        for(int i = 0; i < n; ++i)
        {
            int m = 0;
            while(!pq.empty() && i - prev_idx[pq.top().second] < k)
            {
                buffer[m] = pq.top();
                ++m;
                pq.pop();
            }
            // if(pq.empty()) return "";
            PII cur = pq.top();
            pq.pop();
            for(int j = 0; j < m; ++j)
                pq.push(buffer[j]);
            result[i] = cur.second + 'a';
            prev_idx[cur.second] = i;
            --cur.first;
            if(cur.first > 0)
                pq.push(cur);
        }
        return result;
    }
};

更新答案时候，k 个字符一组: 用 vector<PII> buffer(k); 一次捞 k 个，就不用看上次的位置了。

// 更新答案
vector<PII> buffer(k);
string result(n, ' ');
for(int i = 0; i < n; i += k)
{
    for(int j = 0; j < min(k, n - i); ++j)
    {
        buffer[j] = pq.top();
        pq.pop();
    }
    for(int j = 0; j < min(k, n - i); ++j)
    {
        PII cur = buffer[j];
        result[i + j] = cur.second + 'a';
        --cur.first;
        if(cur.first > 0)
            pq.push(cur);
    }
}
return result;

767. 重构字符串

给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。

返回 s 的任意可能的重新排列。若不可行，返回空字符串 “” 。

提示:

1 2	1 <= s.length <= 500 s 只包含小写字母

示例 1:
输入: s = “aab”
输出: “aba”

示例 2:
输入: s = “aaab”
输出: “”

算法：贪心、堆

与 358. K 距离间隔重排字符串一样的堆贪心思路。

代码 (C++)

class Solution {
public:
    string reorganizeString(string S) {
        vector<int> char_cnts(26);
        for(const char &ch: S)
            ++char_cnts[ch - 'a'];

        using PIC = pair<int, char>;
        priority_queue<PIC> pq;
        for(char ch = 'a'; ch <= 'z'; ++ch)
            if(char_cnts[ch - 'a'] > 0)
                pq.push(PIC(char_cnts[ch - 'a'], ch));

        string result;
        while(!pq.empty())
        {
            PIC buf1 = pq.top();
            pq.pop();
            result += buf1.second;
            --buf1.first;
            if(pq.empty() && buf1.first > 0)
                return "";
            if(!pq.empty())
            {
                PIC buf2 = pq.top();
                pq.pop();
                result += buf2.second;
                --buf2.first;
                if(buf2.first > 0)
                    pq.push(buf2);
            }
            if(buf1.first > 0)
                pq.push(buf1);
        }
        return result;
    }
};

621. 任务调度器

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个相同种类的任务之间必须有长度为 n 的冷却时间。

返回完成所有任务所需要的最短时间间隔。

提示：

1
2
3

1 <= tasks.length <= 1e4
tasks[i] 是大写英文字母
0 <= n <= 100

示例 1：
输入：tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

示例 2：
输入：tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
[“A”,”A”,”A”,”B”,”B”,”B”]
[“A”,”B”,”A”,”B”,”A”,”B”]
[“B”,”B”,”B”,”A”,”A”,”A”]
…
诸如此类

示例 3：
输入：tasks = [“A”,”A”,”A”,”A”,”A”,”A”,”B”,”C”,”D”,”E”,”F”,”G”], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

算法：贪心、堆

与 358. K 距离间隔重排字符串基本相同，区别的地方在于当没有合法的字符可选择的时候，用空格代替。

预处理信息，用堆维护构造答案过程中字符的剩余个数。

每一轮取最多 n + 1 个字符，更新答案，再更新各个字符的剩余个数，再放回堆中。

另：本题可以通过画图和推公式的方式解决(主体依然是贪心，但是通过数学推导就不用频繁的入堆出堆了)。

代码 (C++)

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> char_cnts(26);
        for(const char &ch: tasks)
            ++char_cnts[ch - 'A'];
        using PIC = pair<int, char>;
        priority_queue<PIC> pq;
        for(char ch = 'A'; ch <= 'Z'; ++ch)
            if(char_cnts[ch - 'A'] > 0)
                pq.push(PIC(char_cnts[ch - 'A'], ch));

        // 更新答案
        vector<PIC> buffer;
        int ans = 0;
        while(!pq.empty())
        {
            // 不断从堆顶取元素，直至堆空或者已经取满 n + 1 个
            buffer.clear();
            for(int j = 0; j < n + 1 && !pq.empty(); ++j)
            {
                PIC cur = pq.top();
                pq.pop();
                buffer.push_back(cur);
            }
            int num_char = buffer.size();
            for(PIC &item: buffer)
            {
                --item.first;
                if(item.first > 0)
                    pq.push(item);
            }
            if(pq.empty())
                ans += num_char;
            else
                ans += n + 1;
        }
        return ans;
    }
};

1054. 距离相等的条形码

题解参考：自定义堆或优先级队列的比较规则：基于比较函数或键函数。

$2 田忌赛马：A[i] > B[i] 的数目最大化

870. 优势洗牌

给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

示例 1：
输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]

示例 2：
输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]

提示：

1
2
3

1 <= nums1.length <= 1e5
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 1e9

算法：贪心、平衡树

贪心：从前向后枚举 B 中元素 b，在 A 中找到大于 b 的元素中最小的那一个作为当前选择的 a，如果 A 没有比 b 大的，则取 A 中最小的作为当前选择的 a。

维护贪心的算法或数据结构：平衡树。

代码 (C++)

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        int n = A.size();
        multiset<int> setA;
        for(int a: A)
            setA.insert(a);
        vector<int> result(n);
        for(int i = 0; i < n; ++i)
        {
            int b = B[i];
            // 在 A 中找到大于 b 的最小的 a
            // 如果没有大于 b 的，则取最小的 a
            auto it = setA.upper_bound(b);
            if(it == setA.end())
            {
                result[i] = *setA.begin();
                setA.erase(setA.begin());
            }
            else
            {
                result[i] = *it;
                setA.erase(it);
            }
        }
        return result;
    }
};

455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

提示：

1
2
3

1 <= g.length <= 3e4
0 <= s.length <= 3e4
1 <= g[i], s[j] <= 231 - 1

算法：贪心、平衡树

贪心：从前向后枚举 G 中元素 g，在 S 中找到大于等于 g 的元素中最小的那一个作为当前选择的 s，如果 S 没有比 g 大的，不取 s。

维护贪心的算法或数据结构：平衡树。

代码 (C++)

class Solution {
public:
    int findContentChildren(vector<int>& G, vector<int>& S) {
        int n = S.size();
        multiset<int> setS;
        for(int s: S)
            setS.insert(s);
        int ans = 0;
        int m = G.size();
        for(int i = 0; i < m; ++i)
        {
            int g = G[i];
            // 在 S 中找到大于等于 g 的最小的 s
            // 如果没有大于等于 g 的，不取 s
            auto it = setS.lower_bound(g);
            if(it != setS.end())
            {
                setS.erase(it);
                ++ans;
            }
        }
        return ans;
    }
};

1433. 检查一个字符串是否可以打破另一个字符串

给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1 的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。

字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。

提示：

s1.length == n
s2.length == n
1 <= n <= 1e5
所有字符串都只包含小写英文字母。

示例 1：
输入：s1 = “abc”, s2 = “xya”
输出：true
解释：”ayx” 是 s2=”xya” 的一个排列，”abc” 是字符串 s1=”abc” 的一个排列，且 “ayx” 可以打破 “abc” 。

示例 2：
输入：s1 = “abe”, s2 = “acd”
输出：false
解释：s1=”abe” 的所有排列包括：”abe”，”aeb”，”bae”，”bea”，”eab” 和 “eba” ，s2=”acd” 的所有排列包括：”acd”，”adc”，”cad”，”cda”，”dac” 和 “dca”。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。

示例 3：
输入：s1 = “leetcodee”, s2 = “interview”
输出：true

算法：贪心、排序

赢的条件是所有的字符均要大于另一个字符串的字母，比正常的田忌赛马简单。

代码 (C++)

class Solution {
public:
    bool checkIfCanBreak(string s1, string s2) {
        int n = s1.size();
        if(n == 1) return true;
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        // 找到第一个不相同的位置
        int i = 0;
        while(i < n && s1[i] == s2[i])
            ++i;
        if(i == n) return true;
        if(s1[i] > s2[i])
        {
            for(int j = i + 1; j < n; ++j)
                if(s1[j] < s2[j])
                    return false;
        }
        else
        {
            for(int j = i + 1; j < n; ++j)
                if(s1[j] > s2[j])
                    return false;
        }
        return true;
    }
};

$3 权值最大

1589. 所有排列中的最大和

有一个整数数组 nums ，和一个查询数组 requests ，其中 requests[i] = [starti, endi] 。第 i 个查询求 nums[starti] + nums[starti + 1] + … + nums[endi - 1] + nums[endi] 的结果，starti 和 endi 数组索引都是从 0 开始的。

你可以任意排列 nums 中的数字，请你返回所有查询结果之和的最大值。

由于答案可能会很大，请你将它对 1e9 + 7 取余后返回。

提示：

n == nums.length
1 <= n <= 1e5
0 <= nums[i] <= 1e5
1 <= requests.length <= 1e5
requests[i].length == 2
0 <= starti <= endi < n

示例 1：
输入：nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
输出：19
解释：一个可行的 nums 排列为 [2,1,3,4,5]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
总和为：8 + 3 = 11。
一个总和更大的排列为 [3,5,4,2,1]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5 = 8
总和为： 11 + 8 = 19，这个方案是所有排列中查询之和最大的结果。

示例 2：
输入：nums = [1,2,3,4,5,6], requests = [[0,1]]
输出：11
解释：一个总和最大的排列为 [6,5,4,3,2,1] ，查询和为 [11]。

示例 3：
输入：nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
输出：47
解释：一个和最大的排列为 [4,10,5,3,2,1] ，查询结果分别为 [19,18,10]。

算法：贪心、排序

查询次数越多的 idx，放置越大的数字。

代码 (C++)

struct Idx
{
    int idx;
    int cnt;
    Idx(int idx, int cnt=0):idx(idx),cnt(cnt){}
};

struct IdxCmp
{
    bool operator()(const Idx& i1, const Idx& i2) const
    {
        return i1.cnt < i2.cnt;
    }
};

class Solution {
public:
    int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
        int n = nums.size();
        vector<int> left_end(n), right_end(n);
        for(const vector<int> &e: requests)
        {
            ++left_end[e[0]];
            ++right_end[e[1]];
        }
        vector<Idx> idxs;
        int cnt = 0;
        for(int i = 0; i < n; ++i)
        {
            cnt += left_end[i];
            idxs.emplace_back(i, cnt);
            cnt -= right_end[i];
        }
        sort(idxs.begin(), idxs.end(), IdxCmp());
        sort(nums.begin(), nums.end());
        vector<int> rearranged(n);
        for(int i = 0; i < n; ++i)
            rearranged[idxs[i].idx] = nums[i];
        vector<int> sums(n + 1);
        for(int i = 1; i <= n; ++i)
            sums[i] = sums[i - 1] + rearranged[i - 1];
        int ans = 0;
        for(const vector<int> &e: requests)
        {
            ans = (ans + (ll)sums[e[1] + 1] - sums[e[0]]) % MOD;
        }
        return ans;
    }

private:
    using ll = long long;
    const int MOD = 1e9 + 7;
};

1402. 做菜顺序

一个厨师收集了他 n 道菜的满意程度 satisfaction ，这个厨师做出每道菜的时间都是 1 单位时间。

一道菜的「 like-time 系数」定义为烹饪这道菜结束的时间（包含之前每道菜所花费的时间）乘以这道菜的满意程度，也就是 time[i]*satisfaction[i] 。

返回厨师在准备了一定数量的菜肴后可以获得的最大 like-time 系数总和。

你可以按任意顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。

提示：

1
2
3

n == satisfaction.length
1 <= n <= 500
-1000 <= satisfaction[i] <= 1000

示例 1：
输入：satisfaction = [-1,-8,0,5,-9]
输出：14
解释：去掉第二道和最后一道菜，最大的 like-time 系数和为 (-11 + 02 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。

示例 2：
输入：satisfaction = [4,3,2]
输出：20
解释：可以按照任意顺序做菜 (21 + 32 + 4*3 = 20)

示例 3：
输入：satisfaction = [-1,-4,-5]
输出：0
解释：大家都不喜欢这些菜，所以不做任何菜就可以获得最大的 like-time 系数。

算法：贪心、排序

喜爱之越高的，越放在后面做，使其对权的贡献尽可能大。

代码 (C++)

class Solution {
public:
    int maxSatisfaction(vector<int>& s) {
        if(s.empty()) return 0;
        sort(s.begin(), s.end(), greater<int>());
        int n = s.size();
        int ans = 0;
        int dp = 0;
        int sum = 0;
        for(int i = 0; i < n; ++i)
        {
            sum += s[i];
            dp = dp + sum;
            ans = max(ans, dp);
        }
        return ans;
    }
};

561. 数组拆分

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该最大总和。

提示：

1
2
3

1 <= n <= 1e4
nums.length == 2 * n
-1e4 <= nums[i] <= 1e4

示例 1：
输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：

(1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3

(1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3

(1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

示例 2：
输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

算法：贪心

将 nums 分为若干项 $\min(a_{i}, b_{i})$，不妨设 $a_{i} < b_{i}$，对于给定 $a_{i}$，$b_{i}$ 选择大于等于 $a_{i}$ 的元素中最小的。

代码 (Python)

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum([nums[i] for i in range(len(nums)) if (i & 1) == 0])

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法基础算法

贪心：不限操作方式的重排问题

$1 要求相邻 k 个元素互不相同

358. K 距离间隔重排字符串

算法：贪心、堆

代码 (C++)

767. 重构字符串

算法：贪心、堆

代码 (C++)

621. 任务调度器

算法：贪心、堆

代码 (C++)

1054. 距离相等的条形码

$2 田忌赛马：A[i] > B[i] 的数目最大化

870. 优势洗牌

算法：贪心、平衡树

代码 (C++)

455. 分发饼干

算法：贪心、平衡树

代码 (C++)

1433. 检查一个字符串是否可以打破另一个字符串

算法：贪心、排序

代码 (C++)

$3 权值最大

1589. 所有排列中的最大和

算法：贪心、排序

代码 (C++)

1402. 做菜顺序

算法：贪心、排序

代码 (C++)

561. 数组拆分

算法：贪心

代码 (Python)