hot100 | 九、图论

1-leetcode200. 岛屿数目

注意：×

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

1.     public int numIslands(char[][] grid) {
2.         int res = 0;
3.         int n = grid.length;;
4.         int m = grid[0].length;
6.         for (int i = 0; i < n; i++) {
7.             for (int j = 0; j < m; j++) {
8.                 if (grid[i][j] == '1'){
9.                     res++;
10.                     dfs(grid, i, j);
11.                 }
12.             }
13.         }
14.         return res;
15.     }
17.     private void dfs(char[][] grid, int i, int j) {
18.         if (i<0 || i>=grid.length || j<0 || j>=grid[0].length){
19.             return;
20.         }
21.         if (grid[i][j] == '0'){
22.             return;
23.         }
24.         grid[i][j] = '0';
25.         dfs(grid, i+1, j);
26.         dfs(grid, i, j+1);
27.         dfs(grid, i-1, j);
28.         dfs(grid, i, j-1);
29.     }

复制代码

leetcode994. 腐烂的橘子

注意：×

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

1. [/code] [size=5]3-leetcode207. 课程表[/size]
3. 注意：××
4. [list=1]
5. [*]花了许多时间，注意的地方太多了
6. [*]创建List<Integer>[] graph的时候，Labuladong说写代码的时候大部分都是这种连接表的格式，先创建一个LinkedList类型的数组，然后一定要注意，是graph[i] = new LinkedList<>();
7. [*]第二个注意的地方是有hasVisited和onPath两种记录，onPath的记录我能明确，hasVisited的记录还需要思索一下，主要的目的就是办理重复搜索
8. [/list] [code]
9.     boolean hasCycle = false;
10.     boolean[] hasVisited;
11.     boolean[] onPath;
13.     public boolean canFinish(int numCourses, int[][] prerequisites) {
14.         List<Integer>[] graph = buildGraph(numCourses, prerequisites);
15.         hasVisited = new boolean[numCourses];
16.         onPath = new boolean[numCourses];
18.         for (int i = 0; i < numCourses; i++) {
19.             traverse(graph, i);
20.         }
22.         return !hasCycle;
23.     }
25.     private void traverse(List<Integer>[] graph, int i) {
26.         if (onPath[i]){
27.             hasCycle = true;
28.         }
29.         if (hasCycle || hasVisited[i]){
30.             return;
31.         }
32.         
33.         hasVisited[i] = true;
34.         
35.         onPath[i] = true;
37.         for (Integer integer : graph[i]) {
38.             traverse(graph, integer);
39.         }
40.         
41.         onPath[i] = false;
42.     }
44.     private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
45.         List<Integer>[] graph = new LinkedList[numCourses];
46.         for (int i = 0; i < graph.length; i++) {
47.             graph[i] = new LinkedList<>();
48.         }
49.         for (int[] prerequisite : prerequisites) {
50.             int from = prerequisite[1];
51.             int to = prerequisite[0];
52.             graph[from].add(to);
53.         }
54.         return graph;
55.     }

复制代码

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

注意：×

• 看了题解再写，感觉照旧有点压力
  
• 注意isEnd的调用
  

1.     class Trie {
2.         class TrieNode{
3.             boolean isEnd;
4.             TrieNode[] nodes;
5.             public TrieNode(){
6.                 isEnd = false;
7.                 nodes = new TrieNode[26];
8.             }
9.         }
11.         private TrieNode root;
13.         public Trie() {
14.             root = new TrieNode();
15.         }
17.         public void insert(String word) {
18.             TrieNode node = root;
19.             for (char c : word.toCharArray()) {
20.                 if (node.nodes[c-'a'] == null){
21.                     node.nodes[c-'a'] = new TrieNode();
22.                 }
23.                 node = node.nodes[c-'a'];
24.             }
25.             node.isEnd = true;
26.         }
28.         public boolean search(String word) {
29.             TrieNode node = root;
30.             for (char c : word.toCharArray()) {
31.                 if (node.nodes[c-'a'] == null){
32.                     return false;
33.                 }
34.                 node = node.nodes[c-'a'];
35.             }
36.             return node.isEnd;
37.         }
39.         public boolean startsWith(String prefix) {
40.             TrieNode node = root;
41.             for (char c : prefix.toCharArray()) {
42.                 if (node.nodes[c-'a'] == null){
43.                     return false;
44.                 }
45.                 node = node.nodes[c-'a'];
46.             }
47.             return true;
48.         }
49.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。