开贴刷题，坐标波士顿

lz白天实习上班，晚上刷题，目标5月底实习结束刷到350+，一个月100左右吧，然后准备ood和系统设计。ps lz主业是ds相关...所以ml和nlp也不能落下，嗯就这样。

最近刷dfs
leetcode257
Sum Root to Leaf Numbers
207. Course Schedule
261. Graph Valid Tree

leetcode 257
是一道最基础的dfs，基本思路就是使用recursion的思想来完成dfs
tricky的地方数据结构上使用stringBuilder而不是string，原因是有多次的删减
另一个tricky的地方时删除当前层添加的字符串，使用了stringBuilder.setLength()这个方法，在function开始是记录最初的sb长度，然后最后setLength(originalLength)
还有一个小trick就是处理root节点的 "->", 因为root前面并没有"->",所以中间做了一个小的处理 代码如下
关于stringBuilder的reference 参见
https://docs.oracle.com/javase/tutorial/java/data/buffers.html

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        List<String> finalResult = new LinkedList<String>();
        if(root == null) return finalResult;
        dfsHelper(root, sb, finalResult);
        return finalResult;
    }
   
    private void dfsHelper(TreeNode root, StringBuilder sb, List<String> finalResult){
        int currL = sb.length();
        sb.append(root.val);
        if(root.left == null && root.right == null)  finalResult.add(sb.toString());
        sb.append("->");
        if(root.left != null) dfsHelper(root.left, sb, finalResult);
        if(root.right != null) dfsHelper(root.right, sb, finalResult);
        sb.setLength(currL);
        return;   
    }
}

leetcode 207
https://leetcode.com/problems/course-schedule/

初看此题，很自然联想到拓扑排序，我使用dfs解此题
代码如下
class Solution {
   
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(numCourses == 0){
            return true;
        }
        //make a graph based on prerequisites using hashMap
        //for each course from 0 to n-1, should have a key
        //because not all course will be expressed in prerequisites list,
        //there may be some course does not have any prerequisites)
        
        HashMap<Integer, List<Integer>> courseGraph =  new HashMap<Integer, List<Integer>>();
        for(int i = 0; i < numCourses; i++){
            courseGraph.put(i, new ArrayList<Integer>());
        }
        for(int[] courseEdge: prerequisites){
            courseGraph.get(courseEdge[0]).add(courseEdge[1]);
        }
        
        //hold states for all course, there are three states for each course
        //0 --> not visited
        //1 --> visited, but not in active path
        //2 --> visited, and in active path
        int[] visitedCourse = new int[numCourses];
        for(int i = 0; i < numCourses; i++ ){
            boolean result = dfsHelper(i, courseGraph, visitedCourse);
            if(result == false){
                return false;
            }
        }
        return true;
    }
   
    private boolean dfsHelper(
        int course,
        HashMap<Integer, List<Integer>> courseGraph,
        int[]visitedCourse
    ){
        //course has been visited and in active path
        if(visitedCourse[course] == 2){
            return false;
        }
        //course has been visited but not in active path
        else if(visitedCourse[course] == 1){
            return true;
        }
        //path has not been visited, add to active path
        else{
            visitedCourse[course] = 2;
        }
        
        List<Integer> courseList = courseGraph.get(course);
        for(int i = 0; i < courseList.size(); i++){
            if( !dfsHelper(courseList.get(i), courseGraph, visitedCourse)){
                return false;
            }
        }
        
        //remove from active path
        visitedCourse[course] = 1;
        return true;
    }
}

261. Graph Valid Tree

idea is make sure there is no cycle in an undirected graph.
To determine whether a graph is a valid tree, followings have to be checked:
1.  no cycle in the graph
2. every node has to be connected within one component

Todo:
1. convert edges to adjencyList
2. do dfs from any start node
3. if has cycle or any node has not been visited during the dfs, return false


Note:
1. This is a undirected graph, for adjencyList, has to add edge to every end node for each edge.
2. when check visitedState, make sure skip parent node
3. similar to course schedule but is an undirected graph.

代码如下

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if(n == 1){
            return true;
        }
        if(edges.length == 0 || edges[0].length == 0){
            return false;
        }
        
        List<List<Integer>> adjList = new ArrayList<List<Integer>>();
        for(int i = 0; i < n; i++){
            adjList.add(new LinkedList<Integer>());
        }
        for(int[] edge: edges){
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
        }
        
        int[] visitState = new int[n];
        
        if( hasCycle(edges[0][0], -1, adjList, visitState)){
            return false;
        };
        
        for(int visited: visitState){
            if(visited == 0){
                return false;
            }
        }
        return true;
    }
   
   
    public boolean hasCycle(int currNode, int preNode, List<List<Integer>>adjList, int[] visitState){
        if(visitState[currNode] == 1){
            return true;
        }
        visitState[currNode] = 1;
        List<Integer> nodeList = adjList.get(currNode);
        for(Integer node: nodeList){
            if(node != preNode){
                if(hasCycle(node, currNode, adjList, visitState) == true) return true;
            }
        }
        return false;
    }
}

679. 24 Game
https://leetcode.com/problems/24-game/
这题第一反应是一个排列组合，大致是往recursion和dfs上面想了，但是有很多tricky的点
1. 因为有除法和减法，那么应该是一道排列
2. 只有四个数和5种operator，即使是遍历也是O（1）的时间复杂度， 空间复杂度也是O（4） --> O(1)

Steps （recursion):
1. base case, 如果nums只有一个数，只需要判断是否等于24， 如果等于则为true， 不等于则为false
2. 对于每一步，因为最多只有四个数，每次运算选两个，两层for loop即可遍历所有两个数的情况， 对于选出的两个数， 进行 + - * /  运算，复制除这两个数以外的原数组，并将运算结果添加进新的数组
3. 对新数组进行recursion运算，如果在所有数对进行运算后有一个符合结果，return true

tricky part:
因为有除法的存在，所以int类型的数组并无法带入下一层的运算，所以要使用double或者float，并且在计算分数的时候要保留一定的误差范围，java无法进行精确的小数计算

1. class Solution {
   
2.     public boolean judgePoint24(int[] nums) {
   
3.         double[] doubleNums = new double[nums.length];
   
4.         for(int i = 0; i<nums.length; i++){
   
5.             doubleNums[i] = (double) nums[i];
   
6.         }
   
7.         return judgePoint24(doubleNums);
   
8.     }
   
9.    
   
10.     public boolean judgePoint24(double[] nums){
    
11.         if(nums.length == 0){
    
12.             return false;
    
13.         }
    
14.         if(nums.length == 1){
    
15.             if(Math.abs(nums[0] -24 )< 0.00001){
    
16.                 return true;
    
17.             }else{
    
18.                 return false;
    
19.             }
    
20.         }
    
21.       
    
22.         for(int i = 0; i < nums.length; i++){
    
23.             for(int j = i + 1; j < nums.length; j++){
    
24.                 double[] newNums = new double[nums.length - 1];
    
25.                 int index = 0;
    
26.                 for(int x = 0; x < nums.length; x ++){
    
27.                     if(x != i && x != j){
    
28.                         newNums[index] = nums[x];
    
29.                         index ++;
    
30.                     }
    
31.                     
    
32.                 }
    
33.                 newNums[newNums.length - 1] = nums[i] + nums[j];
    
34.                 if(judgePoint24(newNums)) return true;
    
35.                
    
36.                 newNums[newNums.length - 1] = nums[i] - nums[j];;
    
37.                 if(judgePoint24(newNums)) return true;
    
38.                
    
39.                 newNums[newNums.length - 1] = nums[j] - nums[i];
    
40.                 if(judgePoint24(newNums)) return true;
    
41.                
    
42.                 newNums[newNums.length - 1] = nums[i] * nums[j];
    
43.                 if(judgePoint24(newNums)) return true;
    
44.                
    
45.                 if(nums[j] != 0){
    
46.                     newNums[newNums.length - 1] = nums[i] / nums[j];
    
47.                     if(judgePoint24(newNums)) return true;
    
48.                 }
    
49.                
    
50.                 if(nums[i] != 0){
    
51.                     newNums[newNums.length - 1] = nums[j] / nums[i];
    
52.                     if(judgePoint24(newNums)) return true;
    
53.                 }   
    
54.             }
    
55.         }
    
56.         return false;
    
57.     }
    
58. }
    
59.    

复制代码