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

【数据结构与算法】 LeetCode:回溯

文章目录

  • 回溯算法
    • 组合
    • 组合总和(Hot 100)
    • 组合总和 II
    • 电话号码的字母组合(Hot 100)
    • 括号生成(Hot 100)
    • 分割回文串(Hot 100)
    • 复原IP地址
    • 子集(Hot 100)
    • 全排列(Hot 100)
    • N皇后(Hot 100)
    • 单词搜索(Hot 100)

回溯算法

组合

组合

class Solution {
private:vector<vector<int>> result; // 存放符合条件结果的集合vector<int> path; // 用来存放符合条件结果void backtracking(int n, int k, int startIndex) {if (path.size() == k) {result.push_back(path);return;}for (int i = startIndex; i <= n; i++) {path.push_back(i); // 处理节点backtracking(n, k, i + 1); // 递归path.pop_back(); // 回溯,撤销处理的节点 }}
public:vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return result;}
};

剪枝。例如,去掉达不到k=4的分支:
在这里插入图片描述

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(int n, int k, int startIndex) {if (path.size() == k) {result.push_back(path);return;}// 剪枝优化// 还需要的元素个数为: k - path.size();// 令待加入path的数为:i = startIndex;i及其之后的元素个数:n - i +1// 需要满足:k - path.size()  <= n - i +1for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {    path.push_back(i); // 处理节点backtracking(n, k, i + 1);path.pop_back(); // 回溯,撤销处理的节点}}
public:vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return result;}
};

组合总和(Hot 100)

组合总和

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {if (sum > target) {return;}if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size(); i++) {sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i); // 不用i+1了,表示可以重复读取当前的数sum -= candidates[i];path.pop_back();}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {result.clear();path.clear();backtracking(candidates, target, 0, 0);return result;}
};

组合总和 II

组合总和 II

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {if (sum > target) {return;}if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size(); i++) {// 避免同一层级重复使用相同的元素if (i > startIndex && candidates[i] == candidates[i - 1]) {continue;}sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i + 1); // 注意这里是 i + 1,表示下一层级不再使用当前元素sum -= candidates[i];path.pop_back();}}public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end()); // 首先对候选数组进行排序,以便处理重复元素的情况backtracking(candidates, target, 0, 0);return result;}
};

电话号码的字母组合(Hot 100)

电话号码的字母组合


class Solution {
private:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};
public:vector<string> result;string s;void backtracking(const string& digits, int index) {if (index == digits.size()) {result.push_back(s);return;}int digit = digits[index] - '0';        // 将index指向的数字转为intstring letters = letterMap[digit];      // 取数字对应的字符集for (int i = 0; i < letters.size(); i++) {s.push_back(letters[i]);            // 处理backtracking(digits, index + 1);    // 递归,注意index+1,下一层要处理下一个数字了s.pop_back();                       // 回溯}}vector<string> letterCombinations(string digits) {s.clear();result.clear();if (digits.size() == 0) return result;backtracking(digits, 0);return result;}
};

括号生成(Hot 100)

括号生成

左括号 ‘(’ 必须用相同数量的右括号 ‘)’ 闭合。
左括号 ‘(’ 必须在对应的右括号 ‘)’ 之前。

class Solution {  void backtrack(vector<string>& ans, // 存储结果的vector  string& cur,         // 当前生成的括号组合字符串  int open,            // 当前已经放置的左括号数量  int close,           // 当前已经放置的右括号数量  int n) {             // 目标括号对的数量  // 如果当前括号组合的长度达到了目标长度(即2n)  if (cur.size() == n * 2) {  // 将当前组合添加到结果中  ans.push_back(cur);  // 回溯完成,返回上一层  return;  }  // 如果左括号数量小于n,说明可以继续放置左括号  if (open < n) {  // 在当前组合后添加一个左括号  cur.push_back('(');  // 递归调用,左括号数量加1,右括号数量不变  backtrack(ans, cur, open + 1, close, n);  // 回溯,撤销刚才的选择(即移除刚才添加的左括号)  cur.pop_back();  }  // 如果右括号数量小于左括号数量,说明可以继续放置右括号  if (close < open) {  // 在当前组合后添加一个右括号  cur.push_back(')');  // 递归调用,左括号数量不变,右括号数量加1  backtrack(ans, cur, open, close + 1, n);  // 回溯,撤销刚才的选择(即移除刚才添加的右括号)  cur.pop_back();  }  }  public:  vector<string> generateParenthesis(int n) {  vector<string> ans; // 存储最终结果的vector  string current;        // 当前正在构建的括号组合  //  回溯生成括号组合  backtrack(ans, current, 0, 0, n);  return ans;  }  
};

分割回文串(Hot 100)

分割回文串

class Solution {
private:vector<vector<string>> result;  //  [ ["aa","b"], ["a","a","b"] ]vector<string> path; // 放已经回文的子串  ["aa","b"]或 ["a","a","b"] void backtracking (const string& s, int startIndex) {// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了if (startIndex >= s.size()) {result.push_back(path);return;}for (int i = startIndex; i < s.size(); i++) {// 存在不是回文的字串,跳过之后的递归(因为分割得到的所有子串都必须为回文的)if (!isPalindrome(s, startIndex, i)) continue; // 与组合不同,这里是分割// 获取[startIndex,i]在s中的子串string str = s.substr(startIndex, i - startIndex + 1);path.push_back(str);backtracking(s, i + 1); // 寻找i+1为起始位置的子串path.pop_back(); // 回溯过程,弹出本次已经添加的子串}}bool isPalindrome(const string& s, int start, int end) {for (int i = start, j = end; i < j; i++, j--) {if (s[i] != s[j]) return false;}return true;}
public:vector<vector<string>> partition(string s) {result.clear();path.clear();backtracking(s, 0);return result;}
};

复原IP地址

复原IP地址

// https://www.programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html#%E6%80%9D%E8%B7%AF
class Solution {
private:vector<string> result;// 记录结果// startIndex: 搜索的起始位置,pointNum:添加逗点的数量void backtracking(string& s, int startIndex, int pointNum) {if (pointNum == 3) { // 逗点数量为3时,分隔结束// 判断第四段子字符串是否合法,如果合法就放进result中if (isValid(s, startIndex, s.size() - 1)) {result.push_back(s);}return;}for (int i = startIndex; i < s.size(); i++) {if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点pointNum++;backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2pointNum--;                         // 回溯s.erase(s.begin() + i + 1);         // 回溯删掉逗点} else break; // 不合法,直接结束本层循环}}// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法bool isValid(const string& s, int start, int end) {if (start > end) {return false;}if (s[start] == '0' && start != end) { // 0开头的数字不合法return false;}int num = 0;for (int i = start; i <= end; i++) {if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法return false;}num = num * 10 + (s[i] - '0');if (num > 255) { // 如果大于255了不合法return false;}}return true;}
public:vector<string> restoreIpAddresses(string s) {result.clear();if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了backtracking(s, 0, 0);return result;}
};

子集(Hot 100)

子集

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); // 收集子集for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);return result;}
};

全排列(Hot 100)

全排列

class Solution {
private:void backtrack(vector<int>& nums, vector<vector<int>>& result, int start){if(start == nums.size()-1 ){result.push_back(nums);return;}for(int i = start; i < nums.size(); i++){swap(nums[i],nums[start]);backtrack(nums, result,start+1);  swap(nums[i],nums[start]);}}public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> result;backtrack(nums, result, 0);return result;}
};

N皇后(Hot 100)

N皇后

class Solution {
private:
vector<vector<string>> result;void backtracking(int n, int row, vector<string>& chessboard) {if (row == n) {result.push_back(chessboard);return;}for (int col = 0; col < n; col++) {// 递归的时候row + 1,每一行放一个,所以不用对行进行检查if (isValid(row, col, chessboard, n)) { // 验证合法就可以放chessboard[row][col] = 'Q'; // 放置皇后backtracking(n, row + 1, chessboard);chessboard[row][col] = '.'; // 回溯,撤销皇后}}
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {// 检查列for (int i = 0; i < row; i++) { // 这是一个剪枝if (chessboard[i][col] == 'Q') return false;}// 检查 45度角是否有皇后for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {if (chessboard[i][j] == 'Q') return false;}// 检查 135度角是否有皇后for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (chessboard[i][j] == 'Q') return false;}return true;
}
public:vector<vector<string>> solveNQueens(int n) {result.clear();std::vector<std::string> chessboard(n, std::string(n, '.'));backtracking(n, 0, chessboard);return result;}
};

单词搜索(Hot 100)

单词搜索

class Solution {
private:int rows, cols;bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {// k 表示在 word 字符串中当前要匹配的字符的索引// i越界或j越界或不匹配if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;// board[i][j] = word[k]if (k == word.size() - 1) return true; // 字符串匹配完成board[i][j] = '\0'; // 代表此元素已访问过,防止之后搜索时重复访问// 搜索下一单元格: 朝当前元素的 上、下、左、右 四个方向开启下层递归,// 使用或代表只需找到一条可行路径就直接返回,不再做后续 DFS,并记录结果至 res bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);board[i][j] = word[k]; // 回溯:还原当前矩阵元素return res;}
public:bool exist(vector<vector<char>>& board, string word) {rows = board.size();cols = board[0].size();for(int i = 0; i < rows; i++) {for(int j = 0; j < cols; j++) { // 每一个格子向四周if (dfs(board, word, i, j, 0)) return true;}}return false;}
};

相关文章:

【数据结构与算法】 LeetCode:回溯

文章目录 回溯算法组合组合总和&#xff08;Hot 100&#xff09;组合总和 II电话号码的字母组合&#xff08;Hot 100&#xff09;括号生成&#xff08;Hot 100&#xff09;分割回文串&#xff08;Hot 100&#xff09;复原IP地址子集&#xff08;Hot 100&#xff09;全排列&…...

SpringBoot线程池的使用

SpringBoot线程池的使用 在现代Web应用开发中&#xff0c;特别是在使用Spring Boot框架时&#xff0c;合理使用线程池可以显著提高应用的性能和响应速度。线程池不仅能够减少线程创建和销毁的开销&#xff0c;还能有效地控制并发任务的数量&#xff0c;避免因线程过多而导致的…...

Neural Magic 发布 LLM Compressor:提升大模型推理效率的新工具

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

HttpServletRequest req和前端的关系,req.getParameter详细解释,req.getParameter和前端的关系

HttpServletRequest 对象在后端和前端之间起到了桥梁的作用&#xff0c;它包含了来自客户端的所有请求信息。通过 HttpServletRequest 对象&#xff0c;后端可以获取前端发送的请求参数、请求头、请求方法等信息&#xff0c;并根据这些信息进行相应的处理。以下是对 HttpServle…...

React-useEffect的使用

useEffect react提供的一个常用hook&#xff0c;用于在函数组件中执行副作用操作&#xff0c;比如数据获取、订阅或手动更改DOM。 基本用法&#xff1a; 接受2个参数&#xff1a; 一个包含命令式代码的函数&#xff08;副作用函数&#xff09;。一个依赖项数组&#xff0c;用…...

MySQL数据库与Informix:能否创建同名表?

MySQL数据库与Informix:能否创建同名表? 一、MySQL数据库中的同名表创建1. 使用CREATE TABLE ... SELECT语句2. 使用CREATE TABLE LIKE语句3. 复制表结构并选择性复制数据4. 使用同义词(Synonym)二、Informix数据库中的同名表创建1. 使用不同所有者2. 使用不同模式3. 复制表…...

爬虫实战:采集知乎XXX话题数据

目录 反爬虫的本意和其带来的挑战目标实战开发准备代码开发发现问题1. 发现问题[01]2. 发现问题[02] 解决问题1. 解决问题[01]2. 解决问题[02] 最终结果 结语 反爬虫的本意和其带来的挑战 在这个数字化时代社交媒体已经成为人们表达观点的重要渠道&#xff0c;对企业来说&…...

大数据新视界 -- Hive 数据桶原理:均匀分布数据的智慧(上)(9/ 30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...

【小白学机器学习33】 大数定律python的 pandas.Dataframe 和 pandas.Series基础内容

目录 0 总结 0.1pd.Dataframe有一个比较麻烦琐碎的地方&#xff0c;就是引号 和括号 0.2 pd.Dataframe关于括号的原则 0.3 分清楚几个数据类型和对应的方法的范围 0.4 几个数据结构的构造关系 list → np.array(list) → pd.Series(np.array)/pd.Dataframe 1 python 里…...

【shodan】(五)网段利用

shodan基础&#xff08;五&#xff09; 声明&#xff1a;该笔记为up主 泷羽的课程笔记&#xff0c;本节链接指路。 警告&#xff1a;本教程仅作学习用途&#xff0c;若有用于非法行为的&#xff0c;概不负责。 nsa ip address range www.nsa.gov需科学上网 搜索网段 shodan s…...

LeetCode739. 每日温度(2024冬季每日一题 15)

给定一个整数数组 temperatures &#xff0c;表示每天的温度&#xff0c;返回一个数组 answer &#xff0c;其中 answer[i] 是指对于第 i 天&#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高&#xff0c;请在该位置用 0 来代替。 示例 1: 输入: temperatu…...

Node.js的http模块:创建HTTP服务器、客户端示例

新书速览|Vue.jsNode.js全栈开发实战-CSDN博客 《Vue.jsNode.js全栈开发实战&#xff08;第2版&#xff09;&#xff08;Web前端技术丛书&#xff09;》(王金柱)【摘要 书评 试读】- 京东图书 (jd.com) 要使用http模块&#xff0c;只需要在文件中通过require(http)引入即可。…...

加菲工具 - 好用免费的在线工具集合

加菲工具 https://orcc.online AI 工具 加菲工具 集合了目前主流的&#xff0c;免费可用的ai工具 文档处理 加菲工具 pdf转word、office与pdf互转等等工具都有链接 图片图标 加菲工具 统计了好用免费的在线工具 编码解码 加菲工具 base64编码解码、url编码解码、md5计算…...

.NET9 - 新功能体验(二)

书接上回&#xff0c;我们继续来聊聊.NET9和C#13带来的新变化。 01、新的泛型约束 allows ref struct 这是在 C# 13 中&#xff0c;引入的一项新的泛型约束功能&#xff0c;允许对泛型类型参数应用 ref struct 约束。 可能这样说不够直观&#xff0c;简单来说就是Span、ReadO…...

map和redis关系

Map 和 Redis 都是用于存储和管理数据的工具&#xff0c;但它们在用途、实现和应用场景上有所不同。下面详细解释 Map 和 Redis 之间的关系和区别。 1. Map 数据结构 定义 Map 是一种数据结构&#xff0c;用于存储键值对&#xff08;key-value pairs&#xff09;。每个键都是…...

《数据结构》学习系列——图(中)

系列文章目录 目录 图的遍历深度优先遍历递归算法堆栈算法 广度优先搜索 拓扑排序定义定理算法思想伪代码 关键路径基本概念关键活动有关量数学公式伪代码时间复杂性 图的遍历 从给定连通图的某一顶点出发&#xff0c;沿着一些边访问遍图中所有的顶点&#xff0c;且使每个顶点…...

探索Python的HTTP之旅:揭秘Requests库的神秘面纱

文章目录 **探索Python的HTTP之旅&#xff1a;揭秘Requests库的神秘面纱**第一部分&#xff1a;背景介绍第二部分&#xff1a;Requests库是什么&#xff1f;第三部分&#xff1a;如何安装Requests库&#xff1f;第四部分&#xff1a;Requests库的五个简单函数使用方法第五部分&…...

Python 爬虫从入门到(不)入狱学习笔记

爬虫的流程&#xff1a;从入门到入狱 1 获取网页内容1.1 发送 HTTP 请求1.2 Python 的 Requests 库1.2 实战&#xff1a;豆瓣电影 scrape_douban.py 2 解析网页内容2.1 HTML 网页结构2.2 Python 的 Beautiful Soup 库 3 存储或分析数据&#xff08;略&#xff09; 一般爬虫的基…...

IDEA优雅debug

目录 引言一、断点分类&#x1f384;1.1 行断点1.2 方法断点1.3 属性断点1.4 异常断点1.5 条件断点1.6 源断点1.7 多线程断点1.8 Stream断点 二、调试动作✨三、Debug高级技巧&#x1f389;3.1 watch3.2 设置变量3.3 异常抛出3.4 监控JVM堆大小3.5 数组过滤和筛选 引言 使用ID…...

wp the_posts_pagination 与分类页面搭配使用

<ul> <?php while( have_posts() ) : the_post(); <li > <a href"<?php the_permalink(); ?>"> <?php xizhitbu_get_thumbnail(thumb-pro); ?> </a> <p > <a href&q…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...