leetcode 面试题08.08 有重复字符串的排列组合 C/C++ 排序 + 深度优先搜索(分支限界)
2022/9/4 14:23:04
本文主要是介绍leetcode 面试题08.08 有重复字符串的排列组合 C/C++ 排序 + 深度优先搜索(分支限界),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Solution {
public:
vector<string> permutation(string S) {
sort(S.begin(),S.end());
vector<string> retVec;
vector<int> used_posVec(S.size());
string cur_S;
recursive(retVec,S,cur_S,1,used_posVec);
return retVec;
}
/** 采用深度优先搜索 + 分支限界的方式****/
void recursive(vector<string> &retVec, string &sort_S,string &cur_S,int cur_index,vector<int> &used_posVec){
if(cur_index == sort_S.size()) //递归叶子节点,递归终止
{
//查看当前还有哪个字符没有被使用
for(int i = 0;i < used_posVec.size();i++)
if(!used_posVec[i]) {
cur_S.push_back(sort_S.at(i));
retVec.push_back(cur_S); //诞生一种新的情况
cur_S.pop_back();
}
}else{
char last_try_char = 0; // 上一个被当前位置使用的字符是什么
for(int i = 0;i < used_posVec.size();i++){
cur_S.push_back(sort_S.at(i));
if(!used_posVec[i] && last_try_char != sort_S.at(i)) // 该字符在这个位置没有被使用,并且不等于上一个在该位置尝试过的字符
{
used_posVec[i] = 1;
recursive(retVec,sort_S,cur_S,cur_index+1,used_posVec);
used_posVec[i] = 0;
last_try_char = sort_S.at(i);
}
cur_S.pop_back();
}
}
}
};
int main(){
Solution s;
vector<string> retVec = s.permutation("abccc");
for(auto it = retVec.begin();it!=retVec.end();it++){
cout<<*it<<endl;
}
return 1;
}
这篇关于leetcode 面试题08.08 有重复字符串的排列组合 C/C++ 排序 + 深度优先搜索(分支限界)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!