leetcode biweekly contest 102

感觉就是纯手速场的题目了，没什么意思。

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

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

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

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

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

示例 1：

输入：grid = [[1],[22],[333]]
输出：[3]
解释：第 0 列中，333 字符串长度为 3 。

示例 2：

输入：grid = [[-15,1,3],[15,7,12],[5,6,-2]]
输出：[3,1,2]
解释：
第 0 列中，只有 -15 字符串长度为 3 。
第 1 列中，所有整数的字符串长度都是 1 。
第 2 列中，12 和 -2 的字符串长度都为 2 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-109 <= grid[r][c] <= 109

地址

https://leetcode.cn/contest/biweekly-contest-102/problems/find-the-width-of-columns-of-a-grid/

题意

直接枚举

思路

直接枚举所有的列，并求出每列中的数字转换为字符串后的最大长度即可。
复杂度分析：

时间复杂度：$O(m\times n \log U)$。
空间复杂度：$O(\log u)$。

代码

class Solution {
public:
    vector<int> findColumnWidth(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> res(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res[i] = max(res[i], (int)to_string(grid[j][i]).size());
            }
        }
        return res;
    }
};

6334. 一个数组所有前缀的分数

定义一个数组 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] 的分数。

示例 1：

输入：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 。

示例 2：

输入：nums = [1,1,2,4,8,16]
输出：[2,4,8,16,32,64]
解释：
对于前缀 [1] ，转换数组为 [2] ，所以分数为 2 。
对于前缀 [1, 1]，转换数组为 [2, 2] ，所以分数为 4 。
对于前缀 [1, 1, 2]，转换数组为 [2, 2, 4] ，所以分数为 8 。
对于前缀 [1, 1, 2, 4]，转换数组为 [2, 2, 4, 8] ，所以分数为 16 。
对于前缀 [1, 1, 2, 4, 8]，转换数组为 [2, 2, 4, 8, 16] ，所以分数为 32 。
对于前缀 [1, 1, 2, 4, 8, 16]，转换数组为 [2, 2, 4, 8, 16, 32] ，所以分数为 64 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109

地址

https://leetcode.cn/problems/convert-an-array-into-a-2d-array-with-conditions/

题意

前缀和

思路

题目比较简单，首先我们求出数组 $arr$ 的每个元素，其中每个元素的值为 $nums[i]$ 加上前 $i$ 个元素的最大值，然后其 $arr$ 的前缀和数组即可。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为数组的长度。遍历两遍数组即可。
空间复杂度：$O(n)$，其中 $n$ 为数组的长度。

代码

class Solution {
public:
    vector<long long> findPrefixScore(vector<int>& nums) {
        int n = nums.size();
        vector<long long> res(n);
        vector<int> arr(n);
        int curr = 0;
        for (int i = 0; i < n; i++) {
            curr = max(curr, nums[i]);
            arr[i] = nums[i] + curr;
        }
        res[0] = arr[0];
        for (int i = 1; i < n; i++) {
            res[i] = arr[i] + res[i - 1];
        }
        return res;
    }
};

6335. 二叉树的堂兄弟节点 II

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

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

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

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

示例 1：

输入：root = [5,4,9,1,10,null,7]
输出：[0,0,0,7,7,null,11]
解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
- 值为 5 的节点没有堂兄弟，所以值修改为 0 。
- 值为 4 的节点没有堂兄弟，所以值修改为 0 。
- 值为 9 的节点没有堂兄弟，所以值修改为 0 。
- 值为 1 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。
- 值为 10 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。
- 值为 7 的节点有两个堂兄弟，值分别为 1 和 10 ，所以值修改为 11 。

示例 2：

输入：root = [3,1,2]
输出：[0,0,0]
解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
- 值为 3 的节点没有堂兄弟，所以值修改为 0 。
- 值为 1 的节点没有堂兄弟，所以值修改为 0 。
- 值为 2 的节点没有堂兄弟，所以值修改为 0 。

提示：

树中节点数目的范围是 [1, 105] 。
1 <= Node.val <= 104

地址

https://leetcode.cn/contest/biweekly-contest-102/problems/cousins-in-binary-tree-ii/

题意

二叉树层次遍历，广度优先搜索

思路

题目比较简单了，我们按照层次遍历二叉树，每次遍历二叉树的每一层，并将每一层的叶子节点的值进行求和：
- 依次对当前节点的孩子节点进行计算，总的和减去当前节点的孩子节点的值即为当前孩子节点的最终结果；
- 按照上述解法，我们只需遍历一遍二叉树即可。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为节点的数目。
空间复杂度：$O(n)$，其中 $n$ 为节点的数目。

代码

class Solution {
public:
  
    TreeNode* replaceValueInTree(TreeNode* root) {
        queue<TreeNode *> qu;
        root->val = 0;
        qu.emplace(root);
        while (!qu.empty()) {
            int sz = qu.size();
            long long tot = 0;
            vector<TreeNode *> arr;
            for (int i = 0; i < sz; i++) {
                TreeNode *curr = qu.front();
                qu.pop();
                arr.emplace_back(curr);
                if (curr->left) {
                    qu.emplace(curr->left);
                    tot += curr->left->val;
                }
                if (curr->right) {
                    qu.emplace(curr->right);
                    tot += curr->right->val;
                }
            }
            for (int i = 0; i < sz; i++) {
                int val = tot;
                TreeNode *curr = arr[i];
                if (curr->left) val -= curr->left->val;
                if (curr->right) val -= curr->right->val;    
                if (curr->left) {
                     curr->left->val = val;
                }
                if (curr->right) {
                    curr->right->val = val;
                }
            }
        }
        return root;
    }
};

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

给你一个有 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 。一条路径的代价是路径中所有边代价之和。

示例 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]

解释：
Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);
g.shortestPath(3, 2); // 返回 6 。从 3 到 2 的最短路径如第一幅图所示：3 -> 0 -> 1 -> 2 ，总代价为 3 + 2 + 1 = 6 。
g.shortestPath(0, 3); // 返回 -1 。没有从 0 到 3 的路径。
g.addEdge([1, 3, 4]); // 添加一条节点 1 到节点 3 的边，得到第二幅图。
g.shortestPath(0, 3); // 返回 6 。从 0 到 3 的最短路径为 0 -> 1 -> 3 ，总代价为 2 + 4 = 6 。

提示：

1 <= n <= 100
0 <= edges.length <= n * (n - 1)
edges[i].length == edge.length == 3
0 <= fromi, toi, from, to, node1, node2 <= n - 1
1 <= edgeCosti, edgeCost <= 106
图中任何时候都不会有重边和自环。
调用 addEdge 至多 100 次。
调用 shortestPath 至多 100 次。

地址

https://leetcode.cn/contest/biweekly-contest-102/problems/design-graph-with-shortest-path-calculator/

题意

dijistra算法

思路

由于题目给定的节点数目只有 $100$ 个，因此解法就变的非常容易了，我们只需要查询时求一遍最短路径即可。速度较快的即可用堆即可。
复杂度分析：

时间复杂度：$O((n + m) \log n)$，其中 $n$ 为节点的数目,$m$ 表示边的数目。
空间复杂度：$O(n + m)$，其中 $n$ 为节点的数目,$m$ 表示边的数目。

代码

class Graph {
public:
    Graph(int n, vector<vector<int>>& edges) {
        this->n = n;
        this->graph = vector<vector<pair<int, int>>>(n);
        for (int i = 0; i < edges.size(); i++) {
            int x = edges[i][0];
            int y = edges[i][1];
            int cost = edges[i][2];
            graph[x].emplace_back(y, cost);
        }
    }
    
    void addEdge(vector<int> edge) {
        
        int x = edge[0];
        int y = edge[1];
        int cost = edge[2];
        graph[x].emplace_back(y, cost);
    }
    
    int shortestPath(int node1, int node2) {
        priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>>> pq;
        vector<int> dist(n, INT_MAX);
        dist[node1] = 0;
        pq.emplace(0, node1);
        
        while (!pq.empty()) {
            auto [cost, x] = pq.top();
            pq.pop();
            if (x == node2) {
                return cost;
            }
            for (auto [y, c] : graph[x]) {
                if (dist[y] > cost + c) {
                    dist[y] = cost + c;
                    pq.emplace(cost + c, y);
                }
            }
        }
        return -1;
    }
private:
    vector<vector<pair<int, int>>> graph;
    int n;
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛题解

← leetcode biweekly contest 101 leetcode weekly contest 339 →

扫描二维码，分享此文章