厦门专业做网站,湖州建设培训入口网站,高明搜索seo,做ptt网站⭐️ 本文已收录到 AndroidFamily#xff0c;技术和职场问题#xff0c;请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架#xff0c;你的思考越抽象#xff0c;它能覆盖的问题域就越广#xff0c;理解难度… ⭐️ 本文已收录到 AndroidFamily技术和职场问题请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架你的思考越抽象它能覆盖的问题域就越广理解难度也更复杂。在这个专栏里小彭与你分享每场 LeetCode 周赛的解题报告一起体会上分之旅。 本文是 LeetCode 上分之旅系列的第 45 篇文章往期回顾请移步到文章末尾~ LeetCode 双周赛 113 概览
T1. 使数组成为递增数组的最少右移次数Easy
标签模拟、暴力、线性遍历
T2. 删除数对后的最小数组长度Medium
标签二分答案、双指针、找众数、
T3. 统计距离为 k 的点对Medium
标签枚举、散列表
T4. 可以到达每一个节点的最少边反转次数Hard
标签树上 DP T1. 使数组成为递增数组的最少右移次数Easy
https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/description/题解一暴力枚举
简单模拟题。
由于题目数据量非常小可以把数组复制一份拼接在尾部再枚举从位置 i i i 开始长为 n n n 的连续循环子数组是否连续是则返回 ( n − i ) % n (n - i)\%n (n−i)%n
class Solution {fun minimumRightShifts(nums: MutableListInt): Int {val n nums.sizenums.addAll(nums)for (i in 0 until n) {if ((i 1 .. i n).all { nums[it] nums[it - 1]}) return (n - i) % n}return -1}
}class Solution:def minimumRightShifts(self, nums: List[int]) - int:n len(nums)nums numsfor i in range(0, n):if all(nums[j] nums[j - 1] for j in range(i 1, i n)):return (n - i) % nreturn -1复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2) 双重循环空间复杂度 O ( n ) O(n) O(n) 循环数组空间。
题解二线性遍历
更优的写法我们找到第一个逆序位置再检查该位置后续位置是否全部为升序且满足 n u m s [ n − 1 ] n u m s [ 0 ] nums[n - 1] nums[0] nums[n−1]nums[0]
class Solution {fun minimumRightShifts(nums: ListInt): Int {val n nums.sizefor (i in 1 until n) { // 第一段if (nums[i] nums[i - 1]) continue// 第二段if (nums[n - 1] nums[0]) return -1for (j in i until n - 1) { if (nums[j] nums[j 1]) return -1}return n - i}return 0}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) i i i 指针和 j j j 指针总计最多移动 n n n 次空间复杂度 O ( 1 ) O(1) O(1) 仅使用常量级别空间。 T2. 删除数对后的最小数组长度Medium
https://leetcode.cn/problems/minimum-array-length-after-pair-removals/题解一二分答案
问题存在单调性
当操作次数 k k k 可以满足时操作次数 k − 1 k - 1 k−1 一定能满足当操作次数 k k k 不可满足时操作次数 k 1 k 1 k1 一定不能满足。
那么原问题相当于求解满足目标的最大操作次数。
现在需要考虑的问题是如何验证操作次数 k k k 是否可以完成
一些错误的思路
尝试 1 - 贪心双指针 n u m s [ i ] nums[i] nums[i] 优先使用最小值 n u m s [ j ] nums[j] nums[j] 优先使用最大值错误用例 [ 1236 ] [1 2 3 6] [1236]尝试 2 - 贪心 n u m s [ i ] nums[i] nums[i] 优先使用最小值 n u m s [ j ] nums[j] nums[j] 使用大于 n u m s [ i ] nums[i] nums[i] 的最小值错误用例 [ 1246 ] [1 2 4 6] [1246]尝试 3 - 贪心 从后往前遍历 n u m s [ i ] nums[i] nums[i] 优先使用较大值 n u m s [ j ] nums[j] nums[j] 使用大于 n u m s [ i ] nums[i] nums[i] 的最小值错误用例 [ 2348 ] [2 3 4 8] [2348]。
开始转换思路
能否将数组拆分为两部分作为 nums[i] 的分为一组作为 n u m s [ j ] nums[j] nums[j] 的分为一组。 例如在用例 [ 12 ∣ 36 ] [1 2 | 3 6] [12∣36] 和 [ 12 ∣ 46 ] [1 2 | 4 6] [12∣46] 和 [ 23 ∣ 48 ] [2 3 | 4 8] [23∣48] 中将数组的前部分作为 n u m s [ i ] nums[i] nums[i] 而后半部分作为 n u m s [ j ] nums[j] nums[j] 时可以得到最优解至此发现贪心规律。
设数组的长度为 n n n最大匹配对数为 k k k
结论 1 使用数组的左半部分作为 n u m s [ i ] nums[i] nums[i] 且使用数组的右半部分作为 n u m s [ j ] nums[j] nums[j] 总能取到最优解。反之如果使用右半部分的某个数 n u m s [ t ] nums[t] nums[t] 作为 n u m s [ i ] nums[i] nums[i]相当于占用了一个较大的数不利于后续 n u m s [ i ] nums[i] nums[i] 寻找配对结论 2 当固定 n u m s [ i ] nums[i] nums[i] 时 n u m s [ j ] nums[j] nums[j] 越小越好否则会占用一个较大的位置不利于后续 n u m s [ i ] nums[i] nums[i] 寻找配对。因此最优解一定是使用左半部分的最小值与右半部分的最小值配对。
总结如果存在 k k k 对匹配那么一定可以让最小的 k k k 个数和最大的 k k k 个数匹配。
基于以上分析可以写出二分答案
class Solution {fun minLengthAfterRemovals(nums: ListInt): Int {val n nums.sizevar left 0var right n / 2while (left right) {val k (left right 1) ushr 1if ((0 .. k).all { nums[it] nums[n - k it] }) {left k} else {right k - 1}}return n - 2 * left}
}复杂度分析
时间复杂度 O ( n l g n ) O(nlgn) O(nlgn) 二分答案次数最大为 l g n lgn lgn 次单次检验的时间复杂度是 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1) 仅使用常量级别空间。
题解二双指针
基于题解一的分析以及删除操作的上界 n / 2 n / 2 n/2我们可以仅使用数组的后半部分与前半部分作比较具体算法
i 指针指向索引 0 0 0j 指针指向索引 ( n 1 ) / 2 (n 1) / 2 (n1)/2向右枚举 j j j 指针如果 i i i、 j j j 指针指向的位置能够匹配则向右移动 i i i 指针最后 i i i 指针移动的次数就等于删除操作次数。
class Solution {fun minLengthAfterRemovals(nums: ListInt): Int {val n nums.sizevar i 0for (j in (n 1) / 2 until n) {if (nums[i] nums[j]) i}return n - 2 * i}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) 线性遍历空间复杂度 O ( 1 ) O(1) O(1) 仅使用常量级别空间。
题解三众数
由于题目的操作只要满足 n u m s [ i ] n u m s [ j ] nums[i] nums[j] nums[i]nums[j]即两个数不相等即可那么问题的解最终仅取决于数组中的众数的出现次数
如果众数的出现次数比其他元素少那么所有元素都能删除问题的结果就看数组总长度是奇数还是偶数否则剩下的元素就是众数 s − ( n − s ) s - (n - s) s−(n−s)
最后由于数组是非递减的因此可以在 O ( 1 ) O(1) O(1) 空间求出众数的出现次数
class Solution {fun minLengthAfterRemovals(nums: ListInt): Int {val n nums.sizevar s 1var cur 1for (i in 1 until n) {if (nums[i] nums[i - 1]) {s max(s, cur)} else {cur 1}}if (s n - s) {return n % 2} else {return s - (n - s)}}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) 线性遍历空间复杂度 O ( 1 ) O(1) O(1) 仅使用常量级别空间。
题解四找规律 二分查找
继续挖掘数据规律 s n − s s n - s sn−s 等价于众数的出现次数超过数组长度的一半由于数组是有序的那么一定有数组的中间位置就是众数我们可以用二分查找找出众数在数组中出现位置的边界从而计算出众数的出现次数。
由此我们甚至不需要线性扫描都能计算出众数以及众数的出现次数Nice
当然最后计算出来的出现次数有可能没有超过数组长度的一半。
class Solution {fun minLengthAfterRemovals(nums: ListInt): Int {val n nums.sizeval x nums[n / 2]val s lowerBound(nums, x 1) - lowerBound(nums, x)return max(2 * s - n, n % 2)}fun lowerBound(nums: ListInt, target: Int): Int {var left 0var right nums.size - 1while (left right) {val mid (left right 1) ushr 1if (nums[mid] target) {right mid - 1} else {left mid}}return if (nums[left] target) left else left 1}
}复杂度分析
时间复杂度 O ( l g n ) O(lgn) O(lgn) 单次二分查找的时间复杂度是 O ( l g n ) O(lgn) O(lgn)空间复杂度 O ( 1 ) O(1) O(1) 仅使用常量级别空间。
相似题目
2576. 求出最多标记下标 T3. 统计距离为 k 的点对Medium
https://leetcode.cn/problems/count-pairs-of-points-with-distance-k/题解散列表
问题目标 求 ( x 1 x o r x 2 ) ( y 1 x o r y 2 ) k (x1 xor x2) (y1 xor y2) k (x1xorx2)(y1xory2)k 的方案数技巧 对于存在多个变量的问题可以考虑先固定其中一个变量
容易想到两数之和的问题模板唯一需要思考的问题是如何设计散列表的存取方式
对于满足 ( x 1 x o r x 2 ) ( y 1 x o r y 2 ) k (x1\ xor\ x2) (y1\ xor\ y2) k (x1 xor x2)(y1 xor y2)k 的方案我们抽象为两部分 i j k i j k ijk其中 i ( x 1 x o r x 2 ) i (x1\ xor\ x2) i(x1 xor x2) 的取值范围为 [ 0 , k ] [0, k] [0,k]而 j k − i j k - i jk−i即总共有 k 1 k 1 k1 种方案。本题的 k k k 数据范围很小所以我们可以写出时间复杂度 O ( n k ) O(nk) O(nk) 的算法。
class Solution {fun countPairs(coordinates: ListListInt, k: Int): Int {var ret 0// x, y, cntval map HashMapInt, HashMapInt, Int()for ((x2, y2) in coordinates) {// 记录方案for (i in 0 .. k) {if (!map.containsKey(i xor x2)) continueret map[i xor x2]!!.getOrDefault((k - i) xor y2, 0)}// 累计次数map.getOrPut(x2) { HashMapInt, Int() }[y2] map[x2]!!.getOrDefault(y2, 0) 1}return ret}
}Python 计数器支持复合数据类型的建可以写出非常简洁的代码
class Solution:def countPairs(self, coordinates: List[List[int]], k: int) - int:c Counter()ret 0for x2, y2 in coordinates:# 记录方案for i in range(k 1):ret c[(i ^ x2, (k - i) ^ y2)]# 累计次数c[(x2, y2)] 1return ret复杂度分析
时间复杂度 O ( n ⋅ k ) O(n·k) O(n⋅k) 线性枚举每个元素枚举 k k k 种方案空间复杂度 O ( n ) O(n) O(n) 散列表空间。 T4. 可以到达每一个节点的最少边反转次数Hard
https://leetcode.cn/problems/minimum-edge-reversals-so-every-node-is-reachable/问题分析
初步分析
问题目标 求出以每个节点为根节点时从根节点到其他节点的反转操作次数此题属于换根 DP 问题
思考实现
暴力 以节点 i i i 为根节点走一次 BFS/DFS就可以在 O ( n ) O(n) O(n) 时间内求出每个节点的解整体的时间复杂度是 O ( n 2 ) O(n^2) O(n2)
思考优化
重叠子问题 相邻边连接的节点间存在重叠子问题当我们从根节点 u u u 移动到其子节点 v v v 时我们可以利用已有信息在 O ( 1 ) O(1) O(1) 时间算出 v v v 为根节点时的解。
具体实现
1、随机选择一个点为根节点 u u u在一次 DFS 中根节点 u u u 的反转操作次数2、 u → v u → v u→v 的状态转移 如果 u → v u → v u→v 是正向边则反转次数 1 1 1如果 u → v u → v u→v 是反向边则反转次数 − 1 - 1 −1从 v v v 到 u u u 不用反转 3、由于题目是有向图我们可以转换为无向图再利用标记位 1 1 1 和 − 1 -1 −1 表示边的方向 1 1 1 为正向边 − 1 -1 −1 为反向边。
题解换根 DP
class Solution {fun minEdgeReversals(n: Int, edges: ArrayIntArray): IntArray {val dp IntArray(n)val graph Array(n) { LinkedListIntArray() }// 建图for ((from, to) in edges) {graph[from].add(intArrayOf(to, 1))graph[to].add(intArrayOf(from, -1))}// 以 0 为根节点fun dfs(i: Int, fa: Int) {for ((to, gain) in graph[i]) {if (to fa) continueif (gain -1) dp[0] dfs(to, i)}}fun dp(i: Int, fa: Int) {for ((to, gain) in graph[i]) {if (to fa) continue// 状态转移dp[to] dp[i] gaindp(to, i)}}dfs(0, -1)dp(0, -1)return dp}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) DFS 和换根 DP 都是 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n) 递归栈空间与 DP 数组空间。 推荐阅读 LeetCode 上分之旅系列往期回顾 LeetCode 单周赛第 361 场 · 同余前缀和问题与经典倍增 LCA 算法LeetCode 单周赛第 360 场 · 当 LeetCode 考树上倍增出题的趋势在变化吗LeetCode 双周赛第 112 场 · 计算机科学本质上是数学吗LeetCode 双周赛第 111 场 · 按部就班地解决动态规划问题 ⭐️ 永远相信美好的事情即将发生欢迎加入小彭的 Android 交流社群~
