07.BFS&DFS 拓扑排序

[conchincradle]

79. Word Search

    boolean flag; 
    public boolean dfs(char[][] board, char[] words,int start,int i, int j,boolean[][] visited){
        int h = board.length,w=board[0].length;
        if(board[i][j]!=words[start]){
            return false;
        }else if(start==words.length-1){
            return true;
        }
        int[][] directs = {{0,1},{0,-1},{1,0},{-1,0}};
        visited[i][j] = true;
        for(int[] direct: directs){
            int ii = i+direct[0];
            int jj = j+direct[1];
            if(0<=ii&&ii<h&&0<=jj&&jj<w&&!visited[ii][jj]){
                boolean flag = dfs(board,words,start+1,ii,jj,visited);       
                if(flag) return true;
            }
        }
        visited[i][j]=false;
        return false;

[conchincradle]

核心的问题在于，末尾处必须 visited[i][j]=false; 查找分支全部结束后，这个点必须回归没有访问的状态 这就是为什么做不出来的原因，因为都是公用一个访问的状态数组，但是末尾处必须还原成没访问 然后记得如果ｔｒｕｅ的提前返回

[conchincradle]

207. Course Schedule

[conchincradle]

// bfs
       int n = numCourses;
       List<List<Integer>> edges = new ArrayList<List<Integer>> ();
       int[] inDeg = new int[n];
       for(int i=0; i<n;i++){
           edges.add(new ArrayList<Integer>());
       }
       for(int[] each: prerequisites){
           edges.get(each[1]).add(each[0]);
           inDeg[each[0]]++;
       }
       Queue<Integer> queue = new LinkedList<>();
       for(int i=0; i<n;++i){
           if(inDeg[i]==0) queue.offer(i);
       }

        int visited = 0;
        while(!queue.isEmpty()){
            int u =  queue.poll();
            visited++;
            for(int v: edges.get(u)){
                inDeg[v]--;
                if(inDeg[v]==0) queue.add(v);
            }

       }
       return visited==n;
   }

[conchincradle]

       edges = new ArrayList<List<Integer>>();
        int n = numCourses;
        int i = n;
        while(i-->0){
            edges.add(new ArrayList<Integer>());
        }
        for(int[] each: prerequisites){
            edges.get(each[1]).add(each[0]);
        }
        visited = new int[n];
        for(i=0;i<n ; ++i){
            if(visited[i]==0){
                dfs( i);
                if(!valid) return false;
            }
        }
        return valid;

    }
    public void dfs(int i){
        if(visited[i] == 1) {
            valid = false;
            return;
        }else if(visited[i]==0){
            visited[i] = 1;
            for(int u: edges.get(i)){
                dfs(u);
                if(!valid) return;
            }
        }
        visited[i] = 2;
    }

[conchincradle]

bfs

空列表来存储边的左节点，这个不容易想到，这样直接就是0对应0的空列表 面试的时候这个很难想起来的

 List<List<Integer>> edges = new ArrayList<List<Integer>>();
       for(int i=0;i<nums;i++){
           edges.add(new ArrayList<Integer>);
       }

然后用inDegree 保存入度 然后用一个队列存入所有的入度为0的 然后广度优先搜索 while queue visited++; for(int v: edges.get(curr)){ inDegrees[v]--; if(inDegrees[v]==0) queue.offer(v);} 注意，不需要删除edges的列表，因为入度已经为0 了，也就是没有边会指向它 有循环的话，这个点的入度永远不为0，所以根本不会进入队列

[conchincradle]

dfs 这个和单词搜索一样，就是暂时的搜索，需要有回溯的，对于单词搜索，在最末尾的时候，回溯到源节点的时候必须重新归为没访问的状态 而这个的话，就是为了确保没有环，那么每次搜索，应该有，搜索中，未搜索，还有已搜索结束 其实就是最末尾的没有出度的节点先放入栈中，

那么首先必须有全局变量， visited valid edges; 在函数中初始化，防止多次调用

注意是【0，1】1在0的前面，也就是必须是1指着0，那么也就是pre[1].addpre[0]，别搞错了

visited[curr]=1; for(int v: edges.get(curr)){ if(visited[v]==0){ dfs(v); if(!valid) return; }else if(visited[v]==1){ valid=false; return; } } visited[curr]=2;

[conchincradle]

210. Course Schedule II return an array 直接在visited[curr]=2; 之后加入到列表中即可

[conchincradle]

200. Number of Islands dfs so easy