Technologieaustausch

hot100 |. 9. Graphentheorie

2024-07-12

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

1-leetcode200. Anzahl der Inseln

Hinweis: ×

  1. Ziemlich cleverer Ansatz, direkt zu lesen1gib wannresWert+1, und dann verwandelt die Tiefensuche alle angrenzenden Landflächen in Ozeane
  2. BeachtendfsDas Reichweitenurteil im Inneren,[0, **length-1]**
  3. Länge-1
  4. Länge-1
  5. Länge-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. faule Orangen

Hinweis: ×

  1. Ich habe es nicht geschrieben. Ich habe gesehen, dass es zu wenige Prüfungen gab und ich zu faul zum Schreiben war.

  • 1

3-leetcode207. Kursplan

Hinweis: ××

  1. Ich habe viel Zeit investiert und auf zu viele Dinge geachtet.
  2. erstellenList<Integer>[] graphDamals sagte Labuladong, dass er beim Schreiben von Code meistens in diesem Adjazenzlistenformat vorliegt. Erstellen Sie zunächst ein Array vom Typ LinkedList und achten Sie dann darauf.graph[i] = new LinkedList<>();
  3. Das zweite, was zu beachten ist, ist, dass es welche gibthasVisitedUndonPathZwei Arten von Aufzeichnungen,onPathIch kann die Aufzeichnung verstehen,hasVisitedÜber die Datensätze muss nachgedacht werden. Der Hauptzweck besteht darin, wiederholte Suchvorgänge zu lösen.

    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. Trie implementieren (Präfixbaum)

Hinweis: ×

  1. Nachdem ich die Lösung der Frage gelesen und dann geschrieben habe, fühle ich mich immer noch etwas gestresst.
  2. Beachten Sie den Aufruf von 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