6376. Row With Maximum Ones
给你一个大小为 m x n 的二进制矩阵 mat ，请你找出包含最多 1 的行的下标（从 0 开始）以及这一行中 1 的数目。
如果有多行包含最多的 1 ，只需要选择 行下标最小 的那一行。
返回一个由行下标和该行中 1 的数量组成的数组。
测试样例
输入：mat = [[0,1],[1,0]]
输出：[0,1]
解释：两行中 1 的数量相同。所以返回下标最小的行，下标为 0 。该行 1 的数量为 1 。所以，答案为 [0,1] 。
解答：暴力计算每一行1的个数，然后判断最大值
class Solution {
public int[] rowAndMaximumOnes(int[][] mat) {
int offset = 0;
int[] res = {-1,-1};
for (int[] r : mat) {
int c = 0;
for (int n : r) {
c += n;
}
if (c > res[1]) {
res[0] = offset;
res[1] = c;
}
++offset;
}
return res;
}
}6350. Find the Maximum Divisibility Score
给你两个下标从 0 开始的整数数组 nums 和 divisors 。
divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。
返回 可整除性得分 最大的整数 divisors[i] 。如果有多个整数具有最大得分，则返回数值最小的一个。
测试样例：
输入：nums = [4,7,9,3,9], divisors = [5,2,3]
输出：3
解释：
divisors 中每个元素的可整除性得分为：
- divisors[0] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 5 整除。
- divisors[1] 的可整除性得分为 1 ，因为 nums[0] 能被 2 整除。
- divisors[2] 的可整除性得分为 3 ，因为 nums[2]、nums[3] 和 nums[4] 都能被 3 整除。
因此，返回 divisors[2] ，它的可整除性得分最大。
解答：有条件：1 <= nums.length, divisors.length <= 1000， 暴力遍历计算count就可以了
class Solution {
public int maxDivScore(int[] nums, int[] divisors) {
int maxScore = -1, div = -1;
for (int d : divisors) {
int c = 0;
for (int n : nums) {
if (n % d == 0) {
++c;
}
}
if (c > maxScore) {
maxScore = c;
div = d;
} else if (c == maxScore) {
div = Math.min(div, d);
}
}
return div;
}
}
6375. Minimum Additions to Make Valid String
给你一个字符串 word ，你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次，返回使 word 有效 需要插入的最少字母数。
如果字符串可以由 "abc" 串联多次得到，则认为该字符串 有效 。
测试样例
输入：word = "b"
输出：2
解释：
在 "b" 之前插入 "a" ，在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。
解答：记录一下当前位置应该出现的字母。如果不符合，那res += 1。否则进入下一位判断。需要注意的是：还需要判断一下word遍历完毕之后，abc是否也同时刚好遍历完一次。否则还需要在word末尾填补。
class Solution {
public int addMinimum(String word) {
int count = 0, res = 0;
int pos = 0;
while (pos < word.length()) {
if (word.charAt(pos) - 'a' != count) {
++res;
} else {
++pos;
}
count = (count + 1) % 3;
}
while (count != 0) {
count = (count + 1) % 3;
++res;
}
return res;
}
}6378. Minimize the Total Price of the Trips
现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。
每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。
给定路径的 价格总和 是该路径上所有节点的价格之和。
另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。
在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。
返回执行所有旅行的最小价格总和。
测试样例
输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出：23
解释：
- 第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
- 第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
- 第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。
解答：首先这道题目是一颗树，所以每一次trip的路线是固定的（否则必然存在引入额外节点的问题，cost只会单向上升）。这样我们第一步直接将每一次trip会途径的点遍历出来，然后生成一个count数组（即每个节点在完成所有trip，需要途径的次数）。我在竞赛的时候偷懒了，直接暴力遍历了trip，实际上应该有更好的算法。
生成count数组之后，这道题目就变成一道动态规划题了。因为目标是选择一些非相邻节点价格减半，同时要所有旅行的最小价格总和。我们可以利用动态规划，记录当前节点减半和不减半 2 种可能。然后计算得出最小值。
class Solution {
private List<Integer>[] edges;
private Integer[][] mem;
private int[] count, price;
public int minimumTotalPrice(int n, int[][] _edges, int[] price, int[][] trips) {
if (n == 1) {
int res = 0;
for (int[] t : trips) {
res += price[0] / 2;
}
return res;
}
edges = new List[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
this.price = price;
this.count = new int[n];
for (int[] t : trips) {
LinkedList<Integer> path = new LinkedList<>();
boolean[] isMet = new boolean[n];
dfsTrip(t[0], t[1], path, isMet);
for (int i : path) {
count[i] += 1;
}
}
mem = new Integer[n][2];
return dfsPrice(_edges[0][0], 0, -1);
}
public boolean dfsTrip(int node1, int node2, LinkedList<Integer> path, boolean[] isMet) {
if (isMet[node1]) {
return false;
}
isMet[node1] = true;
path.add(node1);
if (node1 == node2) {
return true;
}
for (int n : edges[node1]) {
if (dfsTrip(n, node2, path, isMet)) {
return true;
}
}
path.removeLast();
return false;
}
private int dfsPrice(int node, int last, int previousNode) {
if (mem[node][last] == null) {
mem[node][last] = price[node] * count[node];
for (int i : edges[node]) {
if (i != previousNode) {
mem[node][last] += dfsPrice(i, 0, node);
}
}
if (last == 0) {
int tmp = price[node] * count[node] / 2;
for (int i : edges[node]) {
if (i != previousNode) {
tmp += dfsPrice(i, 1, node);
}
}
mem[node][last] = Math.min(mem[node][last], tmp);
}
}
return mem[node][last];
}
}