Week3-2016

course-sched.java

public boolean canFinish(int numCourses, int[][] prerequisites) {
	    if(prerequisites == null){
	        throw new IllegalArgumentException("Invalid Prerequisites");
	    }
	 
	    int p_len = prerequisites.length;
	 
	    if(p_len == 0||numCourses == 0){
	        return true;
	    }
	 

	    int[] pCount = new int[numCourses];
	    
	    for(int i=0; i<p_len; i++){
	        pCount[prerequisites[i][0]]++;
	    }
	 
	    ArrayList<Integer> llist = new ArrayList<Integer>();
	    for(int i=0; i<numCourses; i++){
	        if(pCount[i]==0){
	            llist.add(i);
	        }
	    }
	 

	    int nopreCount = llist.size();
	 
	    while(!llist.isEmpty()){
	        int top = llist.remove(llist.size()-1);
	        for(int i=0; i<p_len; i++){
	            if(prerequisites[i][1]==top){
	                pCount[prerequisites[i][0]]--;
	                if(pCount[prerequisites[i][0]]==0){
	                    nopreCount++;
	                    llist.add(prerequisites[i][0]);
	                }
	            }
	        }
	    }
	 
	    return nopreCount == numCourses;
	}

sumroot.java

public class Solution {
        public int sumNumbers(TreeNode root) {
  		
	  	int ans = 0;
	  	List<String> sums = new ArrayList<String>();
	  	pot(root,"",sums);
		
	  	for (String s:sums){
	  		ans += Integer.parseInt(s);
	  	}
	  	return ans>0?ans-1:0;//To remove the first 1 in the array or check if array is empty
  }
  
  static public void pot (TreeNode n, String num, List<String> sums ){
	  
	  if (n==null){
	      if(num.length()>0){
		  num= num.substring(0, num.length()-1);//remove the most recent number
	      }
		  return;
		  }
	  
	  num = visit(n,num, sums);
	  pot(n.left,num, sums); 
	  pot(n.right,num, sums);
	  
  }
  
  public static String visit(TreeNode n, String num, List<String> sums){
	  num = num+n.val;
	  sums.add(num);
	  return num;
	  }
}

valid-bst.java

public class Solution {
	public boolean isValidBST(TreeNode root) {
        return iot(root);
    }
    
    TreeNode prev = null;
    
    public boolean iot(TreeNode root) {

        if (root == null){
            return true;
        }
        
        if (!iot(root.left)){
            return false;
        }
        
        if (prev != null) {
            if (root.val <= prev.val)
                return false;
        }
        prev = root;
        
        if (!iot(root.right)){
            return false;
        }
        
        return true;
    } 
	
   
}