本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。
大家好，我是小彭。
昨晚是 LeetCode 第 98 场双周赛，你加入了吗？这场周赛须要脑筋急转弯，转不过去 Medium 就会变成 Hard，转得过去就变成 Easy。
小彭的 Android 交换群 02 群曾经建设啦，公众号回复“加群”退出咱们~
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 = "$num"
var max = num
var min = num
for (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(log^2\,{num})$ 数字最多有 log num 位，外层循环与内存循环的字符串替换操作都是 $O(log\,{num})$ 工夫级别复杂度；
- 空间复杂度：$O(log\,{num})$ 字符串占用空间。
// 思路 2
class Solution {fun minMaxDifference(num: Int): Int {
val numStr = "$num"
val min = numStr.replace(numStr[0], '0').toInt()
var max = num
for (element in numStr) {if ('9' != element) {max = numStr.replace(element, '9').toInt()
break
}
}
return max - min
}
}复杂度剖析：
- 工夫复杂度：$O(log\,{num})$ 内存循环的字符串替换操作最多只会执行一次，均摊下来整体只有 $O(log\,{num})$ 级别的工夫复杂度；
- 空间复杂度：$O(log\,{num})$ 字符串占用空间。
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.size
val 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)$ 疾速排序占用的工夫，如果手动保护最小的 3 个元素和最大的 3 个元素能够升高到 $O(n)$ 工夫复杂度；
- 空间复杂度：$O(lgn)$ 排序占用的递归栈空间。
再扩大思考一下，如果题目阐明最多能够批改 $k（0 ≤ 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 - k
nums.sort()
var min = Integer.MAX_VALUE
for (left in 0..n - len) {
val right = left + len - 1
min = 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 = 0
- 1 = 0001 = 1
- 2 = 0010 = 2
- 3 = 0011 = 2 | 1
- 4 = 0100 = 4
- 5 = 0101 = 4 | 1
- 6 = 0110 = 4 | 2
- 7 = 0111 = 4 | 2 | 1，或者 5 | 1
- 8 = 1000 = 8
- 9 = 1001 = 8 | 1
- 10 = 1010 = 8 | 2
咱们发现以下 2 点信息：
- 除了数字 7 = 5 | 1 的非凡计划外，其余数字的示意计划都能够由形如 $x = 2^i | 2^j | 2^ k$ 的格局表白（很容易了解）；
- $2^i$ 格局的数字不可能被其余数用“或”的模式示意（也很容易了解）。
由此能够得出结论：影响数组最小可表白数的关键在于数组中“未呈现的最小的 $2^i$”，并且这个数就是不可表白的最小非零数。
举例说明：假如 8 是数组中未呈现的最小 $2^i$（此时 [1, 2, 4] 必定在数组中呈现 $2^i$），那么数字 1 ~ 7 之间的所有数字都能够由 [1、2、4] 通过或示意，而 8 无奈被 [1, 2, 3, 4, 5, 6 ,7] 之间的任何数字表白，同时也无奈被大于 8 的其余数示意，因而 8 就是最小的可表白数。
实现问题转换后编码就很容易了，咱们只有从小到大枚举所有 $2^i$，并查看它是否在数组中呈现即可：
class Solution {fun minImpossibleOR(nums: IntArray): Int {val numSet = nums.toHashSet()
var i = 1
while (numSet.contains(i)) {i = i shl 1}
return i
}
}复杂度剖析：
- 工夫复杂度：$O(n + logU)$ 其中 n 是数组长度，U 是数组的最大值，最多只须要查看 logU 位数字；
- 空间复杂度：$O(n)$ 散列表占用的空间。
题解二（位运算）
题解一应用散列表来辅助判断 $2^i$ 是否存在于数组中，能够进一步优化：咱们将间接从数组元素的二进制数据中提取特征值，并还原出“未呈现的最小的 $2^i$”：
- 1、遍历数组中所有元素，如果元素值是 $2^i$ 则将其记录到 mask 特征值中；
- 2、遍历完结后将失去形如
0011, 1011格局的特征值，此时“未呈现的最小的 $2^i$”正好位于从低位到高位呈现的首个 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 = 0
for (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)$ 其中 n 是数组长度；
- 空间复杂度：$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数组的初始整体和sum； - 2、建设
nums1数组的线段树； - 3、顺次解决每种操作，操作一对线段树做区间更新，操作二对线段树做区间求和后乘以
p，并累加到整体和sum中，操作三将sum推入后果列表。
// 程序主框架
class Solution {fun handleQuery(nums1: IntArray, nums2: IntArray, queries: Array<IntArray>): LongArray {
val n = nums1.size
val resultList = LinkedList<Long>()
// 整体和
var sum = 0L
for (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] * p）sum += 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: Array<IntArray>): LongArray {
val n = nums1.size
val resultList = LinkedList<Long>()
// 整体和
var sum = 0L
for (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] * p）sum += 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 = Array<Node?>(4 * data.size) {null} as Array<Node>
// 左子节点的索引
private val Int.left get() = this * 2 + 1
// 右子节点的索引
private val Int.right get() = this * 2 + 2
init {
// 建树
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->0
tree[index].value = tree[index].value xor 1
return
}
// 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->0
tree[index].value = tree[index].value xor 1
return
}
// 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(n + q_1n + q_2)$ 其中 n 是 nums1 数组长度，$q_1$ 是操作一的个数，$q_2$ 是操作二的个数。咱们须要破费 $O(n)$ 工夫建树，操作一线段树区间更新的工夫复杂度是 $O(n)$，操作二线段树区间查问的复杂度是 $O(lgn)$，但本题中的查问正好是线段树根节点，所以操作二实际上只须要 $O(1)$ 复杂度。
- 空间复杂度：$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 次，其它节点没有被批改。
接下来就是实现线段树的外部代码了。
- 技巧 1：0 /1 反转是负负得正的，所以 Lazy Tag 能够用
Boolean类型示意，true示意被反转； - 技巧 2：区间反转能够用区间长度 – 旧值实现，即：
value = right - left + 1 - value。
提醒：相比题解一改变的函数有【懒更新】标记。
class Solution {fun handleQuery(nums1: IntArray, nums2: IntArray, queries: Array<IntArray>): LongArray {
val n = nums1.size
val resultList = LinkedList<Long>()
// 整体和
var sum = 0L
for (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] * p）sum += 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 = Array<Node?>(4 * data.size) {null} as Array<Node>
// 左子节点的索引
private val Int.left get() = this * 2 + 1
// 右子节点的索引
private val Int.right get() = this * 2 + 2
init {
// 建树
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(n + q_1lgn + q_2)$ 其中 n 是 nums1 数组长度，$q_1$ 是操作一的个数，$q_2$ 是操作二的个数。
- 空间复杂度：$O(n)$ 线段树空间。