2021-05-30LC “阿里题库” 200.岛屿数量 1114.按序打印_阿里 岛屿题目-程序员宅基地

技术标签: 算法  # 大厂高频题  

在这里插入图片描述

/*
--------------------------------------------------------------------------------------------------------------------------------------
昨天考完试,可能2个小时坐风扇下面,吹的头疼,回宿舍躺着就在看大佬对网格型的dfs进行一个分析,今天自己整理一下
首先想一下一个树的一个dfs遍历
void tarverse(TreeNode root){
    if(root == null)
        return;
    tarverse(root.left);
    tarverse(root.right);
}
通过树的dfs遍历我们可以发现有两个特点,1、访问相邻点 2、找类似于递归头的东西
1、树中访问相邻结点就是左右子树,而对应网格中就是上下左右结点
2、找类似于递归头的东西,就是判断是否在网格范围内
因此可以得到网格dfs的框架:
void dfs(int[][] grid , int i ,int j){
    if(!inArea(grid , i ,j)){
        return;
    }
    dfs(grid,i-1,j);
    dfs(grid,i,j-1);
    dfs(grid,i+1,j);
    dfs(grid,i,j+1);
}
boolean inArea(int[][] grid , int i ,int j){
    return i>=0 && i<grid.length && j>=0 && j<grid[0].length;
}
虽然遍历了,但是会出现很多重复的遍历点,因此需要在此基础上加标志,标志已经遍历过得结点
0-----海洋格子
1-----陆地格子
2-----陆地格子
void dfs(int[][] grid , int l , int r){
    if(!inArea(grid,l,r)){
        return;
    }
    //我们要的陆地格子
    if(grid[i][j]!=1)
        return;
    //遍历过的我们要设置标志位
    grid[i][j] ==2
    //然后我们要访问上下左右四个结点
    dfs(grid , i+1 , j);
    dfs(grid , i-1 , j);
    dfs(grid , i , j+1);
    dfs(grid , i , j-1);
}
boolean inArea(int[][] grid , int i , int j){
    return i>=0 && i<grid.length && j>=0 && j<grid[0].length;
这就是一个岛屿问题的dfs遍历方法,现在我们对这个题来写过程
}
*/
/*
---------------------------------------------------------------------------------------------------------------
时间复杂度O(mn) 空间复杂度O(mn)
*/
class Solution {
    

    public int numIslands(char[][] grid) {
    
       //题目中提示给了m,n的限制所以不用对为0进行判断
       int carryL = grid.length , rowL = grid[0].length , num_IsLands = 0;
       //遍历数组去求
       for(int i=0 ; i<carryL ; i++){
    
           for( int j=0 ; j<rowL ; j++){
    
               if(grid[i][j] == '1'){
    
                   num_IsLands++;
                   dfs(grid , i , j);
               }
           }
       }
       return num_IsLands;
    }
    private void dfs(char[][] grid , int i ,int j){
      //这里的dfs是为了找网格中一个岛屿多大,只要碰到了"0"或者"2"就返回
        //先判断
        if(!inArea(grid , i , j)){
    
            return;
        }
        //进一步设置递归头,也就是结束的地方
        if( grid[i][j]!='1')
            return;
        grid[i][j] = '2';
        dfs(grid , i-1 , j);
        dfs(grid , i+1 , j);
        dfs(grid , i , j-1);
        dfs(grid , i , j+1);
    }
    private boolean inArea(char[][] grid , int i , int j){
    
        return i>=0 && i<grid.length && j>=0 && j<grid[0].length;
    }
}
//------------------------------------------------------------------------------------------------------------------------------------------
/*“bfs”:扫描整个二维网格,如果一个位置为1,则将其加入队列,队列里面存的是第几个网格,开始进行广度优先搜索。在bfs的过程中,每个搜索到的1都
被重新标记为0,直到队列为空,搜索结束
时间复杂度O(mn)  空间复杂度O(min(m,n))
*/
class Solution {
    

    public int numIslands(char[][] grid) {
    
        int carL = grid.length , rowL = grid[0].length  , num_IsLands = 0;
        for(int i=0 ; i<carL ; i++){
    
            for(int j=0 ; j<rowL ; j++){
    
                if(grid[i][j]=='1'){
    
                    num_IsLands++;
                    grid[i][j]='0';
                    Queue<Integer> queue = new LinkedList<>();
                    queue.add(i*rowL+j);
                    while(!queue.isEmpty()){
    
                        int curVal = queue.remove();
                        int curC = curVal/rowL;
                        int curR = curVal%rowL;
                        if(curC-1>=0 && grid[curC-1][curR]=='1'){
    
                            queue.add((curC-1)*rowL+curR);
                            grid[curC-1][curR]='0';
                        }
                        if(curC+1 < carL && grid[curC+1][curR]=='1'){
    
                            queue.add((curC+1)*rowL+curR);
                            grid[curC+1][curR]='0';
                        }
                        if(curR-1>=0 && grid[curC][curR-1]=='1'){
    
                            queue.add(curC*rowL+curR-1);
                            grid[curC][curR-1]='0';
                        }
                        if(curR+1<rowL && grid[curC][curR+1]=='1'){
    
                            queue.add(curC*rowL+curR+1);
                            grid[curC][curR+1]='0';
                        }
                    }
                }
            }
        }
        return num_IsLands++;
    }
}

在这里插入图片描述

// //第一种用synchronized实现 ,第二种用volatile实现
class Foo {
    

    public Foo() {
    
        
    }

    private Object foo = new Object();
    private boolean firstFinished = false;
    private boolean secondFinished = false;
     
    public void first(Runnable printFirst) throws InterruptedException {
    
        synchronized(foo){
    
            firstFinished = true;
            printFirst.run();
            foo.notifyAll();
        }
        // printFirst.run() outputs "first". Do not change or remove this line.
    }

    public void second(Runnable printSecond) throws InterruptedException {
    
        
        // printSecond.run() outputs "second". Do not change or remove this line.
        synchronized(foo){
    
            while(firstFinished!=true){
    
                foo.wait();
            }
            printSecond.run();
            secondFinished = true;
            foo.notifyAll();
        }
    }

    public void third(Runnable printThird) throws InterruptedException {
    
        
        // printThird.run() outputs "third". Do not change or remove this line.
        synchronized(foo){
    
            while(secondFinished!=true){
    
                foo.wait();
            }
            printThird.run();
        }
    }
}


// //第二种用volatile实现
class Foo {
    

    public Foo() {
    
        
    }

    private volatile int count = 1;

    public void first(Runnable printFirst) throws InterruptedException {
    
        // printFirst.run() outputs "first". Do not change or remove this line.
        while(count==1){
    
            printFirst.run();
            count++;
        }
    }

    public void second(Runnable printSecond) throws InterruptedException {
    
        
        // printSecond.run() outputs "second". Do not change or remove this line.
        while(count!=2);
        printSecond.run();
        count++;
    }

    public void third(Runnable printThird) throws InterruptedException {
    
        
        // printThird.run() outputs "third". Do not change or remove this line.
        while(count!=3);
        printThird.run();

    }
}

//第三种用CountDownLatch实现
//import java.util.concurrent.CountDownLatch;
class Foo {
    

    public Foo() {
    
        
    }
    private CountDownLatch second = new CountDownLatch(1);
    private CountDownLatch third = new CountDownLatch(1);
    public void first(Runnable printFirst) throws InterruptedException {
    
        // printFirst.run() outputs "first". Do not change or remove this line.
       printFirst.run();
       second.countDown();
    }

    public void second(Runnable printSecond) throws InterruptedException {
    
        
        // printSecond.run() outputs "second". Do not change or remove this line.
        second.await();
        printSecond.run();
        third.countDown();
    }

    public void third(Runnable printThird) throws InterruptedException {
    
        
        // printThird.run() outputs "third". Do not change or remove this line.
        third.await();
        printThird.run();
        third.countDown();
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wwj17647590781/article/details/117394424

智能推荐

linux pycharm 的tools选项下没有deployment_pycharm没有deployment-程序员宅基地

文章浏览阅读8.1k次。一、问题pycharm 的tools下没有deployment选项,无法进行远程执行。二、前言使用的pycharm版本PyCharm 2019.3.2 (Community Edition)Build #PC-193.6015.41, built on January 21, 2020Runtime version: 11.0.5+10-b520.30 amd64VM: Op..._pycharm没有deployment

[实战]input失焦事件先于点击事件发生时怎么办?_失去焦点优先于点击事件-程序员宅基地

文章浏览阅读2.3k次,点赞2次,收藏3次。例子:看上面这个例子,我们的需求是:点击备注表格时,该表格变为可编辑状态的输入框,会出现输入框、两个按钮。点击对勾时,会修改备注发送给后端修改请求,修改备注,变为不编辑状态,输入框、按钮消失。失去焦点时,输入框同样变为不可编辑状态,输入框、按钮消失。问题的关键在于,input失焦事件总是先于对勾按钮的点击事件发生的。即当我们点击按钮对勾时,已经先失去了焦点,将按钮隐藏了。因此根本不可能..._失去焦点优先于点击事件

wangeditor 取消自动获取焦点_wangeditor默认不获得的焦点-程序员宅基地

文章浏览阅读5.6k次。使用wangeditor 富文本编辑器的时候 在打开的页面的时候 总会自动定位到此处 有时候富文本 在底部时 也会定位到那 很不方便在node_module 中 找到wangeditor/release/wangeditor.js 将this.selection.createRangeByElem($last, false, true);this.selection.restoreSelec..._wangeditor默认不获得的焦点

pytorch使用之微调网络模型_获取线性全连接层的输入维度-程序员宅基地

文章浏览阅读3.6k次。import torchvision.models as models1.调整最后一层输出维度model = models.ResNet(pretrained=True)fc_features = model.fc.in_features# 获取全连接层输入维度model.fc = torch.nn.Linear(fc_features, num_class)2.调整某一层参数impo..._获取线性全连接层的输入维度

T1型造影剂介绍及核磁共振成像MRI造影剂介绍_二氧化锰(mno2),磁共振造影剂 t1 t2-程序员宅基地

文章浏览阅读2k次。核磁共振成像MRI造影剂可以分为纵向弛豫造影剂(T1制剂)和横向弛豫造影剂(T2制剂)。T1制剂是通过水分子中的氢核和顺磁性金属离子直接作用来缩短T1,从而增强信号,图像较亮;T2制剂是通过对外部局部磁性环境的不均匀性进行干扰,使邻近氢质子在弛豫中很快产生相(diphase)来缩短T2,从而减弱信号,图像较暗。弛豫效率是MRI造影剂关键指标之一。弛豫效率高的样品,可以使用少的量达到好的效果;在造影剂研究领域,纽迈专门开发了小型的核磁共振成像分析仪,可测试方便的测试造影剂T1、T2弛豫时间,并..._二氧化锰(mno2),磁共振造影剂 t1 t2

利用Azure搭建自己的个人网站_azure 部署网站-程序员宅基地

文章浏览阅读3.5k次,点赞3次,收藏3次。一、实验目的 在云平台部署自己的个人网站二.实验平台 Azure三、实验步骤及内容(需要过程即截图) 1. 搭建云服务器 打开Azure登陆 新建 -&gt;Web+移动 -&gt;Web应用 选择应用服务计划-&gt;新建,选择阶层,确认,然后创建 搭建成功 ..._azure 部署网站

随便推点

和我一起作Tess的windbg lab - Lab3, Memory-程序员宅基地

文章浏览阅读131次。原文地址:http://blogs.msdn.com/b/tess/archive/2008/02/15/net-debugging-demos-lab-3-memory.aspx操作步骤:1、产生压力:tinyget -srv:localhost -uri:/BuggyBits/Links.aspx -loop:40002、观察taskmgr的输出,w3wp的内存每秒钟大概...

@在 centos7 下安装 oracle 12c_在设置specify recovery options 时报磁盘空间不足-程序员宅基地

文章浏览阅读1.1k次。@在 centos7 下安装 oracle 12c文章目录@在 centos7 下安装 oracle 12c环境安装必须的软件包前期准备修改 hostname配置 SSH 和 X11 转发安装 Oracle 12c创建目录和部署安装文件创建安装用目录(按照OFA标准)修改 ulimit 值:最大文件描述符数为4096修改 ulimit 值:最大用户进程数为16384增大 tmpfs 到4GB若 ..._在设置specify recovery options 时报磁盘空间不足

程序员的那些反模式-程序员宅基地

文章浏览阅读2.2k次,点赞4次,收藏7次。有鸡汤就有反鸡汤,有模式就有反模式。今天,我们来谈一谈程序员的行为中的那些反模式,涉及程序员的日常工作和学习的各个方面。这些反行为模式,并不针对某些特定的个人。如果你不幸中招,千万不要懊恼,因为这实在太正常不过了,很多反模式的坑我也是亲身踩过的^-^稍微修改几行代码就调试对所有程序员来说,这个行为有一点心理上的原因:工程师都喜欢在做完一点修改之后,立即看到它的效..._反模式开发

人工智能、机器学习和模式识别以及神经网络_智能控制,智能检测,模式识别,神经网络,模糊逻辑,机器学习,人工智能,深度学习,优化-程序员宅基地

文章浏览阅读2.8k次。梯度下降的定义梯度下降问题就是沿着导数下降的地方移动,直到某点梯度最小,这个时候就达到了最优解多变量的梯度下降问题神经网络中遇到的问题是多变量的最优解,即多变量的梯度为零的解局部最优和全局最优问题通常,我们求得的最优解不一定是全局最优解,其可能只是局部最优解。..._智能控制,智能检测,模式识别,神经网络,模糊逻辑,机器学习,人工智能,深度学习,优化

每个人在职场上都不是一帆风顺的,总是会在工作中遇到各种各样的困难_工作没有一帆风顺总有坎坷不平-程序员宅基地

文章浏览阅读2.4k次。每个人在职场上都不是一帆风顺的,总是会在工作中遇到各种各样的困难,这时候有些职场人就会坚持不住,产生消极的情绪,这对我们在职场上的发展是很不利的。为了我们能在职场上更好的发展,一定要学会控制好自己的情绪,要有一定的心理承受能力。有一些人,因为自身性格的原因,喜欢比较与别人在习惯或者生活中的不同,通常会表现出一种自卑的心理。那你一定不要有这样的想法,每个人从小的生活经历不同,做事习惯肯定也不相同,因此我们要在职场上中养成这四个好习惯,让我们在职场上更加自信。要勇于认识自己的缺点在工作中,我们通常会对自己_工作没有一帆风顺总有坎坷不平

Eigen notes_eigen::matrix4f转eigen::affine3f-程序员宅基地

文章浏览阅读193次。Eigen::Affine3与Eigen::Matrix4的转换// Matrix4f to Affine3fEigen::Matrix4f matrixTrans;Eigen::Transform<float, 3, Eigen::Affine> affineTrans (matrixTrans);// Affine3f to Matrix4fEigen::Transf..._eigen::matrix4f转eigen::affine3f

推荐文章

热门文章

相关标签