代码随想录算法训练day59---图论系列4

news/2025/2/22 15:15:20

代码随想录算法训练

—day59

文章目录

  • 代码随想录算法训练
  • 前言
  • 一、110.字符串接龙
  • 二、105.有向图的完全可达性
    • dfs版本1
    • dfs版本2
    • bfs版本
  • 三、100. 岛屿的最大面积
    • 方法一
    • 方法二
  • 总结

前言

今天是算法营的第59天，希望自己能够坚持下来！
今天继续图论part！今日任务：
● 110.字符串接龙
● 105.有向图的完全可达性
● 106.岛屿的周长

一、110.字符串接龙

卡码网题目链接
leetcode题目链接
文章讲解

思路：
从 startStr 到 endStr，找在 strList 中最短的路径，本题只需要求出最短路径的长度就可以了，不用找出具体路径。
所以这道题要解决两个问题：

  • 图中的线是如何连在一起的
  • 起点和终点的最短路径长度

1.由题目可得，strList中的字符串是以“ 只变化一个字符“作为连接
2.并且适合用广搜，因为广搜只要到达终点就是最短距离

另外需要有一个注意点：

  • 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环
  • 使用set来检查字符串是否出现在字符串集合里更快一些

代码如下：

#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<queue>
#include<string>
using namespace std;
 
//需要求最短距离，适合用广度优先搜索
//strList中的字符串是以“ 只变化一个字符“作为连接
int main() {
    int n;
    string beginStr, endStr, str;
     
    cin >> n;
    cin >> beginStr >> endStr;
     
    unordered_set<string> strSet; //用set方便查找
     
    while (n--) {
        cin >> str;
        strSet.insert(str);
    }
     
    //记录strSet里的字符串是否被访问过，同时记录路径长度
    unordered_map<string, int> visitMap; //<记录的字符串，路径长度>
     
    //初始化队列
    queue<string> que;
    que.push(beginStr);
     
    visitMap.insert(pair<string,int>(beginStr, 1));
     
    while (!que.empty()) {
        string word = que.front();
        que.pop();
        int path = visitMap[word]; //这个字符串在路径中的长度
         
        //开始在这个str中，挨个字符去替换
        for (int i = 0; i < word.size(); i++) {
            string newWord = word; //用一个新字符串替换str，因为每次要置换一个字符
             
            //遍历26字母
            for(int j = 0; j < 26; j++) {
                newWord[i] = j + 'a'; //从a开始换，替换掉str的第i个字母
                if (newWord == endStr) { //替换字母后，与重点字符串相同
                    cout << path + 1 << endl; //找到路径了
                    return 0;
                }
                //字符串集合中有newWord,并且newWord没有被访问过
                if (strSet.find(newWord) != strSet.end() && visitMap.find(newWord) == visitMap.end()) {
                    visitMap[newWord] = path + 1; //添加访问信息
                    que.push(newWord); //将新字符串放到队列中
                }
            }
        }
    }
     
    //没找到路径，输出0
    cout << 0 << endl;
}

二、105.有向图的完全可达性

卡码网题目链接
文章讲解

思路：
本题是一个有向图搜索全路径的问题。只能用深搜（DFS）或者广搜（BFS）来搜。

深搜三部曲：
1.确认递归函数，参数：需要地图，当前位置，标记访问过的位置的数组
2.确认终止条件：递归函数可以是处理当前节点，也可以是处理下一个节点。根据不同的写法有不同的终止条件。我这里是按照当前节点来写。那么终止条件就是当前节点已经访问过了，所以直接返回。
3.处理目前搜索节点出发的路径：处理当前路径就是对当前路径标记成true，并且找到下一个路径
注意：这里不需要回溯，因为题目求的是需要到达所有的节点，不需要退回标记。而回溯是找不同的路径时，到了终点需要掉头的时候就需要回溯，才能得出一条条不一样的路。

dfs版本1

代码如下：

// 写法一：dfs 处理当前访问的节点
#include <iostream>
#include <vector>
#include <list>
using namespace std;

void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {
    if (visited[key]) {
        return;
    }
    visited[key] = true;
    list<int> keys = graph[key];
    for (int key : keys) {
        // 深度优先搜索遍历
        dfs(graph, key, visited);
    }
}

int main() {
    int n, m, s, t;
    cin >> n >> m;

    // 节点编号从1到n，所以申请 n+1 这么大的数组
    vector<list<int>> graph(n + 1); // 邻接表
    while (m--) {
        cin >> s >> t;
        // 使用邻接表 ，表示 s -> t 是相连的
        graph[s].push_back(t);
    }
    vector<bool> visited(n + 1, false);
    dfs(graph, 1, visited);
    //检查是否都访问到了
    for (int i = 1; i <= n; i++) {
        if (visited[i] == false) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << 1 << endl;
}

dfs版本2

第二种写法注意有注释的地方是和写法一的区别：

写法二：dfs处理下一个要访问的节点
#include <iostream>
#include <vector>
#include <list>
using namespace std;

void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {
    list<int> keys = graph[key];
    for (int key : keys) {
        if (visited[key] == false) { // 确认下一个是没访问过的节点
            visited[key] = true;
            dfs(graph, key, visited);
        }
    }
}

int main() {
    int n, m, s, t;
    cin >> n >> m;

    vector<list<int>> graph(n + 1);
    while (m--) {
        cin >> s >> t;
        graph[s].push_back(t);

    }
    vector<bool> visited(n + 1, false);

    visited[1] = true; // 节点1 预先处理
    dfs(graph, 1, visited);

    for (int i = 1; i <= n; i++) {
        if (visited[i] == false) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << 1 << endl;
}

bfs版本

#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

int main() {
    int n, m, s, t;
    cin >> n >> m;

    vector<list<int>> graph(n + 1);
    while (m--) {
        cin >> s >> t;
        graph[s].push_back(t);

    }
    vector<bool> visited(n + 1, false);
    visited[1] = true; //  1 号房间开始
    queue<int> que;
    que.push(1); //  1 号房间开始

    // 广度优先搜索的过程
    while (!que.empty()) {
        int key = que.front(); que.pop();
         list<int> keys = graph[key];
         for (int key : keys) {
             if (!visited[key]) {
                 que.push(key);
                 visited[key] = true;
             }
         }
    }

    for (int i = 1; i <= n; i++) {
        if (visited[i] == false) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << 1 << endl;
}

三、100. 岛屿的最大面积

卡码网题目链接
leetcode题目链接
文章讲解

方法一

遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。
当岛屿周边是边界或者是水域的话，说明找到了一条边。
在这里插入图片描述
在这里插入图片描述

代码如下：

#include<iostream>
#include<vector>
using namespace std;
 
int main() {
    int n, m;
    cin >> n >> m;
     
    vector<vector<int>> graph(n, vector<int>(m, 0));
     
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> graph[i][j];
        }
    }
 
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
    int result = 0;
    //遍历每个节点
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //如果是岛屿的话
            if (graph[i][j] == 1) {
                //遍历岛屿四周
                for (int k = 0; k < 4; k++) {
                int x = i + dir[k][0];
                int y = j + dir[k][1];
                 
                //xy位置在边界上，或者是水域，则周长+1
                if (x < 0 
                        || x >= n 
                        || y < 0 
                        || y >= m 
                        || graph[x][y] == 0) {
                        result++;
                    }
                }
            }
             
        }
    }
    cout << result << endl;
}

方法二

在这里插入图片描述
假设一个岛屿有4条边，
有一对相邻两个陆地，边的总数就要减2，
那么result = 岛屿数量 * 4 - cover * 2;

代码如下：

#include<iostream>
#include<vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> graph(n, vector<int>(m, 0));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> graph[i][j];
        }
    }

    int sum = 0; //陆地数量
    int cover = 0; //相邻数量
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (graph[i][j] == 1) {
                sum++;
                //统计当前岛屿左边相邻陆地
                if (i-1 >= 0 && graph[i-1][j] == 1) cover++;
                //统计当前岛屿左边相邻陆地
                if(j-1 >= 0 && graph[i][j-1] == 1) cover++;
                //不需要统计下边和右边，因为会重复计算
            }
        }
    }
    //岛屿周长= 岛屿数量*4 - 相邻的岛屿数*2
    cout << sum*4 - 2*cover << endl;
}

总结

  • 字符串接龙 ：求最短路径，考虑用广搜。根据题意可知节点的连接是“只替换一个字符”，遍历字符串，再分别替换成26字母，并用set检查是否在list中。
  • 有向图的完全可达性：需要有一个数组来记录到达过的路径，注意这里不需要回溯。
  • 岛屿的最大面积：方法一：岛屿周围是水或者边界就是边长 方法二：周长= 岛屿数量4 - 相邻的岛屿数2

明天继续加油！


http://www.niftyadmin.cn/n/5862436.html

相关文章

工控自动化领域：数字量信号与模拟量信号的差异解析

工控自动化领域：数字量信号与模拟量信号的差异解析

在工控自动化的神秘世界里&#xff0c;信号如同传递指令和信息的使者&#xff0c;而数字量信号和模拟量信号则是其中的两大主角。它们各自有着独特的 “性格” 和 “使命”&#xff0c;在不同的场景中发挥着关键作用。下面&#xff0c;就让我们一起来深入了解一下它们的区别。 …
阅读更多...
x安全服务 y安全体系 z网络安全模型 网络安全体系设计

x安全服务 y安全体系 z网络安全模型 网络安全体系设计

这一年来&#xff0c;网络安全行业兴奋异常。各种会议、攻防大赛、黑客秀&#xff0c;马不停蹄。随着物联网大潮的到来&#xff0c;在这个到处都是安全漏洞的世界&#xff0c;似乎黑客才是安全行业的主宰。然而&#xff0c;我们看到的永远都是自己的世界&#xff0c;正如医生看…
阅读更多...
关于css中bfc的理解

关于css中bfc的理解

首先需要了解的是bfc的缩写是block formatting context 块级格式化上下文 那么块级格式化上下文意味着我们在bfc的区域内生成了一块独立于当前文本流的样式、它不受外界样式的影响、有着专属于自己的样式。 基于这样的定义我们可以避免一些样式冲突、在我们开发者面对复杂布局…
阅读更多...
今天踩个大坑，jdk1.8版本对应可使用的gradle

今天踩个大坑，jdk1.8版本对应可使用的gradle

这俩版本都是基于jdk1.8版本的as可以使用的gradle版本
阅读更多...
直播美颜SDK的底层技术解析：图像处理与深度学习的结合

直播美颜SDK的底层技术解析：图像处理与深度学习的结合

直播美颜SDK通过高效的图像处理技术和深度学习算法&#xff0c;使得用户在直播过程中可以获得更为自然、精致的美颜效果。本文将深入解析直播美颜SDK的底层技术&#xff0c;探讨图像处理与深度学习如何在这一领域实现完美结合&#xff0c;提升用户体验并推动行业创新。 一、直…
阅读更多...
算法从0到100之【专题一】- 双指针第一练（数组划分、数组分块）

算法从0到100之【专题一】- 双指针第一练（数组划分、数组分块）

文章目录 【题目一】移动零题目要求算法原理&#xff08;思路讲解 画图模拟演示&#xff09;代码实现 【题目二】复写零题目要求算法原理&#xff08;思路讲解 画图模拟演示&#xff09;代码实现 【题目一】移动零 题目要求 给定一个数组 nums&#xff0c;编写一个函数将所…
阅读更多...
代码随想录二刷|动态规划8

代码随想录二刷|动态规划8

dp动态规划 动态规划五步曲 动态规划数组的含义 dp[i] 递推公式 动态规划数组的初始化 确定遍历顺序 手动模拟验证 动态规划遇到问题要打印dp数组&#xff0c;看和模拟结果哪里不一样 一 基础问题 斐波那契数 题干 斐波那契数 &#xff08;通常用 F(n) 表示&#xf…
阅读更多...
[答疑]领域建模：邓丽君、周杰伦和少女时代

[答疑]领域建模：邓丽君、周杰伦和少女时代

DDD领域驱动设计批评文集 做强化自测题获得“软件方法建模师”称号 《软件方法》各章合集 第五元素 2025-2-18 17:12 潘老师&#xff0c;画线的这句话&#xff0c;在这个类图中怎么体现呢&#xff1f; &#xff08;回答者补注&#xff1a;问题的素材来自《邓丽君的领域建模》…
阅读更多...
最新文章

Copyright @ 2022~2023