diff options
-rw-r--r-- | leetcode.h | 2 | ||||
-rw-r--r-- | path_max_probability.c | 45 | ||||
-rw-r--r-- | path_max_probability.cpp | 9 | ||||
-rw-r--r-- | path_max_probability.py | 64 |
4 files changed, 93 insertions, 27 deletions
@@ -69,7 +69,7 @@ void listnode_free(struct ListNode *head); struct TreeNode *treenode_create(int val); void treenode_print(struct TreeNode *root); -void treenode_free(struct treeTreeNode *root); +void treenode_free(struct TreeNode *root); struct Node *node_create(int val, int numChildren); void node_print(struct Node *root, int depth); diff --git a/path_max_probability.c b/path_max_probability.c index 11e2b41..0513b93 100644 --- a/path_max_probability.c +++ b/path_max_probability.c @@ -1,8 +1,5 @@ // 1514. Path with Maximum Probability -#include <math.h> -#include <stdbool.h> -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * given an undirected weighted graph of 'n' nodes (0-indexed). represented by @@ -14,27 +11,25 @@ * will be accepted if it differs from the correct answer by at most '1e-5' */ -#define LOWER_BOUND 1e-5 - typedef struct { int next; double val; } node; void dfs(int n, bool *visited, double val, double *ans, int curr, int end, - int *cn, node **map) { + int *cnt, node **map) { if (curr == end) *ans = fmax(*ans, val); if (*ans >= val) return; - if (val - *ans <= LOWER_BOUND) + if (val - *ans <= 1e-5) return; if (visited[curr]) return; visited[curr] = true; - for (int i = 0; i < cn[curr]; i++) { + for (int i = 0; i < cnt[curr]; i++) { double new_val = val * map[curr][i].val; - dfs(n, visited, new_val, ans, map[curr][i].next, end, cn, map); + dfs(n, visited, new_val, ans, map[curr][i].next, end, cnt, map); } visited[curr] = false; } @@ -43,17 +38,17 @@ double maxProbability(int n, int **edges, int edges_size, int *edges_col_size, double *succ_prob, int succ_prob_size, int start, int end) { double ans = 0; - bool *visited = calloc(n, sizeof(bool)); - int *cn = calloc(n, sizeof(int)); - node **map = calloc(n, sizeof(node *)); + bool *visited = (bool *)calloc(n, sizeof(bool)); + int *cnt = (int *)calloc(n, sizeof(int)); + node **map = (node **)calloc(n, sizeof(node *)); for (int i = 0; i < edges_size; i++) { - cn[edges[i][0]]++; - cn[edges[i][1]]++; + cnt[edges[i][0]]++; + cnt[edges[i][1]]++; } for (int i = 0; i < n; i++) - if (cn[i]) - map[i] = malloc(cn[i] * sizeof(node)); - int *m_idx = calloc(n, sizeof(int)); + if (cnt[i]) + map[i] = (node *)malloc(cnt[i] * sizeof(node)); + int *m_idx = (int *)calloc(n, sizeof(int)); for (int i = 0; i < edges_size; i++) { int prob = edges[i][0], next = edges[i][1], idx = m_idx[prob]; map[prob][idx].next = next; @@ -66,12 +61,20 @@ double maxProbability(int n, int **edges, int edges_size, int *edges_col_size, map[prob][idx].val = succ_prob[i]; m_idx[prob]++; } - dfs(n, visited, 1.0, &ans, start, end, cn, map); + dfs(n, visited, 1.0, &ans, start, end, cnt, map); free(visited); for (int i = 0; i < n; i++) - if (cn[i]) + if (cnt[i]) free(map[i]); - free(cn); + free(cnt); free(map); return ans; } + +int main() { + int edges[3][2] = {{0, 1}, {1, 2}, {0, 2}}, edges_col_size = 3; + double succ_prob[] = {0.5, 0.5, 0.2}; + printf("%f\n", maxProbability(3, (int **)edges, ARRAY_SIZE(edges), + &edges_col_size, succ_prob, + ARRAY_SIZE(succ_prob), 0, 2)); // expect: 0.2500 +} diff --git a/path_max_probability.cpp b/path_max_probability.cpp index 12eb644..0a64961 100644 --- a/path_max_probability.cpp +++ b/path_max_probability.cpp @@ -32,12 +32,11 @@ public: int node = top.second; if (!seen[node]) { seen[node]++; - for (auto to : vvp[node]) { + for (auto to : vvp[node]) if (mx[to.first] < to.second * prob_a) { mx[to.first] = to.second * prob_a; pqp.push({mx[to.first], to.first}); } - } } } return mx[end]; @@ -46,8 +45,8 @@ public: int main() { Solution obj; - vvd(int) e = {{0, 1}, {1, 2}, {0, 2}}; + vvd(int) e1 = {{0, 1}, {1, 2}, {0, 2}}, e2 = {{0, 1}, {1, 2}, {0, 2}}; vector<double> sp1 = {0.5, 0.5, 0.2}, sp2 = {0.5, 0.5, 0.3}; - printf("%f\n", obj.maxProbability(3, e, sp1, 0, 2)); // expect: 0.25000 - printf("%f\n", obj.maxProbability(3, e, sp2, 0, 2)); // expect: 0.30000 + printf("%f\n", obj.maxProbability(3, e1, sp1, 0, 2)); // expect: 0.25000 + printf("%f\n", obj.maxProbability(3, e2, sp2, 0, 2)); // expect: 0.30000 } diff --git a/path_max_probability.py b/path_max_probability.py new file mode 100644 index 0000000..5f49d42 --- /dev/null +++ b/path_max_probability.py @@ -0,0 +1,64 @@ +# 1514. Path with Maximum Probability +import collections + +""" +given an undirected weighted graph of 'n' nodes (0-indexed). represented by +an edge list where 'edges[i] = [a, b]' is an undirected edge connecting the +nodes 'a' and 'b' with a probability of success of traversing that edge +'succ_prob[i]'. given two nodes 'start, end', find the path with the maximum +probability of success to go from 'start' to 'end' and return its success +probability. if there is no path from 'start' to 'end', return 0. your answer +will be accepted if it differs from the correct answer by at most '1e-5' +""" + + +class Solution(object): + def maxProbability(self, n, edges, succProb, start_node, end_node): + """ + :type n: int + :type edges: List[List[int]] + :type succProb: List[float] + :type start_node: int + :type end_node: int + :rtype: float + """ + g, dq = collections.defaultdict(list), collections.deque([start_node]) + for i, (a, b) in enumerate(edges): + g[a].append([b, i]) + g[b].append([a, i]) + p = [0.0] * n + p[start_node] = 1.0 + while dq: + curr = dq.popleft() + for n, i in g[curr]: + if p[curr] * succProb[i] > p[n]: + p[n] = p[curr] * succProb[i] + dq.append(n) + return p[end_node] + + +if __name__ == "__main__": + obj = Solution() + print( + obj.maxProbability( + n=3, + edges=[[0, 1], [1, 2], [0, 2]], + succProb=[0.5, 0.5, 0.2], + start_node=0, + end_node=2, + ) + ) + print( + obj.maxProbability( + n=3, + edges=[[0, 1], [1, 2], [0, 2]], + succProb=[0.5, 0.5, 0.3], + start_node=0, + end_node=2, + ) + ) + print( + obj.maxProbability( + n=3, edges=[[0, 1]], succProb=[0.5], start_node=0, end_node=2 + ) + ) |