23-3-17 今日leecode

200：

递归+标记

class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        for(int i = 0; i< grid.length;i++){
            for(int j = 0;j<grid[0].length;j++){
                if(grid[i][j] == '1'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }

    public void dfs(char[][] grid, int i,int j){
        //判断i，j是否越界，越界
        if( !check(i,j,grid)|| grid[i][j] != '1') return;

        grid[i][j] = '2';
        //没有越界朝下和朝右、朝左扩散
        dfs(grid,i+1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
        dfs(grid,i-1,j);
    }

    public boolean check(int i,int j, char[][] grid){
        return (i>=0 && i< grid.length)&&(j >=0 && j < grid[0].length);
    }

}

206 反转链表

简单题，主要是创建一个伪头部

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummpy = new ListNode(0);
        ListNode start = dummpy;
        ListNode p1 = head,p2 = head;
        while(p1 != null){
            p2 = p1.next;
            p1.next = start.next;
            start.next = p1;
            p1 = p2;
        }
        return dummpy.next;
    }
}

207 课程表

参考官方评论区：

拓扑排序：可以使用队列，每次取出队列中的值，遍历所有节点，将所有结点的被指向次数-1，如果减到0说明该课程可以修。就是判断是否有环，如果有环，那么在去除掉没有环的部分后，剩下的部分没有入度为0的点，也就是没有安全课程。

class Solution {
    public boolean canFinish(int n, int[][] prerequisites) {
        int len = prerequisites.length;
        if (len == 0) return true;
        int[] pointer = new int[n];// 每个课程被指向的次数
        for (int[] p : prerequisites) ++pointer[p[1]];
        boolean[] removed = new boolean[len];// 标记prerequisites中的元素是否被移除
        int remove = 0;// 移除的元素数量
        while (remove < len) {
            int currRemove = 0;// 本轮移除的元素数量
            for (int i = 0; i < len; i++) {
                if (removed[i]) continue;// 被移除的元素跳过
                int[] p = prerequisites[i];
                if (pointer[p[0]] == 0) {// 如果被安全课程指向
                    --pointer[p[1]];// 被指向次数减1
                    removed[i] = true;
                    ++currRemove;
                }
            }
            if (currRemove == 0) return false;// 如果一轮跑下来一个元素都没移除，则没必要进行下一轮
            remove += currRemove;
        }
        return true;
    }
}

使用队列：

class Solution {
    public boolean canFinish(int n, int[][] prerequisites) {
        int len = prerequisites.length;
        if (len == 0) return true;
        int[] pointer = new int[n];
        Queue<int[]> queue = new ArrayDeque<>(len);
        for (int[] p : prerequisites) {
            ++pointer[p[1]];
            queue.offer(p);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] p = queue.poll();
                if (pointer[p[0]] == 0) --pointer[p[1]];
                else queue.offer(p);
            }
            if (size == queue.size()) return false;
        }
        return true;
    }
}