【英雄哥七月集训】第 27天：图

---

一、1791. 找出星型图的中心节点

1791. 找出星型图的中心节点

有一个无向的 星型 图，由 n 个编号从 1 到 n 的节点组成。星型图有一个 中心 节点，并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。
给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。请你找出并返回 edges 所表示星型图的中心节点。

leetcode 1791 java

思路

度大于1

class Solution {
    
    public int findCenter(int[][] edges) {
    
        int[] degree = new int[edges.length+2];
        for(int[] edge:edges){
    
            degree[edge[0]]++;
            degree[edge[1]]++;
        }

        for(int i=0; ;i++){
    
            if(degree[i]>1){
    
                return i;
            }
        }
    }
}

二、797. 所有可能的路径

797. 所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

leetcode 797 java

思路

dfs

class Solution {
    
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> stack = new ArrayDeque<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    
        stack.offerLast(0);
        dfs(graph,0,graph.length-1);
        return ans;
    }

    public void dfs(int[][] graph, int x, int n){
    
        if(x==n){
    
            ans.add(new ArrayList<Integer>(stack));
        }
        for(int y:graph[x]){
    
            stack.offerLast(y);
            dfs(graph,y,n);
            stack.pollLast();
        }
    }
}

三、851. 喧闹和富有

851. 喧闹和富有

有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。
给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自洽（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 ）。
现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。

leetcode 851 java

思路

邻接矩阵

class Solution {
    
   
    public int[] loudAndRich(int[][] richer, int[] quiet) {
    
        int n = quiet.length;
        
        int[][] w = new int[n][n];
        int[] in = new int[n];
        for(int[] rich:richer){
    
            w[rich[0]][rich[1]]=1;
            in[rich[1]]++;
        }

        Deque<Integer> queue = new ArrayDeque<>();
        //初始化栈和结果集
        int[] ans = new int[n];
        for(int i=0;i<n;i++){
    
            ans[i]=i;
            if(in[i]==0) queue.addLast(i);
        }


        while(!queue.isEmpty()){
    
            int t = queue.pollFirst();
            for(int u=0;u<n;u++){
    
                if(w[t][u]==1){
    
                    if(quiet[ans[t]]<quiet[ans[u]]) ans[u]=ans[t];
                    if(--in[u]==0) queue.addLast(u);
                }
            }
        }
        return ans;

        

    }
}

四、959. 由斜杠划分区域

959. 由斜杠划分区域

在由 1 x 1 方格组成的 n x n 网格 grid 中，每个 1 x 1 方块由 ‘/’、‘’ 或空格构成。这些字符会将方块划分为一些共边的区域。
给定网格 grid 表示为一个字符串数组，返回 区域的数量 。
请注意，反斜杠字符是转义的，因此 ‘’ 用 ‘\’ 表示。

leetcode 959 java

思路

dfs

class Solution {
    
    int[][] dir = {
    {
    0,1},{
    1,0},{
    0,-1},{
    -1,0}};
    

    public void dfs(int[][] grid,int x,int y){
    
        int m =grid.length;
        for(int i=0 ;i<4 ;i++ ){
    
            int nx = x + dir[i][0], ny = y + dir[i][1];
            if(nx>=0 && nx<m && ny>=0 && ny<m && grid[nx][ny]==0){
    
                grid[nx][ny]=1;
                dfs(grid,nx,ny);
            }
        }
        
    }
    public int regionsBySlashes(String[] grid) {
    
        int m = grid.length; //行
        int[][] new_grid = new int[3*m][3*m];
        for(int i=0;i<m;i++){
    
            for(int j =0;j<m;j++){
    
                
                if(grid[i].charAt(j)=='/'){
    
                    new_grid[3*i][3*j+2]=1;
                    new_grid[3*i+1][3*j+1]=1;
                    new_grid[3*i+2][3*j]=1;
                } else if(grid[i].charAt(j)=='\\'){
    
                    new_grid[3*i][3*j]=1;
                    new_grid[3*i+1][3*j+1]=1;
                    new_grid[3*i+2][3*j+2]=1;
                }

            }
            
        }
        

        int cnt=0;
        for(int i=0;i<3*m;i++){
    
            for(int j=0;j<3*m;j++){
    
                if(new_grid[i][j]==0){
    
                    cnt++;
                    new_grid[i][j]=1;
                    dfs(new_grid,i,j);
                }
            }
        }
        return cnt;




    }
}

---

总结