【每日一题Day245】面试题 16.19. 水域大小 | dfs

这篇具有很好参考价值的文章主要介绍了【每日一题Day245】面试题 16.19. 水域大小 | dfs。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

面试题 16.19. 水域大小

你有一个用于表示一片土地的整数矩阵land,该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小,返回值需要从小到大排序。

dfs感染~

  • 思路

    对于每一个水域dfs搜索其八个方向连通的水域大小,添加至动态数组中,最后将动态数组排序后返回

    • 为了避免重复访问,访问过一个水域后,将其设置为土地
  • 实现文章来源地址https://www.toymoban.com/news/detail-496749.html

    class Solution {
        int m, n;
        int[][] land;
        public int[] pondSizes(int[][] land) {
            this.m = land.length;
            this.n = land[0].length;
            this.land = land;
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < m; i++){
                for (int j = 0; j < n; j++){
                    if (land[i][j] == 0){
                        list.add(dfs(i, j));
                    }
                }
            }
            return list.stream().sorted().mapToInt(x -> x).toArray();
        }
        public int dfs(int x, int y){
            int res = 0;
            if (land[x][y] == 0){
                land[x][y] = 1;
                res += 1;
                for (int i = -1; i <= 1; i++){
                    for (int j = -1; j <= 1; j++){
                        if (i == 0 && j == 0) continue;
                        int newX = x + i;
                        int newY = y + j;
                        if (newX >= 0 && newX < m && newY >= 0 && newY < n){
                            res += dfs(newX, newY);
                        }
                    }
                }
            }
            return res;
        }
    }
    
    • 复杂度
      • 时间复杂度: O ( m ∗ n ) \mathcal{O}(m*n) O(mn)
      • 空间复杂度: O ( m ∗ n ) \mathcal{O}(m*n) O(mn)

到了这里,关于【每日一题Day245】面试题 16.19. 水域大小 | dfs的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 每日一题2023.7.19|ACM模式

    参考博客 最基本,最常用的字符或者数字的输入方式。在输入过程中会过滤掉不可见字符、如空格、回车、tab。若不想过滤掉空白字符,可以使用noskipws流进行控制。 运行结果 遇到空格回车等会结束获取输入的字符串,后面的字符串会被过滤掉(存放在输入流中),如果后面还

    2024年02月16日
    浏览(45)
  • [Week 19]每日一题(C++,数学,并查集,动态规划)

    目录 [Daimayuan] T1 倒数第n个字符串(C++,进制) 输入格式 输出格式 样例输入 样例输出 解题思路 [Daimayuan] T2 排队(C++,并查集) 输入格式 输出格式 样例输入1 样例输出1 样例输入2 样例输出2 样例输入3 样例输出3 数据规模 解题思路 [Daimayuan] T3 素数之欢(C++,BFS) 数据规模

    2024年02月02日
    浏览(52)
  • 2023-07-16力扣每日一题

    链接: 834. 树中距离之和 题意: 给定一个树,有n个节点,需要得到每个节点与其他节点的距离和 解: 还以为是弗洛伊德,一看范围3E4直接晕倒 想了四个小时,实在是想不出来了,看了一下评论里的转移公式 设 DP[i] 为节点 i 与其他节点的距离和, DP[F] 是节点 i 的父节点与

    2024年02月16日
    浏览(42)
  • 2023-08-16力扣每日一题

    链接: 2682. 找出转圈游戏输家 题意: 环形1到n,从1开始,每次 移动 第i次*k ,当移动到出现过的序号时停下, 求没移动到的数字 解: 简单模拟题,我也以为有数学做法,可恶 实际代码: 限制: 1 = k = n = 50

    2024年02月12日
    浏览(37)
  • C语言每日一题:16:数对。

    1.x,y均不大于n,就是小于等于n。 2.x%y大于等于k。 3.一般的思路使用双for循环去遍历每一对数。 代码实现: 我们的运行结果是 我们在vs2022下测试代码的结果是正确的什么说明我们的代码思路是没有问题可以计算出结果但是呢,题目要求时间限制是1s,在vs运行出结果至少用了

    2024年02月13日
    浏览(40)
  • LeetCode 每日一题 2023/7/10-2023/7/16

    记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步 7/10 16. 最接近的三数之和 排序 先确定一个最小数 双指针确定之后两个数 7/11 1911. 最大子序列交替和 dp dp[i][0/1] 表示第i个数坐标为偶数或奇数的最大交替和 dp[i][0]=max(dp[i-1][0],dp[i-1][1

    2024年02月16日
    浏览(50)
  • 2023-06-16 LeetCode每日一题(并行课程 II)

    点击跳转到题目位置 给你一个整数 n 表示某所大学里课程的数目,编号为 1 到 n ,数组 relations 中, relations[i] = [xi, yi] 表示一个先修课的关系,也就是课程 xi 必须在课程 yi 之前上。同时你还有一个整数 k 。 在一个学期中,你 最多 可以同时上 k 门课,前提是这些课的先修课

    2024年02月09日
    浏览(46)
  • Leetcode-每日一题【剑指 Offer 16. 数值的整数次方】

    实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。 示例 1: 输入: x = 2.00000, n = 10 输出: 1024.00000 示例 2: 输入: x = 2.10000, n = 3 输出: 9.26100 示例 3: 输入: x = 2.00000, n = -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25 提示: -10

    2024年02月13日
    浏览(41)
  • 【每日一题】Leetcode - 19. Remove Nth Node From End of List

    Leetcode - 19. Remove Nth Node From End of List Drawing on the method of finding midpoints in linked lists, use quick slow pointer Finding midpoints in linked lists nothing

    2024年02月12日
    浏览(52)
  • LeetCode 每日一题 Day 46 ||枚举

    给你一个下标从 0 开始的数组 words ,数组中包含 互不相同 的字符串。 如果字符串 words[i] 与字符串 words[j] 满足以下条件,我们称它们可以匹配: 字符串 words[i] 等于 words[j] 的反转字符串。 0 = i j words.length 请你返回数组 words 中的 最大 匹配数目。 注意,每个字符串最多匹配

    2024年01月22日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包