本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。
大家好，我是小彭。
这场周赛是 LeetCode 双周赛第 103 场，难得在五一假期第一天打周赛的人数也没有少太多。这场比赛前 3 题比较简单，我们把篇幅留给最后一题。
往期周赛回顾：LeetCode 单周赛第 342 场 · 容斥原理、计数排序、滑动窗口、子数组 GCB
Q1. K 个元素的最大和（Easy）
简单模拟题，不过多讲解。
Q2. 找到两个数组的前缀公共数组（Medium）
简单模拟题，在计数的实现上有三种解法：
Q3. 网格图中鱼的最大数目（Hard）
这道题的难度标签是认真的吗？打 Medium 都过分了居然打 Hard？
Q4. 将数组清空（Hard）
这道题的难点在于如何想到以及正确地将原问题转换为区间求和问题，思路想清楚后用树状数组实现。
https://leetcode.cn/problems/maximum-sum-with-exactly-k-elements/
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你需要执行以下操作 恰好 k 次，最大化你的得分：
nums 中选择一个元素 m 。m 从数组中删除。m + 1 添加到数组中。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 <= 1001 <= nums[i] <= 1001 <= k <= 100显然第一次操作的分数会选择数组中的最大值 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
}
}
复杂度分析：
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 <= 501 <= A[i], B[i] <= nA 和 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
}
}
复杂度分析：
题解一需要使用多倍空间，我们发现 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
}
}
复杂度分析：
既然 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
}
}
复杂度分析：
https://leetcode.cn/problems/maximum-number-of-fish-in-a-grid/description/
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，其中下标在 (r, c) 处的整数表示：
grid[r][c] = 0 ，那么它是一块 陆地 。grid[r][c] > 0 ，那么它是一块 水域 ，且包含 grid[r][c] 条鱼。一位渔夫可以从任意 水域 格子 (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.lengthn == grid[i].length1 <= m, n <= 100 <= grid[i][j] <= 10求 “加权连通分量 / 岛屿问题”，用二维 BFS 或 DFS 或并查集都可以求出所有连通块的最大值，史上最水 Hard 题。
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
}
}
复杂度分析：
附赠一份并查集的解法：
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
}
}
}
复杂度分析：
相似题目：
推荐阅读：
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 <= 105109 <= nums[i] <= 109nums 中的元素 互不相同 。循环数组：将数组尾部元素的后继视为数组首部元素，数组首部元素的前驱视为数组尾部元素。
树状数组也叫二叉索引树（Binary Indexed Tree），是一种支持 “单点修改” 和 “区间查询” 的代码量少的数据结构。相比于线段树来说，树状数组的代码量远远更少，是一种精妙的数据结构。
树状数组核心思想是将数组 [0,x] 的前缀和拆分为不多于 logx 段非重叠的区间，在计算前缀和时只需要合并 logx 段区间信息，而不需要合并 n 个区间信息。同时，在更新单点值时，也仅需要修改 logx 段区间，而不需要（像前缀和数组）那样修改 n 个信息。可以说，树状数组平衡了单点修改和区间和查询的时间复杂度：
树状数组
求消除数组的操作次数。
以序列 [3,4,-1] 为例，一共操作 5 次：
消除操作需要按照元素值从小到大的顺序删除，那么如何判断数组首部元素是否为最小值？
如何表示元素的移动操作：
如何解决问题：
至此，问题陷入瓶颈。
解决方法是重复「分析问题要件」-「具体化解决手段」的过程，枚举掌握的算法、数据结构和 Tricks 寻找突破口：
表示元素的移动操作的新手段：
解决问题的新手段：
区分上次位置与当前位置的前后关系，需要分类讨论：
如何实现手段 2（计数）：
在代码实现上，涉及到「区间求和」和「单点更新」可以用线段数和树状数组实现。树状数组的代码量远比线段树少，所以我们选择后者。
示意图
答疑：
由于消除是按照元素值从小到大的顺序消除的，所以未被消除的元素一定比当前元素大，所以我们不强调元素大小关系。
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)
}
}
复杂度分析：
附赠一份最小堆排序的代码：
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
}
}
复杂度分析：
相似题目：