【LeetCode】2023.11.5 周赛

编程入门行业动态更新时间:2024-10-26 22:27:49

【<a href=https://www.elefans.com/category/jswz/34/1769930.html style= LeetCode】2023.11.5 周赛"/>

【LeetCode】2023.11.5 周赛

2923. 找到冠军 I

题意

对于二维矩阵 grid[][]，若 grid[i][j] == 1，则说明 i 队比 j 队强；
求冠军。

解答逆向思维

若 grid[i][j] == 1，则说明 i 队比 j 队强，也说明 j 队比 i 队弱。

而如果不存在强于 a 队的队伍，则 a 为冠军。

因此，如果对于所有的 i，grid[i][a] != 1 成立，就说明没有比 a 强的队伍，那么 a 队就是冠军。

class Solution {
public:int findChampion(vector<vector<int>>& grid) {int n = grid.size();for(int j = 0; j < n; j++){bool flag = true;for(int i = 0; i < n; i++){if(i != j && grid[i][j] == 1){flag = false;break;}}if(flag) return j;}return -1;}
};

复杂度

时间复杂度： O ( n 2 ) O(n^2) O(n2)
空间复杂度： O ( 1 ) O(1) O(1)

2924. 找到冠军 II

题意

有一张有向无环图，若图中存在边 (a, b)，则说明 a 队比 b 队强。
求冠军。若唯一，返回冠军；若不唯一或不存在，返回 -1。

解答入度

若图中存在边 (a, b)，则说明 a 队比 b 队强，或者说， b 队比 a 队弱。因此，对于图中的点来说，他的 入度表示了比它强的队伍的数量。

首先计算每个点的入度；
如果存在两个及以上入度为 0 的点，则冠军不唯一，返回 -1；如果不存在入度为 0 的点，则冠军不存在（有环），返回 -1；
如果仅存在一个入度为 0 的点 a，那么，它就是冠军。因为如果 a 不是冠军，那么：
- 要么存在 b 队比 a 队强（那么就存在边 (b, a)，a 的入度不为 0），
- 要么存在 b 与 a 不连通（那么就存在两个连通分支，入度为 0 的点不止一个），
- 两者都不可能，因此 a 一定是冠军。

class Solution {
public:int findChampion(int n, vector<vector<int>>& edges) {vector<int> in(n, 0);vector<vector<int> > m_edges(n);for(auto e : edges){int u = e[0], v = e[1];m_edges[u].push_back(v);in[v]++;}int ans = -1;queue<int> q;int cnt = 0;for(int i = 0; i < n; i++){if(in[i] == 0)q.push(i);}if(q.size() != 1) return -1;    // 多个入度为0的点ans = q.front();return ans;}
};

复杂度

时间复杂度： O ( m + n ) O(m + n) O(m+n)，m 为边的数量，n 为点的数量；
空间复杂度： O ( n ) O(n) O(n)

2925. 在树上执行操作以后得到的最大分数

题意

给定一棵树，根为 0
要确保每条根到叶子结点的路径上都剩有一个结点
求可以获得的最大份数

解答递归

树的问题一般都是宏观上自上而下递归，回溯上自下而上考虑的。

从孩子的角度考虑：

从叶子结点开始，因为每条路径都需要至少一个结点，那么不妨就假设留下叶子结点 leaf。因此，最开始的得分（obtain）为 0，而留下的得分（remain）为 leaf->value；
然后向上回溯，显然，回溯经过的点都可能影响得分。假设遇到结点 node，而 p->value < remain，那么显然，我们可以将结点 node 作为它相关的路径上的结点，而把之前留下的结点作为新的得分收下；反之，因为这些路径上已经有节点了，所以我收下结点 node 作为新的得分。

从父亲的角度考虑：
对于一个非叶节点 node 来说，假设它有孩子结点 child1，child2，child3。那么在比较 p->value 和 remain 时，应当是比较 p->value 和 remain(child1) + child(2) + child(3)，因为假使我选择留下当前结点 node，那么它可以保证以他为根的子树所有路径健康，所以我可以收回所有之前留下的结点。

题目里还有一个坑是：给定的是无向边，但是在遍历树时，是一个自上而下的有向遍历。因此我选择了先用层次遍历记录每个结点的层，从而来分辨父亲结点和孩子结点。

class Solution {
public:// 返回留下的值int recur(vector<vector<int>>& g, int node, vector<int>& values, long long& ans, vector<int>& rank){long long tmp = 0;for(auto v : g[node])   // 遍历 node 的邻接点{if(rank[v] > rank[node])  // v 是 node 的孩子tmp += 1ll * recur(g, v, values, ans, rank);    // 所有孩子留下的和}int res = 0;if(tmp == 0){res = values[node];return res;}if(tmp > values[node]){ans += 1ll * tmp;   // 拿走所有孩子，留它res = values[node];}else{ans+=values[node];  // 拿走他，留孩子们res=tmp;}return res;}long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {int n = values.size();vector<vector<int> > g(n);vector<int> rank(n, -1);for(auto e : edges){int u = e[0], v = e[1];g[u].push_back(v);g[v].push_back(u);}int r = 0;queue<int> q;q.push(0);while(!q.empty()){for(int i = q.size(); i > 0; i--){int u = q.front();q.pop();rank[u] = r;for(auto v :g[u]){if(rank[v] == -1) q.push(v);}}r++;}long long ans = 0;recur(g, 0, values, ans, rank);return ans;}
};