技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1-leetcode200。

注：×

1. 直接読むという非常に賢いアプローチ1いつ与えるres価値+1次に、深さ優先探索により、隣接するすべての陸地が海洋に変更されます。
2. 知らせdfs内部の範囲判定、[0, **length-1]**
3. 長さ-1
4. 長さ-1
5. 長さ-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);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

leetcode994 腐ったオレンジ

注：×

1. 試験が少なすぎて書くのが面倒だったので書きませんでした。

1

3-leetcode207のコーススケジュール。

注: ××

1. 多くの時間を費やし、多くのことに注意を払いすぎました。
2. 作成するList<Integer>[] graphその際、Labuladong 氏は、コードを書くときは、ほとんどの場合、この隣接リスト形式で、まず LinkedList 型の配列を作成し、次にそれに注意を払うようにすると述べました。graph[i] = new LinkedList<>();
3. 2 番目に注意すべきことは、hasVisitedそしてonPathレコードは2種類、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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

4-leetcode208 を実装します (プレフィックス ツリー)。

注：×

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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49