本文主要是介绍LeetCode-207. Course Schedule 236. Lowest Common Ancestor of a Binary Tree 210. Course Schedule,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
207. Course Schedule
class Solution {public static int[] visitStatus;public static ArrayList<ArrayList<Integer>> adjList;//邻接表public boolean canFinish(int numCourses, int[][] prerequisites) {adjList=new ArrayList<>();visitStatus=new int[numCourses];for(int i=0;i<numCourses;i++)adjList.add(new ArrayList<>());for(int[] tmp:prerequisites){adjList.get(tmp[1]).add(tmp[0]);}for(int i=0;i<numCourses;i++){if(visitStatus[i]!=0)continue;if(!dfs(i))return false;}return true;}public static boolean dfs(int i){visitStatus[i]=1;for(int j=0;j<adjList.get(i).size();j++){int m=adjList.get(i).get(j);if(visitStatus[m]==2)continue;if(visitStatus[m]==1)return false;if(!dfs(m))return false;}visitStatus[i]=2;return true;}
}
236. Lowest Common Ancestor of a Binary Tree
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {HashMap<TreeNode,TreeNode> child_parent=new HashMap<>();Stack<TreeNode> stack=new Stack<>();stack.push(root);child_parent.put(root,null);while(!child_parent.containsKey(p) || !child_parent.containsKey(q)){TreeNode node=stack.pop();if(node.left!=null){stack.push(node.left);child_parent.put(node.left,node);}if(node.right!=null){stack.push(node.right);child_parent.put(node.right,node);} }HashSet<TreeNode> set=new HashSet<>();while(p!=null){set.add(p);p=child_parent.get(p);}while(!set.contains(q)){q=child_parent.get(q);}return q;}
}
210. Course Schedule II
class Solution {public static int[] reversePost;public static int idx;public static int[] visitStatus;public static ArrayList<ArrayList<Integer>> adjList;//邻接表public int[] findOrder(int numCourses, int[][] prerequisites) {idx=numCourses-1;reversePost=new int[numCourses];adjList=new ArrayList<>();visitStatus=new int[numCourses];for(int i=0;i<numCourses;i++)adjList.add(new ArrayList<>());for(int[] tmp:prerequisites){adjList.get(tmp[1]).add(tmp[0]);}for(int i=0;i<numCourses;i++){if(visitStatus[i]!=0)continue;if(!dfs(i))return new int[0];}return reversePost;}public static boolean dfs(int i){visitStatus[i]=1;for(int j=0;j<adjList.get(i).size();j++){int m=adjList.get(i).get(j);if(visitStatus[m]==2)continue;if(visitStatus[m]==1)return false;if(!dfs(m))return false;}visitStatus[i]=2;reversePost[idx--]=i;return true;}
}
这篇关于LeetCode-207. Course Schedule 236. Lowest Common Ancestor of a Binary Tree 210. Course Schedule的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!