2021-09-07周赛and双周赛
2021-09-07 本文已影响0人
Cipolee
思想没错，缺点是没有理解题意+数据结构模糊+没有预处理+取模和去除多余数
给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以用若干个 互不相同的质数 相乘得到，那么我们称它为 好子集 。
比方说，如果 nums = [1, 2, 3, 4] ：
[2, 3] ，[1, 2, 3] 和 [1, 3] 是 好 子集，乘积分别为 6 = 23 ，6 = 23 和 3 = 3 。
[1, 4] 和 [4] 不是 好 子集，因为乘积分别为 4 = 22 和 4 = 22 。
请你返回 nums 中不同的 好 子集的数目对 109 + 7 取余 的结果。
nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。
示例 1：
输入：nums = [1,2,3,4]
输出：6
解释：好子集为：
- [1,2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [1,2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [1,3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/the-number-of-good-subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def numberOfGoodSubsets(self, nums: List[int]) -> int:
mod=10**9+7
#不加预处理暴力肯定过不去
'''
dict_={1,2,3,5,6,7,10,11,13,15,14,17,19,21,22,23,26,29,30}
dialed=[]
for i in nums:
if i in dict_:
dialed.append(i)
dict2={}
for i in dialed:
dict2[i]=dict2.get(i,0)+1
#print(dict2)
dialed=list(set(dialed))
n=len(dialed)
'''
dict_={2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30}
# 0,1,2,3,4,5, 6, 7, 8, 9, 10,11,12,13,14,15,16,17
#12,13,15,17
dialed=[]
#dict2={}
dict2=defaultdict(int)
valid=[True]*(1<<18)
for i in range(1,1<<18):
if not i&1:
if i&(1<<3) or i&(1<<5) or i&(1<<8) or i&(1<<13) or i&(1<<15) \
or i&(1<<17):
valid[i]=False
if i&(1<<1):
if i&(1<<3) or i&(1<<12) or i&(1<<17):
valid[i]=False
if i&(1<<2):
if i&(1<<5) or i&(1<<17):
valid[i]=False
if i&(1<<3):
if i&(1<<5) or i&(1<<8) or i&(1<<9) or i&(1<<12) or i&(1<<13) \
or i&(1<<15) or i&(1<<17):
valid[i]=False
if i&(1<<4):
if i&(1<<8) or i&(1<<12):
valid[i]=False
if i&(1<<5):
if i&(1<<8) or i&(1<<9) or i&(1<<13) or i&(1<<15) or i&(1<<17):
valid[i]=False
if i&(1<<6):
if i&(1<<13):
valid[i]=False
if i&(1<<7):
if i&(1<<15):
valid[i]=False
if i&(1<<8):
if i&(1<<12) or i&(1<<13) or i&(1<<15) or i&(1<<17):
valid[i]=False
if i&(1<<9):
if i&(1<<12) or i&(1<<17):
valid[i]=False
if i&(1<<12):
if i&(1<<17):
valid[i]=False
if i&(1<<13):
if i&(1<<15) or i&(1<<17):
valid[i]=False
if i&(1<<15):
if i&(1<<17):
valid[i]=False
#12,13,15,17
for i in nums:
if i in dict_ and i not in dict2:
dialed.append(i)
if i in dict_ or i==1:
dict2[i]=dict2.get(i,0)+1
n=len(dialed)
if n==1 and dialed[0]==1:
return 0
def cal(n):
if n==1:
return 1
ans=0
#for i in range(2,int(math.sqrt(n))+1):
for i in range(2,n+1):
#print(n,n%i)
while n and n%i==0:
n//=i
ans|=1<<i
#print('hi')
if not n:
break
return ans
dict_encode={}
for i in dialed:
dict_encode[i]=cal(i)
ans=0
#print(dialed)
#print(n)
#print(dict_encode)
cmp_1=1
if 1 in dict2:
cmp_1=2**dict2[1]
#print(cmp_1)
de_1=False
for i in range(1,1<<n):
#for i in range(1,1<<18)
if not valid[i]:
continue
#cmp=(1<<(n+1))-1
cmp=0
base=1
flag=False
flag_equal=False
try:
for j in range(n):
if (i>>j)&1:
if not flag:
#cmp&=dict_encode[dialed[j]]
cmp=dict_encode[dialed[j]]
base*=dict2[dialed[j]]
'''
if dialed[j]!=1:
base*=dict2[dialed[j]]
else:
base*=2**dict2[dialed[j]]-1
'''
flag=True
#base%=mod
else:
if cmp&dict_encode[dialed[j]]:
flag_equal=True
break
else:
cmp|=dict_encode[dialed[j]]
#base*=dict2[dialed[j]]
base*=dict2[dialed[j]]
'''
if dialed[j]!=1:
base*=dict2[dialed[j]]
else:
base*=2**dict2[dialed[j]]-1
'''
#base%=mod
except:
if i>>(n-2):
print('here')
print(i)
if not flag_equal:
if 1 in dict2:
base*=cmp_1
ans+=base
if 1 in dict_encode and ans>cmp_1 and not de_1:
de_1=True
ans-=cmp_1-1
#if ans>mod:
#ans=0
#print(ans%mod)
#ans=ans%mod
#return 0
else:
ans=ans%mod
##if base>=4:
# print(base)
#print(i)
#print(2**dict2[1]-1)
#print(type(dict2[1]))
#return ans if 1 not in dict_encode else 0
#return ans if 1 not in dict_encode else 2**dict2[1]-1
#return 0
#return ans if 1 not in dict_encode else ans -(2**dict2[1]+1)%mod
#编码方式也过不去。。怎么回事呀
return ans
python做算法题真的要求高
别人用C++能暴力过的，python过不去，必须使用时间复杂度上的优化才行。
class Solution:
def numberOfGoodSubsets(self, nums: List[int]) -> int:
mod=10**9+7
dict_=[2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30]
# 0,1,2,3,4,5, 6, 7, 8, 9, 10,11,12,13,14,15,16,17
dict2=defaultdict(int)
valid=[True]*(1<<18)
for i in range(1,1<<18):
if i&1:
if i&(1<<3) or i&(1<<5) or i&(1<<8) or i&(1<<13) or i&(1<<15) \
or i&(1<<17):
valid[i]=False
if i&(1<<1):
if i&(1<<3) or i&(1<<9) or i&(1<<12) or i&(1<<17):
valid[i]=False
if i&(1<<2):
if i&(1<<5) or i&(1<<17) or i&(1<<9):
valid[i]=False
if i&(1<<3):
if i&(1<<5) or i&(1<<8) or i&(1<<9) or i&(1<<12) or i&(1<<13) \
or i&(1<<15) or i&(1<<17):
valid[i]=False
if i&(1<<4):
if i&(1<<8) or i&(1<<12):
valid[i]=False
if i&(1<<5):
if i&(1<<8) or i&(1<<9) or i&(1<<13) or i&(1<<15) or i&(1<<17):
valid[i]=False
if i&(1<<6):
if i&(1<<13):
valid[i]=False
if i&(1<<7):
if i&(1<<15):
valid[i]=False
if i&(1<<8):
if i&(1<<12) or i&(1<<13) or i&(1<<15) or i&(1<<17):
valid[i]=False
if i&(1<<9):
if i&(1<<12) or i&(1<<17):
valid[i]=False
if i&(1<<12):
if i&(1<<17):
valid[i]=False
if i&(1<<13):
if i&(1<<15) or i&(1<<17):
valid[i]=False
if i&(1<<15):
if i&(1<<17):
valid[i]=False
#12,13,15,17
for i in nums:
if i in dict_ or i==1:
dict2[i]=dict2.get(i,0)+1
#只能类似于拒绝采样的方式了
res=0
#print(valid[8])
#print(dict2[dict_[3]]>0)
for i in range(1,1<<18):
if valid[i]:
'''
flag=False
t=[]
p=i
for j in range(18):
if p>>j&1:
if dict2[dict_[j]]>0:
t.append('1')
else:
#print(j==3)
flag=True
else:
t.append('0')
if flag:
continue
#print(''.join(t))
'''
ans=1
for j in range(18):
if (i>>j)&1:
#print(j==3)
#print(dict2[dict_[j]])
ans=ans*dict2[dict_[j]]%mod
if dict2[1]>0:
ans=ans*(pow(2,dict2[1],mod))%mod
#print(ans)
res+=ans
res=res%mod
#z=(pow(2,dict2[1],mod)-1+mod)%mod
#while res<z:
# res+=mod
#print("------")
#return res-z
return res
python在该算法下过不去
class Solution:
def numberOfGoodSubsets(self, nums: List[int]) -> int:
primes = [2,3,5,7,11,13,17,19,23,29]
cnt = [0] * 31
for num in nums:
cnt[num] += 1
cnt[1] = 2 ** cnt[1]
MODULE = 10 ** 9 + 7
# condition 1
ans = cnt[1]
for k in primes:
ans *= (cnt[k] + 1)
s = ans
# speacial case should be minused
ans -= cnt[1]
# condition 2
p = s // (cnt[2] + 1)
for i in [3,5,7,11,13]:
ans += p // (cnt[i] + 1) * cnt[2 * i]
# condition 3
p = s // (cnt[3] + 1)
for i in [5,7]:
ans += p // (cnt[i] + 1) * cnt[3 * i]
# condition 6
p = s // (cnt[2] + 1)
for i in [5,7,11,13]:
for j in [5,7]:
if j !=i:
ans += p // (cnt[i]+1) // (cnt[3]+1) // (cnt[j]+1) * cnt[2*i] * cnt[3*j]
# condition 5
p = s // ((cnt[2] + 1) * (cnt[3] + 1) * (cnt[5] + 1))
ans += p * (cnt[30])
return int(ans % MODULE)
作者：Utoppia
链接：https://leetcode-cn.com/problems/the-number-of-good-subsets/solution/shu-xue-by-utoppia-ijm9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
另一个python过不去的题
给你一个整数数组 nums ，你可以在 nums 上执行下述操作 任意次 ：
如果 gcd(nums[i], nums[j]) > 1 ，交换 nums[i] 和 nums[j] 的位置。其中 gcd(nums[i], nums[j]) 是 nums[i] 和 nums[j] 的最大公因数。
如果能使用上述交换方式将 nums 按 非递减顺序 排列，返回 true ；否则，返回 false 。
该题一大fancy是判断排序后的数字和初始数组在同一位置是否属于同一连接块。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gcd-sort-of-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def gcdSort(self, nums: List[int]) -> bool:
n=len(nums)
fa=[i for i in range(n)]
p=[-1]*(10**5+5)
def find(x):
p=x
while fa[p]!=p:
p=fa[p]
return p
def union(x,y):
u,v=find(x),find(y)
if u==v:
return
fa[u]=fa[v]
a=[]
for i in range(n):
t=nums[i]
for j in range(2,int(math.sqrt(t))+1):
#for j in range(2,t+1):
if t%j==0:
if p[j]!=-1:
union(p[j],i)
else:
p[j]=i
while not t%j:
t//=j
if t>1:
if p[t]==-1:
p[t]=i
else:
union(p[t],i)
a.append([nums[i],i])
#print(fa)
a=sorted(a,key=lambda x:x[0])
for i in range(n):
if find(i)!=find(a[i][1]):
return False
return True
离谱的是稍微改了一下并查集结构，边界处暴过了
class Solution:
def gcdSort(self, nums: List[int]) -> bool:
n=len(nums)
fa=[i for i in range(n)]
p=[-1]*(10**5+5)
def find(x):
p=x
while fa[p]!=p:
p=fa[p]
return p
def union(x,y):
u,v=find(x),find(y)
if u==v:
return
fa[u]=fa[v]
fa[x]=fa[v]
a=[]
##路径压缩怎么搞
for i in range(n):
t=nums[i]
for j in range(2,int(math.sqrt(t))+1):
#for j in range(2,t+1):
if t%j==0:
if p[j]!=-1:
union(i,p[j])
else:
p[j]=i
while not t%j:
t//=j
if t>1:
if p[t]==-1:
p[t]=i
else:
union(p[t],i)
a.append([nums[i],i])
#print(fa)
a=sorted(a,key=lambda x:x[0])
for i in range(n):
if find(i)!=find(a[i][1]):
return False
return True
