如何用免费个人网站制作,WordPress修改模板,wordpress访问统计,编程代码怎么学⭐️ 本文已收录到 AndroidFamily#xff0c;技术和职场问题#xff0c;请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架#xff0c;你的思考越抽象#xff0c;它能覆盖的问题域就越广#xff0c;理解难度… ⭐️ 本文已收录到 AndroidFamily技术和职场问题请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架你的思考越抽象它能覆盖的问题域就越广理解难度也更复杂。在这个专栏里小彭与你分享每场 LeetCode 周赛的解题报告一起体会上分之旅。 本文是 LeetCode 上分之旅系列的第 49 篇文章往期回顾请移步到文章末尾~ LeetCode 周赛 365
T1. 有序三元组中的最大值 IEasy
标签模拟、前后缀分解、线性遍历
T2. 有序三元组中的最大值 IIMedium
标签模拟、前后缀分解、线性遍历
T3. 无限数组的最短子数组Medium
标签滑动窗口
T4. 有向图访问计数Hard
标签内向基环树、拓扑排序、DFS T1. 有序三元组中的最大值 IEasy
https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-i/description/同 T2。 T2. 有序三元组中的最大值 IIMedium
https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/description/问题分析
初步分析
问题目标 构造满足条件的合法方案使得计算结果最大问题条件 数组下标满足 i j k i j k ijk 的三位数计算结果 ( n u m s [ i ] − n u m s [ j ] ) ∗ n u m s [ k ] (nums[i] - nums[j]) * nums[k] (nums[i]−nums[j])∗nums[k]。
思考实现
T1. 有序三元组中的最大值 I 的数据量只有 100 100 100枚举所有合法的 [ i , j , k ] [i, j, k] [i,j,k] 组合时间复杂度是 O ( n 3 ) O(n^3) O(n3)T2. 有序三元组中的最大值 II 的数据量有 1 0 5 10^5 105我们需要思考更优解法。
思考优化
为了使得计算结果尽可能大显然应该让乘法的左右两部分尽可能大。对于存在多个变量的问题一个重要的技巧是 「固定一个思考另一个」 这就容易多了。
固定 j j j 为了让结果更大应该找到 n u m s [ j ] nums[j] nums[j] 左边最大的 n u m s [ i ] nums[i] nums[i] 和右边最大的 n u m s [ k ] nums[k] nums[k] 组合时间复杂度是 O ( n 2 ) O(n^2) O(n2)。我们也可以使用前后缀分解预处理出来这样时间复杂度就是 O ( n ) O(n) O(n)固定 k k k 同理固定 k k k 寻找应该找到左边使得 n u m s [ i ] − n u m s [ j ] nums[i] - nums[j] nums[i]−nums[j] 最大的方案这可以实现线性时间和常量空间。
题解一枚举
枚举所有方案记录最优解。
class Solution {fun maximumTripletValue(nums: IntArray): Long {var ret 0Lval n nums.sizefor (i in 0 until n) {for (j in i 1 until n) {for (k in j 1 until n) {ret max(ret, 1L * (nums[i] - nums[j]) * nums[k])}}}return ret}
}复杂度分析
时间复杂度 O ( n 3 ) O(n^3) O(n3)空间复杂度 O ( 1 ) O(1) O(1)
题解二前后缀分解
预处理出每个位置前后的最大值再枚举 n u m s [ j ] nums[j] nums[j] 记录最优解。
class Solution {fun maximumTripletValue(nums: IntArray): Long {val n nums.sizeval preMax IntArray(n)var sufMax IntArray(n)for (i in 1 until n) {preMax[i] max(preMax[i - 1], nums[i - 1])}for (i in n - 2 downTo 0) {sufMax[i] max(sufMax[i 1], nums[i 1])}return max(0, (1 .. n - 2).maxOf { 1L * (preMax[it] - nums[it]) * sufMax[it] })}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
题解三线性遍历
线性遍历 n u m s [ k ] nums[k] nums[k] 并记录 ( n u m s [ i ] − n u m s [ j ] ) (nums[i] - nums[j]) (nums[i]−nums[j]) 的最大值记录最优解。
class Solution {fun maximumTripletValue(nums: IntArray): Long {val n nums.sizevar ret 0Lvar maxDelta 0var maxI 0for (e in nums) {ret max(ret, 1L * maxDelta * e)maxDelta max(maxDelta, maxI - e)maxI max(maxI, e)}return ret}
}class Solution:def maximumTripletValue(self, nums: List[int]) - int:ret maxDelta maxI 0for e in nums:ret max(ret, maxDelta * e)maxDelta max(maxDelta, maxI - e)maxI max(maxI, e)return retclass Solution {
public:long long maximumTripletValue(vectorint nums) {long long ret 0;int max_delta 0, max_i 0;for (int e : nums) {ret max(ret, (long long) max_delta * e);max_delta max(max_delta, max_i - e);max_i max(max_i, e);}return ret;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1) T3. 无限数组的最短子数组Medium
https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/description/问题分析
令 n u m s nums nums 数组的整体元素和为 s s s考虑 t a r g e t target target 的两种情况
对于 t a r g e t target target 很小的情况小于数组整体和 s s s这是很简单的滑动窗口问题对于 t a r g e t target target 较大的情况大于等于数组的整体和 s s s那么最小长度中一定包含整数倍的 s s s以及某个 n u m s nums nums 的子数组。
class Solution {fun minSizeSubarray(nums: IntArray, t: Int): Int {val n nums.sizeval s nums.sum()val k t % s// 同向双指针var left 0var sum 0var len nfor (right in 0 until 2 * n) {sum nums[right % n]while (sum k) {sum - nums[left % n]left }if (sum k) len min(len, right - left 1)}return if (len n) -1 else n * (t / s) len}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) 最大扫描 2 2 2 倍数组长度空间复杂度仅使用常量级别空间。 T4. 有向图访问计数Hard
https://leetcode.cn/problems/count-visited-nodes-in-a-directed-graph/description/问题分析
初步分析
对于 n n n 个点 n n n 条边的有向弱连通图图中每个点的出度都是 1 1 1因此它是一棵 「内向基环树」。那么对于每个点有 2 2 2 种情况
环上节点绕环行走一圈后就会回到当前位置因此最长访问路径就是环长树链节点那么从树链走到环上后也可以绕环行走一圈因此最长访问路径就是走到环的路径 环长。 图片不记得出处了~ 思考实现
只有一个连通分量的情况 那么问题就相对简单我们用拓扑排序剪去树链并记录链上节点的深度到环上的距离最后剩下的部分就是基环有多个连通分量的情况 我们需要枚举每个连通分量的基环再将基环的长度累加到该连通分量的每个节点。
题解拓扑排序 DFS
第一个问题将基环的长度累加到该连通分量的每个节点
拓扑排序减去树链很容易实现考虑到我们这道题在找到基环后需要反向遍历树链因此我们考虑构造反向图外向基环树
第二个问题找到基环长度
在拓扑排序后树链上节点的入度都是 0 0 0因此入度大于 0 0 0 的节点就位于基环上。枚举未访问的基环节点走 DFS就可以找到该连通分量的基环。
class Solution {fun countVisitedNodes(edges: ListInt): IntArray {// 内向基环树val n edges.sizeval degree IntArray(n)val graph Array(n) { LinkedListInt() }for ((x,y) in edges.withIndex()) {graph[y].add(x)degree[y] // 入度}// 拓扑排序val ret IntArray(n)var queue LinkedListInt()for (i in 0 until n) {if (0 degree[i]) queue.offer(i)}while(!queue.isEmpty()) {val x queue.poll()val y edges[x] if (0 -- degree[y]) queue.offer(y)}// 反向 DFSfun rdfs(i: Int, depth: Int) {for (to in graph[i]) {if (degree[to] -1) continueret[to] depthrdfs(to, depth 1)}}// 枚举连通分量for (i in 0 until n) {if (degree[i] 0) continueval ring LinkedListInt()var x iwhile (true) {degree[x] -1ring.add(x)x edges[x]if (x i) break}for (e in ring) {ret[e] ring.sizerdfs(e, ring.size 1)}}return ret}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) 拓扑排序和 DFS 都是线性时间空间复杂度 O ( n ) O(n) O(n) 图空间和队列空间。
题解二朴素 DFS
思路参考小羊的题解。
我们发现这道题的核心在于 「找到每个基环的节点」 除了拓扑排序剪枝外对于内向基环树来从任何一个节点走 DFS 走到的最后一个节点一定是基环上的节点。
在细节上对于每个未访问过的节点走 DFS 的结果会存在 3 3 3 种情况
环上节点刚好走过基环树链节点走过树链 基环。还有 1 1 1 种情况DFS 起点是从树链的末端走的而前面树链的部分和基环都被走过此时 DFS 终点就不一定是基环节点了。这种情况就同理从终点直接反向遍历就好了等于说省略了处理基环的步骤。
class Solution {fun countVisitedNodes(edges: ListInt): IntArray {val n edges.sizeval ret IntArray(n)val visit BooleanArray(n)for (i in 0 until n) {if (visit[i]) continue// DFSval link LinkedListInt()var x iwhile (!visit[x]) {visit[x] truelink.add(x)x edges[x]}if (ret[x] 0) {val depth link.size - link.indexOf(x) // (此时 x 位于基环入口)repeat(depth) {ret[link.pollLast()] depth}}var depth ret[x]while (!link.isEmpty()) {ret[link.pollLast()] depth}}return ret}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) DFS 都是线性时间空间复杂度 O ( n ) O(n) O(n) 图空间和队列空间。 推荐阅读 LeetCode 上分之旅系列往期回顾 LeetCode 单周赛第 364 场 · 前后缀分解结合单调栈的贡献问题LeetCode 单周赛第 363 场 · 经典二分答案与质因数分解LeetCode 双周赛第 114 场 · 一道简单的树上动态规划问题LeetCode 双周赛第 113 场 · 精妙的 O(lgn) 扫描算法与树上 DP 问题 ⭐️ 永远相信美好的事情即将发生欢迎加入小彭的 Android 交流社群~
