6376. 一最多的行
给你一个大小为 m x n 的二进制矩阵 mat ，请你找出包含最多 1 的行的下标（从 0 开始）以及这一行中 1 的数目。
如果有多行包含最多的 1 ，只需要选择 行下标最小 的那一行。
返回一个由行下标和该行中 1 的数量组成的数组。
示例 1：
输入：mat = [[0,1],[1,0]]
输出：[0,1]
解释：两行中 1 的数量相同。所以返回下标最小的行，下标为 0 。该行 1 的数量为 1 。所以，答案为 [0,1] 。
示例 2：
输入：mat = [[0,0,0],[0,1,1]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。
示例 3：
输入：mat = [[0,0],[1,1],[0,0]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。
提示：
m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] 为 0 或 1解答：按照题意暴力解答
class Solution {
public int[] rowAndMaximumOnes(int[][] mat) {
int maxOnes = 0;
int rowIndex = 0;
for (int i = 0; i < mat.length; i++) {
int rowOnes = 0;
for (int j = 0; j < mat[i].length; j++) {
if (mat[i][j] == 1) {
rowOnes++;
}
}
if (rowOnes > maxOnes) {
maxOnes = rowOnes;
rowIndex = i;
}
}
return new int[] {rowIndex, maxOnes};
}
}6350. 找出可整除性得分最大的整数
给你两个下标从 0 开始的整数数组 nums 和 divisors 。
divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。
返回 可整除性得分 最大的整数 divisors[i] 。如果有多个整数具有最大得分，则返回数值最小的一个。
示例 1：
输入：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] ，它的可整除性得分最大。
示例 2：
输入：nums = [20,14,21,10], divisors = [5,7,5]
输出：5
解释：divisors 中每个元素的可整除性得分为：
divisors[0] 的可整除性得分为 2 ，因为 nums[0] 和 nums[3] 都能被 5 整除。
divisors[1] 的可整除性得分为 2 ，因为 nums[1] 和 nums[2] 都能被 7 整除。
divisors[2] 的可整除性得分为 2 ，因为 nums[0] 和 nums[3] 都能被5整除。
由于 divisors[0]、divisors[1] 和 divisors[2] 的可整除性得分都是最大的，因此，我们返回数值最小的一个，即 divisors[2] 。
示例 3：
输入：nums = [12], divisors = [10,16]
输出：10
解释：divisors 中每个元素的可整除性得分为：
divisors[0] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 10 整除。
divisors[1] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 16 整除。
由于 divisors[0] 和 divisors[1] 的可整除性得分都是最大的，因此，我们返回数值最小的一个，即 divisors[0] 。
提示：
1 <= nums.length, divisors.length <= 1000
1 <= nums[i], divisors[i] <= 10^9解答：按照题意直接模拟
class Solution {
public int maxDivScore(int[] nums, int[] divisors) {
int maxScore = 0;
int minDivisor = Integer.MAX_VALUE;
for (int i = 0; i < divisors.length; i++) {
int score = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] % divisors[i] == 0) {
score++;
}
}
if (score > maxScore) {
maxScore = score;
minDivisor = divisors[i];
} else if (score == maxScore) {
minDivisor = Math.min(minDivisor, divisors[i]);
}
}
return minDivisor;
}
}
6375. 构造有效字符串的最少插入数
给你一个字符串 word ，你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次，返回使 word 有效 需要插入的最少字母数。
如果字符串可以由 "abc" 串联多次得到，则认为该字符串 有效 。
示例 1：
输入：word = "b"
输出：2
解释：在 "b" 之前插入 "a" ，在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。
示例 2：
输入：word = "aaa"
输出：6
解释：在每个 "a" 之后依次插入 "b" 和 "c" 可以得到有效字符串 "abcabcabc" 。
示例 3：
输入：word = "abc"
输出：0
解释：word 已经是有效字符串，不需要进行修改。
提示：
1 <= word.length <= 50
word 仅由字母 "a"、"b" 和 "c" 组成。解答：找到数组中连续的递增子数组的个数，乘3就是最后的abc串长度
class Solution {
public int addMinimum(String word) {
int count=1;
for(int i=1;i<word.length();i++){
if(word.charAt(i)>word.charAt(i-1))continue;
else count++;// 必须生成一个新的 abc
}
return count*3-word.length();
}
}6378. 最小化旅行的价格总和
现有一棵无向、无根的树，树中有 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 。
在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。
返回执行所有旅行的最小价格总和。
示例 1：
输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出：23
解释：
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 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 是可以实现的最小答案。
示例 2：
输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。
第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。
所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。
提示：
1 <= n <= 50
edges.length == n - 1
0 <= ai, bi <= n - 1
edges 表示一棵有效的树
price.length == n
price[i] 是一个偶数
1 <= price[i] <= 1000
1 <= trips.length <= 100
0 <= starti, endi <= n - 1解答：
class Solution {
private List<Integer>[] g;
private int[] price, cnt;
private int end;
public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (var e : edges) {
int x = e[0], y = e[1];
g[x].add(y);
g[y].add(x); // 建树
}
this.price = price;
cnt = new int[n];
for (var t : trips) {
end = t[1];
path(t[0], -1);
}
var p = dfs(0, -1);
return Math.min(p[0], p[1]);
}
private boolean path(int x, int fa) {
if (x == end) { // 到达终点（注意树只有唯一的一条简单路径）
++cnt[x]; // 统计从 start 到 end 的路径上的点经过了多少次
return true; // 找到终点
}
for (var y : g[x])
if (y != fa && path(y, x)) {
++cnt[x]; // 统计从 start 到 end 的路径上的点经过了多少次
return true; // 找到终点
}
return false; // 未找到终点
}
// 类似 337. 打家劫舍 III https://leetcode.cn/problems/house-robber-iii/
private int[] dfs(int x, int fa) {
int notHalve = price[x] * cnt[x]; // x 不变
int halve = notHalve / 2; // x 减半
for (var y : g[x])
if (y != fa) {
var p = dfs(y, x); // 计算 y 不变/减半的最小价值总和
notHalve += Math.min(p[0], p[1]); // x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值
halve += p[0]; // x 减半，那么 y 只能不变
}
return new int[]{notHalve, halve};
}
}
