力扣第 102 场双周赛

题目链接：https://leetcode.cn/contest/biweekly-contest-102/

# T1. 查询网格图中每一列的宽度

链接：https://leetcode.cn/problems/find-the-width-of-columns-of-a-grid/

# 代码

	class Solution {
	public int[] findColumnWidth(int[][] grid) {
	int m = grid.length;
	int n = grid[0].length;

	int[] ans = new int[n];

	for (int i = 0; i < n; ++i) {
	int max = 0;
	for (int j = 0; j < m; ++j) {
	int abs = Math.abs(grid[j][i]);
	int l = len(abs);
	l = grid[j][i] < 0 ? l + 1 : l;
	max = Math.max(l, max);
	}
	ans[i] = max;
	}

	return ans;
	}

	private int len(int k) {
	if (k == 0) return 1;
	int ret = 0;
	while (k > 0) {
	++ret;
	k /= 10;
	}
	return ret;
	}
	}

# T2. 一个数组所有前缀的分数

链接：https://leetcode.cn/problems/find-the-score-of-all-prefixes-of-an-array/

# 思路

根据题意模拟即可

# 提交结果

# 代码

	class Solution {
	public long[] findPrefixScore(int[] nums) {
	int n = nums.length;
	long[] ans = new long[n];

	long max = 0;

	for (int i = 0; i < n; ++i) {
	max = Math.max(nums[i], max);
	ans[i] = max + nums[i];
	if (i > 0) {
	ans[i] += ans[i - 1];
	}
	}

	return ans;
	}
	}

# T3. 二叉树的堂兄弟节点 II

链接：https://leetcode.cn/problems/cousins-in-binary-tree-ii/

# 解题思路

二叉树层序遍历：

记录每个节点的直接父亲节点
根据父亲节点进行分组求和，最后更新左右子节点的值即可

具体看代码

# 提交结果

# 代码

	class Solution {
	public TreeNode replaceValueInTree(TreeNode root) {
	if (root == null) return null;
	Queue<TreeNode[]> que = new ArrayDeque<>();
	root.val = 0;

	if (root.left != null) {
	que.offer(new TreeNode[] {root, root.left});
	}

	if (root.right != null) {
	que.offer(new TreeNode[] {root, root.right});
	}


	while (!que.isEmpty()) {
	Map<TreeNode, Integer> sumMap = new HashMap<>();
	int sum = 0;
	for (int i = que.size(); i > 0; --i) {
	TreeNode[] cur = que.poll();
	sumMap.put(cur[0], sumMap.getOrDefault(cur[0], 0) + cur[1].val);
	sum += cur[1].val;
	if (cur[1].left != null) {
	que.offer(new TreeNode[] {cur[1], cur[1].left});
	}

	if (cur[1].right != null) {
	que.offer(new TreeNode[] {cur[1], cur[1].right});
	}

	}

	for (Map.Entry<TreeNode, Integer> e : sumMap.entrySet()) {
	TreeNode node = e.getKey();
	int value = e.getValue();
	int v = sum - value;
	if (node.left != null) {
	node.left.val = v;
	}

	if (node.right != null) {
	node.right.val = v;
	}
	}
	}

	return root;
	}
	}

# 优化

不用每次记录当前节点的父节点，而是每次遍历一层时，更新下一层的节点值即可。

	class Solution {
	public TreeNode replaceValueInTree(TreeNode root) {
	// 在 parent 层，处理 children 层
	if (root == null) return null;
	Queue<TreeNode> que = new ArrayDeque<>();
	// 根节点直接赋值 0
	root.val = 0;

	que.offer(root);

	while (!que.isEmpty()) {
	Map<TreeNode, Integer> sumMap = new HashMap<>();
	// 记录所有父节点的所有子节点值的和
	int sum = 0;
	for (TreeNode p : que) {
	sum += p.left != null ? p.left.val : 0;
	sum += p.right != null ? p.right.val : 0;
	}

	// 更新父节点的子节点的值
	for (int i = que.size(); i > 0; --i) {
	TreeNode cur = que.poll();

	int cs = cur.left != null ? cur.left.val : 0;
	cs += cur.right != null ? cur.right.val : 0;

	if (cur.left != null) {
	cur.left.val = sum - cs;
	que.offer(cur.left);
	}

	if (cur.right != null) {
	cur.right.val = sum - cs;
	que.offer(cur.right);
	}
	}
	}

	return root;
	}
	}

# T4. 设计可以求最短路径的图类

链接：https://leetcode.cn/problems/design-graph-with-shortest-path-calculator/

# 解题思路

典型 Dijkstra 算法应用

# 提交结果

# 代码

	class Graph {
	// 边的权值：es [i][j] 表示 i -> j，有一条权值 es [i][j] 的有向边
	//es [i][j]=Integer.MAX_VALUE 表示 i -> j 为不可达
	int[][] es;
	// 节点总数
	int nodeCnt;

	public Graph(int n, int[][] edges) {
	es = new int[n][n];
	this.nodeCnt = n;

	// 初始化所有点相互之间的距离
	for (int i = 0; i < n; ++i) {
	Arrays.fill(es[i], Integer.MAX_VALUE);
	}

	for (int[] e : edges) {
	es[e[0]][e[1]] = e[2];
	}
	}

	public void addEdge(int[] edge) {
	es[edge[0]][edge[1]] = edge[2];
	}

	public int shortestPath(int node1, int node2) {
	if (node1 == node2) return 0;

	int[] dis = new int[nodeCnt];
	boolean[] vis = new boolean[nodeCnt];

	// 加入集合
	vis[node1] = true;

	// 更新 node1 -> 其他节点的直接距离
	for (int i = 0; i < nodeCnt; ++i) {
	dis[i] = es[node1][i];
	}


	// 最多松弛 nodeCnt - 1 次
	for (int i = 1; i < nodeCnt; ++i) {
	// 到下一个最短路径的点
	int nxt = -1;
	// 到下一个点的最短距离
	int minDis = Integer.MAX_VALUE;

	for (int j = 0; j < nodeCnt; ++j) {
	if (!vis[j] && dis[j] < minDis) {
	nxt = j;
	minDis = dis[j];
	}
	}

	// 没有多余的到可达点，直接退出
	// 优化：已经到达终点
	if (nxt == -1 \|\| nxt == node2) break;

	// 找到一个点
	vis[nxt] = true;

	// 松弛操作，通过 nxt 节点
	for (int j = 0; j < nodeCnt; j++) {
	if (!vis[j] // 未加入集合
	&& es[nxt][j] != Integer.MAX_VALUE // 可达
	&& minDis + es[nxt][j] < dis[j]) { // 可松弛，更新最小值
	dis[j] = minDis + es[nxt][j];
	}
	}
	}

	return dis[node2] == Integer.MAX_VALUE ? -1 : dis[node2];
	}
	}
	/**
	* Your Graph object will be instantiated and called as such:
	* Graph obj = new Graph(n, edges);
	* obj.addEdge(edge);
	* int param_2 = obj.shortestPath(node1,node2);
	*/

leetcode 题解周赛 Dijkstra

# T1. 查询网格图中每一列的宽度

# 代码

# T2. 一个数组所有前缀的分数

# 思路

# 提交结果

# 代码

# T3. 二叉树的堂兄弟节点 II

# 解题思路

# 提交结果

# 代码

# 优化

# T4. 设计可以求最短路径的图类

# 解题思路

# 提交结果

# 代码

每日一题：不邻接植花

力扣第 341 场周赛题解