1655-分配重复整数

Raphael Liu Lv10

给你一个长度为 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])
 Comments
On this page
1655-分配重复整数