赞
踩
本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。
大家好,我是小彭。
昨晚是 LeetCode 第 98 场双周赛,你参加了吗?这场周赛需要脑筋急转弯,转不过来 Medium 就会变成 Hard,转得过来就变成 Easy。
https://leetcode.cn/problems/maximum-difference-by-remapping-a-digit/
给你一个整数 num
。你知道 Danny Mittal 会偷偷将 0
到 9
中的一个数字 替换 成另一个数字。
请你返回将 num
中 恰好一个 数字进行替换后,得到的最大值和最小值的差位多少。
注意:
d1
替换成另一个数字 d2
时,Danny 需要将 nums
中所有 d1
都替换成 d2
。num
可以不变。简单模拟题,有 2 个思路:
9
取得最大值,将其替换为 0
取得最小值,最后取所有方案的最大值和最小值取差值;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
}
}
复杂度分析:
// 思路 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
}
}
复杂度分析:
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 个元素的最小得分” 问题,最后再说。
这道题的关键在于得分的定义:
理解题意后容易发现:
因此得知: 这道题的关键点在于修改数组的最大值或最小值成为数组中间的某个元素。 要么让最大值变小,要么让最小值变大。由于题目最多只能修改 2 次,因此最多只能以下 3 种情况:
nums[n - 3]
;nums[2]
;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))
}
}
复杂度分析:
再扩展思考一下,如果题目说明最多可以修改 k ( 0 ≤ k ≤ n u m s . l e n g t h ) k (0 ≤ k ≤ nums.length) k(0≤k≤nums.length)次的话,应该解决问题呢? —— 即 “求最多修改 k 个元素的最小得分”,原题就是 k = 2 的情况。
那么这道题就是考察 “滑动窗口” 技巧了,我们可以将修改的范围视为一个跨越数组首尾且长度为 k 的滑动窗口,那么而问题的答案就取决于 “不被” 滑动窗口包围的另一部分。再逆向思考一下,我们可以用长度为 length - k
的滑动窗口在数组上移动,并记录窗口首尾元素的差值,枚举所有情况后记录最小值即为最小得分:
举个例子,在输入数组为 [1, 4, 5, 7, 8] ,k = 2
时,前文提到的 3 种方案分别对应以下 3 个窗口状态:
1,4 | 5,7,8 |
| 1,4,5 | 7,8
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
}
}
复杂度分析同上。
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
这道题需要脑筋急转弯。
首先,我们先观察输入数据范围中小数值的二进制表示,尝试发现规律:
我们发现以下 2 点信息:
由此可以得出结论: 影响数组最小可表达数的关键在于数组中 “未出现的最小的 2 i 2^i 2i”,并且这个数就是不可表达的最小非零数。
举例说明:假设 8
是数组中未出现的最小
2
i
2^i
2i(此时 [1, 2, 4]
肯定在数组中出现
2
i
2^i
2i),那么数字 1 ~ 7
之间的所有数字都可以由 [1、2、4]
通过或表示,而 8
无法被 [1, 2, 3, 4, 5, 6 ,7]
之间的任何数字表达,同时也无法被大于 8 的其他数表示,因此 8
就是最小的可表达数。
完成问题转换后编码就很容易了,我们只要从小到大枚举所有 2 i 2^i 2i ,并检查它是否在数组中出现即可:
class Solution {
fun minImpossibleOR(nums: IntArray): Int {
val numSet = nums.toHashSet()
var i = 1
while (numSet.contains(i)) {
i = i shl 1
}
return i
}
}
复杂度分析:
题解一使用散列表来辅助判断 2 i 2^i 2i 是否存在于数组中,可以进一步优化:我们将直接从数组元素的二进制数据中提取特征值,并还原出 “未出现的最小的 2 i 2^i 2i”:
0011, 1011
格式的特征值,此时 “未出现的最小的
2
i
2^i
2i” 正好位于从低位到高位出现的首个 0 的位置,即 0000, 0100
;x = ~x // 按位取反: 0011,1011 => 1100,0100
x & -x // lowbit 公式:1100,0100 => 0000,0100
class 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
}
}
复杂度分析:
https://leetcode.cn/problems/handling-sum-queries-after-update/
给你两个下标从 0 开始的数组 nums1
和 nums2
,和一个二维数组 queries
表示一些操作。总共有 3 种类型的操作:
queries[i] = [1, l, r]
。你需要将 nums1
从下标 l
到下标 r
的所有 0
反转成 1
或将 1
反转成 0
。l
和 r
下标都从 0 开始。queries[i] = [2, p, 0]
。对于 0 <= i < n
中的所有下标,令 nums2[i] = nums2[i] + nums1[i] * p
。queries[i] = [3, 0, 0]
。求 nums2
中所有元素的和。请你返回一个数组,包含所有第三种操作类型的答案。
类似的区间求和问题,我们先回顾一下解决方案:
这道题涉及 “区间更新” 和 “区间求和”,所以属于线段树的典型例题。
我们先理解题目中三种操作的含义:
nums1
数组中位于 [left, right]
区间的数进行反转,也就是进行 “区间更新”;nums1
数组上的数值 nums1[index]
乘以 p
后累加到 nums2
数组的相同位置上,即 nums2[index] += nums1[index] * p
,同样也是进行 “区间更新”;nums2
数组中所有元素和,即 “求区间和”。OK,既然操作一和操作二是对不同数组进行 “区间更新”,那么我们需要分别为这两个数组建立线段树吗?并不需要,这是题目抛出的烟雾弹。
因为题目最终的解是求 nums2
数组的全体和,所以我们并不需要真正地维护 nums2
数组,只需要将操作二的增量累加到全体和中。这样的话就是只需要维护 nums1
数组的线段树。
理解题意后,我们可以写出题解的主框架:
nums2
数组的初始全体和 sum
;nums1
数组的线段树;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 {
}
}
}
接下来就是实现线段树的内部代码了。
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 ) 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 次,其它节点没有被修改。接下来就是实现线段树的内部代码了。
Boolean
类型表示,true
表示被反转;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
}
}
}
复杂度分析:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。