🌟欢迎来到 我的博客 —— 探索技术的无限可能！
3.分糖果 II
题目链接：1103. 分糖果 II
排排坐，分糖果。
我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。
给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。
然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。
重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。
示例 1：
输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。
示例 2：
输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。
提示：
1 <= candies <= 10^9
1 <= num_people <= 1000
题解：
方法：模拟
public class Solution { public int[] distributeCandies(int candies, int n) { int[] ans = new int[n]; for (int i = 1; candies > 0; i++) { ans[(i - 1) % n] += Math.min(i, candies); candies -= i; } return ans; } }
4.在带权树网络中统计可连接服务器对数目
给你一棵无根带权树，树中总共有 n 个节点，分别表示 n 个服务器，服务器从 0 到 n - 1 编号。同时给你一个数组 edges ，其中 edges[i] = [ai, bi, weighti] 表示节点 ai 和 bi 之间有一条双向边，边的权值为 weighti 。再给你一个整数 signalSpeed 。
如果两个服务器 a ，b 和 c 满足以下条件，那么我们称服务器 a 和 b 是通过服务器 c 可连接的 ：
a < b ，a != c 且 b != c 。
从 c 到 a 的距离是可以被 signalSpeed 整除的。
从 c 到 b 的距离是可以被 signalSpeed 整除的。
从 c 到 b 的路径与从 c 到 a 的路径没有任何公共边。
请你返回一个长度为 n 的整数数组 count ，其中 count[i] 表示通过服务器 i 可连接 的服务器对的 数目 。
示例 1：
输入：edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1
输出：[0,4,6,6,4,0]
解释：由于 signalSpeed 等于 1 ，count[c] 等于所有从 c 开始且没有公共边的路径对数目。
在输入图中，count[c] 等于服务器 c 左边服务器数目乘以右边服务器数目。
示例 2：
输入：edges = [[0,6,3],[6,5,3],[0,3,1],[3,2,7],[3,1,6],[3,4,2]],
signalSpeed = 3
输出：[2,0,0,0,0,0,2]
解释：通过服务器 0 ，有 2 个可连接服务器对(4, 5) 和 (4, 6) 。
通过服务器 6 ，有 2 个可连接服务器对 (4, 5) 和 (0, 5) 。
所有服务器对都必须通过服务器 0 或 6 才可连接，所以其他服务器对应的可连接服务器对数目都为 0 。
提示：
2 <= n <= 1000
edges.length == n - 1
edges[i].length == 3
0 <= ai, bi < n
edges[i] = [ai, bi, weighti]
1 <= weighti <= 106
1 <= signalSpeed <= 106
输入保证 edges 构成一棵合法的树。
题解：
方法：深度优先搜索
class Solution { public int[] countPairsOfConnectableServers(int[][] edges, int signalSpeed) { int n = edges.length + 1; List<int[]>[] g = new ArrayList[n]; Arrays.setAll(g, i -> new ArrayList<>()); for (int[] e : edges) { int x = e[0]; int y = e[1]; int wt = e[2]; g[x].add(new int[]{y, wt}); g[y].add(new int[]{x, wt}); } int[] ans = new int[n]; for (int i = 0; i < n; i++) { if (g[i].size() == 1) { continue; } int sum = 0; for (int[] e : g[i]) { int cnt = dfs(e[0], i, e[1], g, signalSpeed); ans[i] += cnt * sum; sum += cnt; } } return ans; } private int dfs(int x, int fa, int sum, List<int[]>[] g, int signalSpeed) { int cnt = sum % signalSpeed == 0 ? 1 : 0; for (int[] e : g[x]) { int y = e[0]; if (y != fa) { cnt += dfs(y, x, sum + e[1], g, signalSpeed); } } return cnt; } }
5.将元素分配到两个数组中 II
题目链接：3072. 将元素分配到两个数组中 II
给你一个下标从 1 开始、长度为 n 的整数数组 nums 。
现定义函数 greaterCount ，使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。
你需要使用 n 次操作，将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：
如果 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr1 。
如果 greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr2 。
如果 greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，将 nums[i] 追加到元素数量较少的数组中。
如果仍然相等，那么将 nums[i] 追加到 arr1 。
连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。
返回整数数组 result 。
示例 1：
输入：nums = [2,1,3,3]
输出：[2,3,1,3]
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是零，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，两个数组中大于 3 的元素数量都是零，但 arr2 的长度较小，因此，将 nums[4] 追加到 arr2 。
在 4 次操作后，arr1 = [2,3] ，arr2 = [1,3] 。
因此，连接形成的数组 result 是 [2,3,1,3] 。
示例 2：
输入：nums = [5,14,3,1,2]
输出：[5,3,1,2,14]
解释：在前两次操作后，arr1 = [5] ，arr2 = [14] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是一，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，arr1 中大于 1 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[4] 追加到 arr1 。
在第 5 次操作中，arr1 中大于 2 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[5] 追加到 arr1 。
在 5 次操作后，arr1 = [5,3,1,2] ，arr2 = [14] 。
因此，连接形成的数组 result 是 [5,3,1,2,14] 。
示例 3：
输入：nums = [3,3,3,3]
输出：[3,3,3,3]
解释：在 4 次操作后，arr1 = [3,3] ，arr2 = [3,3] 。
因此，连接形成的数组 result 是 [3,3,3,3] 。
提示：
3 <= n <= 105
1 <= nums[i] <= 109
题解：
方法：树状数组 二分查找
class Fenwick { private final int[] tree; public Fenwick(int n) { tree = new int[n]; } // 把下标为 i 的元素增加 1 public void add(int i) { while (i < tree.length) { tree[i]++; i += i & -i; } } // 返回下标在 [1,i] 的元素之和 public int pre(int i) { int res = 0; while (i > 0) { res += tree[i]; i &= i - 1; } return res; } } class Solution { public int[] resultArray(int[] nums) { int[] sorted = nums.clone(); Arrays.sort(sorted); // 只排序不去重 int n = nums.length; List<Integer> a = new ArrayList<>(n); // 预分配空间 List<Integer> b = new ArrayList<>(); a.add(nums[0]); b.add(nums[1]); Fenwick t1 = new Fenwick(n + 1); Fenwick t2 = new Fenwick(n + 1); t1.add(Arrays.binarySearch(sorted, nums[0]) + 1); t2.add(Arrays.binarySearch(sorted, nums[1]) + 1); for (int i = 2; i < nums.length; i++) { int x = nums[i]; int v = Arrays.binarySearch(sorted, x) + 1; int gc1 = a.size() - t1.pre(v); // greaterCount(a, v) int gc2 = b.size() - t2.pre(v); // greaterCount(b, v) if (gc1 > gc2 || gc1 == gc2 && a.size() <= b.size()) { a.add(x); t1.add(v); } else { b.add(x); t2.add(v); } } a.addAll(b); for (int i = 0; i < n; i++) { nums[i] = a.get(i); } return nums; } }
6.区分黑球与白球
题目链接：2938. 区分黑球与白球
桌子上有 n 个球，每个球的颜色不是黑色，就是白色。
给你一个长度为 n 、下标从 0 开始的二进制字符串 s，其中 1 和 0 分别代表黑色和白色的球。
在每一步中，你可以选择两个相邻的球并交换它们。
返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 最小步数」。
示例 1：
输入：s = “101”
输出：1
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = “011”。
最开始，1 没有都在右侧，需要至少 1 步将其移到右侧。
示例 2：
输入：s = “100”
输出：2
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = “010”。
- 交换 s[1] 和 s[2]，s = “001”。
可以证明所需的最小步数为 2 。
示例 3：
输入：s = “0111”
输出：0
解释：所有黑色球都已经在右侧。
提示：
1 <= n == s.length <= 105
s[i] 不是 ‘0’，就是 ‘1’。
题解：
方法：累加
class Solution { public long minimumSteps(String s) { long ans = 0; int cnt1 = 0; for (char c : s.toCharArray()) { if (c == '1') { cnt1++; } else { ans += cnt1; } } return ans; } }
7.相同分数的最大操作数目 I
题目链接：3038. 相同分数的最大操作数目 I
给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作：
选择 nums 中的前两个元素并将它们删除。
一次操作的 分数 是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。
示例 1：
输入：nums = [3,2,1,4,5]
输出：2
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,4,5] 。
- 删除前两个元素，分数为 1 + 4 = 5 ，nums = [5] 。
由于只剩下 1 个元素，我们无法继续进行任何操作。
示例 2：
输入：nums = [3,2,6,1,4]
输出：1
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。
由于下一次操作的分数与前一次不相等，我们无法继续进行任何操作。
提示：
2 <= nums.length <= 100
1 <= nums[i] <= 1000
题解：
方法：模拟
class Solution { public int maxOperations(int[] nums) { int s = nums[0] + nums[1]; int ans = 1; for (int i = 3; i < nums.length && nums[i - 1] + nums[i] == s; i += 2) { ans++; } return ans; } }
8.相同分数的最大操作数目 II
题目链接：3040. 相同分数的最大操作数目 II
给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个：
选择 nums 中最前面两个元素并且删除它们。
选择 nums 中最后两个元素并且删除它们。
选择 nums 中第一个和最后一个元素并且删除它们。
一次操作的 分数 是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。
示例 1：
输入：nums = [3,2,1,2,3,4]
输出：3
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。
- 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。
- 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。
由于 nums 为空，我们无法继续进行任何操作。
示例 2：
输入：nums = [3,2,6,1,4]
输出：2
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。
- 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。
至多进行 2 次操作。
提示：
2 <= nums.length <= 2000
1 <= nums[i] <= 1000
题解：
方法：记忆化搜索
class Solution { private int[] nums; private int[][] memo; public int maxOperations(int[] nums) { this.nums = nums; int n = nums.length; memo = new int[n][n]; int res1 = helper(2, n - 1, nums[0] + nums[1]); // 删除前两个数 int res2 = helper(0, n - 3, nums[n - 2] + nums[n - 1]); // 删除后两个数 int res3 = helper(1, n - 2, nums[0] + nums[n - 1]); // 删除第一个和最后一个数 return Math.max(Math.max(res1, res2), res3) + 1; // 加上第一次操作 } private int helper(int i, int j, int target) { for (int[] row : memo) { Arrays.fill(row, -1); // -1 表示没有计算过 } return dfs(i, j, target); } private int dfs(int i, int j, int target) { if (i >= j) { return 0; } if (memo[i][j] != -1) { // 之前计算过 return memo[i][j]; } int res = 0; if (nums[i] + nums[i + 1] == target) { // 删除前两个数 res = Math.max(res, dfs(i + 2, j, target) + 1); } if (nums[j - 1] + nums[j] == target) { // 删除后两个数 res = Math.max(res, dfs(i, j - 2, target) + 1); } if (nums[i] + nums[j] == target) { // 删除第一个和最后一个数 res = Math.max(res, dfs(i + 1, j - 1, target) + 1); } return memo[i][j] = res; // 记忆化 } }
9.戳气球
题目链接：312. 戳气球
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 315 + 358 + 138 + 181 = 167
示例 2：
输入：nums = [1,5]
输出：10
提示：
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
题解：
方法：动态规划
class Solution { public int maxCoins(int[] nums) { int n = nums.length; int[] arr = new int[n + 2]; arr[0] = 1; arr[n + 1] = 1; System.arraycopy(nums, 0, arr, 1, n); int[][] f = new int[n + 2][n + 2]; for (int i = n - 1; i >= 0; i--) { for (int j = i + 2; j <= n + 1; j++) { for (int k = i + 1; k < j; k++) { f[i][j] = Math.max(f[i][j], f[i][k] + f[k][j] + arr[i] * arr[k] * arr[j]); } } } return f[0][n + 1]; } }
