龙空技术网

LeetCode 周赛上分之旅 #46 经典二分答案与质因数分解

彭旭锐 63

前言:

眼前兄弟们对“二分查找java的leetcode典型例题”大致比较关切,各位老铁们都想要分析一些“二分查找java的leetcode典型例题”的相关知识。那么小编在网摘上网罗了一些关于“二分查找java的leetcode典型例题””的相关文章,希望我们能喜欢,我们快快来学习一下吧!

⭐️ 本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。

本文是 LeetCode 上分之旅系列的第 46 篇文章,往期回顾请移步到文章末尾~

LeetCode 周赛 363

T1. 计算 K 置位下标对应元素的和(Easy)

标签:位运算

T2. 让所有学生保持开心的分组方法数(Medium)

标签:贪心、排序、计数排序

T3. 最大合金数(Medium)

标签:二分查找

T4. 完全子集的最大元素和(Hard)

标签:数学、质因素分解、散列表T1. 计算 K 置位下标对应元素的和(Easy)

题解(模拟)

简单模拟题。

写法 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}    }}

复杂度分析:

时间复杂度:�(�) Java Integer#bitCount 的时间复杂度是 �(1)空间复杂度:�(1) 仅使用常数级别空间。T2. 让所有学生保持开心的分组方法数(Medium)

问题分析

思考选哪个:

条件 1: 如果选中的学生 ����[�] 越小,那么越容易满足选中人数 > ����[�];条件 2: 如果未选中的学生 ����[�] 越大,那么越容易满足选中人数 < ����[�];

因此,在合法的选择方案中,应该优先选择越小的学生。

题解(排序 + 贪心)

先对数组排序,再枚举分割点验证条件 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,70|2,3,3,6,6,7,70,2|3,3,6,6,7,70,2,3|3,6,6,7,7

对于分割点 i 的要求是:

条件 1:�+1>����[�],利用有序性质只需要判断已选列表的最大值 ����[�];条件 2:�+1<����[�+1],利用有序性质只需要判断未选列表的最小值 ����[�+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    }}

复杂度分析:

时间复杂度:�(����) 瓶颈在排序;空间复杂度:�(���) 排序递归栈空间。T3. 最大合金数(Medium)

问题分析

初步分析:

问题目标: 求在预算限制下最大可以制造的合金数量;关键信息: 所有合金都需要由同一台机器制造,这样难度就降低很多了。

容易发现原问题的单调性:

如果合金数 x 可以制造,那么合金数 �−1 一定可以制造;如果合金数 x 不可制造,那么合金数 �+1 一定不可制造。

因此,可以用二分答案来解决问题:

合金数的下界:0合金数的上界:2∗108,即金钱和初始金属的最大值;

现在需要思考的问题是: 「如何验证合金数 � 可以构造」

由于所有合金都需要由同一台机器制造,判断很简单,只需要先计算目标数量需要的每种金属的初始金属数是否足够,不足则花金钱购买。如果花费超过限制则不可制造。

题解(二分答案)

基于以上问下,我们枚举机器,使用二分查找寻找可以制造的合金数的上界:

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    }}

复杂度分析:

时间复杂度:�(�·�·���) 其中 � 为机器数,� 为金属种类,� 为二分上界;空间复杂度:�(1) 除结果数组外仅使用常量级别空间。T4. 完全子集的最大元素和(Hard)

问题分析

初步分析:

问题目标: 求解满足条件的目标子集的元素最大和;目标子集: 子集元素的下标两两相乘的乘积是完全平方数,允许仅包含一个元素的子集;

观察测试用例 2:

对于下标 1 和下标 4:两个完全平方数的乘积自然是完全平方数;对于下标 2 和下标 8:2 和 8 都包含质因子 2,2 的平方自然是完全平方数;

由此得出结论:

核心思路: 我们消除每个下标中的完全平方数因子,再对剩余的特征分组,能够构造目标子集的方案有且只能出现在相同的特征分组中(否则,子集中一定存在两两相乘不是完全平方数的情况)。

{2 | 6} x 需要相同的因子{6 | 6} ok 

思考实现:

预处理: 预处理覆盖所有测试用例下标的特征值质因素分解: 有 2 种基础算法:

朴素算法:枚举 [2,�] 将出现次数为奇数的质因子记录到特征值中,时间复杂度是 �(�):

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    }}

复杂度分析:

时间复杂度:预处理时间为 �(��),单次测试用例时间为 �(�);空间复杂度:�(�) 预处理空间,单次测试用例空间比较松的上界为 �(�)。题解二(找规律)

题解一的时间复杂度瓶颈在之因素分解。

继续挖掘数据特征,我们观察同一个分桶内的数据规律:

假设分桶中的最小值为 x,那么将分桶的所有元素排序后必然是以下序列的子序列:�,4∗�,9∗�,16∗�…,由此发现规律:我们可以枚举分桶的最小值,再依次乘以完全平方数序列来计算,既可以快速定位分桶中的元素,而不需要预处理质因数分解。

那怎么度量此算法的时间复杂度呢?

显然,该算法一个比较松上界是 �(�·�),其中 � 为数据范围内的完全平方数个数,�=100。严格证明参考羊神题解,该算法线性时间复杂度 �(�)。

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    }}

复杂度分析:

时间复杂度:�(�) 线性算法;空间复杂度:�(�) 预处理完全平方数序列空间,可以优化。

推荐阅读

LeetCode 上分之旅系列往期回顾:

LeetCode 单周赛第 361 场 · 同余前缀和问题与经典倍增 LCA 算法

LeetCode 单周赛第 360 场 · 当 LeetCode 考树上倍增,出题的趋势在变化吗

LeetCode 双周赛第 113 场 · 精妙的 O(lgn) 扫描算法与树上 DP 问题

LeetCode 双周赛第 112 场 · 计算机科学本质上是数学吗?

⭐️ 永远相信美好的事情即将发生,欢迎加入小彭的 Android 交流社群~

标签: #二分查找java的leetcode典型例题