我正在参与「启航计划」

大家好，我是小彭。

昨晚是 LeetCode 第 98 场双周赛，你参与了吗？这场周赛需求脑筋急转弯，转不过来 Medium 就会变成 Hard，转得过来就变成 Easy。

小彭的 Android 沟通群 02 群现已树立啦，大众号回复 “加群” 参加咱们~

LeetCode 双周赛 98，脑筋急转弯转不过来！

LeetCode 双周赛 98，脑筋急转弯转不过来！

2566. 替换一个数字后的最大差值（Easy）

标题地址

leetcode.cn/problems/ma…

标题描绘

给你一个整数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(log2 num)O(log^2\,{num}) 数字最多有 log num 位，外层循环与内存循环的字符串替换操作都是 O(log num)O(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)O(log\,{num}) 等级的时刻复杂度；
  • 空间复杂度：O(log num)O(log\,{num}) 字符串占用空间。

2567. 修正两个元素的最小分数（Medium)

标题地址

leetcode.cn/problems/mi…

标题描绘

给你一个下标从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)O(nlgn) 快速排序占用的时刻，假如手动保护最小的 3 个元素和最大的 3 个元素能够降低到 O(n)O(n) 时刻复杂度；
  • 空间复杂度：O(lgn)O(lgn) 排序占用的递归栈空间。

再扩展考虑一下，假如标题说明最多能够修正 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：修正数组中最大的两个数：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）

标题地址

leetcode.cn/problems/mi…

标题描绘

给你一个下标从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=2i∣2j∣2kx = 2^i | 2^j | 2^ k 的格局表达（很简单了解）；
  • 2i2^i 格局的数字不行能被其他数用 “或” 的形式表明（也很简单了解）。

由此能够得出结论： 影响数组最小可表达数的要害在于数组中 “未呈现的最小的 2i2^i”，并且这个数便是不行表达的最小非零数。

举例说明：假设 8 是数组中未呈现的最小 2i2^i（此刻 [1, 2, 4] 必定在数组中呈现2i2^i），那么数字 1 ~ 7 之间的一切数字都能够由 [1、2、4] 通过或表明，而 8 无法被 [1, 2, 3, 4, 5, 6 ,7] 之间的任何数字表达，一起也无法被大于 8 的其他数表明，因而 8 便是最小的可表达数。

完结问题转化后编码就很简单了，咱们只需从小到大枚举一切 2i2^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)O(n + logU) 其间 n 是数组长度，U 是数组的最大值，最多只需求查看 logU 位数字；
  • 空间复杂度：O(n)O(n) 散列表占用的空间。

题解二（位运算）

题解一运用散列表来辅佐判断 2i2^i 是否存在于数组中，能够进一步优化：咱们将直接从数组元素的二进制数据中提取特征值，并复原出 “未呈现的最小的 2i2^i”：

  • 1、遍历数组中一切元素，假如元素值是 2i2^i 则将其记载到 mask 特征值中；
  • 2、遍历结束后将得到形如 0011, 1011 格局的特征值，此刻 “未呈现的最小的 2i2^i” 正好位于从低位到高位呈现的首个 0 的方位，即 0000, 0100;
  • 3、为了复原出方针数，履行以下位运算：
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
    }
}

复杂度剖析：

  • 时刻复杂度：O(n)O(n) 其间 n 是数组长度；
  • 空间复杂度：O(1)O(1) 仅占用常数等级空间。

2569. 更新数组后处理求和查询（Hard）

标题地址

leetcode.cn/problems/ha…

标题描绘

给你两个下标从0开端的数组nums1和nums2，和一个二维数组queries表明一些操作。总共有 3 种类型的操作：

  1. 操作类型 1 为queries[i]= [1, l, r]。你需求将nums1从下标l到下标r的一切0回转成1或将1回转成0。l和r下标都从0开端。
  2. 操作类型 2 为queries[i]= [2, p, 0]。对于0 <= i < n中的一切下标，令nums2[i] =nums2[i]+ nums1[i]* p。
  3. 操作类型 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+q1n+q2)O(n + q_1n + q_2) 其间 n 是 nums1 数组长度，q1q_1 是操作一的个数，q2q_2 是操作二的个数。咱们需求花费 O(n)O(n) 时刻建树，操作一线段树区间更新的时刻复杂度是 O(n)O(n)，操作二线段树区间查询的复杂度是 O(lgn)O(lgn)，但本题中的查询正好是线段树根节点，所以操作二实际上只需求 O(1)O(1) 复杂度。
  • 空间复杂度：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 次，其它节点没有被修正。

接下来便是完成线段树的内部代码了。

  • 技巧 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+q1lgn+q2)O(n + q_1lgn + q_2) 其间 n 是 nums1 数组长度，q1q_1 是操作一的个数，q2q_2 是操作二的个数。
  • 空间复杂度：O(n)O(n) 线段树空间。

咱们下周见，有用请点赞关注！

本文已收录到 AndroidFamily，技能和职场问题，请关注大众号 [彭旭锐] 发问。

LeetCode 双周赛 98，脑筋急转弯转不过来！