LeetCode 周賽 363
T1. 計(jì)算 K 置位下標(biāo)對應(yīng)元素的和（Easy）
- 標(biāo)簽：位運(yùn)算
T2. 讓所有學(xué)生保持開心的分組方法數(shù)（Medium）
- 標(biāo)簽：貪心吼旧、排序饱亿、計(jì)數(shù)排序
T3. 最大合金數(shù)（Medium）
- 標(biāo)簽：二分查找
T4. 完全子集的最大元素和（Hard）
- 標(biāo)簽：數(shù)學(xué)腌逢、質(zhì)因素分解萨西、散列表
T1. 計(jì)算 K 置位下標(biāo)對應(yīng)元素的和（Easy）
https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/description/
題解（模擬）
簡單模擬題妄壶。
寫法 1：
class Solution {
fun sumIndicesWithKSetBits(nums: List<Int>, k: Int): Int {
var ret = 0
for (i in nums.indices) {
if (Integer.bitCount(i) == k) ret += nums[i]
}
return ret
}
}
寫法 2：
class Solution {
fun sumIndicesWithKSetBits(nums: List<Int>, k: Int): Int {
return nums.indices.fold(0) { acc, it -> if (Integer.bitCount(it) == k) acc + nums[it] else acc}
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
Java
Integer#bitCount的時間復(fù)雜度是 - 空間復(fù)雜度：
僅使用常數(shù)級別空間霞扬。
T2. 讓所有學(xué)生保持開心的分組方法數(shù)（Medium）
https://leetcode.cn/problems/happy-students/description/
問題分析
思考選哪個：
-
條件 1： 如果選中的學(xué)生
越小佑笋，那么越容易滿足選中人數(shù) >
-
條件 2： 如果未選中的學(xué)生
因此猎荠，在合法的選擇方案中，應(yīng)該優(yōu)先選擇越小的學(xué)生蜀备。
題解（排序 + 貪心）
先對數(shù)組排序关摇，再枚舉分割點(diǎn)驗(yàn)證條件 1 與條件 2：
6,0,3,3,6,7,2,7
排序 =>
0,2,3,3,6,6,7,7
|0,2,3,3,6,6,7,7
0|2,3,3,6,6,7,7
0,2|3,3,6,6,7,7
0,2,3|3,6,6,7,7
對于分割點(diǎn) i 的要求是：
- 條件 1：
，利用有序性質(zhì)只需要判斷已選列表的最大值
- 條件 2：
输虱，利用有序性質(zhì)只需要判斷未選列表的最小值
；
- 最后針對全選和都不選的情況特殊判斷脂凶。
class Solution {
fun countWays(nums: MutableList<Int>): Int {
nums.sort()
val n = nums.size
var ret = 0
// 都不選
if (nums[0] > 0) ret += 1
// 都選
if (nums[n - 1] < n) ret += 1
// 選一部分
for (i in 0 until n - 1) {
if (nums[i] < i + 1 && nums[i + 1] > i + 1) ret += 1
}
return ret
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
瓶頸在排序宪睹；
- 空間復(fù)雜度：
排序遞歸棧空間蚕钦。
T3. 最大合金數(shù)（Medium）
https://leetcode.cn/problems/maximum-number-of-alloys/description/
問題分析
初步分析：
- 問題目標(biāo)： 求在預(yù)算限制下最大可以制造的合金數(shù)量亭病；
- 關(guān)鍵信息： 所有合金都需要由同一臺機(jī)器制造，這樣難度就降低很多了嘶居。
容易發(fā)現(xiàn)原問題的單調(diào)性：
- 如果合金數(shù) x 可以制造罪帖，那么合金數(shù)
一定可以制造；
- 如果合金數(shù) x 不可制造邮屁，那么合金數(shù)
一定不可制造整袁。
因此，可以用二分答案來解決問題：
- 合金數(shù)的下界：
- 合金數(shù)的上界：
樱报，即金錢和初始金屬的最大值葬项；
現(xiàn)在需要思考的問題是： 「如何驗(yàn)證合金數(shù) 可以構(gòu)造」
由于所有合金都需要由同一臺機(jī)器制造，判斷很簡單迹蛤，只需要先計(jì)算目標(biāo)數(shù)量需要的每種金屬的初始金屬數(shù)是否足夠民珍，不足則花金錢購買襟士。如果花費(fèi)超過限制則不可制造。
題解（二分答案）
基于以上問下嚷量，我們枚舉機(jī)器陋桂，使用二分查找尋找可以制造的合金數(shù)的上界：
class Solution {
fun maxNumberOfAlloys(n: Int, k: Int, limit: Int, composition: List<List<Int>>, stock: List<Int>, cost: List<Int>): Int {
var ret = 0
// 枚舉方案
for (com in composition) {
fun check(num: Int): Boolean {
// 計(jì)算需要的金屬原料
var money = 0L
for (i in 0 until n) {
// 原料不足，需要購入
money += max(0L, 1L * com[i] * num - stock[i]) * cost[i] // 注意整型溢出
if (money > limit.toLong()) return false
}
return true
}
var left = 0
var right = 2*1e8.toInt()
while (left < right) {
val mid = (left + right + 1) ushr 1
if (check(mid)) {
left = mid
} else {
right = mid - 1
}
}
ret = max(ret, left)
}
return ret
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
其中
為機(jī)器數(shù)蝶溶，
為金屬種類嗜历，
為二分上界；
- 空間復(fù)雜度：
T4. 完全子集的最大元素和（Hard）
https://leetcode.cn/problems/maximum-element-sum-of-a-complete-subset-of-indices/description/
問題分析
初步分析：
- 問題目標(biāo)： 求解滿足條件的目標(biāo)子集的元素最大和梨州；
- 目標(biāo)子集： 子集元素的下標(biāo)兩兩相乘的乘積是完全平方數(shù)，允許僅包含一個元素的子集田轧；
觀察測試用例 2：
- 對于下標(biāo)
和下標(biāo)
：兩個完全平方數(shù)的乘積自然是完全平方數(shù)暴匠；
- 對于下標(biāo)
和下標(biāo)
：
由此得出結(jié)論：
- 核心思路： 我們消除每個下標(biāo)中的完全平方數(shù)因子每窖，再對剩余的特征分組，能夠構(gòu)造目標(biāo)子集的方案有且只能出現(xiàn)在相同的特征分組中（否則弦悉，子集中一定存在兩兩相乘不是完全平方數(shù)的情況）窒典。
{2 | 6} x 需要相同的因子
{6 | 6} ok
思考實(shí)現(xiàn)：
- 預(yù)處理： 預(yù)處理覆蓋所有測試用例下標(biāo)的特征值
- 質(zhì)因素分解： 有 2 種基礎(chǔ)算法：
樸素算法：枚舉 將出現(xiàn)次數(shù)為奇數(shù)的質(zhì)因子記錄到特征值中，時間復(fù)雜度是
：
private val U = 1e4.toInt()
private val core = IntArray(U + 1)
init {
for (num in 1 .. U) {
// 質(zhì)因素分解
var prime = 2
var x = num
var key = 1
while (prime * prime <= x) {
var cnt = 0
while (x % prime == 0) {
x /= prime
cnt ++
}
if (cnt % 2 == 1) key *= prime // 記錄特征值
prime ++
}
if (x > 1) key *= x // 記錄特征值
core[num] = key
}
}
篩法：枚舉質(zhì)因子稽莉，將記錄質(zhì)因子的整數(shù)倍的特征值瀑志。
private val U = 1e4.toInt()
private val core = IntArray(U + 1) { 1 }
private val isMark = BooleanArray(U + 1)
init {
// 質(zhì)因素分解
for (i in 2 .. U) {
// 檢查是否為質(zhì)數(shù)，這里不需要調(diào)用 isPrime() 函數(shù)判斷是否質(zhì)數(shù)肩祥，因?yàn)樗鼪]被小于它的數(shù)標(biāo)記過后室，那么一定不是合數(shù)
if (isMark[i]) continue
for (num in i .. U step i) {
isMark[num] = true
var x = num
var cnt = 0
while (x % i == 0) {
x /= i
cnt ++
}
if (cnt % 2 != 0) core[num] *= i // 記錄特征值
}
}
}
題解一（質(zhì)因素分解 + 分桶）
組合以上技巧缩膝，枚舉下標(biāo)做質(zhì)因數(shù)分解混狠，將數(shù)值累加到分桶中，最后返回最大分桶元素和疾层。
class Solution {
companion object {
private val U = 1e4.toInt()
private val core = IntArray(U + 1)
init {
for (num in 1 .. U) {
// 質(zhì)因素分解
var prime = 2
var x = num
var key = 1
while (prime * prime <= x) {
var cnt = 0
while (x % prime == 0) {
x /= prime
cnt ++
}
if (cnt % 2 == 1) key *= prime // 記錄特征值
prime ++
}
if (x > 1) key *= x // 記錄特征值
core[num] = key
}
}
}
fun maximumSum(nums: List<Int>): Long {
var ret = 0L
val buckets = HashMap<Int, Long>()
for (i in 1 .. nums.size) {
val key = core[i]
buckets[key] = buckets.getOrDefault(key, 0) + nums[i - 1]
ret = max(ret, buckets[key]!!)
}
return ret
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：預(yù)處理時間為
将饺，單次測試用例時間為
- 空間復(fù)雜度：
預(yù)處理空間痛黎，單次測試用例空間比較松的上界為
題解二（找規(guī)律）
題解一的時間復(fù)雜度瓶頸在之因素分解。
繼續(xù)挖掘數(shù)據(jù)特征湖饱，我們觀察同一個分桶內(nèi)的數(shù)據(jù)規(guī)律：
假設(shè)分桶中的最小值為 x掖蛤，那么將分桶的所有元素排序后必然是以下序列的子序列：，由此發(fā)現(xiàn)規(guī)律：我們可以枚舉分桶的最小值井厌，再依次乘以完全平方數(shù)序列來計(jì)算蚓庭，既可以快速定位分桶中的元素致讥，而不需要預(yù)處理質(zhì)因數(shù)分解。
那怎么度量此算法的時間復(fù)雜度呢器赞？
顯然垢袱，該算法一個比較松上界是 ，其中
為數(shù)據(jù)范圍內(nèi)的完全平方數(shù)個數(shù)港柜，
请契。嚴(yán)格證明參考羊神題解，該算法線性時間復(fù)雜度
夏醉。
class Solution {
companion object {
// 預(yù)處理完全平方數(shù)序列
private val s = LinkedList<Int>()
init {
for (i in 1 .. 100) {
s.add(i * i)
}
}
}
fun maximumSum(nums: List<Int>): Long {
val n = nums.size
var ret = 0L
// 枚舉分桶最小值
for (i in 1 .. n) {
var sum = 0L
for (k in s) {
if (k * i > n) break
sum += nums[k * i - 1]
}
ret = max(ret, sum)
}
return ret
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
預(yù)處理完全平方數(shù)序列空間，可以優(yōu)化畔柔。
推薦閱讀
LeetCode 上分之旅系列往期回顧：
