[brother hero's July training] day 27: picture

---

One 、1791. Find the central node of the star graph

1791. Find the central node of the star graph

There is an undirected Star type chart , from n A number from 1 To n Node composition of . The star graph has a center node , And there is n - 1 The edges connect the central node to each other .
Here's a two-dimensional array of integers edges , among edges[i] = [ui, vi] At the node ui and vi There is an edge between . Please find out and return to edges The center node of the star graph represented by .

leetcode 1791 java

Ideas

The degree is greater than 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;
            }
        }
    }
}

Two 、797. All possible paths

797. All possible paths

Here you are n Of nodes Directed acyclic graph （DAG）, Please find all slave nodes 0 To the node n-1 And output （ No specific order is required ）
graph[i] Is a slave node i List of all nodes that can be accessed （ That is, the slave node i To the node graph[i][j] There is a directed side ）.

leetcode 797 java

Ideas

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();
        }
    }
}

3、 ... and 、851. Noise and wealth

851. Noise and wealth

There is a group n Individuals as subjects , from 0 To n - 1 Number , Each of them has a different amount of money , And different levels of quiet value （quietness）. For convenience , We'll number it x The person of is abbreviated as "person x ".
Give you an array richer , among richer[i] = [ai, bi] Express person ai Than person bi More money . Give you another integer array quiet , among quiet[i] yes person i Quiet value of .richer The data given in Self-consistent logic （ in other words , stay person x Than person y More money at the same time , There will be no person y Than person x More money ）.
Now? , Returns an array of integers answer As the answer , among answer[x] = y The premise is , There must be no less than person x Of the people ,person y Is the quietest person （ That is, quiet value quiet[y] The youngest ）.

leetcode 851 java

Ideas

Adjacency matrix

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<>();
        // Initialize stack and result set 
        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;

        

    }
}

Four 、959. Area by slash

959. Area by slash

In by 1 x 1 Made up of squares n x n grid grid in , Every 1 x 1 The square is made of ‘/’、‘’ Or a space . These characters will divide the blocks into some common areas .
Given grid grid Expressed as an array of strings , return The number of areas .
Please note that , The backslash character is escaped , therefore ‘’ use ‘\’ Express .

leetcode 959 java

Ideas

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; // That's ok 
        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;




    }
}

---

summary