本文主要是介绍C++回溯算法之一,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
/*
给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例:
输入:"abbaca"
输出:"ca"
解释:例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
*/
#include <iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
string str = "abbaca";
string result;
for (char s : str)
{
if (result.empty()||result.back()!=s)
{
result.push_back(s);
}
else
{
result.pop_back();
}
}
cout << result;
}
/*
给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
*/
#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
//#include<map>
//#include<set>
//#include<unordered_set>
#include<stack>
using namespace std;
class Solution {
private:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件结果
void backtracking(int n, int k, int startIndex=1)
{
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);
return result;
}
};
/*
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
所有数字都是正整数。
解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
*/
#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
class Solution {
private:
vector<vector<int>> result; // 存放结果集
vector<int> path; // 符合条件的结果
int comback = 0;
int into = 0;
// targetSum:目标和,也就是题目中的n。
// k:题目中要求k个数的集合。
// sum:已经收集的元素的总和,也就是path里元素的总和。
// startIndex:下一层for循环搜索的起始位置。
void backtracking(int targetSum, int k, int sum, int startIndex=1) {
if (path.size() == k) // 如果path.size() == k 但sum != targetSum 直接返回
{
if (sum == targetSum)
{
result.push_back(path);
}
return; //递归中的retuen相当于for循环中的break,直接中断此次递归
}
for (int i = startIndex; i <= 9; i++) //递归的次数是由for'循环来控制,
{ //结束递归有2种方式,1-不符合条件reruen。 2-for到达循环终止条件自动结束递归
//三重递归加自身for循环,形成四重循环。 最后一重递归由return终止,前面三层
//均有for循环参数来控制范围
sum += i; // 处理
path.push_back(i); // 处理
into++;
cout << "调用递归==" << into << endl;
backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
comback++;
cout << "回溯==" << comback << endl;
sum -= i; // 回溯
path.pop_back(); // 回溯
}
}
public:
vector<vector<int>> combinationSum3(int targetSum, int k) {
backtracking(targetSum, k, 0);
return result;
}
};
int main()
{
Solution Test;
auto num=Test.combinationSum3(9,3);
for (auto s : num) {
for (auto c : s) { cout << c ; }
cout << endl;
};
}
*
题目链接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
*/
#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
//#include<map>
//#include<set>
//#include<unordered_set>
#include<stack>
using namespace std;
// 版本一
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 str;
void backtrack(string &digits,int index=0)
{
if (index==digits.size()) //使用index来控制存储的时机
{
result.push_back(str);
return;
}
int num=digits[index] - '0';
string letter = letterMap[num];
for (size_t i = 0; i < letter.size(); i++)
{
str.push_back(letter[i]);
backtrack(digits,index+1); //递归,递归也可以理解为一层for循环,本质上差不多,写法上有些不同
str.pop_back(); //回溯
}
}
vector<string> combination(string digits)
{
backtrack(digits); //index默认为0,所以可以不传入
return result;
}
};
int main()
{
Solution Test;
auto num= Test.combination("23");
for (auto s : num) {
// for (auto c : s)
{ cout << s ; }
cout << endl;
};
}
/*
题目链接:https://leetcode-cn.com/problems/palindrome-partitioning/
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
*/
#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
class Solution
{
public:
vector<vector <string>> result;
vector<string> str;
void backtracking(const string &s,int index=0)
{
if (index>=s.size()) //控制递归的深度,始终不超过字符串大小
{
result.push_back(str);
return;
}
for (int i = index; i < s.size(); i++)
{
if (palindrome(s, index, i))
{
str.push_back(s.substr(index,i-index+1)); //找到会问字符
}
else
{
continue;
}
backtracking(s, index + 1); //递归调用,下一层递归从+1位置开始查找会问
str.pop_back(); //回溯
}
}
bool palindrome(const string sl,int start,int end)//判断是否回文
{
for (int i = start,j=end; i < j; i++,j--)
{
if (sl[i] != sl[j])
{
return false;
}
}
return true;
}
vector<vector<string>> partition(string s)
{
backtracking(s);
return result;
}
};
int main()
{
Solution Test;
auto num = Test.partition("aab");
for (auto s : num) {
for (auto c : s) { cout << c <<ends; }
cout << endl;
};
}
这篇关于C++回溯算法之一的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!