贪心-分拆问题

摘要: 一些用贪心解决的分拆类问题，

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

---

在文章 分拆类问题汇总 中我们总结了分拆类问题。这类问题没有固定的算法，要根据具体的问题看，本文我们看一下适用贪心算法的分拆问题，涉及 4 道题。以下是总览。

• 子集分拆
  • 846. 一手顺子
  • 1296. 划分数组为连续数字的集合
• 子序列分拆
  • 1121. 将数组分成几个递增序列
  • 659. 分割数组为连续子序列

---

$1 子集分拆

1.1 顺子，不限操作方式

846. 一手顺子

Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize 。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。

提示：

1 <= hand.length <= 1e4
0 <= hand[i] <= 1e9
1 <= groupSize <= hand.length

示例 1：
输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
输出：true
解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。

示例 2：
输入：hand = [1,2,3,4,5], groupSize = 4
输出：false
解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。

算法：贪心

贪心：始终取当前手牌中的最小的牌，看该牌能否形成长为 W 的顺子，如果行，将将这 W 张牌从手牌中删掉，否则就返回 false。

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

代码 (C++)

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int W) {
        multiset<int> setting;
        int n = hand.size();
        if(n % W != 0)
            return false;
        for(int i: hand)
            setting.insert(i);
        while(!setting.empty())
        {
            int left = *setting.begin();
            setting.erase(setting.begin());
            for(int i = 1; i < W; ++i)
            {
                auto it = setting.find(left + i);
                if(it == setting.end())
                    return false;
                setting.erase(it);
            }
        }
        return true;
    }
};

1296. 划分数组为连续数字的集合

给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。

如果可以，请返回 true；否则，返回 false。

提示：

1 <= k <= nums.length <= 1e5
1 <= nums[i] <= 1e9

示例 1：
输入：nums = [1,2,3,3,4,4,5,6], k = 4
输出：true
解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。

示例 2：
输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
输出：true
解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。

示例 3：
输入：nums = [3,3,2,2,1,1], k = 3
输出：true

示例 4：
输入：nums = [1,2,3,4], k = 3
输出：false
解释：数组不能分成几个大小为 3 的子数组。

算法：贪心

与 846. 一手顺子 除了数据规模之外没有不同。

代码 (C++)

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        multiset<int> hands;
        for(int i: nums)
            hands.insert(i);
        if(hands.size() % k != 0)
            return false;
        while(!hands.empty())
        {
            int start = *hands.begin();
            hands.erase(hands.begin());
            for(int i = start + 1; i < start + k; ++i)
            {
                auto it = hands.find(i);
                if(it == hands.end())
                    return false;
                hands.erase(it);
            }
        }
        return true;
    }
};

---

$2 子序列分拆

2.1 递增

1121. 将数组分成几个递增序列

给你一个 非递减 的正整数数组 nums 和整数 K，判断该数组是否可以被分成一个或几个 长度至少 为 K 的 不相交的递增子序列。

提示：

1 <= nums.length <= 10^5
1 <= K <= nums.length
1 <= nums[i] <= 10^5

示例 1：
输入：nums = [1,2,2,3,3,4,4], K = 3
输出：true
解释：
该数组可以分成两个子序列 [1,2,3,4] 和 [2,3,4]，每个子序列的长度都至少是 3。

示例 2：
输入：nums = [5,6,6,7,8], K = 3
输出：false
解释：
没有办法根据条件来划分数组。

算法：贪心

每个子序列要求严格递增，因此相同的数字必须分到不同的子序列中。

贪心：找到数组中出现次数最多的那个数字，其出现次数为 t，nums.size() >= tk，就可以满足。

代码 (C++)

class Solution {
public:
    bool canDivideIntoSubsequences(vector<int>& nums, int K) {
        if(K == 1) return true;
        int n = nums.size();
        unordered_map<int, int> mapping;
        for(int i = 0; i < n; ++i)
            ++mapping[nums[i]];
        int t = 0;
        for(auto i: mapping)
            if(i.second > t)
                t = i.second;
        return t * K <= n;
    }
};

2.2 顺子

659. 分割数组为连续子序列

给你一个按 非递减顺序 排列的整数数组 nums 。

请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述 两个 条件：

• 每个子序列都是一个 连续递增序列（即，每个整数 恰好 比前一个整数大 1 ）。
• 所有子序列的长度 至少 为 3 。
• 如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。

提示：

1 <= nums.length <= 1e4
-1000 <= nums[i] <= 1000
nums 按非递减顺序排列

示例 1：
输入：nums = [1,2,3,3,4,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,5] —> 1, 2, 3
[1,2,3,3,4,5] —> 3, 4, 5

示例 2：
输入：nums = [1,2,3,3,4,4,5,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,4,5,5] —> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] —> 3, 4, 5

示例 3：
输入：nums = [1,2,3,4,4,5]
输出：false
解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。

算法：贪心

升序排序的整数数组 num（可能包含重复数字），每个子序列为长度至少为 3 的顺子。

846. 一手顺子 / 1296. 划分数组为连续数字的集合 这两个问题也是选形成顺子的集合且顺子长度固定，但是不同的是这里要选形成顺子的子序列且顺子长度不固定。

错误的贪心算法：

- step1: 对于没选中的最小的数字 c，看以它开头能否有长度等于3的子数组，如果有，则将3个元素标记删除，并记录该顺子的结尾数字，否则直接跳过。
- step2: 对于剩下未被选中的数字 c，查询是否有以 c-1 结尾的顺子，如果有，则插入，并更新顺子结尾的标记，然后将 c 标记删除，若没有返回 false。

标记删除的过程用平衡树维护。**因为 nums 已经升序，因此插入平衡树中不会破坏子序列的顺序性质，但是方便了插入删除。**

正确的贪心算法：

对于没选中的最小数字 c，先看有没有以 c-1 结尾的顺子，如果有则插入到那个顺子里并更新顺子结尾数字的信息，否则再看有没有以 c 开头的顺子，若有就建立该顺子并记录结尾数字，如果再没有就返回 false。

可以将平衡树改为哈希表记录各个数字的出现次数，因为给定数组已经有序，不需要通过插入平衡树的方式来满足顺序条件了。

代码 (C++)

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        multiset<int> hands;
        for(int i: nums)
            hands.insert(i);
        auto iter = hands.begin();
        unordered_map<int, int> mapping; // mapping[i] := 以 i 为结尾的顺子个数
        while(iter != hands.end())
        {
            int cur = *iter;
            if(mapping[cur - 1] > 0)
            {
                --mapping[cur - 1];
                ++mapping[cur];
                iter = hands.erase(iter);
            }
            else if(hands.count(cur + 1) && hands.count(cur + 2))
            {
                hands.erase(hands.find(cur + 1));
                hands.erase(hands.find(cur + 2));
                iter = hands.erase(iter);
                ++mapping[cur + 2];
            }
            else
                return false;
        }
        return true;
    }
};

---