乐趣区

关于android:LeetCode-双周赛-10320230429区间求和的树状数组经典应用

jiezi

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

大家好，我是小彭。

这场周赛是 LeetCode 双周赛第 103 场，难得在五一假期第一天打周赛的人数也没有少太多。这场较量前 3 题比较简单，咱们把篇幅留给最初一题。

往期周赛回顾：LeetCode 单周赛第 342 场 · 容斥原理、计数排序、滑动窗口、子数组 GCB

周赛概览

Q1. K 个元素的最大和（Easy）

简略模拟题，不过多解说。

Q2. 找到两个数组的前缀公共数组（Medium）

简略模拟题，在计数的实现上有三种解法：

  • 解法 1：散列表 $O(n)$ 空间复杂度
  • 解法 2：技数数组 $O(n)$ 空间复杂度
  • 解法 3：状态压缩 $O(1)$ 空间复杂度

Q3. 网格图中鱼的最大数目（Hard）

这道题的难度标签是认真的吗？打 Medium 都过分了竟然打 Hard？

  • 解法 1：BFS / DFS $O(nm)$
  • 解法 2：并查集 $O(nm)$

Q4. 将数组清空（Hard）

这道题的难点在于如何想到以及正确地将原问题转换为区间求和问题，思路想分明后用树状数组实现。

  • 解法 1：树状数组 + 索引数组 $O(nlgn)$
  • 解法 2：树状数组 + 最小堆 $O(nlgn)$

Q1. K 个元素的最大和（Easy）

https://leetcode.cn/problems/maximum-sum-with-exactly-k-elements/

题目形容

给你一个下标从 0 开始的整数数组 nums 和一个整数 k。你须要执行以下操作 恰好 k 次，最大化你的得分：

  1. 从 nums 中抉择一个元素 m。
  2. 将选中的元素 m 从数组中删除。
  3. 将新元素 m + 1 增加到数组中。
  4. 你的得分减少 m。

请你返回执行以上操作恰好 k 次后的最大得分。

示例 1：

输出：nums = [1,2,3,4,5], k = 3
输入：18
解释：咱们须要从 nums 中恰好抉择 3 个元素并最大化得分。第一次抉择 5。和为 5，nums = [1,2,3,4,6]。第二次抉择 6。和为 6，nums = [1,2,3,4,7]。第三次抉择 7。和为 5 + 6 + 7 = 18，nums = [1,2,3,4,8]。所以咱们返回 18。18 是能够失去的最大答案。

示例 2：

输出：nums = [5,5,5], k = 2
输入：11
解释：咱们须要从 nums 中恰好抉择 2 个元素并最大化得分。第一次抉择 5。和为 5，nums = [5,5,6]。第二次抉择 6。和为 6，nums = [5,5,7]。所以咱们返回 11。11 是能够失去的最大答案。

提醒：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= 100

准备常识 – 等差数列求和

  • 等差数列求和公式：(首项 + 尾项) * 项数 / 2

题解（模仿 + 贪婪）

显然第一次操作的分数会抉择数组中的最大值 max，后续操作是以 max 为首项的等差数列，间接应用等差数列求和公式即可。

class Solution {fun maximizeSum(nums: IntArray, k: Int): Int {val max = Arrays.stream(nums).max().getAsInt()
        return (max + max + k - 1) * k / 2
    }
}

复杂度剖析：

  • 工夫复杂度：$O(n)$ 其中 n 是 nums 数组的长度；
  • 空间复杂度：$O(1)$

Q2. 找到两个数组的前缀公共数组（Medium）

https://leetcode.cn/problems/find-the-prefix-common-array-of-two-arrays/

题目形容

给你两个下标从 0 开始长度为 n 的整数排列 A 和 B。

A 和 B 的 前缀公共数组 定义为数组 C，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。

请你返回 A 和 B 的 前缀公共数组。

如果一个长度为 n 的数组蕴含 1 到 n 的元素恰好一次，咱们称这个数组是一个长度为 n 的 排列。

示例 1：

输出：A = [1,3,2,4], B = [3,1,2,4]
输入：[0,2,3,4]
解释：i = 0：没有公共元素，所以 C[0] = 0。i = 1：1 和 3 是两个数组的前缀公共元素，所以 C[1] = 2。i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3。i = 3：1，2，3 和 4 是两个数组的前缀公共元素，所以 C[3] = 4。

示例 2：

输出：A = [2,3,1], B = [3,1,2]
输入：[0,1,3]
解释：i = 0：没有公共元素，所以 C[0] = 0。i = 1：只有 3 是公共元素，所以 C[1] = 1。i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3。

提醒：

  • 1 <= A.length == B.length == n <= 50
  • 1 <= A[i], B[i] <= n
  • 题目保障 A 和 B 两个数组都是 n 个元素的排列。

题解一（散列表）

从左到右遍历数组，并应用散列表记录拜访过的元素，以及两个数组交加：

class Solution {fun findThePrefixCommonArray(A: IntArray, B: IntArray): IntArray {
        val n = A.size
        val ret = IntArray(n)
        val setA = HashSet<Int>()
        val setB = HashSet<Int>()
        val interSet = HashSet<Int>()
        for (i in 0 until n) {setA.add(A[i])
            setB.add(B[i])
            if (setB.contains(A[i])) interSet.add(A[i])
            if (setA.contains(B[i])) interSet.add(B[i])
            ret[i] = interSet.size
        }
        return ret
    }
}

复杂度剖析：

  • 工夫复杂度：$O(n)$ 其中 n 是 nums 数组的长度；
  • 空间复杂度：$O(n)$ 散列表空间。

题解二（计数数组）

题解一须要应用多倍空间，咱们发现 A 和 B 都是 n 的排列，当拜访到的元素 nums[i] 呈现 2 次时就必然处于数组交集中。因而，咱们不须要应用散列表记录拜访过的元素，而只须要记录每个元素呈现的次数。

class Solution {fun findThePrefixCommonArray(A: IntArray, B: IntArray): IntArray {
        val n = A.size
        val ret = IntArray(n)
        val cnt = IntArray(n + 1)
        var size = 0
        for (i in 0 until n) {if (++cnt[A[i]] == 2) size ++
            if (++cnt[B[i]] == 2) size ++
            ret[i] = size
        }
        return ret
    }
}

复杂度剖析：

  • 工夫复杂度：$O(n)$ 其中 n 是 nums 数组的长度；
  • 空间复杂度：$O(n)$ 计数数组空间；

题解三（状态压缩）

既然 A 和 B 的元素值不超过 50，咱们能够应用两个 Long 变量代替散列表优化空间复杂度。

class Solution {fun findThePrefixCommonArray(A: IntArray, B: IntArray): IntArray {
        val n = A.size
        val ret = IntArray(n)
        var flagA = 0L
        var flagB = 0L
        var size = 0
        for (i in 0 until n) {flagA = flagA or (1L shl A[i])
            flagB = flagB or (1L shl B[i])
            // Kotlin 1.5 才有 Long.countOneBits()
            // ret[i] = (flagA and flagB).countOneBits()
            ret[i] = java.lang.Long.bitCount(flagA and flagB)
        }
        return ret
    }
}

复杂度剖析：

  • 工夫复杂度：$O(n)$ 其中 n 是 nums 数组的长度；
  • 空间复杂度：$O(1)$ 仅应用常量级别空间；

Q3. 网格图中鱼的最大数目（Hard）

https://leetcode.cn/problems/maximum-number-of-fish-in-a-grid/description/

题目形容

给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid，其中下标在 (r, c) 处的整数示意：

  • 如果 grid[r] = 0，那么它是一块 海洋。
  • 如果 grid[r] > 0，那么它是一块 水域，且蕴含 grid[r] 条鱼。

一位渔夫能够从任意 水域 格子 (r, c) 登程，而后执行以下操作任意次：

  • 捕捞格子 (r, c) 处所有的鱼，或者
  • 挪动到相邻的 水域 格子。

请你返回渔夫最优策略下，最多 能够捕捞多少条鱼。如果没有水域格子，请你返回 0。

格子 (r, c) 相邻 的格子为 (r, c + 1)，(r, c - 1)，(r + 1, c) 和 (r - 1, c)，前提是相邻格子在网格图内。

示例 1：

输出：grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
输入：7
解释：渔夫能够从格子(1,3) 登程，捕捞 3 条鱼，而后挪动到格子(2,3)，捕捞 4 条鱼。

示例 2：

输出：grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
输入：1
解释：渔夫能够从格子 (0,0) 或者 (3,3)，捕捞 1 条鱼。

提醒：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • 0 <= grid[i][j] <= 10

问题形象

求“加权连通重量 / 岛屿问题”，用二维 BFS 或 DFS 或并查集都能够求出所有连通块的最大值，史上最水 Hard 题。

题解一（二维 DFS）

class Solution {private val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))

    fun findMaxFish(grid: Array<IntArray>): Int {
        var ret = 0
        for (i in 0 until grid.size) {for (j in 0 until grid[0].size) {ret = Math.max(ret, dfs(grid, i, j))
            }
        }
        return ret
    }

    private fun dfs(grid: Array<IntArray>, i: Int, j: Int): Int {if (grid[i][j] <= 0) return 0
        var cur = grid[i][j]
        grid[i][j] = -1
        for (direction in directions) {val newI = i + direction[0]
            val newJ = j + direction[1]
            if (newI < 0 || newI >= grid.size || newJ < 0 || newJ >= grid[0].size || grid[newI][newJ] <= 0) continue
            cur += dfs(grid, newI, newJ)
        }
        return cur
    }
}

复杂度剖析：

  • 工夫复杂度：$O(n · m)$ 其中 n 和 m 是 grid 数组的行和列；
  • 空间复杂度：$O(n + m)$ 递归栈的最大深度。

题解二（并查集）

附赠一份并查集的解法：

class Solution {private val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))

    fun findMaxFish(grid: Array<IntArray>): Int {
        val n = grid.size
        val m = grid[0].size
        var ret = 0
        // 并查集
        val helper = UnionFind(grid)
        // 合并
        for (i in 0 until n) {for (j in 0 until m) {ret = Math.max(ret, grid[i][j])
                if (grid[i][j] <= 0) continue
                for (direction in directions) {val newI = i + direction[0]
                    val newJ = j + direction[1]
                    if (newI < 0 || newI >= grid.size || newJ < 0 || newJ >= grid[0].size || grid[newI][newJ] <= 0) continue
                    ret = Math.max(ret, helper.union(i * m + j, newI * m + newJ))
                }
            }
        }
        // helper.print()
        return ret
    }

    private class UnionFind(private val grid: Array<IntArray>) {

        private val n = grid.size
        private val m = grid[0].size

        // 父节点
        private val parent = IntArray(n * m) {it}
        // 高度
        private val rank = IntArray(n * m)
        // 数值
        private val value = IntArray(n * m)

        init {for (i in 0 until n) {for (j in 0 until m) {value[i * m + j] = grid[i][j]
                }
            }
        }

        // return 子集的和
        fun union(x: Int, y: Int): Int {
            // 按秩合并
            val parentX = find(x)
            val parentY = find(y)
            if (parentX == parentY) return value[parentY]
            if (rank[parentX] < rank[parentY]) {parent[parentX] = parentY
                value[parentY] += value[parentX]
                return value[parentY]
            } else if (rank[parentY] < rank[parentX]) {parent[parentY] = parentX
                value[parentX] += value[parentY]
                return value[parentX]
            } else {parent[parentY] = parentX
                value[parentX] += value[parentY]
                rank[parentY]++
                return value[parentX]
            }
        }

        fun print() {println("parent=${parent.joinToString()}")
            println("rank=${rank.joinToString()}")
            println("value=${value.joinToString()}")
        }

        private fun find(i: Int): Int {
            // 门路压缩
            var x = i
            while (parent[x] != x) {parent[x] = parent[parent[x]]
                x = parent[x]
            }
            return x
        }
    }
}

复杂度剖析：

  • 工夫复杂度：$O(n · m)$ 其中 n 和 m 是 grid 数组的行和列；
  • 空间复杂度：$O(n + m)$ 递归栈的最大深度。

类似题目：

  • 130. 被围绕的区域
  • 200. 岛屿数量
  • 990. 等式方程的可满足性

举荐浏览：

  • 如何应用并查集解决朋友圈问题？

Q4. 将数组清空（Hard）

https://leetcode.cn/problems/make-array-empty/

题目形容

给你一个蕴含若干 互不雷同  整数的数组 nums，你须要执行以下操作  直到数组为空：

  • 如果数组中第一个元素是以后数组中的 最小值，则删除它。
  • 否则，将第一个元素挪动到数组的 开端。

请你返回须要多少个操作使 nums 为空。

示例 1：

输出：nums = [3,4,-1]
输入：5
Operation Array
1 [4, -1, 3]
2 [-1, 3, 4]
3 [3, 4]
4 [4]
5 []

示例 2：

输出：nums = [1,2,4,3]
输入：5
Operation Array
1 [2, 4, 3]
2 [4, 3]
3 [3, 4]
4 [4]
5 []

示例 3：

输出：nums = [1,2,3]
输入：3
Operation Array
1 [2, 3]
2 [3]
3 []

提醒：

  • 1 <= nums.length <= 105
  • 109 <= nums[i] <= 109
  • nums 中的元素 互不雷同。

准备常识 – 循环数组

循环数组：将数组尾部元素的后继视为数组首部元素，数组首部元素的前驱视为数组尾部元素。

准备常识 – 树状数组

OI · 树状数组

树状数组也叫二叉索引树（Binary Indexed Tree），是一种反对“单点批改”和“区间查问”的代码量少的数据结构。相比于线段树来说，树状数组的代码量远远更少，是一种精妙的数据结构。

树状数组核心思想是将数组 [0,x] 的前缀和拆分为不多于 logx 段非重叠的区间，在计算前缀和时只须要合并 logx 段区间信息，而不须要合并 n 个区间信息。同时，在更新单点值时，也仅须要批改 logx 段区间，而不须要（像前缀和数组）那样批改 n 个信息。能够说，树状数组均衡了单点批改和区间和查问的工夫复杂度：

  • 单点更新 add(index,val)：将序列第 index 位元素减少 val，工夫复杂度为 O(lgn)，同时对应于在逻辑树形构造上从小分块节点挪动到大分块节点的过程（批改元素会影响大分块节点（子节点）的值）；
  • 区间查问 prefixSum(index)：查问前 index 个元素的前缀和，工夫复杂度为 O(lgn)，同时对应于在逻辑树形构造上累加区间段的过程。

树状数组

问题结构化

1、概括问题指标

求打消数组的操作次数。

2、剖析题目要件

  • 察看：在每次操作中，须要察看数组首部元素是否为残余元素中的最小值。例如序列 [3,2,1] 的首部元素不是最小值；
  • 打消：在每次操作中，如果数组首部元素是最小值，则能够打消数组头部元素。例序列 [1,2,3] 在一次操作后变为 [2,3]；
  • 挪动：在每次操作中，如果数组首部元素不是最小值，则须要将其挪动到数组开端。例如序列 [3,2,1] 在一次操作后变为 [2,1,3]。

3、察看数据特色

  • 数据量：测试用例的数据量上界为 10^5，这要求咱们实现低于 O(n^2) 工夫复杂度的算法能力通过；
  • 数据大小：测试用例的数据上下界为 [-10^9, 10^9]，这要求咱们思考大数问题。

4、察看测试用例

以序列 [3,4,-1] 为例，一共操作 5 次：

  • [3,4,-1]：-1 是最小值，将 3 和 4 挪动到开端后能力打消 -1，一共操作 3 次；
  • [3,4]：3 是最小值，打消 3 操作 1 次；
  • [4]：4 是最小值，打消 4 操作 1 次；

5、进步形象水平

  • 序列：线性表是由多个元素组成的序列，除了数组的头部和尾部元素之外，每个元素都有一个前驱元素和后继元素。在将数组首部元素挪动到数组开端时，将扭转数组中的局部元素的关系，即原首部元素的前驱变为原尾部元素，原尾部元素的后继变为原首部元素。
  • 是否为决策问题：因为每次操作的行为是固定的，因而这道题只是纯正的模仿问题，并不是决策问题。

6、具体化解决伎俩

打消操作须要依照元素值从小到大的程序删除，那么如何判断数组首部元素是否为最小值？

  • 伎俩 1（暴力枚举）：枚举数组残余元素，判断首部元素是否为最小值，单次判断的工夫复杂度是 O(n)；
  • 伎俩 2（排序）：对原始数组做预处理排序，因为原始数组的元素程序信息在本问题中是至关重要的，所以不能对原始数组做原地排序，须要借助辅助数据结构，例如索引数组、最小堆，单次判断的均摊工夫复杂度是 O(1)。

如何示意元素的挪动操作：

  • 伎俩 1（数组）：应用数组块状复制 Arrays.copy()，单次操作的工夫复杂度是 O(n)；
  • 伎俩 2（双向链表）：将原始数组转换为双向链表，操作链表首尾元素的工夫复杂度是 O(1)，但会耗费更多空间；

如何解决问题：

  • 伎俩 1（模仿）：模仿打消和挪动操作，直到数组为空。在最坏状况下（降序数组）须要操作 n^2 次，因而无论如何都是无奈满足题目的数据量要求；

至此，问题陷入瓶颈。

解决办法是反复「剖析问题要件」-「具体化解决伎俩」的过程，枚举把握的算法、数据结构和 Tricks 寻找突破口：

示意元素的挪动操作的新伎俩：

  • 伎俩 3（循环数组）：将原数组视为循环数组，数组尾部元素的后继是数组首部元素，数组首部元素的前驱是数组尾部元素，不再须要实际性的挪动操作。

解决问题的新伎俩：

  • 伎俩 2（计数）：察看测试用例发现，打消每个元素的操作次数取决于该元素的前驱中未被打消的元素个数，例如序列 [3,4,-1] 中 -1 前有 2 个元素未被删除，所以须要 2 次操作挪动 3 和 4，再减少一次操作打消 -1。那么，咱们能够定义 rangeSum(i,j) 示意区间 [i,j] 中未被删除的元素个数，每次打消操作只须要查问上一次的打消地位（上一个最小值）与以后的打消地位（以后的最小值）两头有多少个数字未被打消 rangeSum(上一个最小值地位, 以后的最小值地位)，这个区间和就是打消以后元素须要的操作次数。

辨别上次地位与以后地位的前后关系，须要分类探讨：

  • id < preId：打消次数 = rangeSum(id, preId)
  • id > preId：打消次数 = rangeSum(-1, id) + rangeSum(preId,n – 1)

如何实现伎俩 2（计数）：

在代码实现上，波及到「区间求和」和「单点更新」能够用线段数和树状数组实现。树状数组的代码量远比线段树少，所以咱们抉择后者。

示意图

答疑：

  • 打消每个元素的操作次数不必思考前驱元素中小于以后元素的元素吗？

因为打消是依照元素值从小到大的程序打消的，所以未被打消的元素肯定比以后元素大，所以咱们不强调元素大小关系。

题解一（树状数组 + 索引数组）

  • 应用「树状数组」的伎俩解决区间和查问和单点更新问题，留神树状数组是 base 1 的；
  • 应用「索引数组」的伎俩解决排序 / 最小值问题。
class Solution {fun countOperationsToEmptyArray(nums: IntArray): Long {
        val n = nums.size
        var ret = 0L
        // 索引数组
        val ids = Array<Int>(n) {it}
        // 排序
        Arrays.sort(ids) { i1, i2 ->
            // 思考大数问题
            // nums[i1] - nums[i2] x
            if (nums[i1] < nums[i2]) -1 else 1
        }
        // 树状数组
        val bst = BST(n)
        // 上一个被删除的索引
        var preId = -1
        // 遍历索引
        for (id in ids) {
            // 区间和
            if (id > preId) {ret += bst.rangeSum(preId, id)
                // println("id=$id, ${bst.rangeSum(preId, id)}")
            } else {ret += bst.rangeSum(-1, id) + bst.rangeSum(preId, n - 1)
                // println("id=$id, ${bst.rangeSum(-1,id)} + ${bst.rangeSum(preId, n - 1)}")
            }
            // 单点更新
            bst.dec(id)
            preId = id
        }
        return ret
    }

    // 树状数组
    private class BST(private val n: Int) {

        // base 1
        private val data = IntArray(n + 1)

        init {// O(nlgn) 建树
            // for (i in 0 .. n) {//     update(i, 1)
            // }
            // O(n) 建树
            for (i in 1 .. n) {data[i] += 1
                val parent = i + lowbit(i)
                if (parent <= n) data[parent] += data[i]
            }
        }

        fun rangeSum(i1: Int, i2: Int): Int {return preSum(i2 + 1) - preSum(i1 + 1)
        }

        fun dec(i: Int) {update(i + 1, -1)
        }

        private fun preSum(i: Int): Int {
            var x = i
            var sum = 0
            while (x > 0) {sum += data[x]
                x -= lowbit(x)
            }
            return sum
        }

        private fun update(i: Int, delta: Int) {
            var x = i
            while (x <= n) {data[x] += delta
                x += lowbit(x)
            }
        }

        private fun lowbit(x: Int) = x and (-x)
    }
}

复杂度剖析：

  • 工夫复杂度：$O(nlgn)$ 其中 n 是 nums 数组的长度，排序 $O(nlgn)$、树状数组建树 $O(n)$、单次打消操作的区间和查问和单点更新的工夫为 $O(lgn)$；
  • 空间复杂度：$O(n)$ 索引数组空间 + 树状数组空间。

题解二（树状数组 + 最小堆）

附赠一份最小堆排序的代码：

  • 应用「树状数组」的伎俩解决区间和查问和单点更新问题，留神树状数组是 base 1 的；
  • 应用「最小堆」的伎俩解决排序 / 最小值问题。
class Solution {fun countOperationsToEmptyArray(nums: IntArray): Long {
        val n = nums.size
        var ret = 0L
        // 最小堆
        val ids = PriorityQueue<Int>() { i1, i2 ->
            if (nums[i1] < nums[i2]) -1 else 1
        }
        for (id in 0 until n) {ids.offer(id)
        }
        // 树状数组
        val bst = BST(n)
        // 上一个被删除的索引
        var preId = -1
        // 遍历索引
        while (!ids.isEmpty()) {val id = ids.poll()
            // 区间和
            if (id > preId) {ret += bst.rangeSum(preId, id)
            } else {ret += bst.rangeSum(-1, id) + bst.rangeSum(preId, n - 1)
            }
            // 单点更新
            bst.dec(id)
            preId = id
        }
        return ret
    }
}

复杂度剖析：

  • 工夫复杂度：$O(nlgn)$ 其中 n 是 nums 数组的长度，堆排序 $O(nlgn)$、树状数组建树 $O(n)$、单次打消操作的区间和查问和单点更新的工夫为 $O(lgn)$；
  • 空间复杂度：$O(n)$ 堆空间 + 树状数组空间。

类似题目：

  • 315. 计算右侧小于以后元素的个数
  • 1040. 挪动石子直到间断 II

往期回顾

  • LeetCode 单周赛第 342 场 · 把问题学简单，再学简略
  • LeetCode 单周赛第 341 场· 难度上来了，图论的问题好多啊！
  • LeetCode 双周赛第 102 场· 这次又是最短路。
  • LeetCode 双周赛第 101 场 · 是时候做出扭转了！
退出移动版