算法图类型刷题

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

基础部分

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

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);
             }
        }
    }
}
第一题:
算法图类型刷题,java,算法,图论,Powered by 金山文档
广度优先算法:
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;
    }
第二题
算法图类型刷题,java,算法,图论,Powered by 金山文档
    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);
        }
    }
第三题
算法图类型刷题,java,算法,图论,Powered by 金山文档
广度优先:
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);
    }
}
第四题:
算法图类型刷题,java,算法,图论,Powered by 金山文档
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);
    }
}
第五题:
算法图类型刷题,java,算法,图论,Powered by 金山文档
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);
        }
    }
}
第六题:
算法图类型刷题,java,算法,图论,Powered by 金山文档
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);
        }
    }
}
第七题:
算法图类型刷题,java,算法,图论,Powered by 金山文档
深度优先:
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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 刷题日记09《图论基础》

    对于图结构而言,常见的存储结构主要有两种:邻接表和邻接矩阵:   邻接表很直观,我把每个节点  x  的邻居都存到一个列表里,然后把  x  和这个列表关联起来,这样就可以通过一个节点  x  找到它的所有相邻节点。 邻接矩阵则是一个二维布尔数组,我们权且称为 

    2024年02月16日
    浏览(34)
  • ✔ ★ 算法基础笔记(Acwing)(三)—— 搜索与图论(17道题)【java版本】

    1. 排列数字(3分钟) 每次遍历dfs参数是 遍历的坑位 原题链接 2. n-皇后问题 原题链接 方法 1. 按行遍历(过程中有回溯、剪枝) 思想: 每次递归中,遍历一行的元素,如果可以放皇后,就递归到下一行,下一行中不行了,就返回来,回溯, 方法2. 按每个元素遍历(没有减枝)

    2024年02月05日
    浏览(48)
  • 刷题笔记26——图论二分图判定

    世界上的事情,最忌讳的就是个十全十美,你看那天上的月亮,一旦圆满了,马上就要亏厌;树上的果子,一旦熟透了,马上就要坠落。凡事总要稍留欠缺,才能持恒。 ——莫言 visited数组是在如果有环的情况下,防止在图中一直绕圈设置的,类似于剪枝操作,走过了就没必要再走一遍

    2024年02月07日
    浏览(40)
  • 刷题笔记25——图论课程表

    为了最终理解你所不理解的,你必须经历一条愚昧无知的道路。为了占有你从未占有的东西,你必须经历被剥夺的道路。为了达到你现在所不在的名位,你必须经历那条你不在其中的道路。——艾略特 非常奇妙,我最初的错误是如下,在找到目标节点后直接加入到res中,但是

    2024年02月07日
    浏览(38)
  • Java算法 leetcode简单刷题记录6

    环和杆: https://leetcode.cn/problems/rings-and-rods/ 统计范围内的元音字符串数: https://leetcode.cn/problems/count-the-number-of-vowel-strings-in-range/ 最长平衡子字符串: https://leetcode.cn/problems/find-the-longest-balanced-substring-of-a-binary-string/ K 个元素的最大和: https://leetcode.cn/problems/maximum-sum-with-exa

    2024年01月24日
    浏览(45)
  • Java算法 leetcode简单刷题记录4

    买卖股票的最佳时机: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 笨办法: 记录当天的值及之后的最大值,相减得到利润; 所有的天都计算下,比较得到利润最大值; 会超时 记录过程中遇到的最低值,每当有利润大于0及大于上一个利润值的情况,赋值; 最小和分割:

    2024年01月23日
    浏览(44)
  • 【图论刷题-6】力扣 797. 所有可能的路径

    机器人的运动范围 矩阵中的路径 图像渲染 水位上升的泳池中游泳 寻找图中是否存在路径 所有可能的路径 力扣地址:https://leetcode.cn/problems/all-paths-from-source-to-target/ 这是一道比较典型的深度优先遍历、广度优先遍历案例,强烈推荐初学者完成这道题并且常常回来看看(也欢

    2024年02月06日
    浏览(42)
  • 【刷题】图论——最小生成树:Prim、Kruskal【模板】

    假设有n个点m条边。 Prim适用于邻接矩阵存的稠密图,时间复杂度是 O ( n 2 ) O(n^2) O ( n 2 ) ,可用堆优化成 O ( n l o g n ) O(nlogn) O ( n l o g n ) 。 Kruskal适用于稀疏图,n个点m条边,时间复杂度是 m l o g ( m ) mlog(m) m l o g ( m ) 。 Prim:遍历n次,每次选择 连通块和外面的点 到连通块距离

    2024年04月13日
    浏览(43)
  • 【离散数学】——期末刷题题库(图论应用题)

    🎃个人专栏: 🐬 算法设计与分析:算法设计与分析_IT闫的博客-CSDN博客 🐳Java基础:Java基础_IT闫的博客-CSDN博客 🐋c语言:c语言_IT闫的博客-CSDN博客 🐟MySQL:数据结构_IT闫的博客-CSDN博客 🐠数据结构:​​​​​​数据结构_IT闫的博客-CSDN博客 💎C++:C++_IT闫的博客-CSDN博

    2024年02月04日
    浏览(37)
  • Java处理doc类型的Word文档转换成html(按顺序保留格式+图片)

    最新有个新需求,就是doc文档转换html内容倒不是很难,给大家分享一下,总体思路就是按doc转html的思路来走,唯一缺点是不会自动转换图片,图片是要手动转成base64,默认是有html、body、head、meta等等标签,我这里都用正则处理掉了。 需要注意的是: .docx 格式的 Word 文档是

    2024年02月03日
    浏览(84)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包