day-27 代码随想录算法训练营(19)回溯part03

39.组合总和

分析:同一个数可以选多次,但是不能有重复的答案;
思路:横向遍历,纵向递归(不同的是递归的时候不需要跳到下一个位置,因为同一个数可以选多次)
class Solution {
public:vector<vector<int>>res;vector<int>mids;void backtrace(vector<int>&candidates,int start,int sum,int target){if(sum>=target){//终止条件if(sum==target)//目标条件res.push_back(mids);return;}for(int i=start;i<candidates.size();i++){mids.push_back(candidates[i]);sum+=candidates[i];backtrace(candidates,i,sum,target);//因为同一个数可以选多次,所以递归为imids.pop_back();sum-=candidates[i];}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtrace(candidates,0,0,target);return res;}
};

 40.组合总和||

思路:重点在于去重
去重:树层去重,需要在递归遍历的时候判断是否重复
class Solution {
public:vector<vector<int>>res;vector<int>mids;void backtrace(vector<int>&candidates,int startIndex,int sum,int target,vector<bool>&used){if(sum==target){res.push_back(mids);return;}//剪枝for(int i=startIndex;i<candidates.size() && sum+candidates[i]<=target;i++){if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==false)//树层去重continue;mids.push_back(candidates[i]);sum+=candidates[i];used[i]=true;backtrace(candidates,i+1,sum,target,used);used[i]=false;mids.pop_back();sum-=candidates[i];}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());vector<bool>used(candidates.size(),false);backtrace(candidates,0,0,target,used);return res;}
};

 131.分割回文串

思路:分割字符串,然后多了一个判断是否回文的操作
class Solution {
public:vector<vector<string>>res;vector<string>mids;bool judge(const string& s,int left,int right){while(left<right){if(s[left]!=s[right]) return false;left++;right--;}return true;}void backtrace(string&s,int startIndex){if(startIndex>=s.size()){res.push_back(mids);return;}for(int i=startIndex;i<s.size();i++){if(!judge(s,startIndex,i)) continue;//判断是否回文串string str=s.substr(startIndex,i-startIndex+1);mids.push_back(str);backtrace(s,i+1);mids.pop_back();}}vector<vector<string>> partition(string s) {backtrace(s,0);return res;}
};

78.子集

画图分析:

 思路:横向遍历,每次遍历的时候都进行一次添加,然后进行纵向递归,递归完之后进行回溯。
  • 注意:空集也是子集。(所有节点都需要添加)
class Solution {
public:vector<vector<int>>res;vector<int>mid;void backtrace(vector<int>&nums,int start){res.push_back(mid);if(start==nums.size()){//res.push_back(mid);return;}for(int i=start;i<nums.size();i++){mid.push_back(nums[i]);backtrace(nums,i+1);mid.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backtrace(nums,0);return res;}
};

90.子集||

分析:和上题一样,区别在于有重复数字
思路:组合问题有重复都考虑先排序再操作!
class Solution {
public:vector<vector<int>>res;vector<int>mid;void backtrace(vector<int>&nums,int start){if(find(res.begin(),res.end(),mid)==res.end())//去重res.push_back(mid);if(start==nums.size())return;for(int i=start;i<nums.size();i++){mid.push_back(nums[i]);backtrace(nums,i+1);mid.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());//需要排序backtrace(nums,0);return res;}
};

491.递增子序列

思路:重点在于set去重以及递增条件
class Solution {
public:vector<vector<int>>midRes,res;vector<int>mid;void backtrace(vector<int>&nums,int start){if(mid.size()>=2 ){//条件限制midRes.push_back(mid);}if(start==nums.size())//终止条件return;unordered_set<int> vistedSet;for(int i=start;i<nums.size();i++){if(vistedSet.find(nums[i])!=vistedSet.end())//去重continue;if(!mid.empty() && mid.back()>nums[i])//递增条件continue;//judge[nums[i]]=true;vistedSet.insert(nums[i]);//遍历标记mid.push_back(nums[i]);backtrace(nums,i+1);mid.pop_back();//回溯}}vector<vector<int>> findSubsequences(vector<int>& nums) {backtrace(nums,0);return midRes;}
};

46.全排列

思路:跟子集的代码几乎一样,主要区别在于
  • 每次遍历都从0开始,并且做树枝去重
class Solution {
public:vector<vector<int>>res;vector<int>mid;void backtrace(vector<int>&nums,int start){if(start==nums.size()){res.push_back(mid);}for(int i=0;i<nums.size();i++){if(find(mid.begin(),mid.end(),nums[i])!=mid.end())//树枝去重continue;mid.push_back(nums[i]);backtrace(nums,start+1);mid.pop_back();}}//树枝去重vector<vector<int>> permute(vector<int>& nums) {backtrace(nums,0);return res;}
};

47.全排列||

思路一:使用哈希表进行树枝下标去重(因为有重复元素)
问题:在数组去重时时间复杂度过高
class Solution {
public:vector<vector<int>>res;vector<int>mid;unordered_map<int,bool>map;void backtrace(vector<int>&nums,int start){if(start==nums.size()){if(find(res.begin(),res.end(),mid)==res.end())//数组去重res.push_back(mid);return;}for(int i=0;i<nums.size();i++){if(map[i])//树枝去重continue;mid.push_back(nums[i]);map[i]=true;backtrace(nums,start+1);mid.pop_back();map[i]=false;}}vector<vector<int>> permuteUnique(vector<int>& nums) {//sort(nums.begin(),nums.end());backtrace(nums,0);return res;}
};

323.重新安排行程 

思路:首先记录航班的映射关系,然后从起点开始根据映射关系一一添加(横向遍历,纵向递归)
注意:
  • 起点航班要先添加
  • 如果添加的路线等于航班数+1时,说明已经走完全部航班(如五个航班,必然是六个站点)
  • 递归深入的时候需要判断当前映射关系是否被添加过
class Solution {
public:unordered_map<string,map<string,int>>targets;vector<string>midres;bool backtrace(vector<vector<string>>& tickets){if(midres.size()==tickets.size()+1)//航班已经走完的终止条件return true;for(pair<const string,int>&target:targets[midres[midres.size()-1]]){//遍历映射关系if(target.second>0){//当映射关系还存在时midres.push_back(target.first);target.second--;if(backtrace(tickets)) return true;//已经找到一条路线midres.pop_back();target.second++;}}return false;}vector<string> findItinerary(vector<vector<string>>& tickets) {midres.push_back("JFK");//先添加起点航班for(auto it:tickets)targets[it[0]][it[1]]++;//记录映射关系backtrace(tickets);return midres;}
};

51.N皇后

思路:二维数组,行递归,列遍历
在列放置皇后的时候,要进行有效判断
  • 1.判断列方向上有没有放置过(行方向是递归遍历进行的,所以只可能放置一个)
  • 2.判断左上方有没有放置过
  • 3.判断右上方有没有放置过(左下方和右下方还没有遍历到,无需遍历)
class Solution {
public:vector<vector<string>>res;bool isvald(int row,int lie,vector<string>&mids,int n){//检查列for(int i=0;i<row;i++){if(mids[i][lie]=='Q')return false;}//检查左上方for(int i=row-1,j=lie-1;i>=0 && j>=0;i--,j--){if(mids[i][j]=='Q')return false;}//检查右上方for(int i=row-1,j=lie+1;i>=0 && j<n;i--,j++){if(mids[i][j]=='Q')return false;}return true;}void backtrace(vector<string>&mids,int n,int row){if(row==n){res.push_back(mids);return;}for(int i=0;i<n;i++){//列的遍历if(isvald(row,i,mids,n)){//判断该位置是否有效mids[row][i]='Q';backtrace(mids,n,row+1);//传入的是下一行不是下一列mids[row][i]='.';}}}vector<vector<string>> solveNQueens(int n) {vector<string>mids(n,string(n,'.'));//二维数组初始化backtrace(mids,n,0);return res;}
};

37.解数独

思路:二维遍历,递归判断
class Solution {
public:bool backtrace(vector<vector<char>>&board){for(int i=0;i<board.size();i++){//遍历行for(int j=0;j<board[0].size();j++){//遍历列if(board[i][j]=='.'){for(char k='1';k<='9';k++){if(isValid(i,j,k,board)){board[i][j]=k;if(backtrace(board)) return true;board[i][j]='.';}}return false;//9个数都遍历完都不对,说明这个位置无法插入}}}return true;//遍历完没有返回false,说明完全ok}bool isValid(int row,int col,char val,vector<vector<char>>&board){for(int i=0;i<9;i++){//判断行里是否重复if(board[row][i]==val) return false;}//判断列里是否重复for(int i=0;i<9;i++){if(board[i][col]==val) return false;}//判断九宫格里是否重复int startRow=(row/3)*3;//得到的是九宫格内的起始坐标int startCol=(col/3)*3;for(int i=startRow;i<startRow+3;i++){for(int j=startCol;j<startCol+3;j++){if(board[i][j]==val) return false;}}return true;}void solveSudoku(vector<vector<char>>& board) {backtrace(board);}
};

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

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

相关文章

基于python+pyqt的opencv汽车分割系统

目录 一、实现和完整UI视频效果展示 主界面&#xff1a; 识别结果界面&#xff1a; 查看分割处理过程图片界面&#xff1a; 二、原理介绍&#xff1a; 加权灰度化 ​编辑 二值化 滤波降噪处理 锐化处理 边缘特征提取 图像分割 完整演示视频&#xff1a; 完整代码链…

4.14 tcp_tw_reuse 为什么默认是关闭的?

开启 tcp_tw_reuse 参数可以快速复用处于 TIME_WAIT 状态的 TCP 连接时&#xff0c;相当于缩短了 TIME_WAIT 状态的持续时间。 tcp_tw_reuse 是什么&#xff1f; TIME_WAIT 状态的持续时间是 60 秒&#xff0c;这意味着这 60 秒内&#xff0c;客户端一直会占用着这个端口。端…

springboot定时任务:同时使用定时任务和websocket报错

背景 项目使用了websocket,实现了消息的实时推送。后来项目需要一个定时任务&#xff0c;使用org.springframework.scheduling.annotation的EnableScheduling注解来实现&#xff0c;启动项目之后报错 Bean com.alibaba.cloud.sentinel.custom.SentinelAutoConfiguration of t…

11.Oracle中rollup函数详解

【基本介绍】 【格式】&#xff1a;group by rollup(字段1,字段2,字段3,...,字段n) 【说明】&#xff1a;rollup主要用于分组汇总&#xff0c;如果rollup中有n个字段&#xff0c;则会分别按【字段1】、【字段1,字段2】&#xff0c;【字段1,字段2,字段3】&#xff0c;...&#…

uniapp,使用canvas制作一个签名版

先看效果图 我把这个做成了页面&#xff0c;没有做成组件&#xff0c;因为之前我是配合uview-plus的popup弹出层使用的&#xff0c;这种组件好像是没有生命周期的&#xff0c;第一次打开弹出层可以正常写字&#xff0c;但是关闭之后再打开就不会显示绘制的线条了&#xff0c;还…

【Linux应用部署篇】在CSDN云IDE平台部署Etherpad文档编辑器

【Linux应用部署篇】在CSDN云IDE平台部署Etherpad文档编辑器 一、CSDN云IDE平台介绍1.1 CSDN云IDE平台简介1.2 CSDN云IDE平台特点 二、本次实践介绍2.1 本次实践介绍2.2 Etherpad简介 三、登录CSDN云IDE平台3.1 登录CSDN开发云3.2 登录云IDE3.3 新建工作空间3.4 进入工作空间 四…

Spring(aop介绍,底层实现,jdk代理,cglib代理)

02-aop简介-aop的作用及其优势_哔哩哔哩_bilibili 122 1、Spring的aop介绍 1.1aop是一种技术&#xff0c;aop是在运行之间执行的&#xff0c;他可以完成程序功能之间的松耦合&#xff0c;动态代理的作用也等同于Aop的作用&#xff1a;他提供了相应的封装&#xff0c;Aop是面向…

unity 模型显示在UI上 并交互(点击、旋转、缩放)

项目工程&#xff1a;unity模型显示在UI上并交互&#xff08;点击、旋转、缩放&#xff09;资源-CSDN文库 1.在Assets创建 Render Texture&#xff08;下面会用到&#xff09;&#xff0c;根据需要设置Size 2.创建UIRawImage&#xff0c;并把Render Texture赋上 3.创建相机&am…

SSL/CA 证书及其相关证书文件(pem、crt、cer、key、csr)

数字证书是网络世界中的身份证&#xff0c;数字证书为实现双方安全通信提供了电子认证。数字证书中含有密钥对所有者的识别信息&#xff0c;通过验证识别信息的真伪实现对证书持有者身份的认证。数字证书可以在网络世界中为互不见面的用户建立安全可靠的信任关系&#xff0c;这…

vue实现表格的动态高度

需求:表格能够根据窗口的大小自动适配页面高度 防抖和节流函数的使用场景是当需要对频繁触发的事件进行限制时,例如: 防抖函数常用于限制用户在短时间内多次触发某一事件,例如搜索框输入并搜索,当用户一直在输入时,我们可以使用防抖函数来避免多次请求搜索结果,减轻服…

切换Debian的crontab的nano编辑器

Debian的crontab默认的编辑器是nano&#xff0c;用起来很不习惯,怎么才能转回vim呢? 用以下命令便可&#xff1a; #update-alternatives --config editor 出现以下所示的界面&#xff1a; 而后选择8使用/usr/bin/vim就能够了。 PS&#xff1a;若是你发现你的定时没有生效&…

【Python编程】将同一种图片分类到同一文件夹中

一、数据结构如下&#xff1a; 二、编程工具&#xff1a;Jupyter-Notebook 三、代码&#xff1a; import os import cv2 import shutilpath0os.getcwd()\\apple\\RGB path1os.getcwd()\\apple\\tof_confidence path2os.getcwd()\\apple\\tof_depth path3os.getcwd()\\apple\\…

【Adobe After Effects】关于ae点击空格不会播放反而回退一帧的解决方案

最近玩ae的时候遇见了一个小问题&#xff0c;就是有时候敲空格&#xff0c;视频没办法播放&#xff0c;反而会回退一帧&#xff0c;经过摸索发现了一个解决办法&#xff1a; 点击编辑---首选项 然后选择“音频硬件” 然后选择正确的默认输出&#xff0c;点击确定即可

Visual Studio 2022的MFC框架——WinMain函数

我是荔园微风&#xff0c;作为一名在IT界整整25年的老兵&#xff0c;今天我们来重新审视一下Visual Studio 2022下开发工具的MFC框架知识。 大家还记得创建Win32应用程序是怎么弄的吗&#xff1f; Win32应用程序的建立到运行是有一个个关系分明的步骤的&#xff1a; 1.进入W…

AURIX TriCore内核架构学习笔记

名词缩写 ISA - Instruction Set Architecture&#xff0c;指令集架构PC - Program Counter, holds the address of the instruction that is currently runningGPRs - 32 General Purpose RegistersPSW - Program Status WordPCXI - Previous Context InformationCSA - Conte…

腾讯云服务器价格表大全_轻量服务器_CVM云服务器报价明细

腾讯云服务器租用费用表&#xff1a;轻量应用服务器2核2G4M带宽112元一年&#xff0c;540元三年、2核4G5M带宽218元一年&#xff0c;2核4G5M带宽756元三年、云服务器CVM S5实例2核2G配置280.8元一年、GPU服务器GN10Xp实例145元7天&#xff0c;腾讯云服务器网长期更新腾讯云轻量…

Spring redis使用报错Read timed out排查解决

文章目录 使用场景报错信息解决方式 使用场景 我们使用redis作为缓存服务&#xff0c;缓存一些业务数据&#xff0c;如路口点位信息、渠化信息、设备信息等有一些需要实时计算的数据&#xff0c;缓存在redis里&#xff0c;如实时信号周期相位、周期内过车数量等有需要不同服务…

基于微信小程序的餐厅预订系统的设计与实现(论文+源码)_kaic

摘 要 随着消费升级&#xff0c;越来越多的年轻人已经开始不再看重餐饮等行业的服务&#xff0c;而是追求一种轻松自在的用餐、购物环境。因此&#xff0c;无人餐厅、无人便利店、无人超市等一些科技消费场所应势而生。餐饮企业用工荒已成为不争的事实。服务员行业的低保障、低…

linux安装部署gitlab全教程,包含配置中文

linux安装部署gitlab全教程&#xff0c;包含配置中文 大家好&#xff0c;我是酷酷的韩~ 1.前期准备 安装包下载地址 https://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el7/ 我这里选择的这个gitlab-ce-15.7.3-ce.0.el7.x86_64.rpm 还有一些相关依赖包(地址等审核过我放到…

Rust处理JSON

基本操作 Cargo.toml: [package]name "json"version "0.1.0"edition "2021"# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html[dependencies]serde { version "1", features …