算法学习——LeetCode力扣图论篇3(127. 单词接龙、463. 岛屿的周长、684. 冗余连接、685. 冗余连接 II)

算法学习——LeetCode力扣图论篇3

在这里插入图片描述

127. 单词接龙

127. 单词接龙 - 力扣(LeetCode)

描述

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk:

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ,返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0 。

示例

示例 1:

输入:beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出:5
解释:一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。

示例 2:

输入:beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出:0
解释:endWord “cog” 不在字典中,所以无法进行转换。

提示

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同

代码解析

深度搜索(超时)
class Solution {
public:
    int result = INT_MAX;
    int tmp_result = 1;
    
    int cheak(string s1 , string s2)
    {
        int no_same_num = 0;
        for(int i=0 ; i<s1.size() ;i++)
        {
            if(s1[i] != s2[i]) no_same_num++;
        }
        return no_same_num;
    }
    void track_back(string beginWord, string endWord, vector<string>& wordList , int indix, vector<bool> &path)
    {
        for(int i=0 ; i<wordList.size() ;i++)
        {
           if(wordList[indix] == endWord && path[i] == false)
            {
                if(tmp_result < result) result = tmp_result;
                // cout<<endl;
                return;
            }else if(cheak(wordList[indix],wordList[i]) == 1 && path[i] == false)
            {
                // cout<<wordList[i]<<' ';
                tmp_result ++;
                path[i] = true;
                track_back(beginWord,endWord,wordList,i,path);
                path[i] = false;
                tmp_result--;
            }
        }
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        vector<bool> path(wordList.size(),false);
        for(int i=0 ; i<wordList.size() ;i++)
        {
            if(cheak(beginWord,wordList[i]) == 1 && path[i]==false)
            {
                // cout<<wordList[i]<<' ';
                path[i] = true;
                tmp_result++;
                track_back(beginWord,endWord,wordList,i,path);
                tmp_result--;
                path[i] = false;
            }
        }
        if(result == INT_MAX) return 0;
        return result;
        
    }
};
广度搜索
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // 将vector转成unordered_set,提高查询速度
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        // 如果endWord没有在wordSet出现,直接返回0
        if (wordSet.find(endWord) == wordSet.end()) return 0;
        // 记录word是否访问过
        unordered_map<string, int> visitMap; // <word, 查询到这个word路径长度>
        // 初始化队列
        queue<string> que;
        que.push(beginWord);
        // 初始化visitMap
        visitMap.insert(pair<string, int>(beginWord, 1));

        while(!que.empty()) 
        {
            string word = que.front();
            que.pop();
            int path = visitMap[word]; // 这个word的路径长度
            for (int i = 0; i < word.size(); i++)
            {
                string newWord = word; // 用一个新单词替换word,因为每次置换一个字母
                for (int j = 0 ; j < 26; j++) 
                {
                    newWord[i] = j + 'a';
                    if (newWord == endWord) return path + 1; // 找到了end,返回path+1

                    // wordSet出现了newWord,并且newWord没有被访问过
                    if (wordSet.find(newWord) != wordSet.end() && visitMap.find(newWord) == visitMap.end()) 
                    {
                        // 添加访问信息
                        visitMap.insert(pair<string, int>(newWord, path + 1));
                        que.push(newWord);
                    }
                }
            }
        }
        return 0;
    }
};

463. 岛屿的周长

463. 岛屿的周长 - 力扣(LeetCode)

描述

给定一个 row x col 的二维网格地图 grid ,其中:grid[i][j] = 1 表示陆地, grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。

岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例

示例 1:

在这里插入图片描述

输入:grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出:16
解释:它的周长是上面图片中的 16 个黄色的边

示例 2:

输入:grid = [[1]]
输出:4

示例 3:

输入:grid = [[1,0]]
输出:4

提示

row == grid.length
col == grid[i].length
1 <= row, col <= 100
grid[i][j] 为 0 或 1

代码解析

class Solution {
public:
    int result = 0;
    int m,n;
    int dir[4][2] = {0,-1,0,1,-1,0,1,0};
    void dfs(vector<vector<int>>& grid ,int x , int y)
    {
        for(int i=0 ; i<4 ;i++)
        {
            int next_x = x + dir[i][0];
            int next_y = y + dir[i][1];
            if(next_x<0||next_x>=m||next_y<0||next_y>=n) result++;
            else if(grid[next_x][next_y] == 0) result++;
        }
        return;
    }
    int islandPerimeter(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();

        for(int i=0 ; i<m ;i++)
        {
            for(int j=0 ; j<n ;j++)
            {
                if(grid[i][j] == 1)
                    dfs(grid,i,j);
            }
        }
        return result;
    }
};

684. 冗余连接

684. 冗余连接 - 力扣(LeetCode)

描述

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的那个。

示例

示例 1:

在这里插入图片描述

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

示例 2:
在这里插入图片描述

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

提示

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的

代码解析

class Solution {
public:
    int n = 0;

    int find(int u , vector<int> &father)
    {
        if(u == father[u]) return father[u];
        father[u] = find(father[u] , father);
        return father[u];
    }
    
    void join(int u , int v , vector<int> &father)
    {
        u = find(u , father);
        v = find(v , father);
        if(u == v) return;
        father[v] = u;
    }

    bool same(int u , int v , vector<int> &father)
    {
        u = find(u , father);
        v = find(v , father);
        return u == v;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        n = edges.size() + 1;
        vector<int> father(n,0);
        for(int i=0 ; i<n ; i++)
            father[i] = i;

        for(int i=0 ; i<edges.size() ; i++)
        {
            if(same(edges[i][0] , edges[i][1] , father)) return edges[i];
            else join(edges[i][0] , edges[i][1] , father);
        }
        return {};
    }
};

685. 冗余连接 II

685. 冗余连接 II - 力扣(LeetCode)

描述

在本问题中,有根树指满足以下条件的 有向 图。该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。

输入一个有向图,该图由一个有着 n 个节点(节点值不重复,从 1 到 n)的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间,这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi],用以表示 有向 图中连接顶点 ui 和顶点 vi 的边,其中 ui 是 vi 的一个父节点。

返回一条能删除的边,使得剩下的图是有 n 个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。

示例

示例 1:
在这里插入图片描述

输入:edges = [[1,2],[1,3],[2,3]]
输出:[2,3]
示例 2:
在这里插入图片描述

输入:edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出:[4,1]

提示

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ui, vi <= n

代码解析

class Solution {
public:
    int n=0;
    int find(int u , vector<int> &father)
    {
        if(u == father[u]) return father[u];
        father[u] = find(father[u],father);
        return father[u];
    }

    void join(int u , int v , vector<int> &father )
    {
        u = find(u,father);
        v = find(v,father);
        if(u == v) return;
        father[v] = u; 
    }

    bool same(int u , int v , vector<int> &father)
    {
        u = find(u,father);
        v = find(v,father);
        return u == v;
    }
    bool tree_remove_edga(vector<vector<int>>& edges , int delete_edge , vector<int> &father)
    {
        for(int i=0 ; i<n ;i++)
        {
            if(i == delete_edge) continue;
            if(same(edges[i][0] , edges[i][1] , father) == true) return false;
            join(edges[i][0] , edges[i][1] , father);
        }
        return true;
    }
    vector<int> get_remove_edge(vector<vector<int>>& edges , vector<int> &father)
    {
        for(int i=0 ; i<n ;i++)
        {
            if(same(edges[i][0] , edges[i][1] , father) == true) return edges[i];
            join(edges[i][0] , edges[i][1] , father);
        }
        return {};
    }
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        n = edges.size();
        vector<int> father(n+1,0);
        vector<int> inDegree(n+1,0);
        for(int i=0 ; i<n ;i++)
        {
            father[i] = i;
            inDegree[edges[i][1]] += 1;
        }
        father[n] = n;

        vector<int> inDeg_2;
        for(int i=n-1 ; i>=0 ;i--)
            if(inDegree[edges[i][1]] >= 2) inDeg_2.push_back(i);
        
        if(inDeg_2.size() > 0)
        {
            if(tree_remove_edga(edges,inDeg_2[0] , father) == true) return edges[inDeg_2[0]];
            else return edges[inDeg_2[1]];
        }

        return get_remove_edge(edges,father);
    }
};

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

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

相关文章

动态内存管理-错题合集讲解

空指针的解应用操作&#xff08;错误信息合集&#xff09; 越界访问 首先我们上一个代码&#xff0c;看看这个的代码的问题 这个代码的问题显而易见 &#xff0c;就是在循环里面&#xff0c;产生了越界访问的问题&#xff0c;这里你开辟了10个整形空间&#xff0c;但是从0-1…

爬虫的验证码处理

1.我们先进入chrome浏览器的审查页面找到input方法&#xff1a; 为了不少找到一个input&#xff0c;我们ctrlf的方法输入input来查找 看见我们有6个需要输入的参数。 除了上面几个的input参数&#xff0c;我们还需要获取验证码的图片&#xff0c;后续要将字母填入进去。 二.安…

XDMA windos 编译

1、先安装 Visual Studio 2019 2、Download the Windows Driver Kit (WDK) - Windows drivers | Microsoft Learn 以前的 WDK 版本和其他下载 - Windows 驱动程序 |Microsoft学习 注意版本&#xff1a;下载2004的版本 3、 选择使用10.0.19041.0 安装这个sdk. 先按vs2019 然后…

后端SpringBoot+Mybatis 查询订单数据库奇怪报错加一

排错过程&#xff1a; 看报错意思是SQL语句存在错误&#xff0c;然后使用图形化工具运行这个SQL语句 其实这里稍微细心想一下就能发现问题&#xff0c;但是当时没深入想&#xff0c;就觉得order表前加了数据库名字影响不大&#xff0c;所以感觉SQL语句是没问题的&#xff0c;然…

HarmonyOS实战开发-一次开发,多端部署-视频应用

介绍 随着智能设备类型的不断丰富&#xff0c;用户可以在不同的设备上享受同样的服务&#xff0c;但由于设备形态不尽相同&#xff0c;开发者往往需要针对具体设备修改或重构代码&#xff0c;以实现功能完整性和界面美观性的统一。OpenHarmony为开发者提供了“一次开发&#x…

【Java与数学】若不等式x^2-a*x+a<0的解集中恰有3个整数,求a的范围?

【分析】 既然不等式存在解集&#xff0c;说明一元二次方程x^2-a*xa0有解&#xff1b; 解之间横跨三个整数&#xff0c;说明Δ大于0&#xff1b; 三个整数必然是连续的&#xff0c;因为f(x)x^2-a*xa最多只与x存在两个交点&#xff0c;这是题设里的隐含条件。 【传统解法】 …

2024 3.23~3.29周报

上周工作 SVInvNet论文研读 本周计划 加入DenseNet&#xff0c;修改网络架构&#xff0c;跑代码 总结 DenseNet 密集块&#xff1a;DenseNet将网络分成多个密集块&#xff08;Dense Block)。在每个密集块内&#xff0c;每一层都连接到前面所有的层。这种跳跃连接有助于解…

Mac m1 Flink的HelloWorld

首先在官方下载Downloads | Apache Flink 下载好压缩包后解压&#xff0c;得到Flink文件夹 进入&#xff1a;cd flink-1.19.0 ls 查看里面的文件&#xff1a; 执行启动集群 ./bin/start-cluster.sh 输出显示它已经成功地启动了集群&#xff0c;并且正在启动 standalonesessio…

Vue ElementPlus Input输入框

Input 输入框 通过鼠标或键盘输入字符 input 为受控组件&#xff0c;它总会显示 Vue 绑定值。 通常情况下&#xff0c;应当处理 input 事件&#xff0c;并更新组件的绑定值&#xff08;或使用v-model&#xff09;。否则&#xff0c;输入框内显示的值将不会改变。不支持 v-mode…

Oracle 低代码平台 Apex 最新版本 23.2 安装过程

趁春节快结束前&#xff0c;安装了一把APEX &#xff0c;到目前为此&#xff0c;APEX最新版本为23.2&#xff0c;23.2和21版本有一些变化&#xff0c;只是用于验证&#xff0c;我 是使用的单独模式&#xff0c;没有安装TOMAT&#xff0c;下面列一下安装过程&#xff1a; 1.环境…

机器学习——最优化模型

最优化模型的概述&#xff1a; 从某种程度上说&#xff0c;我们的世界是由最优化问题组成的。每一天&#xff0c;我们的生活都面临无数的最优化问题&#xff1a;上班怎么选择乘车路线&#xff0c;才能舒服又快速地到达公司&#xff1b;旅游如何选择航班和宾馆&#xff0c;既省…

[flink 实时流基础] 转换算子

flink学习笔记 数据源读入数据之后&#xff0c;我们就可以使用各种转换算子&#xff0c;将一个或多个DataStream转换为新的DataStream。 文章目录 基本转换算子&#xff08;map/ filter/ flatMap&#xff09;聚合算子&#xff08;Aggregation&#xff09;按键分区&#xff08;…

【隐私计算实训营006隐语PIR介绍及开发实践】

1. 隐语实现PIR总体介绍 隐匿查询&#xff08;Private Information Retrieval PIR&#xff09;定义 按服务器数量分类 单服务器方案&#xff08;Single Server&#xff09;多服务器方案&#xff08;Multi-Server&#xff09; 按查询类型分类 Index PIRKeyword PIR 隐语目前…

基于两个单片机串行通信的电子密码锁设计

1.功能 电子号码锁在实际应用中应该有两部分&#xff0c;一部分在外部&#xff0c;有键盘部分和密码显示&#xff1b;另一部分内部&#xff0c;设置密码、显示密码。使用单片机自身带有的串口可以很方便的实现单片机之间的通信&#xff0c;使输入的密码值传送到主机检验是否是…

nginx的https与动态负载均衡

nginx的https 证书可以根据你的域名和服务器服务商去进行签发 , 比如 : 阿里云 腾讯云 百度云 华为云等 这里使用的是腾讯云 : 下载证书 : 选择 nginx: 下载之后传递到服务器上。 下面开始配置nginx的https: 1. 解压下载的证书包 cd /etc/ssl unzip xxcc.dwa_nginx.zip mv…

【A-010】基于SSH的宠物狗商城系统(含论文)

【A-010】基于SSH的宠物狗商城系统&#xff08;含论文&#xff09; 开发环境&#xff1a; Eclipse/MyEclipse、Tomcat8、Jdk1.8 数据库&#xff1a; MySQL 项目介绍&#xff1a; 在科学技术飞速发展的今天&#xff0c;互联网成为人们快速获取、发布和传递信息的重要渠道&am…

Cesium实现渐变面

一、效果图 二、实现思路 使用着色器&#xff0c;通过纹理坐标和其他参数计算出材质的颜色和透明度。通过给定的颜色、漫反射强度和透明度&#xff0c;计算出最终的反射颜色和透明度&#xff0c;并且根据给定的中心点位置和当前像素的纹理坐标&#xff0c;计算出距离中心的距离…

怎么快速上手虚拟化(容器)技术——以 Docker 为例

Docker 整体介绍 Docker 是一种使用 Go 语言开发的容器工具。所谓容器&#xff0c;实际上是一种虚拟化技术&#xff0c;用于为应用提供虚拟化的运行环境&#xff0c;相较于虚拟机具有轻量级、低延迟的特性。 下面是对上述介绍的说明&#xff1a; 应用程序运行需要一定的依赖…

在 C#和ASP.NET Core中创建 gRPC 客户端和服务器

关于gRPC和Google protobuf gRPC 是一种可以跨语言运行的现代高性能远程过程调用 (RPC) 框架。gRPC 实际上已经成为 RPC 框架的行业标准&#xff0c;Google 内外的组织都在使用它来从微服务到计算的“最后一英里”&#xff08;移动、网络和物联网&#xff09;的强大用例。 gRP…

canvas画图,画矩形可拖拽移动,可拖拽更改尺寸大小

提示&#xff1a;canvas画图&#xff0c;画矩形&#xff0c;圆形&#xff0c;直线&#xff0c;曲线可拖拽移动 文章目录 前言一、画矩形&#xff0c;圆形&#xff0c;直线&#xff0c;曲线可拖拽移动总结 前言 一、画矩形&#xff0c;圆形&#xff0c;直线&#xff0c;曲线可拖…