devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

代码随想录-图论

作者：笔触狂放9 | 2024-04-12 02:40:02

赞

踩

代码随想录-图论
797.所有可能的路径：

. - 力扣（LeetCode）

  1. class Solution {
  2.     List<List<Integer>> ans=new LinkedList<>();
  3.     List<Integer> list=new LinkedList<>();
  4.     public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
  5.         list.add(0);
  6.         backTracking(graph,0);
  7.         return ans;
  8.     }
  9.     private void backTracking(int[][] graph,int x){
  10.         if (x==graph.length-1){
  11.             ans.add(new LinkedList<>(list));
  12.         }
  13.         for (int i = 0; i < graph[x].length; i++) {
  14.             list.add(graph[x][i]);
  15.             backTracking(graph,graph[x][i]);
  16.             list.remove(list.size()-1);
  17.         }
  18.     }
  19. }
岛屿数量：

. - 力扣（LeetCode）

深搜：

  1. class Solution {
  2.     int ans=0;
  3.     int[] dx={0,1,-1,0};
  4.     int[] dy={1,0,0,-1};
  5.     public int numIslands(char[][] grid) {
  6.         for (int i = 0; i < grid.length; i++) {
  7.             for (int j = 0; j < grid[0].length; j++) {
  8.                 if (grid[i][j]=='1'){
  9.                     ans++;
  10.                     grid[i][j]='0';
  11.                     backTracking(grid,i,j);
  12.                 }
  13.             }
  14.         }
  15.         return ans;
  16.     }
  17.     private void backTracking(char[][] grid,int x,int y){
  18.         for (int i = 0; i < 4; i++) {
  19.             int newx=x+dx[i];
  20.             int newy=y+dy[i];
  21.             if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]=='0')continue;
  22.             grid[newx][newy]='0';
  23.             backTracking(grid,newx,newy);
  24.         }
  25.     }
  26. }

广搜：

  1. class Solution {
  2.      int ans=0;
  3.     int[] dx={0,1,-1,0};
  4.     int[] dy={1,0,0,-1};
  5.     public int numIslands(char[][] grid) {
  6.         for (int i = 0; i < grid.length; i++) {
  7.             for (int j = 0; j < grid[0].length; j++) {
  8.                 if (grid[i][j]=='1'){
  9.                     ans++;
  10.                     bfs(grid,new boolean[grid.length][grid[0].length],i,j);
  11.                 }
  12.             }
  13.         }
  14.         return ans;
  15.     }
  16.  
  17.     private void bfs(char[][] grid,boolean[][] vis,int x,int y) {
  18.         Deque<Pair> pairDeque=new LinkedList<>();
  19.         pairDeque.push(new Pair(x,y));
  20.         while (!pairDeque.isEmpty()){
  21.             Pair pair = pairDeque.pop();
  22.             int x1 = pair.x;
  23.             int y1 = pair.y;
  24.             for (int i = 0; i < 4; i++) {
  25.                 int newx=x1+dx[i];
  26.                 int newy=y1+dy[i];
  27.                 if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]=='0'){
  28.                     continue;
  29.                 }
  30.                 grid[newx][newy]='0';
  31.                 pairDeque.push(new Pair(newx,newy));
  32.             }
  33.         }
  34.     }
  35.     class Pair{
  36.         int x;
  37.         int y;
  38.  
  39.         public Pair(int x, int y) {
  40.             this.x = x;
  41.             this.y = y;
  42.         }
  43.     }
  44. }
岛屿的最大面积：
 

. - 力扣（LeetCode）

  1.  int max=0;
  2.     int[] dx={0,1,-1,0};
  3.     int[] dy={1,0,0,-1};
  4.     int count=1;
  5.     public int maxAreaOfIsland(int[][] grid) {
  6.         for (int i = 0; i < grid.length; i++) {
  7.             for (int j = 0; j < grid[0].length; j++) {
  8.                 if (grid[i][j]==1){
  9.                     count=0;
  10.                     dfs(grid,i,j);
  11.                     max=Math.max(max,count);
  12.                 }
  13.             }
  14.         }
  15.         return max;
  16.     }
  17.     private void dfs(int[][] grid,int x,int y){
  18.         count++;
  19.         grid[x][y]=0;
  20.         for (int i = 0; i < 4; i++) {
  21.             int newx=x+dx[i];
  22.             int newy=y+dy[i];
  23.             if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]==0){
  24.                 continue;
  25.             }
  26.             grid[newx][newy]=0;
  27.             dfs(grid,newx,newy);
  28.         }
  29.     }
  30.  
  31.     public static void main(String[] args) {
  32.         LeetCode695dfs leetCode695=new LeetCode695dfs();
  33.         int max = leetCode695.maxAreaOfIsland(new int[][]{{1}});
  34.         System.out.println(max);
  35.     }
  1. class Solution {
  2.     int max=0;
  3.     int[] dx={0,1,-1,0};
  4.     int[] dy={1,0,0,-1};
  5.     int count=1;
  6.     public int maxAreaOfIsland(int[][] grid) {
  7.         for (int i = 0; i < grid.length; i++) {
  8.             for (int j = 0; j < grid[0].length; j++) {
  9.                 if (grid[i][j]==1){
  10.                     count=0;
  11.                     bfs(grid,i,j);
  12.                     max=Math.max(count,max);
  13.                 }
  14.             }
  15.         }
  16.         return max;
  17.     }
  18.     private void bfs(int[][] grid,int x,int y){
  19.         Deque<pair> pairDeque=new LinkedList<>();
  20.         pairDeque.push(new pair(x,y));
  21.         grid[x][y]=0;
  22.         while (!pairDeque.isEmpty()){
  23.             pair pop = pairDeque.pop();
  24.             count++;
  25.             int x1 = pop.x;
  26.             int y1 = pop.y;
  27.             for (int i = 0; i < 4; i++) {
  28.                 int newx=x1+dx[i];
  29.                 int newy=y1+dy[i];
  30.                 if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]==0){
  31.                     continue;
  32.                 }
  33.                 grid[newx][newy]=0;
  34.                 pairDeque.push(new pair(newx,newy));
  35.             }
  36.         }
  37.     }
  38.     
  39.     class pair{
  40.         int x;
  41.         int y;
  42.  
  43.         public pair(int x, int y) {
  44.             this.x = x;
  45.             this.y = y;
  46.         }
  47.     }
  48. }
1020：飞地的数量：

. - 力扣（LeetCode）

  1. class Solution {
  2.     int ans=0;
  3.     int[] dx={0,1,-1,0};
  4.     int[] dy={1,0,0,-1};
  5.     boolean flag=true;
  6.     public int numEnclaves(int[][] grid) {
  7.         for (int i = 0; i < grid[0].length; i++) {
  8.             if (grid[0][i]==1){
  9.                 grid[0][i]=0;
  10.                 dfs(grid,0,i);
  11.             }
  12.             if (grid[grid.length-1][i]==1){
  13.                 grid[grid.length-1][i]=0;
  14.                 dfs(grid,grid.length-1,i);
  15.             }
  16.         }
  17.         for (int i = 0; i < grid.length; i++) {
  18.             if (grid[i][0]==1){
  19.                 grid[i][0]=0;
  20.                 dfs(grid,i,0);
  21.             }
  22.             if (grid[i][grid[0].length-1]==1){
  23.                 grid[i][grid[0].length-1]=0;
  24.                 dfs(grid,i,grid[0].length-1);
  25.             }
  26.         }
  27.         for (int i = 1; i < grid.length-1; i++) {
  28.             for (int j = 1; j < grid[0].length-1; j++) {
  29.                 if (grid[i][j]==1) ans++;
  30.             }
  31.         }
  32.         return ans;
  33.     }
  34.     private void dfs(int[][] grid,int x,int y){
  35.         for (int i = 0; i < 4; i++) {
  36.             int newx=x+dx[i];
  37.             int newy=y+dy[i];
  38.             if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]==0){
  39.                 continue;
  40.             }
  41.             grid[newx][newy]=0;
  42.             dfs(grid,newx,newy);
  43.         }
  44.     }
  45. }

 这题广搜更胜一筹：

  1.  
  2. public class LeetCode1020bfs {
  3.     int ans=0;
  4.     int[] dx={0,1,-1,0};
  5.     int[] dy={1,0,0,-1};
  6.     public int numEnclaves(int[][] grid) {
  7.         for (int i = 0; i < grid[0].length; i++) {
  8.             if (grid[0][i]==1){
  9.                 grid[0][i]=0;
  10.                 bfs(grid,0,i);
  11.             }
  12.             if (grid[grid.length-1][i]==1){
  13.                 grid[grid.length-1][i]=0;
  14.                 bfs(grid,grid.length-1,i);
  15.             }
  16.         }
  17.         for (int i = 0; i < grid.length; i++) {
  18.             if (grid[i][0]==1){
  19.                 grid[i][0]=0;
  20.                 bfs(grid,i,0);
  21.             }
  22.             if (grid[i][grid[0].length-1]==1){
  23.                 grid[i][grid[0].length-1]=0;
  24.                 bfs(grid,i,grid[0].length-1);
  25.             }
  26.         }
  27.         for (int i = 1; i < grid.length-1; i++) {
  28.             for (int j = 1; j < grid[0].length-1; j++) {
  29.                 if (grid[i][j]==1) ans++;
  30.             }
  31.         }
  32.         return ans;
  33.     }
  34.     private void bfs(int[][] grid,int x,int y){
  35.         Deque<pair> deque=new LinkedList<>();
  36.         deque.push(new pair(x,y));
  37.         grid[x][y]=0;
  38.         while (!deque.isEmpty()){
  39.             pair pop = deque.pop();
  40.             int x1 = pop.x;
  41.             int y1 = pop.y;
  42.             for (int i = 0; i < 4; i++) {
  43.                 int newx=x1+dx[i];
  44.                 int newy=y1+dy[i];
  45.                 if (newx<0||newy<0||newx>=grid.length||newy>=grid[0].length||grid[newx][newy]==0){
  46.                     continue;
  47.                 }
  48.                 grid[newx][newy]=0;
  49.                 deque.push(new pair(newx,newy));
  50.             }
  51.         }
  52.     }
  53.     class pair{
  54.         int x;
  55.         int y;
  56.  
  57.         public pair(int x, int y) {
  58.             this.x = x;
  59.             this.y = y;
  60.         }
  61.     }
  62. }
被围绕的区域：

 . - 力扣（LeetCode）

  1. class Solution {
  2.     int[] dx={0,1,-1,0};
  3.     int[] dy={1,0,0,-1};
  4.     public void solve(char[][] board) {
  5.         int[][] flag=new int[board.length][board[0].length];
  6.         for (int i = 0; i < board.length; i++) {
  7.             if (board[i][0]=='O'){
  8.                 dfs(board,i,0,flag);
  9.             }
  10.             if (board[i][board[0].length-1]=='O'){
  11.                 dfs(board,i,board[0].length-1,flag);
  12.             }
  13.         }
  14.         for (int i = 0; i < board[0].length; i++) {
  15.             if (board[0][i]=='O'){
  16.                 dfs(board,0,i,flag);
  17.             }
  18.             if (board[board.length-1][i]=='O'){
  19.                 dfs(board,board.length-1,i,flag);
  20.             }
  21.         }
  22.         for (int i = 1; i <board.length-1 ; i++) {
  23.             for (int j = 1; j < board[0].length-1; j++) {
  24.                 if (flag[i][j]==0&&board[i][j]=='O'){
  25.                     board[i][j]='X';
  26.                 }
  27.             }
  28.         }
  29.     }
  30.  
  31.     private void dfs(char[][] board, int x, int y, int[][] flag) {
  32.         flag[x][y]=1;
  33.         for (int i = 0; i < 4; i++) {
  34.             int newx=x+dx[i];
  35.             int newy=y+dy[i];
  36.             if (newx<0||newy<0||newx>=board.length||newy>=board[0].length||board[newx][newy]=='X'||flag[newx][newy]==1){
  37.                 continue;
  38.             }
  39.             dfs(board,newx,newy,flag);
  40.         }
  41.     }
  42. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/408806
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号