LeetCode Biweekly Contest 102

6333. Find the Width of Columns of a Grid

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。矩阵中某一列的宽度是这一列数字的最大 字符串长度 。

• 比方说，如果 grid = [[-10], [3], [12]] ，那么唯一一列的宽度是 3 ，因为 -10 的字符串长度为 3 。

请你返回一个大小为 n 的整数数组 ans ，其中 ans[i] 是第 i 列的宽度。

一个有 len 个数位的整数 x ，如果是非负数，那么 字符串长度 为 len ，否则为 len + 1 。

测试样例

输入：grid = [[1],[22],[333]]

输出：[3]

解释：

第 0 列中，333 字符串长度为 3 。

解答：按照题意暴力运算

class Solution {
    public int[] findColumnWidth(int[][] grid) {
        int n = grid[0].length;
        int[] res = new int[n];
        for (int[] r : grid) {
            for (int i = 0; i < n; ++i) {
                res[i] = Math.max(res[i], String.valueOf(r[i]).length());
            }
        }
        return res;
    }
}

6334. Find the Score of All Prefixes of an Array

定义一个数组 arr 的 转换数组 conver 为：

• conver[i] = arr[i] + max(arr[0..i])，其中 max(arr[0..i]) 是满足 0 <= j <= i 的所有 arr[j] 中的最大值。

定义一个数组 arr 的 分数 为 arr 转换数组中所有元素的和。

给你一个下标从 0 开始长度为 n 的整数数组 nums ，请你返回一个长度为 n 的数组 ans ，其中 ans[i]是前缀 nums[0..i] 的分数。

测试样例：

输入：nums = [2,3,7,5,10]

输出：[4,10,24,36,56]

解释：

• 对于前缀 [2] ，转换数组为 [4] ，所以分数为 4 。
• 对于前缀 [2, 3] ，转换数组为 [4, 6] ，所以分数为 10 。
• 对于前缀 [2, 3, 7] ，转换数组为 [4, 6, 14] ，所以分数为 24 。
• 对于前缀 [2, 3, 7, 5] ，转换数组为 [4, 6, 14, 12] ，所以分数为 36 。
• 对于前缀 [2, 3, 7, 5, 10] ，转换数组为 [4, 6, 14, 12, 20] ，所以分数为 56 。

解答: 计算前缀最大值，然后按照题意累和一下。注意结果是long[], int[]会超范围

class Solution {
    public long[] findPrefixScore(int[] nums) {
        long[] res = new long[nums.length];
        long sum = 0;
        int max = -1;
        for (int i = 0; i < nums.length; ++i) {
            max = Math.max(max, nums[i]);
            long tmp = nums[i];
            tmp += max;
            sum += tmp;
            res[i] = sum;
        }
        return res;
    }
}

6335. Cousins in Binary Tree II

给你一棵二叉树的根 root ，请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和 。

如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为 堂兄弟 。

请你返回修改值之后，树的根 root 。

注意，一个节点的深度指的是从树根节点到这个节点经过的边数。

测试样例：

输入：root = [5,4,9,1,10,null,7]

输出：[0,0,0,7,7,null,11]

解答: 这道题目本质是树的层次遍历。在纯粹的层次遍历过程中，加入一层的累和，同时也需要记录每个节点的父节点。最后在更新原树的时候，把当堂兄弟的和减去

class Solution {
    private class TreeNodeParent {
        TreeNode node;
        TreeNode parent;

        public TreeNodeParent(TreeNode _node, TreeNode _parent) {
            node = _node;
            parent = _parent;
        }
    }

    public TreeNode replaceValueInTree(TreeNode root) {
        List<TreeNodeParent> mem = new ArrayList<>();
        mem.add(new TreeNodeParent(root, new TreeNode(0)));
        while(!mem.isEmpty()) {
            List<TreeNodeParent> next = new ArrayList<>();
            HashMap<TreeNode, Integer> add = new HashMap<>();
            int sum = 0;
            for (TreeNodeParent p : mem) {
                sum += p.node.val;
                add.put(p.parent, add.getOrDefault(p.parent, 0) + p.node.val);
                if (p.node.left != null) {
                    next.add(new TreeNodeParent(p.node.left, p.node));
                }
                if (p.node.right != null) {
                    next.add(new TreeNodeParent(p.node.right, p.node));
                }
            }

            for (TreeNodeParent p : mem) {
                p.node.val = sum - add.get(p.parent);
            }
            mem = next;
        }
        return root;
    }
}

6336. Design Graph With Shortest Path Calculator

给你一个有 n 个节点的 有向带权 图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中 edges[i] = [fromi, toi, edgeCosti] 表示从 fromi 到 toi 有一条代价为 edgeCosti 的边。

请你实现一个 Graph 类：

• Graph(int n, int[][] edges) 初始化图有 n 个节点，并输入初始边。
• addEdge(int[] edge) 向边集中添加一条边，其中 edge = [from, to, edgeCost] 。数据保证添加这条边之前对应的两个节点之间没有有向边。
• int shortestPath(int node1, int node2) 返回从节点 node1 到 node2 的路径 最小 代价。如果路径不存在，返回 -1 。一条路径的代价是路径中所有边代价之和。

测试样例：

输入：["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]
[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]

输出：[null, 6, -1, null, 6]

解答：这道题目有3个很重要的提示：

• 1 <= n <= 100
• 调用 addEdge 至多 100 次
• 调用 shortestPath 至多 100 次

这个规模可以每次调用shortestPath，用Dijstrak算法跑一下最小值就行了

class Graph {
    private List<int[]>[] map;

    public Graph(int n, int[][] edges) {
        map = new List[n];
        for (int i = 0; i < n; ++i) {
            map[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            map[e[0]].add(e);
        }
    }

    public void addEdge(int[] e) {
        map[e[0]].add(e);
    }

    public int shortestPath(int node1, int node2) {
        int[] mem = new int[map.length];
        Arrays.fill(mem, Integer.MAX_VALUE);
        mem[node1] = 0;
        TreeSet<Integer> queue = new TreeSet<>((a, b) -> (mem[a] != mem[b] ? (mem[a] - mem[b]) : (a - b)));
        queue.add(node1);
        while (!queue.isEmpty()) {
            int first = queue.first();
            queue.remove(first);
            if (first == node2) {
                return mem[node2];
            }
            int lastCost = mem[first];
            for (int[] e : map[first]) {
                if (lastCost + e[2] < mem[e[1]]) {
                    queue.remove(e[1]);
                    mem[e[1]] = lastCost + e[2];
                    queue.add(e[1]);
                }
            }
        }
        return -1;
    }
}

这周的题目，又是究极手速场了。最后一道题目蹲一个大佬非暴力算法