muse cc 做网站,公司网站修改怎么做,火车头采集网站,开发网站的申请怎么写⭐️ 本文已收录到 AndroidFamily#xff0c;技术和职场问题#xff0c;请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架#xff0c;你的思考越抽象#xff0c;它能覆盖的问题域就越广#xff0c;理解难度… ⭐️ 本文已收录到 AndroidFamily技术和职场问题请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架你的思考越抽象它能覆盖的问题域就越广理解难度也更复杂。在这个专栏里小彭与你分享每场 LeetCode 周赛的解题报告一起体会上分之旅。 本文是 LeetCode 上分之旅系列的第 44 篇文章往期回顾请移步到文章末尾~ T1. 统计对称整数的数目Easy
标签模拟
T2. 生成特殊数字的最少操作Medium
标签思维、回溯、双指针
T3. 统计趣味子数组的数目Medium
标签同余定理、前缀和、散列表
T4. 边权重均等查询Hard
标签图、倍增、LCA、树上差分 T1. 统计对称整数的数目Easy
https://leetcode.cn/problems/count-symmetric-integers/题解模拟
根据题意模拟亦可以使用前缀和预处理优化。
class Solution {fun countSymmetricIntegers(low: Int, high: Int): Int {var ret 0for (x in low..high) {val s $xval n s.lengthif (n % 2 ! 0) continuevar diff 0for (i in 0 until n / 2) {diff s[i] - 0diff - s[n - 1 - i] - 0}if (diff 0) ret 1}return ret}
}复杂度分析
时间复杂度 O ( ( h i g h − l o w ) l g h i g h ) O((high-low)lg^{high}) O((high−low)lghigh) 单次检查时间为 O ( l g h i g h ) O(lg^{high}) O(lghigh)空间复杂度 O ( 1 ) O(1) O(1) 仅使用常量级别空间。 T2. 生成特殊数字的最少操作Easy
https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/题解一回溯
思维题这道卡了多少人。
阅读理解 在一次操作中您可以选择 n u m num num 的任意一位数字并将其删除求最少需要多少次操作可以使 n u m num num 变成 25 25 25 的倍数规律 对于 25 25 25 的倍数当且仅当结尾为「00、25、50、75」这 4 4 4 种情况时成立我们尝试构造出尾部符合两个数字能被 25 25 25 整除的情况。
可以用回溯解决
class Solution {fun minimumOperations(num: String): Int {val memo HashMapString, Int()fun count(x: String): Int {val n x.lengthif (n 1) return if (x 0) 0 else 1if (((x[n - 2] - 0) * 10 (x[n - 1]- 0)) % 25 0) return 0if(memo.containsKey(x))return memo[x]!!val builder1 StringBuilder(x)builder1.deleteCharAt(n - 1)val builder2 StringBuilder(x)builder2.deleteCharAt(n - 2)val ret 1 min(count(builder1.toString()), count(builder2.toString()))memo[x]retreturn ret}return count(num)}
}复杂度分析
时间复杂度 O ( n 2 ⋅ m ) O(n^2·m) O(n2⋅m) 最多有 n 2 n^2 n2 种子状态其中 m m m 是字符串的平均长度 O ( m ) O(m) O(m) 是构造中间字符串的时间空间复杂度 O ( n ) O(n) O(n) 回溯递归栈空间。
题解二双指针
初步分析
模拟 事实上问题的方案最多只有 4 种回溯的中间过程事实在尝试很多无意义的方案。我们直接枚举这 4 种方案删除尾部不属于该方案的字符。以 25 为例就是删除 5 后面的字符以及删除 2 与 5 中间的字符抽象 本质上是一个最短匹配子序列的问题即 「找到 nums 中最靠后的匹配的最短子序列」问题可以用双指针模拟。
具体实现
双指针 我们找到满足条件的最靠左的下标 i并删除末尾除了目标数字外的整段元素即 r e t n − i − 2 ret n - i - 2 retn−i−2特殊情况 在 4 种构造合法的特殊数字外还存在删除所有非 0 数字后构造出 0 的方案是否要验证数据含有前导零 对于构造「00」的情况是否会存在删到最后剩下多个 0 的情况呢其实是不存在的。因为题目说明输入数据 num 本身是不包含前导零的如果最后剩下多个 0 那么在最左边的 0 左侧一定存在非 0 数字否则与题目说明矛盾。
class Solution {fun minimumOperations(num: String): Int {val n num.lengthvar ret nfor (choice in arrayOf(00, 25, 50, 75)) {// 双指针var j 1for (i in n - 1 downTo 0) {if (choice[j] ! num[i]) continueif (--j -1) {ret min(ret, n - i - 2)break}}}// 特殊情况ret min(ret, n - num.count { it 0})return ret}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) 4 种方案和特殊方案均是线性遍历空间复杂度 O ( 1 ) O(1) O(1) 仅使用常量级别空间。 T3. 统计趣味子数组的数目Medium
https://leetcode.cn/problems/count-of-interesting-subarrays/题解同余 前缀和 散列表
初步分析
问题目标 统计数组中满足目标条件的子数组目标条件 在子数组范围 [ l , r ] [l, r] [l,r] 内设 c n t cnt cnt 为满足 n u m s [ i ] nums[i] % m k nums[i] 的索引 i i i 的数量并且 c n t cnt % m k cnt。大白话就是算一下有多少数的模是 k k k再判断个数的模是不是也是 k k k权重 对于满足 n u m s [ i ] nums[i] % m k nums[i] 的元素它对结果的贡献是 1 1 1否则是 0 0 0
分析到这里容易想到用前缀和实现
前缀和 记录从起点到 [ i ] [i] [i] 位置的 [ 0 , i ] [0, i] [0,i] 区间范围内满足目标的权重数两数之和 从左到右枚举 [ i ] [i] [i]并寻找已经遍历的位置中满足 ( p r e S u m [ i ] − p r e S u m [ j ] ) % m k (preSum[i] - preSum[j]) \% m k (preSum[i]−preSum[j])%mk 的方案数记入结果公式转换 上式带有取模运算我们需要转换一下 原式 ( p r e S u m [ i ] − p r e S u m [ j ] ) % m k (preSum[i] - preSum[j]) \% m k (preSum[i]−preSum[j])%mk考虑 p r e S u m [ i ] % m − p r e S u m [ j ] % m preSum[i] \% m - preSum[j] \% m preSum[i]%m−preSum[j]%m 是正数数的的情况原式等价于 p r e S u m [ i ] % m − p r e S u m [ j ] % m k preSum[i] \% m - preSum[j] \% m k preSum[i]%m−preSum[j]%mk考虑 p r e S u m [ i ] % m − p r e S u m [ j ] % m preSum[i] \% m - preSum[j] \% m preSum[i]%m−preSum[j]%m 是负数的的情况我们在等式左边增加补数 ( p r e S u m [ i ] % m − p r e S u m [ j ] % m m ) (preSum[i] \% m - preSum[j] \% m m) %m k (preSum[i]%m−preSum[j]%mm)联合正数和负数两种情况即我们需要找到前缀和为 ( p r e S u m [ i ] % m − k m ) % m (preSum[i] \% m - k m) \% m (preSum[i]%m−km)%m 的元素 修正前缀和定义 最后我们修改前缀和的定义为权重 % m \% m %m。
组合以上技巧
class Solution {fun countInterestingSubarrays(nums: ListInt, m: Int, k: Int): Long {val n nums.sizevar ret 0Lval preSum HashMapInt, Int()preSum[0] 1 // 注意空数组的状态var cur 0for (i in 0 until n) {if (nums[i] % m k) cur // 更新前缀和val key cur % mval target (key - k m) % mret preSum.getOrDefault(target, 0) // 记录方案preSum[key] preSum.getOrDefault(key, 0) 1 // 记录前缀和}return ret}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) 线性遍历单次查询时间为 O ( 1 ) O(1) O(1)空间复杂度 O ( m ) O(m) O(m) 散列表空间。
相似题目
560. 和为 K 的子数组974. 和可被 K 整除的子数组523. 连续的子数组和525. 连续数组 T4. 边权重均等查询Hard
https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/题解倍增求 LCA、树上差分
初步分析
问题目标 给定若干个查询 [ x , y ] [x, y] [x,y]要求计算将 x , y x, y x,y 的路径上的每条边修改为相同权重的最少操作次数问题要件 对于每个查询 [ x , y ] [x, y] [x,y]我们需要计算 x , y x, y x,y 的路径长度 l l l以及边权重的众数的出现次数 c c c而要修改的操作次数就是 l − c l - c l−c技巧 对于 “树上路径” 问题有一种经典技巧我们可以把 x , y x, y x,y 的路径转换为从 x , l c a x, lca x,lca 的路径与 l c a , y lca, y lca,y 的两条路径
思考实现
长度 将问题转换为经过 l c a lca lca 中转的路径后路径长度 l l l 可以用深度来计算 l d e p t h [ x ] d e p t h [ y ] − 2 ∗ d e p t h [ l c a ] l depth[x] depth[y] - 2 * depth[lca] ldepth[x]depth[y]−2∗depth[lca]权重 同理权重 w [ x , y ] w[x,y] w[x,y] 可以通过 w [ x , l c a ] w[x, lca] w[x,lca] 与 w [ l c a , y ] w[lca, y] w[lca,y] 累加计算
现在的关键问题是如何快速地找到 x , y x, y x,y 的最近公共祖先 LCA
对于单次 LCA 操作来说我们可以走 DFS 实现 O ( n ) O(n) O(n) 时间复杂度的算法而对于多次 LCA 操作可以使用 倍增算法 预处理以空间换时间单次 LCA 操作的时间复杂度进位 O ( l g n ) O(lgn) O(lgn)。
在 LeetCode 有倍增的模板题 1483. 树节点的第 K 个祖先。
在求 LCA 时我们先把 x , y x, y x,y 跳到相同高度再利用倍增算法向上跳 2 j 2^j 2j 个父节点直到到达相同节点即为最近公共祖先。 class Solution {fun minOperationsQueries(n: Int, edges: ArrayIntArray, queries: ArrayIntArray): IntArray {val U 26// 建图val graph Array(n) { LinkedListIntArray() }for (edge in edges) {graph[edge[0]].add(intArrayOf(edge[1], edge[2] - 1))graph[edge[1]].add(intArrayOf(edge[0], edge[2] - 1))}// 预处理深度、倍增祖先节点、倍增路径信息val m 32 - Integer.numberOfLeadingZeros(n - 1)val depth IntArray(n)val parent Array(n) { IntArray(m) { -1 }} // parent[i][j] 表示 i 的第 2^j 个父节点val cnt Array(n) { Array(m) { IntArray(U) }} // cnt[i][j] 表示 i - 2^j 个父节点的路径信息fun dfs(i: Int, par: Int) {for ((to, w) in graph[i]) {if (to par) continue // 避免回环depth[to] depth[i] 1parent[to][0] icnt[to][0][w] 1dfs(to, i)}}dfs(0, -1) // 选择 0 作为根节点// 预处理倍增for (j in 1 until m) {for (i in 0 until n) {val from parent[i][j - 1]if (-1 ! from) {parent[i][j] parent[from][j - 1]cnt[i][j] cnt[i][j - 1].zip(cnt[from][j - 1]) { e1, e2 - e1 e2 }.toIntArray()}}}// 查询val q queries.sizeval ret IntArray(q)for ((i, query) in queries.withIndex()) {var (x, y) query// 特判if (x y || parent[x][0] y || parent[y][0] x) {ret[i] 0}val w IntArray(U) // 记录路径信息var path depth[x] depth[y] // 记录路径长度// 先跳到相同高度if (depth[y] depth[x]) {val temp xx yy temp}var k depth[x] - depth[y]while (k 0) {val j Integer.numberOfTrailingZeros(k) // 二进制分解w.indices.forEach { w[it] cnt[x][j][it] } // 记录路径信息x parent[x][j] // 向上跳 2^j 个父节点k k and (k - 1)}// 再使用倍增找 LCAif (x ! y) {for (j in m - 1 downTo 0) { // 最多跳 m - 1 次if (parent[x][j] parent[y][j]) continue // 跳上去相同就不跳w.indices.forEach { w[it] cnt[x][j][it] } // 记录路径信息w.indices.forEach { w[it] cnt[y][j][it] } // 记录路径信息x parent[x][j]y parent[y][j] // 向上跳 2^j 个父节点}// 最后再跳一次就是 lcaw.indices.forEach { w[it] cnt[x][0][it] } // 记录路径信息w.indices.forEach { w[it] cnt[y][0][it] } // 记录路径信息x parent[x][0]}// 减去重链长度ret[i] path - 2 * depth[x] - w.max()}return ret}
}复杂度分析
时间复杂度 O ( n l g n ⋅ U ) O(nlgn·U) O(nlgn⋅U) 预处理的时间复杂度是 O ( n l g n ⋅ U ) O(nlgn·U) O(nlgn⋅U)单次查询的时间是 O ( l g n ⋅ U ) O(lgn·U) O(lgn⋅U)空间复杂度 O ( n l g n ⋅ U ) O(nlgn·U) O(nlgn⋅U) 预处理倍增信息空间。 推荐阅读 LeetCode 上分之旅系列往期回顾 LeetCode 单周赛第 360 场 · 当 LeetCode 考树上倍增出题的趋势在变化吗LeetCode 单周赛第 359 场 · 结合离散化的线性 DP 问题LeetCode 双周赛第 112 场 · 计算机科学本质上是数学吗LeetCode 双周赛第 111 场 · 按部就班地解决动态规划问题 ⭐️ 永远相信美好的事情即将发生欢迎加入小彭的 Android 交流社群~
