diff options
-rw-r--r-- | longest_path_diff_adjacent_char.c | 74 | ||||
-rw-r--r-- | longest_path_diff_adjacent_char.cpp | 48 | ||||
-rw-r--r-- | longest_path_diff_adjacent_char.py | 48 | ||||
-rw-r--r-- | longest_path_diff_adjacent_char.rs (renamed from longest_path_diff_char.rs) | 32 | ||||
-rw-r--r-- | longest_path_diff_char.cpp | 36 |
5 files changed, 193 insertions, 45 deletions
diff --git a/longest_path_diff_adjacent_char.c b/longest_path_diff_adjacent_char.c new file mode 100644 index 0000000..e77ae15 --- /dev/null +++ b/longest_path_diff_adjacent_char.c @@ -0,0 +1,74 @@ +// 2246. Longest Path With Different Adjacent Characters +#include "leetcode.h" + +/* + * you are given a tree (ie. a connected undirected graph that has no cycles) + * rooted at node '0' consisting of 'n' nodes numbered from '0' to 'n - 1'. the + * tree is represented by a 0-indexed array 'parent' of size 'n' where + * 'parent[i]' is the parent of node 'i'. since node 0 is the root, 'parent[0] = + * -1'. you are also given a string 's' of length 'n', where 's[i]' is the + * character assigned to node 'i'. return the legnth of the longest path in the + * tree such that no pair of adjacnet nodes on the path have the same character + * assigned to them. + */ + +struct node { + bool visited; + int children; + int *adjacent_list; +}; + +void dfs(int curr_node, int *dist, struct node **root, int parent_size, char *s, + int *res) { + int curr_child; + dist[curr_node] = 1; + root[curr_node]->visited = true; + for (int i = 0; i < root[curr_node]->children; i++) { + curr_child = root[curr_node]->adjacent_list[i]; + if (!root[curr_child]->visited) { + dfs(curr_child, dist, root, parent_size, s, res); + if (s[curr_node] != s[curr_child]) { + *res = fmax(*res, dist[curr_node] + dist[curr_child]); + dist[curr_node] = fmax(dist[curr_node], dist[curr_child] + 1); + } + } + } +} + +int longestPath(int *parent, int parentSize, char *s) { + int ans = 1; + int *cnt = (int *)calloc(parentSize, sizeof(int)); + int *dist = (int *)calloc(parentSize, sizeof(int)); + struct node **root = + (struct node **)malloc(parentSize * sizeof(struct node *)); + struct node *curr_node; + for (int i = 1; i < parentSize; i++) { + cnt[parent[i]]++; + cnt[i]++; + } + for (int i = 0; i < parentSize; i++) { + root[i] = (struct node *)malloc(sizeof(struct node)); + root[i]->visited = false; + root[i]->children = 0; + root[i]->adjacent_list = (int *)malloc(cnt[i] * sizeof(int)); + } + for (int i = 1; i < parentSize; i++) { + curr_node = root[parent[i]]; + curr_node->adjacent_list[curr_node->children] = i; + curr_node->children++; + } + dfs(0, dist, root, parentSize, s, &ans); + for (int i = 0; i < parentSize; i++) { + free(root[i]->adjacent_list); + free(root[i]); + } + free(cnt), free(dist), free(root); + return ans; +} + +int main() { + int p1[] = {-1, 0, 0, 1, 1, 2}, p2[] = {-1, 0, 0, 0}; + char *s1 = "abacbe", *s2 = "aabc"; + printf("%d\n", longestPath(p1, ARRAY_SIZE(p1), s1)); // expect: 3 + printf("%d\n", longestPath(p2, ARRAY_SIZE(p2), s2)); // expect: 3 +} diff --git a/longest_path_diff_adjacent_char.cpp b/longest_path_diff_adjacent_char.cpp new file mode 100644 index 0000000..0f60da9 --- /dev/null +++ b/longest_path_diff_adjacent_char.cpp @@ -0,0 +1,48 @@ +// 2246. Longest Path With Different Adjacent Characters +#include "leetcode.h" + +/* + * you are given a tree (ie. a connected undirected graph that has no cycles) + * rooted at node '0' consisting of 'n' nodes numbered from '0' to 'n - 1'. the + * tree is represented by a 0-indexed array 'parent' of size 'n' where + * 'parent[i]' is the parent of node 'i'. since node 0 is the root, 'parent[0] = + * -1'. you are also given a string 's' of length 'n', where 's[i]' is the + * character assigned to node 'i'. return the legnth of the longest path in the + * tree such that no pair of adjacnet nodes on the path have the same character + * assigned to them. + */ + +class Solution { +public: + int longestPath(vector<int> &parent, string s) { + int n = parent.size(), ans = 1; + queue<int> q; + vector<int> cnt(n), top1(n, 1), top2(n, 1); + for (int i = 1; i < n; ++i) + ++cnt[parent[i]]; + for (int i = 1; i < n; ++i) + if (!cnt[i]) + q.push(i); + while (!q.empty() && q.front()) { + int i = q.front(), p = parent[i]; + q.pop(); + if (int len = 1 + (s[i] != s[p] ? top1[i] : 0); top1[p] <= len) { + top2[p] = top1[p]; + top1[p] = len; + } else + top2[p] = max(top2[p], len); + if (--cnt[p] == 0) { + q.push(p); + ans = max(ans, top1[p] + top2[p] - 1); + } + } + return ans; + } +}; + +int main() { + Solution obj; + vector<int> p1 = {-1, 0, 0, 1, 1, 2}, p2 = {-1, 0, 0, 0}; + printf("%d\n", obj.longestPath(p1, "abacbe")); // expect: 3 + printf("%d\n", obj.longestPath(p2, "aabc")); // expect: 3 +} diff --git a/longest_path_diff_adjacent_char.py b/longest_path_diff_adjacent_char.py new file mode 100644 index 0000000..92f4616 --- /dev/null +++ b/longest_path_diff_adjacent_char.py @@ -0,0 +1,48 @@ +# 2246. Longest Path With Different Adjacent Characters + +""" +you are given a tree (ie. a connected undirected graph that has no cycles) +rooted at node '0' consisting of 'n' nodes numbered from '0' to 'n - 1'. the +tree is represented by a 0-indexed array 'parent' of size 'n' where +'parent[i]' is the parent of node 'i'. since node 0 is the root, 'parent[0] = +-1'. you are also given a string 's' of length 'n', where 's[i]' is the +character assigned to node 'i'. return the legnth of the longest path in the +tree such that no pair of adjacnet nodes on the path have the same character +assigned to them. +""" + + +class Solution(object): + def longestPath(self, parent, s): + """ + :type parent: List[int] + :type s: str + :rtype: int + """ + ans, n = 0, len(parent) + g = [[] for _ in range(n)] + for i in range(n): + if parent[i] != -1: + g[parent[i]].append(i) + + def dfs(x): + nonlocal ans + l1, l2 = 0, 0 + for i in g[x]: + val = dfs(i) + if s[x] != s[i]: + if val > l2: + l2 = val + if l2 > l1: + l1, l2 = l2, l1 + ans = max(ans, l1 + l2 + 1) + return l1 + 1 + + dfs(0) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.longestPath(parent=[-1, 0, 0, 1, 1, 2], s="abacbe")) + print(obj.longestPath(parent=[-1, 0, 0, 0], s="aabc")) diff --git a/longest_path_diff_char.rs b/longest_path_diff_adjacent_char.rs index 4539ad3..b35568c 100644 --- a/longest_path_diff_char.rs +++ b/longest_path_diff_adjacent_char.rs @@ -1,13 +1,24 @@ -use std::collections::HashMap; +// 2246. Longest Path With Different Adjacent Characters + +/* + * you are given a tree (ie. a connected undirected graph that has no cycles) + * rooted at node '0' consisting of 'n' nodes numbered from '0' to 'n - 1'. the + * tree is represented by a 0-indexed array 'parent' of size 'n' where + * 'parent[i]' is the parent of node 'i'. since node 0 is the root, 'parent[0] = + * -1'. you are also given a string 's' of length 'n', where 's[i]' is the + * character assigned to node 'i'. return the legnth of the longest path in the + * tree such that no pair of adjacnet nodes on the path have the same character + * assigned to them. + */ + use std::cmp::max; +use std::collections::HashMap; struct Solution; -static mut res: i32 = 0; +static mut res: i32 = 0; impl Solution { pub fn longest_path(parent: Vec<i32>, s: String) -> i32 { - unsafe { - res = 0 - } + unsafe { res = 0 } let mut graph = HashMap::new(); for (i, &u) in parent.iter().enumerate() { if u == -1 { @@ -56,8 +67,11 @@ impl Solution { } fn main() { - let parent1 = vec![-1,0,0,1,1,2]; - let parent2 = vec![-1,0,0,0]; - println!("{}", Solution::longest_path(parent1, String::from("abacbe"))); //expect: 3 - println!("{}", Solution::longest_path(parent2, String::from("aabc"))); //expect: 3 + let parent1 = vec![-1, 0, 0, 1, 1, 2]; + let parent2 = vec![-1, 0, 0, 0]; + println!( + "{}", + Solution::longest_path(parent1, String::from("abacbe")) + ); //expect: 3 + println!("{}", Solution::longest_path(parent2, String::from("aabc"))); //expect: 3 } diff --git a/longest_path_diff_char.cpp b/longest_path_diff_char.cpp deleted file mode 100644 index 8eb9878..0000000 --- a/longest_path_diff_char.cpp +++ /dev/null @@ -1,36 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - int longestPath(vector<int> &parent, string s) { - int n = parent.size(), ans = 1; - queue<int> q; - vector<int> cnt(n), top1(n, 1), top2(n, 1); - for (int i = 1; i < n; ++i) - ++cnt[parent[i]]; - for (int i = 1; i < n; ++i) - if (cnt[i] == 0) - q.push(i); - while (!q.empty() && q.front() != 0) { - int i = q.front(), p = parent[i]; - q.pop(); - if (int len = 1 + (s[i] != s[p] ? top1[i] : 0); top1[p] <= len) { - top2[p] = top1[p]; - top1[p] = len; - } else - top2[p] = max(top2[p], len); - if (--cnt[p] == 0) { - q.push(p); - ans = max(ans, top1[p] + top2[p] - 1); - } - } - return ans; - } -}; - -int main() { - Solution obj; - vector<int> parent1 = {-1, 0, 0, 1, 1, 2}, parent2 = {-1, 0, 0, 0}; - cout << obj.longestPath(parent1, "abacbe") << endl; // expect: 3 - cout << obj.longestPath(parent2, "aabc") << endl; // expect: 3 -} |