> 作者:დ旧言~
> 座右铭:松树千年终是朽,槿花一日自为荣。> 目标:熟练解决最短路径问题算法。
> 毒鸡汤:学习,学习,再学习 ! 学,然后知不足。
> 专栏选自:刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题,这块的刷题是让同学们快速进入C语言,而我们学习c++已经有一段时间了,知识储备已经足够了但缺少了实战,面对这块短板博主续写刷题训练,针对性学习,把相似的题目归类,系统的刷题,而我们刷题的官网可以参考:
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推,求职就业一站解决_牛客网
⭐知识讲解
基本思想:
- 采用 dfs 解决问题
🌙topic-->1
题目链接:1. - 力扣(LeetCode)
题目分析:
给你一个 m x n
的迷宫矩阵 maze
(下标从 0 开始),矩阵中有空格子(用 '.'
表示)和墙(用 '+'
表示)。同时给你迷宫的入口 entrance
,用 entrance = [entrancerow, entrancecol]
表示你一开始所在格子的行和列。
每一步操作,你可以往 上,下,左 或者 右 移动一个格子。你不能进入墙所在的格子,你也不能离开迷宫。你的目标是找到离 entrance
最近 的出口。出口 的含义是 maze
边界 上的 空格子。entrance
格子 不算 出口。
请你返回从 entrance
到最近出口的最短路径的 步数 ,如果不存在这样的路径,请你返回 -1
。
算法原理:
- 解法:采用BFS算法
图解:
代码演示:
class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};public:int nearestExit(vector<vector<char>>& maze, vector<int>& e) {int m = maze.size(), n = maze[0].size();bool vis[m][n];memset(vis, 0, sizeof vis);queue<pair<int, int>> q;q.push({e[0], e[1]});vis[e[0]][e[1]] = true;int step = 0;while (q.size()) {step++;int sz = q.size();for (int i = 0; i < sz; i++) {auto [a, b] = q.front();q.pop();for (int j = 0; j < 4; j++) {int x = a + dx[j], y = b + dy[j];if (x >= 0 && x < m && y >= 0 && y < n &&maze[x][y] == '.' && !vis[x][y]) {// 判断是否已经到达出⼝if (x == 0 || x == m - 1 || y == 0 || y == n - 1)return step;q.push({x, y});vis[x][y] = true;}}}}return -1;}
};
🌙topic-->2
题目链接:2. - 力扣(LeetCode)
题目分析:
基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是 'A'
、'C'
、'G'
和 'T'
之一。
假设我们需要调查从基因序列 start
变为 end
所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
- 例如,
"AACCGGTT" --> "AACCGGTA"
就是一次基因变化。
另有一个基因库 bank
记录了所有有效的基因变化,只有基因库中的基因才是有效的基因序列。(变化后的基因必须位于基因库 bank
中)
给你两个基因序列 start
和 end
,以及一个基因库 bank
,请你找出并返回能够使 start
变化为 end
所需的最少变化次数。如果无法完成此基因变化,返回 -1
。
注意:起始基因序列 start
默认是有效的,但是它并不一定会出现在基因库中。
算法原理:
- 解法:采用BFS算法
图解:
代码演示:
class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_set<string> vis; // ⽤来标记已经搜索过的状态unordered_set<string> hash(bank.begin(),bank.end()); // 存储基因库⾥⾯的字符串string change = "ACGT";if (startGene == endGene)return 0;if (!hash.count(endGene))return -1;queue<string> q;q.push(startGene);vis.insert(startGene);int ret = 0;while (q.size()) {ret++;int sz = q.size();while (sz--) {string t = q.front();q.pop();for (int i = 0; i < 8; i++) {string tmp = t; // 细节问题for (int j = 0; j < 4; j++) {tmp[i] = change[j];if (hash.count(tmp) && !vis.count(tmp)) {if (tmp == endGene)return ret;q.push(tmp);vis.insert(tmp);}}}}}return -1;}
};
🌙topic-->3
题目链接:3. - 力扣(LeetCode)
题目分析:
字典 wordList
中从单词 beginWord
到 endWord
的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk
:
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k
时,每个si
都在wordList
中。注意,beginWord
不需要在wordList
中。 sk == endWord
给你两个单词 beginWord
和 endWord
和一个字典 wordList
,返回 从 beginWord
到 endWord
的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0
。
算法原理:
- 解法:采用BFS算法
图解:
跟上面解法是一样的,这里就是不再赘述了。
代码演示:
class Solution {
public:int ladderLength(string beginWord, string endWord,vector<string>& wordList) {unordered_set<string> hash(wordList.begin(), wordList.end());unordered_set<string> vis; // 标记已经搜索过的单词if (!hash.count(endWord))return 0;queue<string> q;q.push(beginWord);vis.insert(beginWord);int ret = 1;while (q.size()) {ret++;int sz = q.size();while (sz--) {string t = q.front();q.pop();for (int i = 0; i < t.size(); i++) {string tmp = t;for (char ch = 'a'; ch <= 'z'; ch++) {tmp[i] = ch;if (hash.count(tmp) && !vis.count(tmp)) {if (tmp == endWord)return ret;q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};
🌙 topic-->4
题目链接:4. - 力扣(LeetCode)
题目分析:
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n
的矩阵表示, 在这个矩阵中:
0
表示障碍,无法触碰1
表示地面,可以行走比 1 大的数
表示有树的单元格,可以行走,数值表示树的高度
每一步,你都可以向上、下、左、右四个方向之一移动一个单位,如果你站的地方有一棵树,那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树,每砍过一颗树,该单元格的值变为 1
(即变为地面)。
你将从 (0, 0)
点开始工作,返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树,返回 -1
。
可以保证的是,没有两棵树的高度是相同的,并且你至少需要砍倒一棵树。
算法原理:
- 解法:采用BFS算法
图解:
代码演示:
class Solution {int m, n;public:int cutOffTree(vector<vector<int>>& f) {m = f.size(), n = f[0].size();// 1. 准备⼯作:找出砍树的顺序vector<pair<int, int>> trees;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (f[i][j] > 1)trees.push_back({i, j});sort(trees.begin(), trees.end(),[&](const pair<int, int>& p1, const pair<int, int>& p2) {return f[p1.first][p1.second] < f[p2.first][p2.second];});// 2. 按照顺序砍树int bx = 0, by = 0;int ret = 0;for (auto& [a, b] : trees) {int step = bfs(f, bx, by, a, b);if (step == -1)return -1;ret += step;bx = a, by = b;}return ret;}bool vis[51][51];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey) {if (bx == ex && by == ey)return 0;queue<pair<int, int>> q;memset(vis, 0, sizeof vis); // 清空之前的数据q.push({bx, by});vis[bx][by] = true;int step = 0;while (q.size()) {step++;int sz = q.size();while (sz--) {auto [a, b] = q.front();q.pop();for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && f[x][y] &&!vis[x][y]) {if (x == ex && y == ey)return step;q.push({x, y});vis[x][y] = true;}}}}return -1;}
};
🌟结束语
今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。