aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--leetcode.h2
-rw-r--r--path_max_probability.c45
-rw-r--r--path_max_probability.cpp9
-rw-r--r--path_max_probability.py64
4 files changed, 93 insertions, 27 deletions
diff --git a/leetcode.h b/leetcode.h
index 6cdd131..0c0794b 100644
--- a/leetcode.h
+++ b/leetcode.h
@@ -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
+ )
+ )