外贸网站推广平台排名,interiart wordpress,制作移动端网站价格,网站建站网站微信公众号开发⭐️ 本文已收录到 AndroidFamily#xff0c;技术和职场问题#xff0c;请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架#xff0c;你的思考越抽象#xff0c;它能覆盖的问题域就越广#xff0c;理解难度… ⭐️ 本文已收录到 AndroidFamily技术和职场问题请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架你的思考越抽象它能覆盖的问题域就越广理解难度也更复杂。在这个专栏里小彭与你分享每场 LeetCode 周赛的解题报告一起体会上分之旅。 本文是 LeetCode 上分之旅系列的第 39 篇文章往期回顾请移步到文章末尾~ 周赛 358
T1. 数组中的最大数对和Easy
标签数学、分桶
T2. 翻倍以链表形式表示的数字Medium
标签链表
T3. 限制条件下元素之间的最小绝对差Medium
标签双指针、平衡树
T4. 操作使得分最大Hard
标签贪心、排序、中心扩展、单调栈、快速幂 T1. 数组中的最大数对和Easy
https://leetcode.cn/problems/max-pair-sum-in-an-array/题解一分桶 数学
枚举每个元素并根据其最大数位分桶枚举每个分桶计算最大数对和。
class Solution {
public:int maxSum(vectorint nums) {int U 10;// 分桶vectorint buckets[U];for (auto e: nums) {int x e;int m 0;while (x 0) {m max(m, x % 10);x / 10;}buckets[m].push_back(e);}// 配对int ret -1;for (int k 0; k U; k) {if (buckets[k].size() 2) continue;sort(buckets[k].rbegin(), buckets[k].rend());ret max(ret, buckets[k][0] buckets[k][1]);}return ret;}
};复杂度分析
时间复杂度 O ( n l g n ) O(nlgn) O(nlgn) 瓶颈在排序最坏情况下所有元素进入同一个分桶空间复杂度 O ( n ) O(n) O(n) 分桶空间
题解二一次遍历优化
最大数对和一定是分桶中的最大两个数我们只需要维护每个分桶的最大值并在将新元素尝试加入分桶尝试更新结果。
class Solution {
public:int maxSum(vectorint nums) {int U 10;int ret -1;int buckets[U];memset(buckets, -1, sizeof(buckets));for (auto e: nums) {int x e;int m 0;while (x 0) {m max(m, x % 10);x / 10;}if (-1 ! buckets[m]) {ret max(ret, buckets[m] e);}buckets[m] max(buckets[m], e);}return ret;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) 线性遍历空间复杂度 O ( U ) O(U) O(U) 分桶空间。 T2. 翻倍以链表形式表示的数字Medium
https://leetcode.cn/problems/double-a-number-represented-as-a-linked-list/题解一模拟
面试类型题有 O ( 1 ) O(1) O(1) 空间复杂度的写法
先反转链表再依次顺序翻倍最后再反转回来需要注意最后剩余一个进位的情况需要补足节点。
class Solution {fun doubleIt(head: ListNode?): ListNode? {// 反转val p reverse(head)// 翻倍var cur pvar append 0while (cur ! null) {append cur.val * 2cur.val append % 10append append / 10cur cur.next}// 反转if (0 append) return reverse(p)return ListNode(append).apply {next reverse(p)}}fun reverse(head: ListNode?): ListNode? {var p: ListNode? nullvar q headwhile (null ! q) {val next q.nextq.next pp qq next}return p}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) 反转与翻倍是线性时间复杂度空间复杂度 O ( 1 ) O(1) O(1) 仅使用常量级别空间。
题解二一次遍历优化
我们发现进位只发生在元素值大于 4 的情况我们可以提前观察当前节点的后继节点的元素值是否大于 4如果是则增加进位 1。特别地当首个元素大于 4 时需要补足节点。
class Solution {fun doubleIt(head: ListNode?): ListNode? {if (head null) return null// 补足val newHead if (head.val 4) {ListNode(0).also { it.next head}} else {head}// 翻倍var cur: ListNode? newHeadwhile (null ! cur) {cur.val * 2if ((cur?.next?.val ?: 0) 4) cur.val 1cur.val % 10cur cur.next}return newHead}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) 线性遍历空间复杂度 O ( 1 ) O(1) O(1) 仅使用常量级别空间。
相似题目
445. 两数相加 II T3. 限制条件下元素之间的最小绝对差Medium
https://leetcode.cn/problems/minimum-absolute-difference-between-elements-with-constraint/题解双指针 平衡树
滑动窗口的变型题常规的滑动窗口是限定在窗口大小在 x 内而这道题是排除到窗口外。万变不离其宗还得是双指针。其次为了让元素配对的差值绝对值尽可能小应该使用与其元素值相近最大和最小的两个数可以用平衡树在 O(lgn) 时间复杂度内求得整体时间复杂度是 O(ngln)
class Solution {fun minAbsoluteDifference(nums: ListInt, x: Int): Int {if (x 0) return 0 // 特判var ret Integer.MAX_VALUEval n nums.sizeval set TreeSetInt()for (i in x until n) {// 滑动set.add(nums[i - x])val q set.floor(nums[i])val p set.ceiling(nums[i])if (p ! null) ret Math.min(ret, Math.abs(p - nums[i]))if (q ! null) ret Math.min(ret, Math.abs(nums[i] - q))}return ret }
}复杂度分析
时间复杂度 O ( m l g m ) O(mlgm) O(mlgm) 其中 m n - x内层循环二分搜索的时间复杂度是 O ( l g m ) O(lgm) O(lgm)空间复杂度 O ( m ) O(m) O(m) 平衡树空间。 T4. 操作使得分最大Hard
https://leetcode.cn/problems/apply-operations-to-maximize-score/题解一贪心 排序 中心扩展 单调栈 快速幂
这道题难度不算高但使用到的技巧还挺综合的。 阅读理解 可以得出影响结果 3 点关键信息我们的目标是选择 k 个子数组让其中质数分数最大的元素 nums[i] 尽量大 1、元素大小2、元素的质数分数3、左边元素的优先级更高 预处理 先预处理数据范围内每个数的质数分数避免在多个测试用例间重复计算 质因数分解 求解元素的质数分数需要质因数分解有两种写法 暴力写法时间复杂度 O ( n ⋅ n ) O(n·\sqrt{n}) O(n⋅n ) val scores IntArray(U 1)
for (e in 1 .. U) {var cnt 0var x evar prime 2while (prime * prime x) {if (x % prime 0) {cnt while (x % prime 0) x / prime // 消除相同因子}prime}if (x 1) cnt // 剩余的质因子scores[e] cnt
}基于质数筛写法时间复杂度 O(n) val scores IntArray(U 1)
for (i in 2 .. U) {if (scores[i] ! 0) continue // 合数for (j in i .. U step i) {scores[j] 1}
}排序 根据关键信息 「1、元素大小」 可知我们趋向于选择包含较大元素值的子数组且仅包含数组元素最大值的子数组是子数组分数的上界 中心扩展 我们先对所有元素降序排序依次枚举子数组计算该元素对结果的贡献直到该元素无法构造更多子数组。以位置 i 为中心向左右扩展计算左右两边可以记入子数组的元素个数 leftCnt 和 rightCnt。另外根据 「左边元素的优先级更高」 的元素向左边扩展时不能包含质数分数相同的位置向右边扩展时可以包含 乘法原理 包含元素 nums[i] 的子数组个数满足乘法法则leftCnt * rightCnt 单调栈 在中心扩展时我们相当于在求 「下一个更大值」元素这是典型的 单调栈问题可以在 O ( n ) O(n) O(n) 时间复杂度内求得所有元素的下一个更大值 val stack ArrayDequeInt()
for (i in 0 until n) {while (!stack.isEmpty() nums[stack.peek()] nums[i]) {stack.pop()}stack.push(i)
}快速幂 三种写法 暴力写法时间复杂度 O(n)由于题目 k 比较大会超出时间限制 fun pow(x: Int, n: Int, mod: Int): Int {var ret 1Lrepeat (n){ret (ret * x) % mod}return ret.toInt()
}分治写法时间复杂度是 O(lgn) fun pow(x: Int, n: Int, mod: Int): Int {if (n 1) return xval subRet pow(x, n / 2, mod)return if (n % 2 1) {1L * subRet * subRet % mod * x % mod} else {1L * subRet * subRet % mod}.toInt()
}快速幂写法时间复杂度 O© private fun quickPow(x: Int, n: Int, mod: Int): Int {var ret 1Lvar cur nvar k x.toLong()while (cur 0) {if (cur % 2 1) ret ret * k % modk k * k % modcur / 2}return ret.toInt()
}组合以上技巧
class Solution {companion object {private val MOD 1000000007private val U 100000private val scores IntArray(U 1)init {// 质数筛for (i in 2 .. U) {if (scores[i] ! 0) continue // 合数for (j in i .. U step i) {scores[j] 1}}}}fun maximumScore(nums: ListInt, k: Int): Int {val n nums.size// 贡献子数组数val gains1 IntArray(n) { n - it }val gains2 IntArray(n) { it 1}// 下一个更大的分数单调栈从栈底到栈顶单调递减val stack ArrayDequeInt()for (i in 0 until n) {while (!stack.isEmpty() scores[nums[stack.peek()]] scores[nums[i]]) {val j stack.pop()gains1[j] i - j}stack.push(i)}// 上一个更大元素单调栈从栈底到栈顶单调递减stack.clear()for (i in n - 1 downTo 0) {while(!stack.isEmpty() scores[nums[stack.peek()]] scores[nums[i]]) { // val j stack.pop()gains2[j] j - i}stack.push(i)}// 按元素值降序val ids ArrayInt(n) { it }Arrays.sort(ids) { i1, i2 -nums[i2] - nums[i1]}// 枚举每个元素的贡献度var leftK kvar ret 1Lfor (id in ids.indices) {val gain Math.min(gains1[ids[id]] * gains2[ids[id]], leftK)ret (ret * quickPow(nums[ids[id]], gain, MOD)) % MODleftK - gainif (leftK 0) break}return ret.toInt()}// 快速幂private fun quickPow(x: Int, n: Int, mod: Int): Int {var ret 1Lvar cur nvar k x.toLong()while (cur 0) {if (cur % 2 1) ret ret * k % modk k * k % modcur / 2}return ret.toInt()}
}复杂度分析
时间复杂度 O ( n l g n ) O(nlgn) O(nlgn) 其中预处理时间为 O ( U ) O(U) O(U)单次测试用例中使用单调栈计算下一个更大质数分数的时间为 O ( n ) O(n) O(n)排序时间为 O ( n l g n ) O(nlgn) O(nlgn)枚举贡献度时间为 O ( n ) O(n) O(n)整体瓶颈在排序空间复杂度 O ( n ) O(n) O(n) 预处理空间为 O ( U ) O(U) O(U)单次测试用例中占用 O ( n ) O(n) O(n) 空间。
题解二一次遍历优化
在计算下一个更大元素时在使用 while 维护单调栈性质后此时栈顶即为当前元素的前一个更大元素
while (!stack.isEmpty() nums[stack.peek()] nums[i]) {stack.pop()
}
// 此时栈顶即为当前元素的前一个更大元素
stack.push(i)因此我们可以直接在一次遍历中同时计算出前一个更大元素和下一个更大元素
val right IntArray(n) { n } // 下一个更大元素的位置
val left IntArray(n) { -1 } // 上一个更大元素的位置计算贡献度的方法 ( i − l e f t [ i ] ) ∗ ( r i g h t [ i ] − i ) (i - left[i]) * (right[i] - i) (i−left[i])∗(right[i]−i)其中 l e f t [ i ] left[i] left[i] 和 r i g h t [ i ] right[i] right[i] 位置不包含在子数组中。
class Solution {...fun maximumScore(nums: ListInt, k: Int): Int {val n nums.size// 贡献子数组数val right IntArray(n) { n } // 下一个更大元素的位置val left IntArray(n) { -1 } // 上一个更大元素的位置// 下一个更大的分数单调栈从栈底到栈顶单调递减val stack ArrayDequeInt()for (i in 0 until n) {while (!stack.isEmpty() scores[nums[stack.peek()]] scores[nums[i]]) {right[stack.pop()] i // 下一个更大元素的位置}if (!stack.isEmpty()) left[i] stack.peek() // 上一个更大元素的位置stack.push(i)}// 按元素值降序val ids ArrayInt(n) { it }Arrays.sort(ids) { i1, i2 -nums[i2] - nums[i1]}// 枚举每个元素的贡献度val gains IntArray(n) { (it - left[it]) * (right[it] - it)}var leftK kvar ret 1Lfor (id in ids.indices) {val gain Math.min(gains[ids[id]], leftK)ret (ret * quickPow(nums[ids[id]], gain, MOD)) % MODleftK - gainif (leftK 0) break}return ret.toInt()}...
}复杂度分析
同上
相似题目
907. 子数组的最小值之和1856. 子数组最小乘积的最大值2104. 子数组范围和2281. 巫师的总力量和 推荐阅读 LeetCode 上分之旅系列往期回顾 LeetCode 单周赛第 358 场 · 结合排序不等式的动态规划LeetCode 单周赛第 357 场 · 多源 BFS 与连通性问题LeetCode 双周赛第 109 场 · 按部就班地解决动态规划问题LeetCode 双周赛第 107 场 · 很有意思的 T2 题 ⭐️ 永远相信美好的事情即将发生欢迎加入小彭的 Android 交流社群~
