1 GP
[leetcode]1994. The Number of Good Subsets
作者：???＼~O_O~／???│2021-09-05 04:24:27│巴幣：2│人氣：467
題目: 1994. The Number of Good Subsets
難度: Hard
目前下列解法的時(shí)間複雜度: O(n) (因?yàn)閿?shù)值範(fàn)圍極小，實(shí)際上在寫可能直接開滿)
註: 這題睡飽再解， AC 率 18.8% 真的不是假的![]()
題目說(shuō)明
給一堆數(shù)值在 1 到 30 之間(都包含)的整數(shù)，
問(wèn)有幾種這些整數(shù)的子集合，使得子集合中的所有數(shù)乘起來(lái)後的值，可以用 1 或多個(gè)"不同的"質(zhì)數(shù)相乘來(lái)表達(dá)。
例如: [1,2,2,3,4]
6 = 2 * 3 ，質(zhì)數(shù)不重複，ok。
4 = 2 * 2 ，質(zhì)數(shù) 2 重複出現(xiàn)，不ok。
1 = 1 ，不含任何質(zhì)數(shù)，不ok。
故要算進(jìn)來(lái)的子集合只有:
[2] , [3] , [1,2] , [1,3] , [2,3] , [1,2,3] 共 6 種。
解法: dp -> 數(shù)學(xué)
0. 建 1 到 30 的質(zhì)數(shù)表。
1. 一開始先想一個(gè)會(huì)TLE的解法。
a. 先假設(shè)有一張表，此表 value 是選出來(lái)ok的整數(shù)子集合的數(shù)量；key 為這些整數(shù)相乘後"有哪些質(zhì)數(shù)"。
b. 每次看到一個(gè)數(shù)字後從表中去找哪些情況(S)加上這個(gè)數(shù)字(x)後ok，將S的答案加到(S+{x})上。接著 {x} 那格 +1 ，代表只選 x 一個(gè)數(shù)字。
c. 然後看一下發(fā)現(xiàn)1億 ( 10萬(wàn) * pow(2,|1到30的質(zhì)數(shù)數(shù)量=10|) ) 了，再加一些瑣事，TLE。
2. 接著想到相同的數(shù)字根本只會(huì)挑 1 個(gè)是 C n 取 1 ，所以先數(shù)一下 1 到 30 每個(gè)數(shù)字出現(xiàn)過(guò)幾次(n)，改成直接走過(guò) 1 到 30 (都包含)，每次更新的時(shí)候直接乘上 C n 取 1 次。
3. 把每種情況S的答案都加起來(lái)。
4. 然後發(fā)現(xiàn)還是 WA 了，因?yàn)?1 可以取任意多個(gè)都不影響結(jié)果，所以把答案中 1 的部份去掉，改成 2 到 30，然後答案再乘 pow(2,|1出現(xiàn)的次數(shù)|)
5. 顧好上述行為怎麼取餘，好了你可以回傳答案了。
source code
嗯，對(duì)，比賽的時(shí)候我沒(méi)解出來(lái)，然後我就去躺了，睡不著的情況下想到答案。
從執(zhí)行時(shí)間的統(tǒng)計(jì)表中可以看出兩極分布，所以比較慢的到底寫了什麼解法？
引用網(wǎng)址：http://www.jamesdambrosio.com/TrackBack.php?sn=5257913
All rights reserved. 版權(quán)所有，保留一切權(quán)利
創(chuàng)作內(nèi)容
leetcode (7)
