class Solution {
public:
bool canDistribute(vector<int>& nums, vector<int>& quantity) {
}
};
1655. 分配重复整数
给你一个长度为 n 的整数数组 nums ，这个数组中至多有 50 个不同的值。同时你有 m 个顾客的订单 quantity ，其中，整数 quantity[i] 是第 i 位顾客订单的数目。请你判断是否能将 nums 中的整数分配给这些顾客，且满足：
i 位顾客 恰好 有 quantity[i] 个整数。i 位顾客拿到的整数都是 相同的 。如果你可以分配 nums 中的整数满足上面的要求，那么请返回 true ，否则返回 false 。
示例 1：
输入：nums = [1,2,3,4], quantity = [2] 输出：false 解释：第 0 位顾客没办法得到两个相同的整数。
示例 2：
输入：nums = [1,2,3,3], quantity = [2] 输出：true 解释：第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。
示例 3：
输入：nums = [1,1,2,2], quantity = [2,2] 输出：true 解释：第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [2,2] 。
提示：
n == nums.length1 <= n <= 1051 <= nums[i] <= 1000m == quantity.length1 <= m <= 101 <= quantity[i] <= 105nums 中至多有 50 个不同的数字。原站题解
python3 解法, 执行用时: 88 ms, 内存消耗: 25.2 MB, 提交时间: 2023-10-26 23:59:01
'''
记忆化递归，枚举quantidy中的每一个数值应该放到哪个容器中
找到一种合法方案即返回True
'''
from typing import List
from collections import Counter
class Solution:
def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
c = Counter(nums)
m = len(quantity)
containers = [val for val in c.values()]
containers.sort(reverse=True)
containers = containers[:m]
quantity.sort()
# con表示的容器容量元组能否容纳下quantitiy中前i项
from functools import lru_cache
@lru_cache(typed=False, maxsize=128000000)
def dp(con, i):
if i == -1:
return True
if quantity[i] > con[0]:
return False
for j in range(len(con)):
if con[j] >= quantity[i]:
new_con = list(con)
new_con[j] -= quantity[i]
new_con.sort(reverse=True)
if dp(tuple(new_con), i-1):
return True
else:
break
return False
return dp(tuple(containers), m-1)
java 解法, 执行用时: 4 ms, 内存消耗: 53.1 MB, 提交时间: 2023-10-26 23:58:51
class Solution {
public boolean canDistribute(int[] nums, int[] quantity) {
int[] map=new int[1001];
for (int i = 0; i < nums.length; i++) {
map[nums[i]]++;
}
Arrays.sort(map);
int[] maps=Arrays.copyOfRange(map,map.length-50,map.length);
Arrays.sort(quantity);
return backTrack(maps,quantity,quantity.length-1);
}
/**
*
* @param maps 频次数组
* @param quantity
* @param index quantity数组索引
* @return 返回是否可以分配
*/
public boolean backTrack(int[] maps,int[] quantity,int index){
if(index<0)return true;
for (int i = 0; i < maps.length; i++) {
if (i != 0 && maps[i] == maps[i - 1]) {
continue; // 剪枝一下 速度飙升
}
if(maps[i]>=quantity[index]){
maps[i]-=quantity[index];
if(backTrack(maps,quantity,index-1))return true;//能发货就直接返回true
maps[i]+=quantity[index];
}
}
return false;
}
}
cpp 解法, 执行用时: 440 ms, 内存消耗: 76.3 MB, 提交时间: 2023-10-26 23:58:18
class Solution {
public:
bool canDistribute(vector<int>& nums, vector<int>& quantity) {
unordered_map<int, int> cache;
for (int x: nums) {
cache[x]++;
}
vector<int> cnt;
for (auto& kv: cache) {
cnt.push_back(kv.second);
}
int n = cnt.size(), m = quantity.size();
vector<int> sum(1 << m, 0);
for (int i = 1; i < (1 << m); i++) {
for (int j = 0; j < m; j++) {
if ((i & (1 << j)) != 0) {
int left = i - (1 << j);
sum[i] = sum[left] + quantity[j];
break;
}
}
}
vector<vector<bool>> dp(n, vector<bool>(1 << m, false));
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < (1 << m); j++) {
if (i > 0 && dp[i-1][j]) {
dp[i][j] = true;
continue;
}
for (int s = j; s != 0; s = ((s - 1) & j)) { // 子集枚举，详见 https://oi-wiki.org/math/bit/#_14
int prev = j - s; // 前 i-1 个元素需要满足子集 prev = j-s
bool last = (i == 0) ? (prev == 0): dp[i-1][prev]; // cnt[0..i-1] 能否满足子集 prev
bool need = sum[s] <= cnt[i]; // cnt[i] 能否满足子集 s
if (last && need) {
dp[i][j] = true;
break;
}
}
}
}
return dp[n-1][(1<<m)-1];
}
};
golang 解法, 执行用时: 116 ms, 内存消耗: 7.7 MB, 提交时间: 2023-10-26 23:57:41
func canDistribute(a []int, quantity []int) bool {
// 预处理 quantity 每个子集的子集和
m := 1 << len(quantity)
sum := make([]int, m)
for i, v := range quantity {
bit := 1 << i
for j := 0; j < bit; j++ {
sum[bit|j] = sum[j] + v
}
}
cnt := map[int]int{}
for _, v := range a {
cnt[v]++
}
n := len(cnt)
// dp[i][j] 表示 cnt 的前 i 个元素能否满足集合为 j 的顾客
dp := make([][]bool, n+1)
for i := range dp {
dp[i] = make([]bool, m)
dp[i][0] = true
}
i := 0
for _, c := range cnt {
for j, ok := range dp[i] {
if ok {
dp[i+1][j] = true
continue
}
for sub := j; sub > 0; sub = (sub - 1) & j { // 枚举 j 的子集 sub
if sum[sub] <= c && dp[i][j^sub] { // 判断这 c 个数能否全部分给 sub，并且除了 sub 以外的 j 中的顾客也满足
dp[i+1][j] = true
break
}
}
}
i++
}
return dp[n][m-1]
}