百度云建站网站建设,重庆优化网站排名,wordpress关闭主循环,做企业网站要注意什么本文已收录到 AndroidFamily#xff0c;技术和职场问题#xff0c;请关注公众号 [彭旭锐] 提问。 大家好#xff0c;我是小彭。
昨晚是 LeetCode 第 98 场双周赛#xff0c;你参加了吗#xff1f;这场周赛需要脑筋急转弯#xff0c;转不过来 Medium 就会变成 Hard#… 本文已收录到 AndroidFamily技术和职场问题请关注公众号 [彭旭锐] 提问。 大家好我是小彭。
昨晚是 LeetCode 第 98 场双周赛你参加了吗这场周赛需要脑筋急转弯转不过来 Medium 就会变成 Hard转得过来就变成 Easy。 2566. 替换一个数字后的最大差值Easy
题目地址
https://leetcode.cn/problems/maximum-difference-by-remapping-a-digit/
题目描述
给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字 替换 成另一个数字。
请你返回将 num 中 恰好一个 数字进行替换后得到的最大值和最小值的差位多少。
注意
当 Danny 将一个数字 d1 替换成另一个数字 d2 时Danny 需要将 nums 中所有 d1 都替换成 d2 。Danny 可以将一个数字替换成它自己也就是说 num 可以不变。Danny 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。替换后得到的数字可以包含前导 0 。Danny Mittal 获得周赛 326 前 10 名让我们恭喜他。
题解字符串操作
技巧将整型转换为字符串能够更方便地修改具体位置。
简单模拟题有 2 个思路
思路 1 - 暴力枚举尝试枚举每类的数字将其替换为 9 取得最大值将其替换为 0 取得最小值最后取所有方案的最大值和最小值取差值思路 2 - 贪心思路替换越靠近 “高位” 的数字能够使得差值越大所以我们将从高位开始的首个非 9 数字替换为 9例如 90 替换为 99必然得到最大值将从高位开始的首个数字替换为 0例如 90 替换为 00必然得到最小值。
// 思路 1
class Solution {fun minMaxDifference(num: Int): Int {val numStr $numvar max numvar min numfor (element in numStr) {max Math.max(max, numStr.replace(element, 9).toInt())min Math.min(min, numStr.replace(element, 0).toInt())}return max - min}
}复杂度分析
时间复杂度O(log2num)O(log^2\,{num})O(log2num) 数字最多有 log num 位外层循环与内存循环的字符串替换操作都是 O(lognum)O(log\,{num})O(lognum) 时间级别复杂度空间复杂度O(lognum)O(log\,{num})O(lognum) 字符串占用空间。
// 思路 2
class Solution {fun minMaxDifference(num: Int): Int {val numStr $numval min numStr.replace(numStr[0], 0).toInt()var max numfor (element in numStr) {if (9 ! element) {max numStr.replace(element, 9).toInt()break}}return max - min}
}复杂度分析
时间复杂度O(lognum)O(log\,{num})O(lognum) 内存循环的字符串替换操作最多只会执行一次均摊下来整体只有 O(lognum)O(log\,{num})O(lognum) 级别的时间复杂度空间复杂度O(lognum)O(log\,{num})O(lognum) 字符串占用空间。 2567. 修改两个元素的最小分数Medium)
题目地址
https://leetcode.cn/problems/minimum-score-by-changing-two-elements/
题目描述
给你一个下标从 0 开始的整数数组 nums 。
nums 的 最小 得分是满足 0 i j nums.length 的 |nums[i] - nums[j]| 的最小值。nums的 最大 得分是满足 0 i j nums.length 的 |nums[i] - nums[j]| 的最大值。nums 的分数是 最大 得分与 最小 得分的和。
我们的目标是最小化 nums 的分数。你 最多 可以修改 nums 中 2 个元素的值。
请你返回修改 nums 中 至多两个 元素的值后可以得到的 最小分数 。
|x| 表示 x 的绝对值。
题解排序 枚举
这道题也有脑筋急转弯的成分同时我们可以扩展思考下 “最多修改 k 个元素的最小得分” 问题最后再说。
这道题的关键在于得分的定义
“最小得分” 表示任意数组中两个数字之间的最小绝对差“最大得分” 表示任意数组中两个数字之间的最大绝对差。
理解题意后容易发现
影响 “最小得分” 的是数组中最接近的两个数字。当数组中存在两个相同元素时“最小得分” 可以取到最小值 0影响 “最大得分” 的是数组中最不接近的两个数即最大值和最小值。当我们将最大值和最小值修改为数组中间的某个元素时能使得差值变小的同时保持 “最小得分” 取最小值 0。
因此得知 这道题的关键点在于修改数组的最大值或最小值成为数组中间的某个元素。 要么让最大值变小要么让最小值变大。由于题目最多只能修改 2 次因此最多只能以下 3 种情况
情况 1修改数组中最大的两个数为 nums[n - 3]情况 2修改数组中最小的两个数为 nums[2]情况 3修改数组的最大值为 nums[n - 1]修改数组的最小值为 nums[1]。
简单枚举出 3 种情况的解后再进行一轮比较即可。
最后再观察边界条件数组的最小长度为 3所以不需要特判。
class Solution {fun minimizeSum(nums: IntArray): Int {nums.sort()val n nums.sizeval choice1 nums[n - 3] - nums[0]val choice2 nums[n - 1] - nums[2]val choice3 nums[n - 2] - nums[1]return Math.min(choice1, Math.min(choice2, choice3))}
}复杂度分析
时间复杂度O(nlgn)O(nlgn)O(nlgn) 快速排序占用的时间如果手动维护最小的 3 个元素和最大的 3 个元素可以降低到 O(n)O(n)O(n) 时间复杂度空间复杂度O(lgn)O(lgn)O(lgn) 排序占用的递归栈空间。
再扩展思考一下如果题目说明最多可以修改 k0≤k≤nums.lengthk 0 ≤ k ≤ nums.lengthk0≤k≤nums.length次的话应该解决问题呢 —— 即 “求最多修改 k 个元素的最小得分”原题就是 k 2 的情况。
那么这道题就是考察 “滑动窗口” 技巧了我们可以将修改的范围视为一个跨越数组首尾且长度为 k 的滑动窗口那么而问题的答案就取决于 “不被” 滑动窗口包围的另一部分。再逆向思考一下我们可以用长度为 length - k 的滑动窗口在数组上移动并记录窗口首尾元素的差值枚举所有情况后记录最小值即为最小得分
举个例子在输入数组为 [1, 4, 5, 7, 8] k 2 时前文提到的 3 种方案分别对应以下 3 个窗口状态
情况 1修改数组中最大的两个数1,4 | 5,7,8 |情况 2修改数组中最小的两个数| 1,4,5 | 7,8情况 3修改数组的最大值和最小值1 | 4,5,7 | 8
class Solution {fun minimizeSum(nums: IntArray): Int {val n nums.size// 操作次数val k 2// 滑动窗口val len n - knums.sort()var min Integer.MAX_VALUEfor (left in 0..n - len) {val right left len - 1min Math.min(min, nums[right] - nums[left])}return min}
}复杂度分析同上。 2568. 最小无法得到的或值Medium
题目地址
https://leetcode.cn/problems/minimum-impossible-or/
题目描述
给你一个下标从 0 开始的整数数组 nums 。
如果存在一些整数满足 0 index1 index2 ... indexk nums.length 得到 nums[index1] | nums[index2] | ... | nums[indexk] x 那么我们说 x 是 可表达的 。换言之如果一个整数能由 nums 的某个子序列的或运算得到那么它就是可表达的。
请你返回 nums 不可表达的 最小非零整数 。
题解一散列表
相似题目2154. 将找到的值乘以 2
这道题需要脑筋急转弯。
首先我们先观察输入数据范围中小数值的二进制表示尝试发现规律
0 0000 01 0001 12 0010 23 0011 2 | 14 0100 45 0101 4 | 16 0110 4 | 27 0111 4 | 2 | 1或者 5 | 18 1000 89 1001 8 | 110 1010 8 | 2
我们发现以下 2 点信息
除了数字 7 5 | 1 的特殊方案外其他数字的表示方案都可以由形如 x2i∣2j∣2kx 2^i | 2^j | 2^ kx2i∣2j∣2k 的格式表达很容易理解2i2^i2i 格式的数字不可能被其他数用 “或” 的形式表示也很容易理解。
由此可以得出结论 影响数组最小可表达数的关键在于数组中 “未出现的最小的 2i2^i2i”并且这个数就是不可表达的最小非零数。
举例说明假设 8 是数组中未出现的最小 2i2^i2i此时 [1, 2, 4] 肯定在数组中出现2i2^i2i那么数字 1 ~ 7 之间的所有数字都可以由 [1、2、4] 通过或表示而 8 无法被 [1, 2, 3, 4, 5, 6 ,7] 之间的任何数字表达同时也无法被大于 8 的其他数表示因此 8 就是最小的可表达数。
完成问题转换后编码就很容易了我们只要从小到大枚举所有 2i2^i2i 并检查它是否在数组中出现即可
class Solution {fun minImpossibleOR(nums: IntArray): Int {val numSet nums.toHashSet()var i 1while (numSet.contains(i)) {i i shl 1}return i}
}复杂度分析
时间复杂度O(nlogU)O(n logU)O(nlogU) 其中 n 是数组长度U 是数组的最大值最多只需要检查 logU 位数字空间复杂度O(n)O(n)O(n) 散列表占用的空间。
题解二位运算
题解一使用散列表来辅助判断 2i2^i2i 是否存在于数组中可以进一步优化我们将直接从数组元素的二进制数据中提取特征值并还原出 “未出现的最小的 2i2^i2i”
1、遍历数组中所有元素如果元素值是 2i2^i2i 则将其记录到 mask 特征值中2、遍历结束后将得到形如 0011, 1011 格式的特征值此时 “未出现的最小的 2i2^i2i” 正好位于从低位到高位出现的首个 0 的位置即 0000, 0100;3、为了还原出目标数执行以下位运算
x ~x // 按位取反 0011,1011 1100,0100
x -x // lowbit 公式1100,0100 0000,0100class Solution {fun minImpossibleOR(nums: IntArray): Int {var mask 0for (x in nums) {// x (x - 1) 将消除最低位的 1如果消除后值为 1 说明 x 本身就是 2 的幂if (x and (x - 1) 0) mask mask or x}// 取反mask mask.inv()// 取最低位 1 return mask and -mask}
}
复杂度分析
时间复杂度O(n)O(n)O(n) 其中 n 是数组长度空间复杂度O(1)O(1)O(1) 仅占用常数级别空间。 2569. 更新数组后处理求和查询Hard
题目地址
https://leetcode.cn/problems/handling-sum-queries-after-update/
题目描述
给你两个下标从 0 开始的数组 nums1 和 nums2 和一个二维数组 queries 表示一些操作。总共有 3 种类型的操作
操作类型 1 为 queries[i] [1, l, r] 。你需要将 nums1 从下标 l 到下标 r 的所有 0 反转成 1 或将 1 反转成 0 。l 和 r 下标都从 0 开始。操作类型 2 为 queries[i] [2, p, 0] 。对于 0 i n 中的所有下标令 nums2[i] nums2[i] nums1[i] * p 。操作类型 3 为 queries[i] [3, 0, 0] 。求 nums2 中所有元素的和。
请你返回一个数组包含所有第三种操作类型的答案。
预备知识
类似的区间求和问题我们先回顾一下解决方案
1、静态数组求区间和「前缀和数组」、「树状数组」、「线段树」2、频繁单点更新求区间和「树状数组」、「线段树」3、频繁区间更新求具体位置「差分数组」4、频繁区间更新求区间和「线段树 懒更新」
这道题涉及 “区间更新” 和 “区间求和”所以属于线段树的典型例题。
题解一朴素线段树
我们先理解题目中三种操作的含义
操作一对 nums1 数组中位于 [left, right] 区间的数进行反转也就是进行 “区间更新”操作二将 nums1 数组上的数值 nums1[index] 乘以 p 后累加到 nums2 数组的相同位置上即 nums2[index] nums1[index] * p同样也是进行 “区间更新”操作三求 nums2 数组中所有元素和即 “求区间和”。
OK既然操作一和操作二是对不同数组进行 “区间更新”那么我们需要分别为这两个数组建立线段树吗并不需要这是题目抛出的烟雾弹。
因为题目最终的解是求 nums2 数组的全体和所以我们并不需要真正地维护 nums2 数组只需要将操作二的增量累加到全体和中。这样的话就是只需要维护 nums1 数组的线段树。
理解题意后我们可以写出题解的主框架
1、首先计算 nums2 数组的初始全体和 sum2、建立 nums1 数组的线段树3、依次处理每种操作操作一对线段树做区间更新操作二对线段树做区间求和后乘以 p并累加到全体和 sum 中操作三将 sum 推入结果列表。
// 程序主框架
class Solution {fun handleQuery(nums1: IntArray, nums2: IntArray, queries: ArrayIntArray): LongArray {val n nums1.sizeval resultList LinkedListLong()// 全体和var sum 0Lfor (num in nums2) {sum num}val tree SegementTree(nums1)for (query in queries) {when (query[0]) {1 - {// 区间更新tree.update(query[1], query[2])}2 - {// 求区间和nums[index] * psum 1L * query[1] * tree.query(0, n - 1)}3 - {// 记录resultList.add(sum)}}}return resultList.toLongArray()}private class SegementTree(private val data: IntArray) {// 区间更新反转fun update(left: Int, right: Int) {}// 单点更新反转- 本题不需要fun set(pos: Int) {}// 区间查询fun query(left: Int, right: Int): Int {}}
}接下来就是实现线段树的内部代码了。
技巧 1这道题的更新操作是对 0/ 1 反转我们可以用异或来实现技巧 2相对于在函数中重复传递节点所代表的区间范围例如 update(i: int, l: int, r: int, L: int, R: int)使用 Node 节点记录更为方便。
class Solution {fun handleQuery(nums1: IntArray, nums2: IntArray, queries: ArrayIntArray): LongArray {val n nums1.sizeval resultList LinkedListLong()// 全体和var sum 0Lfor (num in nums2) {sum num}val tree SegementTree(nums1)for (query in queries) {when (query[0]) {1 - {// 区间更新tree.update(query[1], query[2])}2 - {// 求区间和nums[index] * psum 1L * query[1] * tree.query(0, n - 1)}3 - {// 记录resultList.add(sum)}}}return resultList.toLongArray()}private class SegementTree(private val data: IntArray) {// 线段树节点区间范围与区间值private class Node(val left: Int, val right: Int, var value: Int)// 线段树数组private val tree ArrayNode?(4 * data.size) { null } as ArrayNode// 左子节点的索引private val Int.left get() this * 2 1// 右子节点的索引private val Int.right get() this * 2 2init {// 建树buildNode(0, 0, data.size - 1)}// 构建线段树节点private fun buildNode(index: Int, left: Int, right: Int) {if (left right) {// 叶子节点tree[index] Node(left, right, data[left])return}val mid (left right) ushr 1// 构建左子节点buildNode(index.left, left, mid)// 构建左子节点buildNode(index.right, mid 1, right)// 合并左右子节点tree[index] Node(left, right, tree[index.left].value tree[index.right].value)}// 区间更新反转fun update(left: Int, right: Int) {update(0, left, right)}// 区间更新反转private fun update(index: Int, left: Int, right: Int) {// 1、当前节点不处于区间范围内if (tree[index].left right || tree[index].right left) return// 2、叶子节点if (tree[index].left tree[index].right) {// 反转0-1,1-0tree[index].value tree[index].value xor 1return}// 3、更新左子树update(index.left, left, right)// 4、更新右子树update(index.right, left, right)// 5、合并子节点的结果tree[index].value tree[index.left].value tree[index.right].value}// 单点更新反转- 本题不需要fun set(pos: Int) {set(0, pos)}// 单点更新反转- 本题不需要private fun set(index: Int, pos: Int) {// 1、当前节点不处于区间范围内if (tree[index].left pos || tree[index].right pos) return// 2、叶子节点if (tree[index].left tree[index].right) {// 反转0-1,1-0tree[index].value tree[index].value xor 1return}// 3、更新左子树set(index.left, pos)// 4、更新右子树set(index.right, pos)// 5、合并子节点的结果tree[index].value tree[index.left].value tree[index.right].value}// 区间查询fun query(left: Int, right: Int): Int {return query(0, left, right)}// 区间查询private fun query(index: Int, left: Int, right: Int): Int {// 1、当前节点不处于区间范围内if (tree[index].left right || tree[index].right left) return 0// 2、当前节点完全处于区间范围之内if (tree[index].left left tree[index].right right) return tree[index].value// 3、合并子节点的结果return query(index.left, left, right) query(index.right, left, right)}}
}复杂度分析
时间复杂度O(nq1nq2)O(n q_1n q_2)O(nq1nq2) 其中 n 是 nums1 数组长度q1q_1q1 是操作一的个数q2q_2q2 是操作二的个数。我们需要花费 O(n)O(n)O(n) 时间建树操作一线段树区间更新的时间复杂度是 O(n)O(n)O(n)操作二线段树区间查询的复杂度是 O(lgn)O(lgn)O(lgn)但本题中的查询正好是线段树根节点所以操作二实际上只需要 O(1)O(1)O(1) 复杂度。空间复杂度O(n)O(n)O(n) 线段树空间。
朴素线段树解法在本题中会超时我们需要优化为 “懒更新” 的线段树实现。
题解二线段树 懒更新
朴素线段树的性能瓶颈在于区间更新需要改动从根节点到叶子节点中所有与目标区间有交集的节点因此单次区间更新操作的时间复杂度是 O(n)O(n)O(n)。
懒更新线段树的核心思想是当一个节点代表的区间完全包含于目标区间内时我们没有必要继续向下递归更新而是在当前节点上标记 Lazy Tag 。只有将来更新该节点的某个子区间时才会将懒更新 pushdown 到子区间。
举个例子在长度为 10 的线段树中执行 [1,10] 和 [1,5] 两次区间更新操作对区间内的元素加一
[1,10] 区间更新从根节点出发此时发现根节点与目标区间 [1,10] 完全相同那么只更新根节点并标记 Lazy Tag更新结束[1,5] 区间更新从根节点出发此时发现根节点有 Lazy Tag那么需要先将懒更新 pushdown 到 [1,5] 和 [6,10] 两个子节点然后再更新 [1,5] 区间。到目前为止[1,10] 和 [1,5] 节点被修改 2 次[6,10] 节点被修改 1 次其它节点没有被修改。
接下来就是实现线段树的内部代码了。
技巧 10 /1 反转是负负得正的所以 Lazy Tag 可以用 Boolean 类型表示true 表示被反转技巧 2区间反转可以用区间长度 - 旧值实现即value right - left 1 - value。
提示相比题解一改动的函数有 【懒更新】 标记 。
class Solution {fun handleQuery(nums1: IntArray, nums2: IntArray, queries: ArrayIntArray): LongArray {val n nums1.sizeval resultList LinkedListLong()// 全体和var sum 0Lfor (num in nums2) {sum num}val tree LazySegementTree(nums1)for (query in queries) {when (query[0]) {1 - {// 区间更新tree.update(query[1], query[2])}2 - {// 求区间和nums[index] * psum 1L * query[1] * tree.query(0, n - 1)}3 - {// 记录resultList.add(sum)}}}return resultList.toLongArray()}private class LazySegementTree(private val data: IntArray) {// 线段树节点区间范围与区间值【懒更新】private class Node(val left: Int, val right: Int, var value: Int, var lazy: Boolean false)// 线段树数组private val tree ArrayNode?(4 * data.size) { null } as ArrayNode// 左子节点的索引private val Int.left get() this * 2 1// 右子节点的索引private val Int.right get() this * 2 2init {// 建树buildNode(0, 0, data.size - 1)}// 构建线段树节点private fun buildNode(index: Int, left: Int, right: Int) {if (left right) {// 叶子节点tree[index] Node(left, right, data[left])return}val mid (left right) ushr 1// 构建左子节点buildNode(index.left, left, mid)// 构建左子节点buildNode(index.right, mid 1, right)// 合并左右子节点tree[index] Node(left, right, tree[index.left].value tree[index.right].value)}// 区间更新反转fun update(left: Int, right: Int) {update(0, left, right)}// 区间更新反转【懒更新】private fun update(index: Int, left: Int, right: Int) {// 1、当前节点不处于区间范围内if (tree[index].left right || tree[index].right left) return// 2、当前节点完全处于区间范围之内if (tree[index].left left tree[index].right right) {lazyUpdate(index)return}// 3、pushdown 到子节点if (tree[index].lazy) {lazyUpdate(index.left)lazyUpdate(index.right)tree[index].lazy false}// 4、更新左子树update(index.left, left, right)// 5、更新右子树update(index.right, left, right)// 6、合并子节点的结果tree[index].value tree[index.left].value tree[index.right].value}// 单点更新反转- 本题不需要fun set(pos: Int) {set(0, pos)}// 单点更新反转【懒更新】- 本题不需要private fun set(index: Int, pos: Int) {// 1、当前节点不处于区间范围内if (tree[index].left pos || tree[index].right pos) return// 2、叶子节点if (tree[index].left tree[index].right) {lazyUpdate(index)return}// 3、pushdown 到子节点if (tree[index].lazy) {lazyUpdate(index.left)lazyUpdate(index.right)tree[index].lazy false}// 4、更新左子树set(index.left, pos)// 5、更新右子树set(index.right, pos)// 6、合并子节点的结果tree[index].value tree[index.left].value tree[index.right].value}// 区间查询fun query(left: Int, right: Int): Int {return query(0, left, right)}// 区间查询private fun query(index: Int, left: Int, right: Int): Int {// 1、当前节点不处于区间范围内if (tree[index].left right || tree[index].right left) return 0// 2、当前节点完全处于区间范围之内if (tree[index].left left tree[index].right right) return tree[index].value// 3、pushdown 到子节点if (tree[index].lazy) {lazyUpdate(index.left)lazyUpdate(index.right)tree[index].lazy false}// 4、合并子节点的结果return query(index.left, left, right) query(index.right, left, right)}// 懒更新private fun lazyUpdate(index: Int) {// 反转tree[index].value tree[index].right - tree[index].left 1 - tree[index].value// 标记负负得正tree[index].lazy !tree[index].lazy}}
}复杂度分析
时间复杂度O(nq1lgnq2)O(n q_1lgn q_2)O(nq1lgnq2) 其中 n 是 nums1 数组长度q1q_1q1 是操作一的个数q2q_2q2 是操作二的个数。空间复杂度O(n)O(n)O(n) 线段树空间。
