算法学习——LeetCode力扣回溯篇1

算法学习——LeetCode力扣回溯篇1

在这里插入图片描述

77. 组合

77. 组合 - 力扣（LeetCode）

描述

任何顺序 返回答案。

示例

示例 1：

输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示

  • 1 <= n <= 20
  • 1 <= k <= n

代码解析

回溯遍历法
class Solution {
public:vector<vector<int>> result;vector<int> path;//left是for的开始 ，right是for的结束。当size==k的时候递归结束void tarversal(int left , int right , int k){if(path.size() == k){result.push_back(path);return;}else{for(int i= left ; i <= right ; i++){path.push_back(i);tarversal(i+1 ,right , k);path.pop_back();}return;}}vector<vector<int>> combine(int n, int k) {tarversal(1,n,k);return result;}
};
回溯剪枝法

剪枝是减少无意义循环的过程
在这里插入图片描述

当输入是n=4，k=4的时候，只有1234符合。我们遍历到2开始时，最多为234，234的长度为3满足长度为4的情况，是无意义的，要剪去。

for(int i= left ; i <= right - (k - path.size()) +1 ; i++) 为剪枝的判断

其中left为遍历的开始，right为遍历的结束。现在还需要找到k - path.size()个点
即 right - left => (k - path.size()) ，为剩下的点可以满足k的要求
=>left <= right - (k - path.size()) +1 ， 其中+1为满足左边闭合。
例，k=3，n=4时，已经选取的为0个（path.size()=0），带入i <= right - ( k - path.size() ) +1 ， i <= 4 - （3-0）+1 ，为i<=2。
即当i最大为从2开始满足，为234 。大于2 剪枝

class Solution {
public:vector<vector<int>> result;vector<int> path;void tarversal(int left , int right , int k){if(path.size() == k){result.push_back(path);return;}else{//i <= right - (k - path.size()) +1为剪枝的过程，避免无意义的循环for(int i= left ; i <= right - (k - path.size()) +1 ; i++){path.push_back(i);tarversal(i+1 ,right , k);path.pop_back();}return;}}vector<vector<int>> combine(int n, int k) {tarversal(1,n,k);return result;}
};

216. 组合总和 III

216. 组合总和 III - 力扣（LeetCode）

描述

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示

  • 2 <= k <= 9
  • 1 <= n <= 60

代码解析

回溯法无减枝
class Solution {
public:vector<vector<int>> result;vector<int> path;void backtraking(int k, int n , int sum ,int startidx){if(path.size() == k && sum == n){result.push_back(path);return;}else{for(int i= startidx ; i < 10 ; i++){path.push_back(i);backtraking(k,n,sum+i,i+1);path.pop_back();}return;}}vector<vector<int>> combinationSum3(int k, int n) {backtraking(k,n,0,1);return result;}
};
回溯剪枝

剪枝原理同 77题

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtraking(int k, int n , int sum ,int startidx){if(sum > n) return;if(path.size() == k && sum == n){result.push_back(path);return;}else{for(int i= startidx ; i < 10 - (k - path.size()) + 1 ; i++){path.push_back(i);backtraking(k,n,sum+i,i+1);path.pop_back();}return;}}vector<vector<int>> combinationSum3(int k, int n) {backtraking(k,n,0,1);return result;}
};

17. 电话号码的字母组合

17. 电话号码的字母组合 - 力扣（LeetCode）

描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例

示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：

输入：digits = “”
输出：[]

示例 3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

提示

  • 0 <= digits.length <= 4
  • digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

代码解析

字符串
class Solution {
public:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};vector<string> result;//输入参：转换后的vector ， 从第几个按键开始循环 ， 已经走的路径void backtarcking(vector<int> &digits_i , int startidx , string path){ 	//当路径的长度等于数组的长度，存入结果if(path.size() == digits_i.size() ){result.push_back(path);return;}else{	//第一次循环，循环数字for(int i = startidx ; i < digits_i.size() ; i++){//找到输入数字对应的字母表string tmp = letterMap[digits_i[i]];vector<char> tmp_v(tmp.begin() , tmp.end()) ;//第二次循环，循环每一个数字的字母for(int j=0 ; j < tmp_v.size() ; j++){//递归回溯，开始循环的数字往后走一个，路径加上已经走的路径backtarcking(digits_i, i+1 , path + tmp_v[j]);}}return;}return;}vector<string> letterCombinations(string digits) {//输入为空时直接返回if(digits.size()==0) return result;//字符串转换成vectorvector<int> digits_i;for(auto i:digits) digits_i.push_back( i - '0' );string path;backtarcking(digits_i , 0 , path);return result;}
};
map表
class Solution {
public:vector<string> result;string worldPath;map<char,vector<string>> myMap;void map_init(){myMap.insert(pair<char,vector<string>>('2',{"a","b","c"})) ;myMap.insert(pair<char,vector<string>>('3',{"d","e","f"})) ;myMap.insert(pair<char,vector<string>>('4',{"g","h","i"})) ;myMap.insert(pair<char,vector<string>>('5',{"j","k","l"})) ;myMap.insert(pair<char,vector<string>>('6',{"m","n","o"})) ;myMap.insert(pair<char,vector<string>>('7',{"p","q","r","s"})) ;myMap.insert(pair<char,vector<string>>('8',{"t","u","v"})) ;myMap.insert(pair<char,vector<string>>('9',{"w","x","y","z"})) ;// for(auto it:myMap)//      cout<<it.first<<':'<<(it.second)[0]<<endl;// cout<<myMap['2'].size();}void dfs(string digits , int fir ){if( worldPath.size() == digits.size()){result.push_back(worldPath);return;}char num = digits[fir];for(int j=0 ; j< myMap[num].size() ;j++){worldPath += myMap[num][j];dfs(digits,fir+1);worldPath.pop_back();}return;}vector<string> letterCombinations(string digits) {if(digits.size()==0) return result;map_init();dfs(digits,0);return result;}
};

39. 组合总和

39. 组合总和 - 力扣（LeetCode）

描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

代码解析

暴力回溯（无剪枝，时间复杂度高）
class Solution {
public:vector<vector<int>> result;vector<int> path;int sum;void backtracking(vector<int>& candidates, int target , int sum){	//检测目标大于时返回if(sum > target) return;if(sum == target){//排序后发现是新结果插入vector<int> tmp(path.begin(),path.end());sort(tmp.begin(),tmp.end());auto it = find(result.begin(),result.end(),tmp);if(it == result.end()) result.push_back(tmp);return;}//无任何限制回溯for(int i = 0 ; i < candidates.size() ;i++){path.push_back(candidates[i]);backtracking(candidates,target,sum+candidates[i]);path.pop_back();}return;}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0);return result;}
};
回溯剪枝
class Solution {
public:vector<vector<int>> result;vector<int> path;int sum;void backtracking(vector<int>& candidates, int target , int sum , int indnx){if(sum > target) return;if(sum == target){result.push_back(path);return;}//剪枝，因为之前已经对输入进行排序，当发现加上i点的值大于目标后，后面的也都大于for(int i = indnx ; i < candidates.size() && sum+candidates[i] <= target ;i++){path.push_back(candidates[i]);//递归的下一个指针和当前一样都是i，不是i+1 //因为一个数可以重复的使用，不能重复是i+1backtracking(candidates,target,sum+candidates[i] , i);path.pop_back();}return;}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {//对输入进行排序，方便后面循环sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);return result;}
};

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

steam搬砖项目，“一个月赚8K+”真的假的？

steam搬砖项目，“一个月赚8K+”真的假的？

在游戏中&#xff0c;搬砖党是永远都不能忽视的存在&#xff0c;随着游戏产业的不断发展&#xff0c;普通人也可以在steam搬砖项目中找到自己的生财之道。由于是低技术的重复工作&#xff0c;和现实的搬砖类似&#xff0c;所以才叫steam搬砖项目。 steam搬砖项目其实就和pdd无…
阅读更多...
数据结构（C语言）代码实现（八）——顺序栈实现数值转换行编辑程序括号分配汉诺塔

数据结构（C语言）代码实现（八）——顺序栈实现数值转换行编辑程序括号分配汉诺塔

目录 参考资料 顺序栈的实现 头文件SqStack.h&#xff08;顺序栈函数声明&#xff09; 源文件SqStack.cpp&#xff08;顺序栈函数实现&#xff09; 顺序栈的三个应用 数值转换 行编辑程序 顺序栈的实现测试 栈与递归的实现&#xff08;以汉诺塔为例&#xff09; 参考资…
阅读更多...
2024-02-13 Unity 编辑器开发之编辑器拓展4 —— EditorGUIUtility

2024-02-13 Unity 编辑器开发之编辑器拓展4 —— EditorGUIUtility

文章目录 1 EditorGUIUtility 介绍2 加载资源2.1 Eidtor Default Resources2.2 不存在返回 null2.3 不存在则报错2.4 代码示例 3 搜索框查询、对象选中提示3.1 ShowObjectPicker3.2 PingObject3.3 代码示例 4 窗口事件传递、坐标转换4.1 CommandEvent4.2 GUIPoint 和 ScreenPoi…
阅读更多...
Vue源码系列讲解——模板编译篇【三】(HTML解析器)

Vue源码系列讲解——模板编译篇【三】(HTML解析器)

目录 1. 前言 2. HTML解析器内部运行流程 3. 如何解析不同的内容 3.1 解析HTML注释 3.2 解析条件注释 3.3 解析DOCTYPE 3.4 解析开始标签 3.5 解析结束标签 3.6 解析文本 4. 如何保证AST节点层级关系 5. 回归源码 5.1 HTML解析器源码 5.2 parseEndTag函数源码 6. …
阅读更多...
【快速上手QT】02-学会查看QT自带的手册QT助手

【快速上手QT】02-学会查看QT自带的手册QT助手

QT助手 为什么大家都说QT简单&#xff0c;第一点就是确实简单&#xff08;bushi&#xff09;。 我个人觉得最关键的点就是人家QT官方就给你准备好了文档&#xff0c;甚至还有专门的IDE——QtCreator&#xff0c;在QTCreator里面还有很多示例代码&#xff0c;只要你会C的语法以…
阅读更多...
ETL是什么，有哪些ETL工具？就业前景如何？

ETL是什么，有哪些ETL工具？就业前景如何？

ETL是什么 ETL&#xff08;Extract-Transform-Load&#xff09;&#xff0c;用来描述将数据从来源端经过抽取(extract)、转换(transform)、加载(load)至目标端的过程。ETL一词较常用在数据仓库&#xff0c;但其对象并不限于数据仓库。它可以自动化数据处理过程&#xff0c;减少…
阅读更多...
2024.2.3 作业

2024.2.3 作业

1、实现单向循环链表的头插头删尾插尾删 #include<stdio.h> #include<string.h> #include<stdlib.h> typedef int datatype; typedef struct node {//数据域int data;//指针域struct node *next; }*Linklist; Linklist create() {Linklist s(Linklist)mallo…
阅读更多...
如何在C# Windows Forms应用程序中实现控件之间的连接线

如何在C# Windows Forms应用程序中实现控件之间的连接线

帮我实现绘图工具多个控件连接线&#xff0c;请用c#代码实现 实现绘图工具中多个控件之间的连接线功能&#xff0c;可以通过以下几个步骤来进行&#xff1a; 定义连接线的数据模型&#xff1a;首先需要定义一个模型来表示连接线&#xff0c;这个模型应该包含起点和终点的坐标。…
阅读更多...
内网穿透 | 推荐两个免费的内网穿透工具

内网穿透 | 推荐两个免费的内网穿透工具

目录 1、简介 2、Ngrok 2.1、下载安装 2.2、运行 2.3、固定域名 2.4、配置多服务 3、cpolar 3.1、下载安装 3.2、运行 &#x1f343;作者介绍&#xff1a;双非本科大三网络工程专业在读&#xff0c;阿里云专家博主&#xff0c;专注于Java领域学习&#xff0c;擅长web应…
阅读更多...
【AutoML】AutoKeras 进行 RNN 循环神经网络训练

【AutoML】AutoKeras 进行 RNN 循环神经网络训练

由于最近这些天都在人工审查之前的哪些问答数据&#xff0c;所以迟迟都没有更新 AutoKeras 的训练结果。现在那部分数据都已经整理好了&#xff0c;20w 的数据最后能够使用的高质量数据只剩下 2k。这 2k 的数据已经经过数据校验并且对部分问题的提问方式和答案内容进行了不改变…
阅读更多...
【龙年大礼】| 2023中国开源年度报告！

【龙年大礼】| 2023中国开源年度报告！

【中国开源年度报告】由开源社从 2015 年发起&#xff0c;是国内首个结合多个开源社区、高校、媒体、风投、企业与个人&#xff0c;以纯志愿、非营利的理念和开源社区协作的模式&#xff0c;携手共创完成的开源研究报告。后来由于一些因素暂停&#xff0c;在 2018 年重启了这个…
阅读更多...
基于Qt的人脸识别项目（功能：颜值检测，口罩检测，表情检测，性别检测，年龄预测等）

基于Qt的人脸识别项目（功能：颜值检测，口罩检测，表情检测，性别检测，年龄预测等）

目录 效果展示代码讲解（待更新）需求一.创建项目二.导入Qt中的摄像头包查看QCamera类的帮助文档三.导入QCameraViewfinder调用百度AI接口完整代码链接完整代码链接在文章末尾 效果展示
阅读更多...
react+antd+CheckableTag实现Tag标签单选或多选功能

react+antd+CheckableTag实现Tag标签单选或多选功能

1、效果如下图 实现tag标签单选或多选功能 2、环境准备 1、react18 2、antd 4 3、功能实现 原理: 封装一个受控组件&#xff0c;接受父组件的参数&#xff0c;数据发现变化后&#xff0c;回传给父组件 1、首先&#xff0c;引入CheckableTag组件和useEffect, useMemo, use…
阅读更多...
CSS之水平垂直居中

CSS之水平垂直居中

如何实现一个div的水平垂直居中 <div class"content-wrapper"><div class"content">content</div></div>flex布局 .content-wrapper {width: 400px;height: 400px;background-color: lightskyblue;display: flex;justify-content:…
阅读更多...
在Linux系统中设置全局HTTP代理的步骤与技巧

在Linux系统中设置全局HTTP代理的步骤与技巧

在Linux系统中&#xff0c;设置全局HTTP代理可以方便我们统一管理和控制网络请求。这不仅可以帮助我们加速网络访问&#xff0c;还可以在某些情况下绕过网络限制或实现匿名上网。下面&#xff0c;我将为你详细介绍在Linux系统中设置全局HTTP代理的步骤与技巧。 步骤一&#xf…
阅读更多...
【c++】内联函数

【c++】内联函数

Hello everybody!今天咱们来讲一下内联函数&#xff0c;它在某些方面还是很有用的&#xff01; 1.定义 以inline修饰的函数叫做内联函数&#xff0c;编译时c编译器会在调用内联函数的地方展开&#xff0c;没有函数调用建立栈帧的开销&#xff0c;内联函数提升程序运行的效率。…
阅读更多...
mysql8.0.36主从复制(读写分离)配置教程

mysql8.0.36主从复制(读写分离)配置教程

1、关闭防火墙 使用命令行关闭防火墙 在Ubuntu系统中&#xff0c;可以使用以下命令关闭防火墙&#xff1a; sudo ufw disable执行该命令后&#xff0c;系统会提示是否要关闭防火墙&#xff0c;确认后即可关闭防火墙。 查看防火墙状态 使用以下命令可以查看防火墙当前的状…
阅读更多...
apk反编译修改教程系列---简单修改apk默认横竖屏显示 手机端与电脑端同步演示【十一】

apk反编译修改教程系列---简单修改apk默认横竖屏显示 手机端与电脑端同步演示【十一】

往期教程&#xff1a; apk反编译修改教程系列-----修改apk应用名称 任意修改名称 签名【一】 apk反编译修改教程系列-----任意修改apk版本号 版本名 防止自动更新【二】 apk反编译修改教程系列-----修改apk中的图片 任意更换apk桌面图片【三】 apk反编译修改教程系列---简单…
阅读更多...
【python量化交易】qteasy使用教程02 - 获取和管理金融数据

【python量化交易】qteasy使用教程02 - 获取和管理金融数据

qteasy教程2 - 获取并管理金融数据 qteasy教程2 - 获取并管理金融数据开始前的准备工作获取基础数据以及价格数据下载交易日历和基础数据查看股票和指数的基础数据下载沪市股票数据从本地获取股价数据生成K线图 数据类型的查找定期下载数据到本地回顾总结 qteasy教程2 - 获取并…
阅读更多...
Swift Combine 网络受限时从备用 URL 请求数据 从入门到精通十四

Swift Combine 网络受限时从备用 URL 请求数据 从入门到精通十四

Combine 系列 Swift Combine 从入门到精通一Swift Combine 发布者订阅者操作者 从入门到精通二Swift Combine 管道 从入门到精通三Swift Combine 发布者publisher的生命周期 从入门到精通四Swift Combine 操作符operations和Subjects发布者的生命周期 从入门到精通五Swift Com…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023