【算法day17-day18】回溯:解决组合问题

devtools/2024/12/23 19:37:22/

不好意思呀各位,最近在忙期末考今天才彻底结束,来让我们继续算法之路吧~

题目引用


  1. 组合
  2. 电话号码的字母组合
  3. 组合总和
  4. 组合总和II
  5. 分割回文串

1.组合


给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1:
输入:n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

我们来看这道回溯入门题,首先呢我要说一下我对回溯的想法,在我看来回溯其实就是在不断递归的过程中形成了一颗多叉树,那么它是个树,我们就可以对其的路径进行记录,剪枝,判断等等一系列操作,从而形成一系列的结果集合。
拿这道题目举例,我们创建一个全局的res用于记录结果,path用于记录多叉树的每一条路径,创建一个递归函数,先设定函数的出口:当我们记录的path.size()==k时,就说明已经得到一种结果了,将path加入到结果数组中。那么递归函数的主体就是把1到n的数都遍历一遍,在每条路径中加入当前数值,再递归下一个元素,返回后pop掉。这其实就是记录树的路径,在前些天讲二叉树时已经讲过了。
那么来看代码:

class Solution {
public:vector<int> path;vector<vector<int>> res;void backtracking(int n,int k,int startIndex){if(path.size()==k){res.push_back(path);return;} for(int i=startIndex;i<=n;i++){path.push_back(i);backtracking(n,k,i+1);path.pop_back();}return;}vector<vector<int>> combine(int n, int k) {backtracking(n,k,1);return res;}
};

怎么样,应该比前几天题目简单不少吧。

2.电话号码的字母组合


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

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

在这里插入图片描述

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

来看这道题目,我们乍一眼一看是不是头都大了,不知道怎么才能解决这种问题。不急~只要我们慢慢分析总能分析出个一二三四,首先是电话号码对应的字母,我们肯定需要一个表来进行映射,再就是如果我们使用回溯的思想,那么就要看一下是不是和上一道题相同,不同的话应该怎么修改。
可以确定的是,这题和上一道题是不太一样的。第一、递归出口不一样。第二、每一层所能选择的元素数目和和元素本身的大小是不确定的。但是好在都能够通过遍历一遍字符串,逐层处理,逐层确定。
那么来解决这道题吧。首先,我们不能使用startIndex来确定每一层的开始位置,而是使用Index来作为源字符串内数字的定位,然后通过数字在我们自己写好的表中找到对应的数字代表的字符串,然后这样每一层的元素才确定了下来,再去回溯就很简单的解决了。
来看代码:

class Solution {
public:string digitsmap[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string> res;string path;void backtracking(string digits,int Index){if(Index==digits.size()){res.push_back(path);return;}int digit=digits[Index]-'0';string letter=digitsmap[digit];for(int i=0;i<letter.size();i++){path+=letter[i];backtracking(digits,Index+1);path.pop_back();}return;}vector<string> letterCombinations(string digits) {if(digits=="") return res;backtracking(digits,0);return res;}
};

这样写,轻轻松松100%啦

3.组合总和


给你一个 无重复元素 的整数数组 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 。
仅有这两种组合。

做完上面那道题,做这道题就是小卡拉米了。需要注意的不过是从数组里面直接取出来和可重复,但是只要把握住这两个点,其实就不会很难。
来看代码:

class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& candidates,int targetSum,int sum,int startIndex){if(sum>targetSum) return;if(sum==targetSum){res.push_back(path);return;}for(int i=startIndex;i<candidates.size()&&sum<targetSum;i++){sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,targetSum,sum,i);sum-=candidates[i];path.pop_back();}return;}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0,0);return res;}
};

是不是简简单单呀~

4.组合总和II


给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意:解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

我们可以看一下这道题和上一道题目的区别,不可重复且只能使用一次。条件是比较苛刻的,所以我们就自己加一点工具来限制住这个多叉树的发展,其实就有一点点像剪枝了。这里我们加上一个used数组来判断这个数是否被用过,再在递归时将startIndex+1就可以了。
这里来看代码:

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {// used[i - 1] == true,说明同一树枝candidates[i - 1]使用过// used[i - 1] == false,说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {continue;}sum += candidates[i];path.push_back(candidates[i]);used[i] = true;backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1,这里是i+1,每个数字在每个组合中只能使用一次used[i] = false;sum -= candidates[i];path.pop_back();}}public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(), false);path.clear();result.clear();// 首先把给candidates排序,让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};

这里大家是不是对树枝和树层比较困惑呢,因为同一树层使用过说明我之前已经在这个位置取过这个数了,那么我现在再取肯定时重复的,同一树枝取过说明我们这一条路径上有一样的元素,但是并不是重复取的,所以是可以入到path里面的。这样说会不会好一点。

5.分割回文串


给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是
回文串
。返回 s 所有可能的分割方案。

示例 1:
输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]

这道题目就比较难想到了。我们利用startIndex来分割题目给的字符串,分割完以后判断这个字符串是不是回文,是就赋值给path,不是就直接开始下一个循环。判断是不是回文串的方法有很多,我们这里采用我们三周之前学过的二分法来做判断(是不是不记得了)。那么这道题目就做完了。其实这些题目看到答案后都不会觉得很难,但难的是想出答案的过程,而这也是区分大家的过程。
来看代码

class Solution {
public:vector<vector<string>> res;vector<string> path;void backtracking(const string& s,int startIndex){if(startIndex>=s.size()) {res.push_back(path);return;}for(int i=startIndex;i<s.size();i++){if(ispl(s,startIndex,i)){string str=s.substr(startIndex,i-startIndex+1);path.push_back(str);}else{continue;}backtracking(s,i+1);path.pop_back();}}bool ispl(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;}vector<vector<string>> partition(string s) {backtracking(s, 0);return res;}
};

总结


其实这些题目看到答案后都不会觉得很难,但难的是想出答案的过程,而这也是区分大家的过程。


http://www.ppmy.cn/devtools/144775.html

相关文章

m4s转mp3——B站缓存视频提取音频

前言 しかのこのこのここしたんたん&#xff08;鹿乃子乃子虎视眈眈&#xff09;非常之好&#xff0c;很适合当闹钟&#xff0c;于是缓存了视频&#xff0c;想提取音频为mp3 直接改后缀可乎&#xff1f;格式转换工具&#xff1f; 好久之前有记录过转MP4的&#xff1a; m4s转为…

结合大语言模型的异常检测方法研究

论文链接 Research on Anomaly Detection Methodology Combining Large Language Models 论文主要内容 研究背景与目的&#xff1a; 随着大数据和人工智能技术的发展&#xff0c;异常检测在数据分析中变得越来越重要。 本研究提出了一种名为SemantEdge Detection (SED)的新…

《XML》教案 第1章 学习XML基础

《XML》教案 第1章 学习XML基础 主讲人&#xff1a; 回顾上一章: [10分钟] 2 课程知识点讲解&#xff1a; 2 while 循环和do…while 循环的区别&#xff1a;[15分钟] 3 for 循环的使用 &#xff1a;[5分钟] 4 嵌套 for 循环 &#xff1a;[20分钟] 5 本章总结 [10分钟] 6 考核点…

clickhouse-副本和分片

1、副本 1.1、概述 集群是副本和分片的基础&#xff0c;它将ClickHouse的服务拓扑由单节点延伸到多个节点&#xff0c;但它并不像Hadoop生态的某些系统那样&#xff0c;要求所有节点组成一个单一的大集群。ClickHouse的集群配置非常灵活&#xff0c;用户既可以将所有节点组成…

【项目介绍】基于机器学习的低空小、微无人机识别技术

文章目录 1.项目介绍2.数据预处理3.特征选取4.模型训练参考文献 1.项目介绍 对于现代雷达探测系统而言&#xff0c;无人机和飞鸟同属于低空小、微特征的一类典型目标&#xff0c;而面对比较复杂的环境&#xff0c;如何有效区分两者类型并完成识别是当下急迫且重要的难题。常规…

Linux系统安装node.js

一、node官网下载想要的node版本 https://nodejs.org/en/download/package-manager 二、将tar.xz文件解压 tar -xvf node-vxxx.tar.xz 三、改文件夹的名字&#xff0c;改成nodejs mv node-xxx nodejs 四、复制nodejs文件&#xff0c;并上传到linux 服务器 /usr/local 目录下…

YOLOv9-0.1部分代码阅读笔记-autoanchor.py

autoanchor.py utils\autoanchor.py 目录 autoanchor.py 1.所需的库和模块 2.def check_anchor_order(m): 3.def check_anchors(dataset, model, thr4.0, imgsz640): 4.def kmean_anchors(dataset./data/coco128.yaml, n9, img_size640, thr4.0, gen1000, verboseTrue…

Windows平台C++部署 vcpkg 安装protobuf + gRPC实现图像传输

vcpkg 安装 https://github.com/microsoft/vcpkg.git.\bootstrap-vcpkg.bat vcpkg --version参考&#xff1a;Windows安装vcpkg教程&#xff08;VS2022&#xff09; protocbuf 安装与编译 vcpkg install grpc:x64-windowsprotocbuf 安装与编译 vcpkg install protobuf proto…