hot100 | 九、图论

1-leetcode200. 岛屿数量

注意：×

1. 蛮巧妙的做法，直接在读取到1的时候给res的值+1,然后深度优先搜索把所有相邻的陆地全部改为海洋
2. 注意dfs里面的范围判断，[0, **length-1]**
3. length-1
4. length-1
5. length-1

    public int numIslands(char[][] grid) {int res = 0;int n = grid.length;;int m = grid[0].length;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == '1'){res++;dfs(grid, i, j);}}}return res;}private void dfs(char[][] grid, int i, int j) {if (i<0 || i>=grid.length || j<0 || j>=grid[0].length){return;}if (grid[i][j] == '0'){return;}grid[i][j] = '0';dfs(grid, i+1, j);dfs(grid, i, j+1);dfs(grid, i-1, j);dfs(grid, i, j-1);}

leetcode994. 腐烂的橘子

注意：×

1. 没写，看着考的太少，懒得写了

3-leetcode207. 课程表

注意：××

1. 花了很多时间，注意的地方太多了
2. 创建List<Integer>[] graph的时候，Labuladong说写代码的时候大部分都是这种邻接表的格式，先创建一个LinkedList类型的数组，然后一定要注意，是graph[i] = new LinkedList<>();
3. 第二个注意的地方是有hasVisited和onPath两种记录，onPath的记录我能理解，hasVisited的记录还需要思考一下，主要的目的就是解决重复搜索

boolean hasCycle = false;boolean[] hasVisited;boolean[] onPath;public boolean canFinish(int numCourses, int[][] prerequisites) {List<Integer>[] graph = buildGraph(numCourses, prerequisites);hasVisited = new boolean[numCourses];onPath = new boolean[numCourses];for (int i = 0; i < numCourses; i++) {traverse(graph, i);}return !hasCycle;}private void traverse(List<Integer>[] graph, int i) {if (onPath[i]){hasCycle = true;}if (hasCycle || hasVisited[i]){return;}hasVisited[i] = true;onPath[i] = true;for (Integer integer : graph[i]) {traverse(graph, integer);}onPath[i] = false;}private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {List<Integer>[] graph = new LinkedList[numCourses];for (int i = 0; i < graph.length; i++) {graph[i] = new LinkedList<>();}for (int[] prerequisite : prerequisites) {int from = prerequisite[1];int to = prerequisite[0];graph[from].add(to);}return graph;}

4-leetcode208. 实现 Trie (前缀树)

注意：×

1. 看了题解再写，感觉还是有点压力
2. 注意isEnd的调用

    class Trie {class TrieNode{boolean isEnd;TrieNode[] nodes;public TrieNode(){isEnd = false;nodes = new TrieNode[26];}}private TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {TrieNode node = root;for (char c : word.toCharArray()) {if (node.nodes[c-'a'] == null){node.nodes[c-'a'] = new TrieNode();}node = node.nodes[c-'a'];}node.isEnd = true;}public boolean search(String word) {TrieNode node = root;for (char c : word.toCharArray()) {if (node.nodes[c-'a'] == null){return false;}node = node.nodes[c-'a'];}return node.isEnd;}public boolean startsWith(String prefix) {TrieNode node = root;for (char c : prefix.toCharArray()) {if (node.nodes[c-'a'] == null){return false;}node = node.nodes[c-'a'];}return true;}}