算法图类型刷题-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法图类型刷题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

基础部分

使用的基础数据结构和方法

class Solution {
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int[][] grid;
    //预处理部分
    …………………………
    //开始计算
     for(int i=0;i<grid.length;i++){
        for(int j=0;j<grid[0].length;j++){
            //从未计算部分开始
            if(grid[i][j]==-1){
                for(int k=0;k<dir.length;k++){
                     DFS(i+dir[k][0],j+dir[k][1],i,j);
                }
            }
         }
     }
     //后处理部分
     …………………………
    public void DFS(int i,int j,int si,int sj){
        if(i>=0 && j>=0 && i<grid.length && j<grid[0].length){
            if(condition){
                grid[i][j]= x;
                DFS(i+dx[k],j+dy[k],si,sj);
             }
        }
    }
}

第一题：

广度优先算法：

publicint[][] floodFill(int[][] image, intsr, intsc, intcolor) {
        if(image==null||image.length==0||image[0].length==0)
        {
            returnimage;
        } //排除特殊情况
        intfirstcolor=image[sr][sc];
        if(firstcolor==color){
            returnimage;
        }
        //广度优先将坐标点作为int数组
        Queue<int[]>st=newLinkedList();
        st.offer(newint[] {sr,sc});
        while(!st.isEmpty()){
            int[] point=st.poll();
            inti=point[0]; intj=point[1];
            if(image[i][j]==firstcolor){
                image[i][j]=color;
                if(i-1>=0&&image[i-1][j]==firstcolor){
                    st.offer(newint[] {i-1,j});
                }
                if(i+1<image.length&&image[i+1][j]==firstcolor){
                    st.offer(newint[] {i+1,j});
                }
                if(j-1>=0&&image[i][j-1]==firstcolor){
                    st.offer(newint[] {i,j-1});
                }
                if(j+1<image[0].length&&image[i][j+1]==firstcolor){
                    st.offer(newint[] {i,j+1});
                }
            }
        }
        returnimage;
}

深度优先：

publicint[][] floodFill(int[][] image, intsr, intsc, intcolor) {
        if(image==null||image.length==0||image[0].length==0||image[sr][sc]==color)
        {
            returnimage;
        }
        inti=sr; intj=sc;
        intfirstcolor=image[i][j];
        image[i][j]=color;
        if(i-1>=0&&image[i-1][j]==firstcolor)
            floodFill(image,i-1,j,color);
        if(i+1<image.length&&image[i+1][j]==firstcolor)
            floodFill(image,i+1,j,color);
        if(j-1>=0&&image[i][j-1]==firstcolor)
            floodFill(image,i,j-1,color);
        if(j+1<image[0].length&&image[i][j+1]==firstcolor)
            floodFill(image,i,j+1,color);
        returnimage;
    }

第二题

    publicintnumIslands(char[][] grid) {
        int[][] temp=newint[grid.length][grid[0].length];
        intcount=0;
        for(inti=0;i<temp.length;i++){
            for(intj=0;j<temp[0].length;j++){
                if(temp[i][j]==0&&grid[i][j]=='1'){
                    DFS(grid,temp,i,j);
                    count++;
                }
            }
        }
        returncount;
    }
    publicvoidDFS(char[][] grid,int[][] temp,inti,intj){
        if(grid[i][j]=='1'){
            temp[i][j]=1;
        if(i-1>=0&&temp[i-1][j]==0)DFS(grid,temp,i-1,j);
        if(i+1<grid.length&&temp[i+1][j]==0)DFS(grid,temp,i+1,j);
        if(j-1>=0&&temp[i][j-1]==0)DFS(grid,temp,i,j-1);
        if(j+1<grid[0].length&&temp[i][j+1]==0)DFS(grid,temp,i,j+1);
        }
    }

第三题

广度优先：

publicintmaxAreaOfIsland(int[][] grid) {
    Queue<int[]>queue=newLinkedList();
    int [][] temp=newint[grid.length][grid[0].length];
    intmax=0;
    for(inti=0;i<temp.length;i++){
        for(intj=0;j<temp[0].length;j++){
            if(temp[i][j]==0&&grid[i][j]==1){
                int[] num= {0};
                queue.offer(newint[]{i,j});
                while(!queue.isEmpty()){
                    int[] point=queue.poll();
                    intleft=point[0]; intright=point[1];
                    temp[left][right]=1;
                    if(grid[left][right]==1){
                        num[0]++;
                        if(left-1>=0&&temp[left-1][right]==0){
                            temp[left-1][right]=1;
                            queue.offer(newint[]{left-1,right});
                        }                                
                        if(left+1<temp.length&&temp[left+1][right]==0){
                            temp[left+1][right]=1;
                            queue.offer(newint[]{left+1,right});
                        }
                        if(right-1>=0&&temp[left][right-1]==0){
                            temp[left][right-1]=1;
                            queue.offer(newint[]{left,right-1});
                        }
                        if(right+1<temp[0].length&&temp[left][right+1]==0){
                            temp[left][right+1]=1;
                            queue.offer(newint[]{left,right+1});
                        }
                    } 
                }
                max=Math.max(max,num[0]);
            }
        }
    }
        returnmax;
    }

深度优先：

publicintmaxAreaOfIsland(int[][] grid) {
    int [][] temp=newint[grid.length][grid[0].length];
    intmax=0;
    for(inti=0;i<temp.length;i++){
        for(intj=0;j<temp[0].length;j++){
            if(temp[i][j]==0&&grid[i][j]==1){
                int[] num= {0};
                DFS(grid,temp,i,j,num);
                max=Math.max(max,num[0]);
            }
        }
    }
    returnmax;
}
publicvoidDFS(int[][] grid,int[][] temp,inti,intj,int[] num){
    if(grid[i][j]==1){
        temp[i][j]=1;
        num[0]++;
        if(i-1>=0&&temp[i-1][j]==0)DFS(grid,temp,i-1,j,num);
        if(i+1<grid.length&&temp[i+1][j]==0)DFS(grid,temp,i+1,j,num);
        if(j-1>=0&&temp[i][j-1]==0)DFS(grid,temp,i,j-1,num);
        if(j+1<grid[0].length&&temp[i][j+1]==0)DFS(grid,temp,i,j+1,num);
    }
}

第四题：

publicintclosedIsland(int[][] grid) {
        int [][]temp=newint[grid.length][grid[0].length];
        intcount=0;
        for(intj=0;j<temp[0].length;j++){
            DFS(grid,temp,0,j);
            DFS(grid,temp,grid.length-1,j);
        }
        for(inti=0;i<temp.length;i++){
            DFS(grid,temp,i,0);
            DFS(grid,temp,i,grid[0].length-1);
        }
        for(inti=0;i<temp.length;i++){
            for(intj=0;j<temp[0].length;j++){
                if(temp[i][j]==0&&grid[i][j]==0){
                    DFS(grid,temp,i,j);
                    count++;
                }
            }
        }
        for(inti[]:temp){
            for(intj:i){
                System.out.print(j);
            }
        }
        returncount;
    }
publicvoidDFS(int[][] grid,int[][] temp,inti,intj){
    if(grid[i][j]==0){
        temp[i][j]=1;
        if(i-1>=0&&temp[i-1][j]==0) DFS(grid,temp,i-1,j);
        if(i+1<grid.length&&temp[i+1][j]==0) DFS(grid,temp,i+1,j);
        if(j-1>=0&&temp[i][j-1]==0) DFS(grid,temp,i,j-1);
        if(j+1<grid[0].length&&temp[i][j+1]==0)DFS(grid,temp,i,j+1);
    }
}

第五题：

classSolution {
    publicintnumEnclaves(int[][] grid) {
        int[][] temp=newint[grid.length][grid[0].length];
        int[] count= {0};
        for(intj=0;j<temp[0].length;j++){
            DFS(grid,temp,0,j,count);
            DFS(grid,temp,grid.length-1,j,count);
        }
        for(inti=0;i<temp.length;i++){
            DFS(grid,temp,i,0,count);
            DFS(grid,temp,i,grid[0].length-1,count);
        }
        count[0] =0;
        for(inti=0;i<temp.length;i++){
            for(intj=0;j<temp[0].length;j++){
                if(temp[i][j]==0&&grid[i][j]==1){
                    DFS(grid,temp,i,j,count);
                }
            }
        }
        returncount[0];
    }
    publicvoidDFS(int[][] grid,int[][] temp,inti,intj,int[] count){
        if(grid[i][j]==1){
            temp[i][j]=1;
            count[0]++;
            if(i-1>=0&&temp[i-1][j]==0) DFS(grid,temp,i-1,j,count);
            if(i+1<grid.length&&temp[i+1][j]==0) DFS(grid,temp,i+1,j,count);
            if(j-1>=0&&temp[i][j-1]==0) DFS(grid,temp,i,j-1,count);
            if(j+1<grid[0].length&&temp[i][j+1]==0) DFS(grid,temp,i,j+1,count);
        }
    }
}

第六题：

classSolution {
    booleannotSub;
    publicintcountSubIslands(int[][] grid1, int[][] grid2) {
        intcount=0;
        for(inti=0;i<grid2.length;i++){
            for(intj=0;j<grid2[0].length;j++){
                if(grid2[i][j]==1){
                    notSub=false;
                    DFS(grid1,grid2,i,j);
                    if(!notSub)count++;
                }
            }
        }
        returncount;
    }
    publicvoidDFS(int[][] grid1,int[][] grid2,inti,intj){
        if (i<0||j<0||i>=grid1.length||j>=grid1[0].length||grid2[i][j] ==0) {
            return;
        } 
         if (grid1[i][j] !=1) {
            notSub=true;
        }
        if(grid1[i][j]==1&&grid2[i][j]==1){
            grid2[i][j]=0;
            DFS(grid1,grid2,i-1,j);
            DFS(grid1,grid2,i+1,j);
            DFS(grid1,grid2,i,j-1);
            DFS(grid1,grid2,i,j+1);
        }
    }
}

第七题：

深度优先：

class Solution {
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int[][] grid;
    public int maxDistance(int[][] grid) {
        this.grid = grid;
        //预处理
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                //先遍历一遍，将陆地标识出来
                if(grid[i][j]==1){
                    grid[i][j]=-1;
                }
            }
        }
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                //从陆地着手，距离公式计算
                if(grid[i][j]==-1){
                    for(int k=0;k<dx.length;k++){
                        DFS(i+dx[k],j+dy[k],i,j);
                    }
                }
            }
        }
        int max=-1;
        for(int[] i:grid){
            for(int j:i){
                max = Math.max(j,max);
            }
        }
        if(max==0) return -1;
        return max;
    }
    public void DFS(int i,int j,int si,int sj){
        if(i>=0 && j>=0 && i<grid.length && j<grid[0].length){
            int dis = Math.abs(si-i)+Math.abs(sj-j);
            if(grid[i][j]>dis||grid[i][j]==0){
                //由于是曼哈顿距离，所以应该是最短距离
                if(grid[i][j]!=0){
                   grid[i][j]=Math.min(grid[i][j],dis);
                }else{
                   grid[i][j]= dis;
                }
                for(int k=0;k<dx.length;k++){
                    DFS(i+dx[k],j+dy[k],si,sj);
                }
            }
        }
    }
}

广度优先：

class Solution {
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
//特殊方法简化方向
    public int maxDistance(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    grid[i][j] = -1;
                }
            }
        } 
        int ans = -1;
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int step = Math.max(grid[poll[0]][poll[1]], 0);
            for (int[] di : dirs) {
                int nx = poll[0] + di[0], ny = poll[1] + di[1];
                if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length) {
                     continue;
                 }
                if (grid[nx][ny] != 0) continue;
                queue.offer(new int[]{nx, ny});
                grid[nx][ny] = step + 1;
                ans = Math.max(ans, step + 1);
            }
        }
        return ans;
    }
}

文章来源地址https://www.toymoban.com/news/detail-590385.html

到了这里，关于算法图类型刷题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！