力扣爆刷第93天之hot100五连刷51-55

一、200. 岛屿数量

题目链接：https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-100-liked
思路：很经典的图论，广度优先和深度优先都可以，求岛屿数量关键是把遍历过的岛屿进行标记，避免重复遍历。

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

    void dfs(char[][] grid, int x, int y) {
        if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return ;
        if(grid[x][y] == '0') return;
        grid[x][y] = '0';
        dfs(grid, x - 1, y);
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
        dfs(grid, x, y + 1);
    }
    
}

二、994. 腐烂的橘子

题目链接：https://leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked
思路：本题是一个多源头同步扩散，所以需要使用广度优先，用队列来模拟二叉树的层序遍历，控制所有的源头进行一圈一圈的扩散。

class Solution {
    int count = 0;
    
    Deque<int[]> queue = new LinkedList<>();
    public int orangesRotting(int[][] grid) {
        int freeNum = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == 1) {
                    freeNum++;
                } 
                if(grid[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }
        
        while(!queue.isEmpty()) {
            if(freeNum == 0) return count;
            count++;
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                int[] temp = queue.poll();
                int x = temp[0], y = temp[1];
                freeNum -= roting(grid, x-1, y);
                freeNum -= roting(grid, x+1, y);
                freeNum -= roting(grid, x, y-1);
                freeNum -= roting(grid, x, y+1);
            }
            
        }
        return freeNum > 0 ? -1 : count;
    }

    int roting(int[][] grid, int x, int y) {
        if(x < 0 || y < 0 || x > grid.length - 1 || y > grid[0].length - 1 || grid[x][y] != 1) {
            return 0;
        }
        grid[x][y] = 2;
        queue.add(new int[]{x, y});
        return 1;
    }
}

三、207. 课程表

题目链接：https://leetcode.cn/problems/course-schedule/description/?envType=study-plan-v2&envId=top-100-liked
思路：根据题目要求需要构建邻接表，然后我们要判断邻接表是否成环，visited数组使用来记录访问过的节点，避免重复访问，flags数组是用来记录从任意一个节点出发是否成环，如果成环则无法完成课程表。
另外就是关于flags数组的使用，单纯的利用visisted是无法判断是否成环的，如下图只遍历邻接表的0和1会发现0重复遍历，但是不成换。。

class Solution {
    boolean[] visited;
    boolean[] flags;
    boolean hasCycle = false;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visited = new boolean[numCourses];
        flags = new boolean[numCourses];
        List<Integer>[] graph = build(numCourses, prerequisites);
        for(int i = 0; i < numCourses; i++) {
            traverse(graph, i);
        }
        return !hasCycle;
    }

    void traverse(List<Integer>[] graph, int i) {
        if(flags[i]) {
            hasCycle = true;
        }
        if(visited[i] || hasCycle) return;
        visited[i] = true;
        flags[i] = true;
        for(int t : graph[i]) {
            traverse(graph, t);
        }
        flags[i] = false;
    }

    List<Integer>[] build(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new ArrayList[numCourses];
        for(int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList();
        }
        for(int[] edge : prerequisites) {
            graph[edge[1]].add(edge[0]);
        }
        return graph;
    }
}

四、208. 实现 Trie (前缀树)

题目链接：https://leetcode.cn/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-100-liked
思路：利用单词构建多叉树，然后遍历多叉树。

class Trie {

    Node root = null;
    class Node{
        int v = 0;
        Node[] child = new Node[26];
    }
    public Trie() {

    }

    public void insert(String word) {
        // if (search(word)) {
        //     return;
        // }
        root = addNode(root, word, 0);
    }

    public boolean search(String word) {
        Node node = getNode(root, word);
        if (node == null || node.v == 0) {
            return false;
        }
        return true;
    }

    public boolean startsWith(String prefix) {
        return getNode(root, prefix) != null;
    }

    Node getNode(Node node, String word) {
        Node p = node;
        for (int i = 0; i < word.length(); i++) {
            if (p == null) {
                return null;
            }
            p = p.child[word.charAt(i)-'a'];
        }
        return p;
    }

    Node addNode(Node node, String word, int i) {
        if (node == null) {
            node = new Node();
        }
        if (i == word.length()) {
            node.v = 1;
            return node;
        }
        int c = word.charAt(i) - 'a';
        node.child[c] = addNode(node.child[c], word, i+1);
        return node;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

五、46. 全排列

题目链接：https://leetcode.cn/problems/permutations/description/?envType=study-plan-v2&envId=top-100-liked
思路：全排列不需要指定起始位置，只需要纵向去重即可。

class Solution {
    
    List<List<Integer>> arrayList = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    boolean[] visited;
    public List<List<Integer>> permute(int[] nums) {
       visited = new boolean[nums.length];
        backTracking(nums);
        return arrayList;
    }
    
    void backTracking(int[] nums) {
        if(list.size() == nums.length) {
            arrayList.add(new ArrayList(list));
            return;
        }
        
        for(int i = 0; i < nums.length; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            list.add(nums[i]);
            backTracking(nums);
            visited[i] = false;
            list.remove(list.size()-1);
        }
    }

}