图论| 827. 最大人工岛 127. 单词接龙

827. 最大人工岛

题目:给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后,grid 中最大的岛屿面积是多少?
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
题目链接:[827. 最大人工岛](https://leetcode.cn/problems/making-a-large-island/)
解题思路:暴力解法 把每一个0改为1计算岛屿面积 复杂度:改每一个0为1:n2计算岛屿最大面积n2 会超时
优化思路:遍历记录所有岛屿面积 将0附近(上下左右)的岛屿进行联通
1.遍历记录所有岛屿面积
如何记录:遍历过的岛屿标记岛屿编号(从2开始) 将岛屿编号和最大面积记录在set中
2. 将0附近(上下左右)的岛屿进行联通
如何判断0周围的面积:遍历0周围的岛屿面积进行联通,将周围的岛屿加入set以防重复叠加
代码如下:

class Solution {
    public int[][] mark;
    public int[][] move={{0,1},{0,-1},{1,0},{-1,0}};
    public HashMap<Integer, Integer> island = new HashMap<Integer, Integer>();
    public int largestIsland(int[][] grid) {
        //遍历岛屿并记录
        int maxArea=0;
        int masknum=2;
        mark=new int[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(mark[i][j]==0&&grid[i][j]==1){
                    bfs(grid,i,j,masknum);
                    masknum++;
                }
            }
        }
        for(int value: island.values()) {
            if(value>maxArea){
                maxArea=value;
            }
        }
        //修改岛屿并记录面积
         for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==0){
                    HashSet<Integer> sites = new HashSet<>();
                    for(int p=0;p<4;p++){
                        int nextx=i+move[p][0];
                        int nexty=j+move[p][1];
                        if(nextx<0||nextx>=grid.length||nexty<0||nexty>=grid.length){
                            continue;
                        }
                        if(mark[nextx][nexty]!=0){
                            sites.add(mark[nextx][nexty]);
                        }
                    }
                    //计算面积
                    int area=1;
                    for(int p:sites){
                        area+=island.get(p);
                    }
                    if(area>maxArea){
                        maxArea=area;
                    }
                }
            }
        }
        return maxArea;
    }
    public void bfs(int[][] grid,int i,int j,int masknum){
        int area=1;
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{i,j});
        mark[i][j]=masknum;
        while(!queue.isEmpty()){
            int[] node=queue.poll();
            for(int p=0;p<4;p++){
                int nextx=node[0]+move[p][0];
                int nexty=node[1]+move[p][1];
                if(nextx<0||nextx>=grid.length||nexty<0||nexty>=grid.length){
                    continue;
                }
                if(mark[nextx][nexty]==0&&grid[nextx][nexty]==1){
                     queue.offer(new int[]{nextx,nexty});
                     mark[nextx][nexty]=masknum;
                     area++;
                }
            }
        }
        island.put(masknum,area);
    }
}

217 单词接龙

题目:字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk:
每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ,返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0 。
题目链接:217 单词接龙
在这里插入图片描述

解题思路:
为了保证从 beginWord 到 endWord 的转换序列是最短路径,我们使用广度优先搜索(BFS)算法。BFS 有一个重要特性:它首先访问距离源点(在这个场景中是 beginWord)最近的节点。因此,当我们首次到达 endWord 时,我们可以确信找到的路径是最短的。
我们使用队列进行广度优先搜索 每次从队列中取出一个单词,查找与其相差一个字母的所有单词,并将这些单词加入队列 为了防止重复处理相同的单词,我们需要从 wordList 中移除已经处理过的单词。具体是将其与对应路径长度加入map中
代码如下

class Solution {
      public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }
        if (!wordList.contains(beginWord)) {
            wordList.add(beginWord);
        }

        HashSet<String> wordSet = new HashSet<>(wordList);
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Map<String, Integer> visited = new HashMap<>();
        visited.put(beginWord, 1);

        while (!queue.isEmpty()) {
            String currentWord = queue.poll();
            int currentLength = visited.get(currentWord);

            for (String word : wordSet) {
                if (isOneLetterDiff(currentWord, word)) {
                    if (word.equals(endWord)) {
                        return currentLength + 1;
                    }
                    if (!visited.containsKey(word)) {
                        queue.offer(word);
                        visited.put(word, currentLength + 1);
                    }
                }
            }
        }
        return 0;
    }

    private boolean isOneLetterDiff(String word1, String word2) {
        if (word1.length() != word2.length()) {
            return false;
        }
        int diffCount = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i)) {
                diffCount++;
                if (diffCount > 1) {
                    return false;
                }
            }
        }
        return diffCount == 1;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/155985.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

佳易王麻将馆计时收费系统怎么安装,麻将馆的灯控什么原理?

佳易王麻将馆计时收费系统怎么安装&#xff0c;麻将馆的灯控什么原理&#xff1f; 佳易王计时计费软件只需将压缩包文件解压即可使用&#xff0c;灯控的原理是&#xff1a;软件在点击开始计时的时候&#xff0c;软件向灯控器发送开灯信号&#xff0c;相应的灯打开&#xff0c;…

【面试】测试/测开(未完成)

1. 黑盒测试方法 黑盒测试&#xff1a;关注的是软件功能的实现&#xff0c;关注功能实现是否满足需求&#xff0c;测试对象是基于需求规格说明书。 1&#xff09;等价类&#xff1a;有效等价类、无效等价类 2&#xff09;边界值 3&#xff09;因果图&#xff1a;不同的原因对应…

C/C+=内存管理

C/C内存管理以及动态内存的申请_c动态内存的申请与释放_Demo Test的博客-CSDN博客 问题是&#xff0c;这个0x0804 8000 到0xC 0000 0000之间&#xff0c;不止3GB&#xff0c;应该有47GB&#xff0c;该怎么解释呢&#xff1f;

【图像分类】【深度学习】【Pytorch版本】ResNet模型算法详解

【图像分类】【深度学习】【Pytorch版本】 ResNet模型算法详解 文章目录 【图像分类】【深度学习】【Pytorch版本】 ResNet模型算法详解前言ResNet讲解Deep residual learning framework(深度残差学习框架)ResNet残差结构ResNet模型结构 ResNet Pytorch代码完整代码总结 前言 …

深入探讨TensorFlow:张量与矩阵

在机器学习和深度学习领域中&#xff0c;TensorFlow作为一款强大且受欢迎的开源机器学习框架&#xff0c;为研究人员和开发者提供了丰富的工具和资源。在TensorFlow中&#xff0c;张量&#xff08;tensor&#xff09;和矩阵&#xff08;matrix&#xff09;是核心概念&#xff0…

Odoo 15开发手册第七章 记录集 - 使用模型数据

在前面的章节中&#xff0c;我们概览了模型创建以及如何向模型加载数据。现在我们已有数据模型和相关数据&#xff0c;是时候学习如何编程与其进行交互了。 业务应用需要业务逻辑来计算数据、执行验证或自动化操作。Odoo框架API为开发者提供了工具用于实现这种业务逻辑。大多数…

(二)什么是Vite——Vite 和 Webpack 区别(冷启动)

vite分享ppt&#xff0c;感兴趣的可以下载&#xff1a; ​​​​​​​Vite分享、原理介绍ppt 什么是vite系列目录&#xff1a; &#xff08;一&#xff09;什么是Vite——vite介绍与使用-CSDN博客 &#xff08;二&#xff09;什么是Vite——Vite 和 Webpack 区别&#xff0…

2018年五一杯数学建模C题江苏省本科教育质量综合评价解题全过程文档及程序

2019年五一杯数学建模 C题 江苏省本科教育质量综合评价 原题再现 随着中国的改革开放&#xff0c;国家的综合实力不断增强&#xff0c;中国高等教育发展整体已进入世界中上水平。作为一个教育大省&#xff0c;江苏省的本科教育发展在全国名列前茅&#xff0c;而江苏省13个地级…

【PB续命05】WinHttp.WinHttpRequest的介绍与使用

0 WinHttp.WinHttpRequest简介 winhttp.winhttprequest是Windows操作系统中的一个API函数&#xff0c;用于创建和发送HTTP请求。它可以用于从Web服务器获取数据&#xff0c;或将数据发送到Web服务器。该函数提供了许多选项&#xff0c;例如设置请求头、设置代理服务器、设置超…

花 200 元测试 1300 个实时数据同步任务

背景 对于将数据作为重要生产资料的公司来说&#xff0c;超大规模的数据迁移同步系统( 1k、5k、10k 条同步任务)是刚需。 本文以此为出发点&#xff0c;介绍近期 CloudCanal 所做的一个容量测试&#xff1a;在单个 CloudCanal 集群上创建 1300 实时任务&#xff0c;验证系统是…

2023年中国骨质疏松治疗仪发展趋势分析:小型且智能将成为产品优化方向[图]

骨质疏松治疗仪利用磁场镇静止痛、消肿消炎的治疗作用迅速缓解患者腰背疼痛等骨质疏松临床症状。同时利用磁场的磁-电效应产生的感生电势和感生电流&#xff0c;改善骨的代谢和骨重建&#xff0c;通过抑制破骨细胞、促进成骨细胞的活性来阻止骨量丢失、提高骨密度。 骨质疏松治…

【软件推荐】我的常用Windows软件

文章目录 前言Colors Lite&#xff08;颜色吸取&#xff09;Everything&#xff08;文件搜索&#xff09;知云文献翻译Directory Opus&#xff08;文件管理器&#xff09;Snipaste&#xff08;截图&#xff09;AxMath&#xff08;公式编辑器&#xff09;Deskpin&#xff08;窗口…

【Android】导入三方jar包/系统的framework.jar

1.Android.mk导包 1).jar包位置 与res和src同一级的libs中(没有就新建) 2).Android.mk文件 LOCAL_STATIC_ANDROID_LIBRARIES&#xff1a;android静态库&#xff0c;经常用于一些support的导包 LOCAL_JAVA_LIBRARIES&#xff1a;依赖的java库&#xff0c;一般为系统的jar…

Linux常用命令——bzcmp命令

在线Linux命令查询工具 bzcmp 比较两个压缩包中的文件 补充说明 bzcmp命令主要功能是在不真正解压缩.bz2压缩包的情况下&#xff0c;比较两个压缩包中的文件&#xff0c;省去了解压缩后在调用cmp命令的过程。 语法 bzcmp(参数)参数 文件1&#xff1a;指定要比较的第一个…

UE基础篇十:材质

导语: 视频文档在文末 虚幻引擎默认是延迟渲染(延迟渲染是通过先算出需要着色的像素,然后再迭代灯光,从而减少大量无效的灯光计算,来达到优化的目的) 一、基础知识 1.1 贴图分辨率尺寸 2的幂次方,长宽随意组合 非2的幂次方,不能设置MipMaps(引擎会生成多张分辨率更…

任务栏上的超萌小猫,实时显示CPU占用率,有趣.Net开源工具

推荐一个非常有趣的.Net开源小工具&#xff0c;它可以在电脑任务栏显示一只奔跑的小猫&#xff0c;实时显示CPU使用率&#xff01; 01 项目简介 一款基于.NET 6.0运行环境的开源小工具&#xff0c;通过它&#xff0c;用户可以直观地查看CPU的使用情况&#xff0c;它会根据 CP…

程序员导航站

探路者 hello.alluniverse.vip 开发者导航 - Pro Developer网站导航 探路者是一款极简导航工具&#xff0c;致力于收录的每个站点都有其独特的作用。同时支持自定义导航&#xff0c;让用户快速实现个性化的导航站点。 特性概述 免费ChatGPT 装机必备 开发工具 Git精选项目 …

云计算(Docker)

Docker简介 Docker 是一个开源的应用容器引擎&#xff0c;基于 Go 语言&#xff0c;并遵从 Apache2.0 协议开源。它可以让开发者打包应用以及依赖包到一个轻量级、可移植的容器中&#xff0c;然后发布到任何流行的 Linux 机器上&#xff0c;也可以实现虚拟化。Docker 可用于开发…

2023年中国涂料树脂需求量、市场规模及行业竞争现状分析[图]

涂料用树脂是涂料的主要原材料&#xff0c;是涂料的主要成膜物&#xff0c;且了为涂料成品提供耐醇、耐磨、耐高温、耐高湿、减少涂料在涂装完成后的损耗、保持涂装后外观以及性状的稳定性等功能。 根据生产产品的性状不同&#xff0c;其下游产品&#xff0c;即涂料成品广泛应用…

锐捷EG易网关login.php以及其后台cli.php/branch_passw.php RCE漏洞复现 [附POC]

文章目录 锐捷EG易网关login.php以及其后台cli.php/branch_passw.php远程代码执行漏洞复现 [附POC]0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 锐捷EG易网关login.php以及其后台cli.php/branch_passw.php远程代码执行漏洞复…