算法--2023.1.16

1.力扣200--岛屿数量

class Solution {
    //深度优先遍历
    public int cnt;
    public char[][] nums;
    public int[] dx,dy;
    public int m,n;
    public int numIslands(char[][] grid) {
        cnt = 0;
        dx = new int[]{1,0,-1,0};
        dy = new int[]{0,-1,0,1};
        m = grid.length;n = grid[0].length;
        nums = new char[m][n];
        //遍历每个节点，如果是1就进行深度优先遍历，将其周围的所有所有的1变成0
        //然后cnt+1
        for(int i = 0;i<m ;i++){
            for(int j = 0;j<n;j++){
                nums[i][j] = grid[i][j];
            }
        }
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(nums[i][j] == '1'){
                    nums[i][j] = 0;
                    dfs(i,j);
                    cnt++;
                    //System.out.println(cnt);
                }
            }
        }
        return cnt;
    }
    //深度优先遍历算法
    public void dfs(int i,int j){
        for(int p = 0;p<4;p++){
            int x = i + dx[p], y = j + dy[p];
            if(x>=0&&x<m&&y>=0&&y<n&&nums[x][y] == '1'){
                nums[x][y] = 0;
                dfs(x,y);
            }
        }
    }
}

2.力扣206--反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode tail = null;
        while(head!=null){
            ListNode temp = head.next;
            head.next = tail;
            tail = head;
            head = temp;
        }
        return tail;

    }
}

3.力扣207--课程表

class Solution {
    //拓扑排序
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //用链表来记录图中的所有边
        List<List<Integer>> contain = new LinkedList<>();
        int[] nums = new int[numCourses];
        //遍历数组，将所有边添加进链表中
        for(int i = 0;i<numCourses;i++){
            contain.add(new LinkedList<>());
        }
        for(int[] temp : prerequisites){
            //b指向a有一条边
            int a = temp[0], b = temp[1];
            contain.get(b).add(a);
            //a的入度加一
            nums[a]++;
        }
        int res = 0;
        //队列用来做广度优先遍历，保存暂时入度为0的点
        Deque<Integer> queue = new LinkedList<>();
        for(int i = 0;i<numCourses;i++){
            if(nums[i] == 0){
                queue.offer(i);
            }
        }
        //遍历队列里面的元素
        while(!queue.isEmpty()){
            int tt = queue.poll();
            res++;
            //出队后值加一
            for(int t1 : contain.get(tt)){
                nums[t1]--;
                //然后遍历出队节点指向的所有子节点的度，所有子节点的度-1
                if(nums[t1] == 0){
                    //如果子节点的度为0，则将该节点放入队列中，以便下一次用来遍历该节点1的子节点
                    queue.offer(t1);
                }
            }
        }
        //System.out.println(res);
        //最后比较出队的节点与总结点的个数
        return res == numCourses;

    }
}