给你一个长度为 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.length
1 <= n <= 105
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 105
nums
中至多有 50
个不同的数字。
Problem: 1655. 分配重复整数
[TOC]
思路
解题方法
- 对于集合中的顾客, 必选一个 数字 ps[idx] 来分配
- 对于 数字 ps[idx] 尝试分配顾客, 如果ps[idx]无法分配任何一个顾客, 看下一个数字
- 相当于遍历了所有情况
Code
[]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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| class Solution: def canDistribute(self, nums: List[int], quantity: List[int]) -> bool: c1=Counter(nums) ps=[] for i,(k,v) in enumerate(c1.items()): ps.append((v,i)) ps.sort(reverse=True) n=len(ps) m=len(quantity) u=(1<<m)-1 @cache def dfs(s, idx, take): if not s: return True if idx==n: return False flag=False takeall=ps[idx][0] for j in range(m): # 尝试分配顾客j if s&(1<<j): if take+quantity[j]<=takeall: flag=dfs(s^(1<<j), idx, take+quantity[j]) else: flag=dfs(s, idx+1, 0) if flag: return True
return False return dfs(u,0, 0) def canDistribute_0(self, nums: List[int], quantity: List[int]) -> bool: c1=Counter(nums) ps=[] for i,(k,v) in enumerate(c1.items()): ps.append((v,i)) ps.sort(reverse=True) n=len(ps) m=len(quantity) u=(1<<m)-1 @cache def dfs(s, idx, rest): if not s: return True if idx==n: return False flag=False for j in range(m): # 尝试分配顾客j if s&(1<<j): if rest>=quantity[j]: flag=dfs(s^(1<<j), idx, rest-quantity[j]) else: if idx+1<n: flag=dfs(s, idx+1, ps[idx+1][0]) if flag: return True
return False return dfs(u,0, ps[0][0])
|