共计 4954 个字符，预计需要花费 13 分钟才能阅读完成。
⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 BaguTree Pro 常识星球发问。
学习数据结构与算法的关键在于把握问题背地的算法思维框架，你的思考越形象，它能笼罩的问题域就越广，了解难度也更简单。在这个专栏里，小彭与你分享每场 LeetCode 周赛的解题报告，一起领会上分之旅。
本文是 LeetCode 上分之旅系列的第 46 篇文章，往期回顾请移步到文章开端 \~
LeetCode 周赛 363
T1. 计算 K 置位下标对应元素的和（Easy）
- 标签：位运算
T2. 让所有学生放弃开心的分组办法数（Medium）
- 标签：贪婪、排序、计数排序
T3. 最大合金数（Medium）
- 标签：二分查找
T4. 齐全子集的最大元素和（Hard）
- 标签：数学、质因素合成、散列表
T1. 计算 K 置位下标对应元素的和（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}
}
}复杂度剖析：
- 工夫复杂度：$O(n)$ Java
Integer#bitCount的工夫复杂度是 $O(1)$ - 空间复杂度：$O(1)$ 仅应用常数级别空间。
T2. 让所有学生放弃开心的分组办法数（Medium）
https://leetcode.cn/problems/happy-students/description/问题剖析
思考选哪个：
- 条件 1： 如果选中的学生 $nums[i]$ 越小，那么越容易满足选中人数 > $nums[i]$；
- 条件 2： 如果未选中的学生 $nums[i]$ 越大，那么越容易满足选中人数 < $nums[i]$；
因而，在非法的抉择计划中，应该优先选择越小的学生。
题解（排序 + 贪婪）
先对数组排序，再枚举宰割点验证条件 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对于宰割点 i 的要求是：
- 条件 1：$i + 1 > nums[i]$，利用有序性质只须要判断已选列表的最大值 $nums[i]$；
- 条件 2：$i + 1 < nums[i + 1]$，利用有序性质只须要判断未选列表的最小值 $nums[i + 1]$；
- 最初针对全选和都不选的状况非凡判断。
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
}
}复杂度剖析：
- 工夫复杂度：$O(nlgn)$ 瓶颈在排序；
- 空间复杂度：$O(lgn)$ 排序递归栈空间。
T3. 最大合金数（Medium）
https://leetcode.cn/problems/maximum-number-of-alloys/description/问题剖析
初步剖析：
- 问题指标： 求在估算限度下最大能够制作的合金数量；
- 要害信息： 所有合金都须要由同一台机器制作，这样难度就升高很多了。
容易发现原问题的枯燥性：
- 如果合金数 x 能够制作，那么合金数 $x – 1$ 肯定能够制作；
- 如果合金数 x 不可制作，那么合金数 $x + 1$ 肯定不可制作。
因而，能够用二分答案来解决问题：
- 合金数的下界：$0$
- 合金数的上界：$2 * 10^8$，即金钱和初始金属的最大值；
当初须要思考的问题是：「如何验证合金数 $x$ 能够结构」
因为所有合金都须要由同一台机器制作，判断很简略，只须要先计算指标数量须要的每种金属的初始金属数是否足够，有余则花金钱购买。如果破费超过限度则不可制作。
题解（二分答案）
基于以上问下，咱们枚举机器，应用二分查找寻找能够制作的合金数的上界：
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 {
// 计算须要的金属原料
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
}
}复杂度剖析：
- 工夫复杂度：$O(k·n·lgU)$ 其中 $k$ 为机器数，$n$ 为金属品种，$U$ 为二分上界；
- 空间复杂度：$O(1)$ 除后果数组外仅应用常量级别空间。
T4. 齐全子集的最大元素和（Hard）
https://leetcode.cn/problems/maximum-element-sum-of-a-complete-subset-of-indices/description/问题剖析
初步剖析：
- 问题指标： 求解满足条件的指标子集的元素最大和；
- 指标子集： 子集元素的下标两两相乘的乘积是齐全平方数，容许仅蕴含一个元素的子集；
察看测试用例 2：
- 对于下标 $1$ 和下标 $4$：两个齐全平方数的乘积天然是齐全平方数；
- 对于下标 $2$ 和下标 $8$：$2$ 和 $8$ 都蕴含质因子 $2$，$2$ 的平方天然是齐全平方数；
由此得出结论：
- 外围思路： 咱们打消每个下标中的齐全平方数因子，再对残余的特色分组，可能结构指标子集的计划有且只能呈现在雷同的特色分组中（否则，子集中肯定存在两两相乘不是齐全平方数的状况）。
{2 | 6} x 须要雷同的因子
{6 | 6} ok 思考实现：
- 预处理： 预处理笼罩所有测试用例下标的特征值
- 质因素合成： 有 2 种根底算法：
奢侈算法：枚举 $[2, \sqrt{n}]$ 将呈现次数为奇数的质因子记录到特征值中，工夫复杂度是 $O(\sqrt{n})$：
private val U = 1e4.toInt()
private val core = IntArray(U + 1)
init {for (num in 1 .. U) {
// 质因素合成
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
}
}筛法：枚举质因子，将记录质因子的整数倍的特征值。
private val U = 1e4.toInt()
private val core = IntArray(U + 1) {1}
private val isMark = BooleanArray(U + 1)
init {
// 质因素合成
for (i in 2 .. U) {// 查看是否为质数，这里不须要调用 isPrime() 函数判断是否质数，因为它没被小于它的数标记过，那么肯定不是合数
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 // 记录特征值
}
}
}题解一（质因素合成 + 分桶）
组合以上技巧，枚举下标做质因数分解，将数值累加到分桶中，最初返回最大分桶元素和。
class Solution {
companion object {private val U = 1e4.toInt()
private val core = IntArray(U + 1)
init {for (num in 1 .. U) {
// 质因素合成
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
}
}复杂度剖析：
- 工夫复杂度：预处理工夫为 $O(U\sqrt{U})$，单次测试用例工夫为 $O(n)$；
- 空间复杂度：$O(U)$ 预处理空间，单次测试用例空间比拟松的上界为 $O(n)$。
题解二（找法则）
题解一的工夫复杂度瓶颈在之因素合成。
持续开掘数据特色，咱们察看同一个分桶内的数据法则：
假如分桶中的最小值为 x，那么将分桶的所有元素排序后必然是以下序列的子序列：${x, 4 * x, 9 * x, 16 * x…}$，由此发现法则：咱们能够枚举分桶的最小值，再顺次乘以齐全平方数序列来计算，既能够疾速定位分桶中的元素，而不须要预处理质因数分解。
那怎么度量此算法的工夫复杂度呢？
显然，该算法一个比拟松上界是 $O(n·C)$，其中 $C$ 为数据范畴内的齐全平方数个数，$C = 100$。严格证实参考羊神题解，该算法线性工夫复杂度 $O(n)$。
class Solution {
companion object {
// 预处理齐全平方数序列
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
}
}复杂度剖析：
- 工夫复杂度：$O(n)$ 线性算法；
- 空间复杂度：$O(C)$ 预处理齐全平方数序列空间，能够优化。
举荐浏览
LeetCode 上分之旅系列往期回顾：
- LeetCode 单周赛第 361 场 · 同余前缀和问题与经典倍增 LCA 算法
- LeetCode 单周赛第 360 场 · 当 LeetCode 考树上倍增，出题的趋势在变动吗
- LeetCode 双周赛第 113 场 · 精妙的 O(lgn) 扫描算法与树上 DP 问题
- LeetCode 双周赛第 112 场 · 计算机科学实质上是数学吗？
⭐️ 永远置信美妙的事件行将产生，欢送退出小彭的 Android 交换社群 \~
正文完
