当前位置：首页 > article >正文

力扣-Hot100-图论【算法学习day.38】

article 2024/11/24 10:57:57

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.岛屿数量

题目链接:200. 岛屿数量 - 力扣（LeetCode）

题面:

分析:定义一个递归函数，用于将从某一点开始的四周相邻的1全部标记，然后我们遍历这个二阶数组，如果grid[i][j]==1&&flag[i][j]==0(flag表示标记该点是否属于其他岛屿)，就将该点传入递归函数，将同属于该岛屿的所有点打上标记，ans++，最后返回ans即可

代码:

class Solution {
    int[][] flag;
    char[][] grid;
    int n;
    int m;
    int ans = 0;
    public int numIslands(char[][] grid) {
        n = grid.length;
        m = grid[0].length;
        flag = new int[n][m];
        this.grid = grid;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(flag[i][j]==0&&grid[i][j]=='1'){
                ans++;
                recursion(i,j);
                }
            }
        }
        return ans;
    }

    public void recursion(int i,int j){
        if(grid[i][j]!='1'||flag[i][j]==1)return;
        flag[i][j] = 1;
        //上
        if(i-1>=0&&flag[i-1][j]==0)recursion(i-1,j);
        //下
        if(i+1<n&&flag[i+1][j]==0)recursion(i+1,j);
        //左
        if(j-1>=0&&flag[i][j-1]==0)recursion(i,j-1);
        //右
        if(j+1<m&&flag[i][j+1]==0)recursion(i,j+1);
    }
}

2.腐烂的橘子

题目链接:994. 腐烂的橘子 - 力扣（LeetCode）

题面:

分析:模拟题，我们可以先遍历二维数组，定义两个队列，来存放下一分钟开始向四周腐烂的橘子的行纵坐标，在额外定义一个遍历来表示新鲜橘子的剩余数量，然后每分钟开始时，我们从队列中取烂橘子，定义一个函数，用来表示一个橘子向四周腐烂的过程，如果将好橘子变成了坏橘子，就将这个新的坏橘子存入队列，并让新鲜橘子减一，当队列中不存在坏橘子时，循环结束，如果仍有好橘子存在，就返回-1，否则返回时间记录变量ans，详细看代码：

代码:

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<Integer> qi = new LinkedList<>();
        Queue<Integer> qj = new LinkedList<>();
        int ans = 0;
        int n = grid.length;
        int m = grid[0].length;
        int freshOrange = 0;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(grid[i][j]==2){
                    qi.offer(i);
                    qj.offer(j);
                }
                else if(grid[i][j]==1){
                    freshOrange++;
                }
            }
        }
        if(freshOrange==0)return 0;
        // System.out.println(freshOrange);
        // System.out.println(qi.size());
        while(!qi.isEmpty()){
            ans++;
        // System.out.println(freshOrange+" "+qi.size());
            int flag = qi.size();
            for(int k = 0;k<flag;k++){
                int i = qi.poll();
                int j = qj.poll();
                //上
                if(i-1>=0&&grid[i-1][j]==1){
                    grid[i-1][j]=2;
                    qi.offer(i-1);
                    qj.offer(j);
                    freshOrange--;
                }
                //下
                if(i+1<n&&grid[i+1][j]==1){
                    grid[i+1][j]=2;
                    qi.offer(i+1);
                    qj.offer(j);
                    freshOrange--;
                }
                //左
                if(j-1>=0&&grid[i][j-1]==1){
                    grid[i][j-1]=2;
                    qi.offer(i);
                    qj.offer(j-1);
                    freshOrange--;
                }
                //右
                if(j+1<m&&grid[i][j+1]==1){
                    grid[i][j+1]=2;
                    qi.offer(i);
                    qj.offer(j+1);
                    freshOrange--;
                }
            }      
        }
        if(freshOrange>0)return -1;
        return ans-1;

    }
}

3.课程表

题目链接:207. 课程表 - 力扣（LeetCode）

题面:

分析:主要是看有没有成环

代码:

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] g = new ArrayList[numCourses];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] p : prerequisites) {
            g[p[1]].add(p[0]);
        }

        int[] colors = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (colors[i] == 0 && dfs(i, g, colors)) {
                return false; // 有环
            }
        }
        return true; // 没有环
    }

    private boolean dfs(int x, List<Integer>[] g, int[] colors) {
        colors[x] = 1; // x 正在访问中
        for (int y : g[x]) {
            if (colors[y] == 1 || colors[y] == 0 && dfs(y, g, colors)) {
                return true; // 找到了环
            }
        }
        colors[x] = 2; // x 完全访问完毕
        return false; // 没有找到环
    }
}

4.实现前缀Trie

题目链接:208. 实现 Trie (前缀树) - 力扣（LeetCode）

题面:

分析:

1.暴力做法就是把字符串存数组里，判断字符串是否存在就是遍历数组，判断是否以某一字符串作为开头，就是使用startWith函数

2.我们可以定义一个内部类Node，表示节点，他有两个属性，分别是子节点数组和是否是end（为某个单词的最后一个字母），当添加一个单词时，我们从root出发，遍历这个单词，如果某个子节点不存在，就创建这个子节点，查某个单词时，就看遍历时是不是都存在以及是否最后一个节点的end值为true，而查前缀就只需看是否都存在，具体请看下图

代码:

class Node{
   Node[] son = new Node[26];
   boolean end;
}
class Trie {
    Node root;
    public Trie() {
      root = new Node();
    }
    
    public void insert(String word) {
       char[] chars = word.toCharArray();
       int n = chars.length;
       Node node = root;
       for(int i = 0;i<n;i++){
            int flag = chars[i]-'a';
            if(node.son[flag]==null){
               node.son[flag] = new Node(); 
            }
            node = node.son[flag];
       }
       node.end = true;
    }
    
    public boolean search(String word) {
       char[] chars = word.toCharArray();
       int n = chars.length;
       Node node = root;
       for(int i = 0;i<n;i++){
            int flag = chars[i]-'a';
            if(node.son[flag]==null){
              return false;
            }
            node = node.son[flag];
       }
       if(node.end)return true;
       return false;
    }
    
    public boolean startsWith(String prefix) {
       char[] chars = prefix.toCharArray();
       int n = chars.length;
       Node node = root;
       for(int i = 0;i<n;i++){
            int flag = chars[i]-'a';
            if(node.son[flag]==null){
              return false;
            }
            node = node.son[flag];
       }
       return true;
    }
}

/**
 * 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);
 */