当前位置: 首页 > article >正文

【递归、搜索与回溯】综合练习(四)

📝前言说明:

  • 本专栏主要记录本人递归,搜索与回溯算法的学习以及LeetCode刷题记录,按专题划分
  • 每题主要记录:(1)本人解法 + 本人屎山代码;(2)优质解法 + 优质代码;(3)精益求精,更好的解法和独特的思想(如果有的话)
  • 文章中的理解仅为个人理解。如有错误,感谢纠错

🎬个人简介:努力学习ing
📋本专栏:C++刷题专栏
📋其他专栏:C语言入门基础,python入门基础,C++学习笔记,Linux
🎀CSDN主页 愚润泽

你可以点击下方链接,进行该专题内不同子专题的学习

点击链接开始学习
导论递归 (一) 、递归 (二)
二叉树的深搜穷举 vs 暴搜 vs 深搜 vs 回溯 vs 剪枝
综合练习(一)综合练习(二)
综合练习(三)综合练习(四)
FloodFill算法记忆化搜索

题目

  • 79. 单词搜索
    • 优质解
  • 1219. 黄金矿工
    • 优质解
  • 980. 不同路径 III
    • 个人解


79. 单词搜索

题目链接:https://leetcode.cn/problems/word-search/description/
在这里插入图片描述


优质解

思路:

  • 从第二步开始,每一步实际上是往周围 4 个位置探索,如果能走就继续递归下一个word字符
  • 不解释了,看注释吧

代码:

class Solution {
public:int m, n;bool check[6][6]; // 最大不会超过这么大// 用两个 4 个元素的数组来表示对应的四个移动方向int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};// pos 记录匹配了几个了,row 和 col 是上一个匹配的字符的行和列bool dfs(vector<vector<char>>& board, string word, int pos, int row, int col){if(pos == word.size()) return true;for(int i = 0; i < 4; i++) // 尝试 4 个搜索方向{int r = row + dx[i], c = col + dy[i];if(r >= 0 && r < m && c >= 0 && c < n && check[r][c] == false && board[r][c] == word[pos]){check[r][c] = true;// 找到路径,就立刻返回 trueif(dfs(board, word, pos + 1, r, c)) return true;check[r][c] = false;}}return false;}bool exist(vector<vector<char>>& board, string word) {m = board.size();n = board[0].size();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == word[0]) // 先单独对第一个字符判断{check[i][j] = true;if(dfs(board, word, 1, i, j)) return true; // 再进入就是第二个字符了check[i][j] = false;}}}return false;}
};

时间复杂度: O ( m ∗ n ∗ 4 L ) O(m * n * 4^L) O(mn4L), L 为单词长度
空间复杂度: O ( m ∗ n + L ) O(m * n + L) O(mn+L)


1219. 黄金矿工

题目链接:https://leetcode.cn/problems/path-with-maximum-gold/description/
在这里插入图片描述


优质解

思路:

  • 对每一个位置进行一遍dfs

代码:

class Solution {
public:int ans;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool check[16][16];int m, n;void dfs(vector<vector<int>>& grid, int row, int col, int path){for(int i = 0; i < 4; i++){int r = row + dx[i], c = col + dy[i];if(r >= 0 && r < m && c >= 0 && c < n && !check[r][c] && grid[r][c]){check[r][c] = true;dfs(grid, r, c, path + grid[r][c]); // 传局部变量path自动回溯check[r][c] = false;}}ans = max(ans, path); // “无路可走”才会到这}int getMaximumGold(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]){check[i][j] = true;dfs(grid, i, j, grid[i][j]);check[i][j] = false;}}}return ans;}
};

时间复杂度: O ( m × n × 4 m × n ) O(m \times n \times 4^ {m\times n}) O(m×n×4m×n),m * n 是最长路径长
空间复杂度: O ( m × n ) O(m \times n) O(m×n)


980. 不同路径 III

题目链接:https://leetcode.cn/problems/unique-paths-iii/description/
在这里插入图片描述

个人解

思路:

  • 不解释了,把前面的题都写好的话,这题应该不是很难

用时:15:00

屎山代码:

class Solution {
public:bool check[20][20];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;int ans;int steps;void dfs(vector<vector<int>>& grid, int row, int col, int s){for(int i = 0; i < 4; i++){int r = row + dx[i], c = col + dy[i];if(r >= 0 && r < m && c >= 0 && c < n){if(!check[r][c] && grid[r][c] == 0){check[r][c] = true;dfs(grid, r, c, s + 1);check[r][c] = false;}if(s == steps && grid[r][c] == 2) // 所有 0 都走过一遍了,并且下一步是 1 {ans++;return;}}}}int uniquePathsIII(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int start_i, start_j;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 1) // 找起始位置{start_i = i;start_j = j;}if(grid[i][j] == -1) // 设置障碍check[i][j] = true;if(grid[i][j] == 0) // 记录总共要走多少步steps++; }}dfs(grid, start_i, start_j, 0);return ans;}
};

时间复杂度: O ( 4 m × n ) O(4^{m × n}) O(4m×n)
空间复杂度: O ( m × n ) O(m \times n) O(m×n)


🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助,那简直是太酷啦!
若有不足,还请大家多多指正,我们一起学习交流!
📢公主,王子:点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持!祝大家都能得偿所愿,天天开心!!!

http://www.lryc.cn/news/2403074.html

相关文章:

  • 强化学习入门:Gym实现CartPole随机智能体
  • STM32:CAN总线精髓:特性、电路、帧格式与波形分析详解
  • 贝叶斯深度学习!华科大《Nat. Commun.》发表BNN重大突破!
  • 【大模型LLM学习】Flash-Attention的学习记录
  • 三、元器件的选型
  • 精益数据分析(95/126):Socialight的定价转型启示——B2B商业模式的价格策略与利润优化
  • stm32_DMA
  • 物联网数据归档之数据存储方案选择分析
  • 【自动驾驶避障开发】如何让障碍物在 RViz 中‘显形’?呈现感知数据转 Polygon 全流程
  • 【C语言】C语言经典小游戏:贪吃蛇(上)
  • usbutils工具的使用帮助
  • vue2中使用jspdf插件实现页面自定义块pdf下载
  • 如何防止服务器被用于僵尸网络(Botnet)攻击 ?
  • 基于cornerstone3D的dicom影像浏览器 第二十九章 自定义菜单组件
  • 【Block总结】DBlock,结合膨胀空间注意模块(Di-SpAM)和频域模块Gated-FFN|即插即用|CVPR2025
  • 【学习笔记】单例类模板
  • 字符串加密(华为OD)
  • 口罩佩戴检测算法AI智能分析网关V4工厂/工业等多场景守护公共卫生安全
  • Double/Debiased Machine Learning
  • HarmonyOS Next 弹窗系列教程(4)
  • 【C】-递归
  • 飞马LiDAR500雷达数据预处理
  • Kerberos面试内容整理-在 Linux/Windows 中的 Kerberos 实践
  • 在 Allegro PCB Editor 中取消(解除或删除)已创建的 **Module** 的操作指南
  • 基于springboot的校园社团信息系统的设计与实现
  • nodejs里面的http模块介绍和使用
  • mamba架构和transformer区别
  • 嵌入式鸿蒙开发环境搭建操作方法与实现
  • 在 Spring Boot 中使用 WebFilter:实现请求拦截、日志记录、跨域处理等通用逻辑!
  • CSS预处理器:Sass与Less的语法和特性(含实际案例)