力扣第 341 场周赛题解

题目链接：https://leetcode.cn/contest/weekly-contest-341/

# T1. 一最多的行

链接：https://leetcode.cn/problems/row-with-maximum-ones/

# 思路

模拟

# 代码

	class Solution {
	public int[] rowAndMaximumOnes(int[][] mat) {
	int row = -1;
	int cnt = -1;

	for (int i = 0; i < mat.length; ++i) {
	int c = 0;
	for (int j = 0; j < mat[i].length; ++j) {
	if (mat[i][j] == 1) ++c;
	}

	if (c > cnt) {
	cnt = c;
	row = i;
	}
	}

	return new int[] {row, cnt};
	}
	}

# T2. 找出可整除性得分最大的整数

链接：https://leetcode.cn/problems/find-the-maximum-divisibility-score/

# 思路

按题目模拟即可

# 代码

	class Solution {
	public int maxDivScore(int[] nums, int[] divisors) {
	int n = nums.length;

	int score = -1;
	int ret = Integer.MAX_VALUE;
	for (int d : divisors) {
	int s = 0;
	for (int i = 0; i < n; ++i) {
	if (nums[i] % d == 0) {
	++s;
	}
	}

	if (s > score) {
	score = s;
	ret = d;
	} else if (s == score) {
	ret = Math.min(ret, d);
	}
	}

	return ret;
	}
	}

# T3. 构造有效字符串的最少插入数

链接：https://leetcode.cn/problems/minimum-additions-to-make-valid-string/

# 法一：利用周期性

最后字符串要变成： abcabcabc... 呈周期循环

如果当前的字符比它前一个字符大，说明：当前字符和前一个字符构成一个周期；
否则当前字符形成一个新周期

最后的插入字符数为 3 * T - len(s) ，T 为周期数

# 代码

	class Solution {
	public int addMinimum(String word) {
	char[] chs = word.toCharArray();
	int n = chs.length;
	// 至少一个周期
	int t = 1;
	for (int i = 1; i < n; ++i) {
	if (chs[i] <= chs[i - 1]) ++t;
	}
	return 3 * t - n;
	}
	}

模拟

if-else 枚举，适用于字符串较短
数学法进行优化：

# 代码

if-else 穷举：

	class Solution {
	public int addMinimum(String word) {
	int cnt = 0;
	char[] chs = word.toCharArray();
	int n = chs.length;
	for (int i = 0; i < n; ++i) {
	if (chs[i] == 'a') {
	if (i + 1 < n && chs[i + 1] == 'b') {
	++i;
	if (i + 1 < n && chs[i + 1] == 'c') {
	++i;
	} else {
	++cnt;
	}
	} else if (i+1 < n && chs[i+1] == 'c'){
	++i;
	++cnt;
	} else {
	cnt += 2;
	}
	} else if (chs[i] == 'b'){
	++cnt;
	if (i + 1 < n && chs[i+1] == 'c') {
	++i;
	} else {
	++cnt;
	}
	} else {
	cnt+= 2;
	}
	}

	return cnt;
	}
	}

利用数学方法优化：

	class Solution {
	public int addMinimum(String word) {
	char[] chs = word.toCharArray();
	int n = chs.length;
	/**
	* 将字符串分成【中间插入】和【首尾插入】，即 aaa -> _a_a_a_， '_' 表示待插入字符串的位置
	*
	* 处理第一字符：chs [0] - 'a'
	* 处理末尾字符：'c' - chs [n-1]
	*
	* 中间位置
	* aa -> abca -> 2
	* ab -> ab -> 0
	* ac -> abc -> 1
	* cb -> cab -> 1
	* ......
	*
	* 即：
	* (chs [i] - chs [i-1] - 1 + 3) % 3
	*/

	int cnt = chs[0] - chs[n-1] + 2;
	// 处理中间插入位置
	for (int i = 1; i < n; ++i) {
	cnt += (chs[i] - chs[i - 1] + 2) % 3;
	}
	return cnt;
	}
	}

# T4. 最小化旅行的价格总和

链接：https://leetcode.cn/problems/minimize-the-total-price-of-the-trips/

# 思路

待补充

# 代码

	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};
	}
	}

leetcode 题解周赛

# T1. 一最多的行

# 思路

# 代码

# T2. 找出可整除性得分最大的整数

# 思路

# 代码

# T3. 构造有效字符串的最少插入数

# 法一：利用周期性

# 代码

# 代码

# T4. 最小化旅行的价格总和

# 思路

# 代码

力扣第 102 场双周赛

每日一题：分隔数组以得到最大和