贪心-分拆问题

  |  

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

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


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


$1 子集分拆

1.1 顺子,不限操作方式

846. 一手顺子

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

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

提示:

1
2
3
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++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
2
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++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
2
3
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++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
2
3
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. 划分数组为连续数字的集合 这两个问题也是选形成顺子的集合且顺子长度固定,但是不同的是这里要选形成顺子的子序列且顺子长度不固定。

错误的贪心算法:

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

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

正确的贪心算法:

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

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

代码 (C++)

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
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;
}
};

Share