Untitled
unknown
plain_text
2 years ago
2.1 kB
7
Indexable
1. Greedy Algorithm : public class GreedyAlgorithm { int currentLevel = 0; final int maxLevel = 3; SocialConnector sc; public GreedyAlgorithm(SocialConnector sc) { this.sc = sc; } } public long findMostFollowersPath(String account) { long max = 0; SocialUser toFollow = null; List followers = sc.getFollowers(account); for (SocialUser el : followers) { long followersCount = el.getFollowersCount(); if (followersCount > max) { toFollow = el; max = followersCount; } } if (currentLevel < maxLevel - 1) { currentLevel++; max += findMostFollowersPath(toFollow.getUsername()); } return max; } 2. Recursive Algorithm : static class Node { Node left; Node right; int data; }; static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.left = null; temp.right = null; return temp; } static void printPath(int Data, HashMap<Integer, Integer> parent) { if (parent.get(Data) == Data) return; printPath(parent.get(Data), parent); System.out.print(parent.get(Data) + " "); } static void leftMostShortest(Node root) { Queue<Node> q = new LinkedList<>(); q.add(root); int LeafData = -1; Node temp = null; HashMap<Integer, Integer> parent = new HashMap<>(); parent.put(root.data, root.data);= while (!q.isEmpty()) { temp = q.poll(); if (temp.left == null && temp.right == null) { LeafData = temp.data; break; } else { if (temp.left != null) { q.add(temp.left); // Set temp's left node's parent // as temp parent.put(temp.left.data, temp.data); } if (temp.right != null) { q.add(temp.right); parent.put(temp.right.data,temp.data); } } } printPath(LeafData, parent); System.out.println(LeafData + " "); } 3. Dynamic Programming : class GFG { static int[] dp = new int[100]; static void dfs(int[] a, Vector<Integer>[] v, int u, int parent) { int maximum = 0; for (int child : v[u]) { if (child == parent) continue; dfs(a, v, child, u);] maximum = Math.max(maximum, dp[child]); } dp[u] += maximum; } Vector<Integer>[] v) { dfs(a, v, 1, 0); return dp[1]; } } Was this answer helpful? Post a question Answers from our experts for your tough homework questions 20 questions left - Renews Jan. 15, 2023 Post a question text
Editor is loading...