1655. 分配重复整数

题目描述

给了一个数组nums，数组中最多有50个不同的值
再给了m个顾客的订单数组，数组元素ei的含义是第i个顾客需要有ei个相同的整数
问给的nums能不能满足以上所有顾客的要求？

基本分析

1. 人数m不超过10？用二进制表示能满足人的子集
2. 具体地取哪些数字重要吗？值不重要，值出现的个数重要->用一个辅助数组cnt去存值出现的次数[1,1,2,2,1,3]转化为[3,2,1]
3. 怎么统计某个子集需要的个数？针对订单为[2,3]情况,ssum[0]=0,ssum[1]=2,ssum[10]=3,ssum[11]=5。这里的5是需要的总和，但不一定要求某个cnt[i]一定要大于这个
4. dp状态？f[i][j]表示考虑前i个数组，分配状态为j时，能不能满足要求
5. dp边界？对所有的i，j=0时候表示不需要分配，此时都能满足
6. 考虑转移？
   • （1）先遍历数组维度i，前i个数字
   • （2）再遍历状态维度。此时可能i-1就能满足j，这个时候直接转移退出j讨论；否则i-1不能满足，需要继续往下走
   • （3）枚举j的子集，把j分为前i-1物品完成的状态prev和利用物品i完成的状态。通过遍历找到满足的情况时，f[i][j]为True。注意枚举子集的时候先把s设置为j，之后用 s = (s-1)&j实现

代码

class Solution:
    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
        tmp = Counter(nums)
        cnt = []
        for k, v in tmp.items():
            cnt.append(v)
        
        n, m = len(cnt), len(quantity)
        mask = 1<<m
        ssum = [0] * mask
        for i in range(1, mask):
            for j in range(m):
                if i &(1<<j) != 0:
                    ssum[i] = ssum[i-(1<<j)] + quantity[j]
                    break
        print(ssum)
        f = [[False] * (mask) for _ in range(n)]
        for i in range(n):
            f[i][0] = True
        
        for i in range(n):
            for j in range(mask):
                if i>0 and f[i-1][j]:
                    f[i][j] = True
                    continue
                s = j
                while s:
                    prev = j-s
                    if i == 0:
                        last = (prev ==0)
                    else:
                        last = f[i-1][prev]
                    
                    need = ssum[s]<=cnt[i]
                    if last and need:
                        f[i][j] = True
                        break
                    s = (s-1)&j

        return f[-1][-1] 

复杂度

时间：\(待确认\)
空间：\(O(n*2^m)\)

总结

1. 看出频数重要，从给出的nums信息中处理出cnt
2. 预处理出ssum数组，可以快速查处某个子集需要的相等数的个数
3. dp中先枚举i个数组的维度；再枚举可能的组合j，对j判断i-1是不是已经满足，满足跳过j，不满足往下走；枚举j的子集，将j分为prev和s两部分，看是不是存在满足f[i-1][prev]==True和ssum[s]<=cnt[i]的关系