diff options
-rw-r--r-- | find_champion_2.c | 40 | ||||
-rw-r--r-- | find_champion_2.py | 29 |
2 files changed, 69 insertions, 0 deletions
diff --git a/find_champion_2.c b/find_champion_2.c new file mode 100644 index 0000000..a6282bb --- /dev/null +++ b/find_champion_2.c @@ -0,0 +1,40 @@ +// 2924. Find Champion II +#include "leetcode.h" + +/* + * there are 'n' teams numbered from 0 to 'n - 1' in a tournament; each team is + * also a node in DAG. you are given the integer 'n' and a 0-indexed 2d integer + * array 'edges' of length 'm' representing the DAG, where 'edges[i] = [u_i, + * v_i]' indicates that is a directed edge from team 'u_i' to team 'v_i' in the + * graph. a directed edge from 'a' to 'b' in the graph means that team 'a' is + * strong than team 'b' and team 'b' is weaker than team 'a'. return the team + * that will be the champion of the tournament if there is a unique champion, + * otherwise return -1. + */ + +int findChampion(int n, int **edges, int edgesSize, int *edgesColSize) { + char state[n]; + memset(state, 'w', sizeof(state)); + for (int i = 0; i < edgesSize; i++) + state[edges[i][1]] = 'l'; + int cnt = 0, ans = 0; + for (int i = 0; i < n; i++) + if (state[i] == 'w') { + cnt++; + ans = i; + } + return cnt == 1 ? ans : -1; +} + +int main() { + int e1i[2][2] = {{0, 1}, {1, 2}}, e2i[3][2] = {{0, 2}, {1, 3}, {1, 2}}; + struct two_d_arr e1, e2; + two_d_arr_init(&e1, 2, 2, e1i); + two_d_arr_init(&e2, 3, 2, e2i); + printf("%d\n", findChampion(3, e1.arr, e1.row_size, e1.col_size)); // expect: + // 0 + printf("%d\n", + findChampion(4, e2.arr, e2.row_size, e2.col_size)); // expect: -1 + two_d_arr_free(&e1); + two_d_arr_free(&e2); +} diff --git a/find_champion_2.py b/find_champion_2.py new file mode 100644 index 0000000..ac139fe --- /dev/null +++ b/find_champion_2.py @@ -0,0 +1,29 @@ +# 2924. Find Champion II + +""" +there are 'n' teams numbered from 0 to 'n - 1' in a tournament; each team is +also a node in DAG. you are given the integer 'n' and a 0-indexed 2d integer +array 'edges' of length 'm' representing the DAG, where 'edges[i] = [u_i, +v_i]' indicates that is a directed edge from team 'u_i' to team 'v_i' in the +graph. a directed edge from 'a' to 'b' in the graph means that team 'a' is +strong than team 'b' and team 'b' is weaker than team 'a'. return the team +that will be the champion of the tournament if there is a unique champion, +otherwise return -1. +""" + + +class Solution(object): + def findChampion(self, n, edges): + """ + :type n: int + :type edges: List[List[int]] + :rtype: int + """ + weak = {b for a, b in edges} + return -1 if len(weak) < n - 1 else n * (n - 1) // 2 - sum(weak) + + +if __name__ == "__main__": + obj = Solution() + print(obj.findChampion(n=3, edges=[[0, 1], [1, 2]])) + print(obj.findChampion(n=4, edges=[[0, 2], [1, 3], [1, 2]])) |