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;}
};
复杂度
时间复杂度: O ( m + n ) O(m + n) O(m+n),m 是边的数量,n 是结点的数量;
空间复杂度: O ( n ) O(n) O(n)。
2926. 平衡子序列的最大和(不会,待续)
更多推荐
【LeetCode】2023.11.5 周赛
发布评论