双周赛103

题解参考：小样肖恩：https://leetcode.cn/circle/discuss/KAtdoc/

6406. K 个元素的最大和

输入：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 是可以得到的最大答案。

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

模拟

题意:每次取一个数，将其作为得分，并对其进行增大 1的操作，进行k次，求总得分最大值。

显然每次取最大值肯定是最好的，因此数组中唯一重要的是最大值 m。因为每次的得分以1为公差依次递增，因此计算一个首项为 m，公差为1，项数为k的等差数列的和即可

时间复杂度为 O(n)，来自于求数组最大值

Java

class Solution {public int maximizeSum(int[] nums, int k) {Arrays.sort(nums);int max = nums[nums.length - 1];int res = 0;while(k-- > 0){res += max;max++;}return res;}
}

python

class Solution:def maximizeSum(self, nums: List[int], k: int) -> int:m = max(nums)ans = 0while k > 0:ans += mm += 1k -= 1return ans
# 推公式：一行代码
class Solution:def maximizeSum(self, nums: List[int], k: int) -> int:# 推公式：假设数组最大值为m，累加k次#   答案就是：m + (m+1) + (m+2) + ... + (m + k - 1)#   ==> (m + m + k - 1)*k / 2【(首项+尾项)*项数 / 2：等差数列的前n项和： Sn=[n(A1+An)]/2】return (2 * max(nums) + k-1) * k // 2;

6405. 找到两个数组的前缀公共数组

输入：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 。

输入：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 。

模拟

java

class Solution {public int[] findThePrefixCommonArray(int[] A, int[] B) {int n = A.length;int[] res = new int[n];int[] cnta = new int[n+1];int[] cntb = new int[n+1];int presum = 0;for(int i = 0; i < n; i++){cnta[A[i]]++;cntb[B[i]]++;if(A[i] != B[i]){if(cntb[A[i]] > 0) presum += 1;if(cnta[B[i]] > 0) presum += 1;   }else{if(cntb[A[i]] > 0) presum += 1;}res[i] = presum;}return res;}
}

由于两个数组都是1到 n 的排列，前缀公共部分种的任意一个数，一定在 A,B 中分别出现一次，即出现两次。因此在一个数出现两次时，前缀公共数字数量增加了 1，使用这一性质更新即可。

时间复杂度为O(n)，来源于遍历数组

class Solution:def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:n, presum = len(A), 0ans = []cnt = [0] * (n+1)for x, y in zip(A, B):cnt[x] += 1if cnt[x] == 2: presum += 1 # 不要在 cnt[y] += 1 后进行，否则 x = y 的情况下分别计数，会多算cnt[y] += 1if cnt[y] == 2:presum += 1ans.append(presum)return ans

6403. 网格图中鱼的最大数目

输入：grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
输出：7
解释：渔夫可以从格子 (1,3) 出发，捕捞 3 条鱼，然后移动到格子 (2,3) ，捕捞 4 条鱼。

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

本质是网格图求连通块大小

对于每一个水域构成的连通块，最多捕捞的鱼的总数为这个连通块里鱼的数量的总和。因此我们只需要对于每一个连通块查看总鱼数量即可。这个可以用深度/广度优先搜索或并查集直接解决。时间复杂度O(nm)。

java（DFS）

在遍历每一个连通块时，可以将遍历过的位置值设置为0，这样就不用开vis数组了

class Solution {int[][] dirts = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};int[][] grid;int n, m;public int findMaxFish(int[][] grid) {int res = 0;n = grid.length; m = grid[0].length;this.grid = grid;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++)res = Math.max(res, dfs(i, j));}return res;}public int dfs(int i, int j){if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == 0)return 0;int result = grid[i][j];grid[i][j] = 0;for(int[] d : dirts){int x = i + d[0], y = j + d[1];result += dfs(x, y);}return result;}
}

python

class Solution:def findMaxFish(self, grid: List[List[int]]) -> int:n, m = len(grid), len(grid[0])ans = 0def dfs(i, j: int) -> int:res = grid[i][j]grid[i][j] = 0for x, y in (i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1): if 0 <= x < n and 0 <= y < m and grid[x][y]:res += dfs(x, y)return resfor i in range(n):for j in range(m):if grid[i][j] > 0:tot = dfs(i, j)ans = max(ans, tot)return ans

更短更优雅的网格图DFS模板:python

class Solution:def findMaxFish(self, grid: List[List[int]]) -> int:n, m = len(grid), len(grid[0])ans = 0def dfs(i, j: int) -> int:if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] == 0:return 0res = grid[i][j]grid[i][j] = 0for x, y in (i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1): res += dfs(x, y)return resreturn max(max(dfs(i, j) for j in range(m)) for i in range(n))

🎉6404. 将数组清空

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

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

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

树状数组

题解：https://leetcode.cn/problems/make-array-empty/solution/shu-zhuang-shu-zu-mo-ni-pythonjavacgo-by-ygvb/

class Solution:"""转换：将第一个元素移动到数组的末尾 ==> 用 下标  来标记当前数组的第一个数是谁，然后不断往后移动举例 ：2413 ==> 当前下标2 ==> 1324 ==>删除1 ==> 324 ==> 当前下标3这个转换是怎么想到的？技巧，相对关系【数字往后移 等价于 用一个下标来模拟】删除一个数后，下标自动向右移动一位（这一次操作是免费的）我们需要记录每一个数的位置，从小到大删除上一个删除的数的下标是 pre， 当前要删除的下标是 i因此我们需要思考【从pre移动到i，需要移动多少次？】1. 维护中间被删除的数字个数==> 树状数组如果pre <= i, 移动次数 i-pre-query(pre,i) 【pre到i，再减去中间删除的个数】如果pre > i, 移动次数 n - pre-query(pre,n) + 1【n到1的那一步】 + (i-1) - query(1,i) 【pre到n，再从1到i】 简化一下： n - pre + i - (k - query(i, pre-1)) 【树状数组中一共有k个数】2. """def countOperationsToEmptyArray(self, nums: List[int]) -> int:ans = n = len(nums) # 先把 n 计入答案t = BIT(n+1) # 树状数组下标从1开始pre = 1 # 上一个最小值的位置，初始为 1# 根据元素大小对下标进行排序，然后枚举 数的位置 从小到大删除每个数ids = sorted(range(n), key = lambda i: nums[i])for k, i in enumerate(ids):i += 1 # 下标i从1开始if pre <= i: # 从 pre 移动到 i，跳过已经删除的数ans += i - pre - t.query(pre, i)else:ans += n - pre + i - (k - t.query(i, pre-1))t.inc(i) # 删除i（添加到树状数组中）pre = ireturn ans# 树状数组模板
class BIT:def __init__(self, n):self.tree = [0] * n# 将下标 i 上的数加一def inc(self, i: int) -> None:while i < len(self.tree):self.tree[i] += 1i += i & -i# 返回闭区间 [1, i] 的元素和def sum(self, i: int) -> int:res = 0while i > 0:res += self.tree[i]i &= i - 1return res# 返回闭区间 [left, right] 的元素和def query(self, left: int, right: int) -> int:return self.sum(right) - self.sum(left - 1)

java

class Solution {public long countOperationsToEmptyArray(int[] nums) {int n = nums.length;Integer[] ids = new Integer[n];for(int i = 0; i < n; i++) ids[i] = i;Arrays.sort(ids, (i, j) -> nums[i] - nums[j]);long ans = n; // 先把n计入答案BinaryIndexedTree t = new BinaryIndexedTree(n+1); // 下标从1开始int pre = 1;for(int k = 0; k < n; k++){int i = ids[k] + 1;// 当前要删除的下标，提前+1（下标从1开始）if(i >= pre) // 从 pre 移动到 i，跳过已经删除的数ans += i - pre - t.RangeSum(pre, i);else // 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数ans += n - pre + i - k + t.RangeSum(i, pre-1);t.add(i, 1); // 删除ipre = i;}return ans;}
}// BIT动态维护 arr 的前缀和(注意这里下标是从1开始的)
class BinaryIndexedTree{private int n;private int[] tree;public BinaryIndexedTree(int n){ // 初始化时，要传入n+1this.n = n;tree = new int[n];}// 将index位置加上val值 arr[i] += val（注意传进来的index要+1）public void add(int index, int val){while(index < n){tree[index] += val;index += index & -index;}}// 查询[1, index]的前缀和（注意传进来的index要+1）public int query(int index) {int s = 0;while (index > 0) {s += tree[index];index -= index & -index; // n&(~n+1) == n&(-n)}return s;}// 返回[left, right]之间的区间和（注意传进来的index要+1）public int RangeSum(int left, int right){return query(right) - query(left-1);}
}