剑指offer27:按字典序打印出该字符串中字符的所…
2019-08-27 07:06:58来源:博客园 阅读 ()
剑指offer27:按字典序打印出该字符串中字符的所有排列
1 题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。2 思路和方法
固定第一个字符,递归取得首位后面的各种字符串组合;再将第一个字符与后面每一个字符交换,同样递归获得其字符串组合;每次递归都是到最后一位时结束,递归的循环过程,就是从每个子串的第二个字符开始依次与第一个字符交换,然后继续处理子串。
3 C++核心代码
去重1
1 class Solution { 2 public: 3 vector<string> result; 4 vector<string> Permutation(string str) { 5 if(str.length()==0) 6 return result; 7 permutation1(str,0); 8 sort(result.begin(), result.end()); 9 return result; 10 } 11 void permutation1(string str, int begin){ 12 if(begin==str.length()) 13 { 14 result.push_back(str); 15 return; 16 } 17 for(int i = begin; str[i]!='\0'; i++) //每个元素与第一个元素交换 18 { 19 if(i!=begin && str[begin]==str[i]) //去重 20 continue; 21 swap(str[begin], str[i]); 22 permutation1(str, begin+1); //交换后,得到子序列,用函数perm得到子序列的全排列 23 swap(str[begin], str[i]); //最后,将元素交换回来,复原,然后交换另一个元素 24 } 25 } 26 };View Code
去重2 https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7
1 void PermutationHelp(vector<string> &ans, int k, string str) //遍历第k位的所有可能 2 { 3 if (k == str.size() - 1) 4 ans.push_back(str); 5 unordered_set<char> us; 6 //sort(str.begin() + k, str.end());//这个我不太懂,我把sort放到最后输出结果 7 for (int i = k; i < str.size(); i++) 8 { 9 if (us.find(str[i]) == us.end()) //只和没交换过的换 10 { 11 us.insert(str[i]); 12 swap(str[i], str[k]); 13 PermutationHelp(ans, k + 1, str); 14 swap(str[i], str[k]); 15 } 16 } 17 } 18 19 vector<string> Permutation(string str) { 20 vector<string> ans; 21 PermutationHelp(ans, 0, str); 22 sort(ans.begin(), ans.end()); 23 return ans; 24 }View Code
4 C++完整代码
1 #include <stdio.h> 2 #include <vector> 3 #include <iostream> 4 #include <string> 5 6 using namespace std; 7 8 void swap(char &a, char &b) { 9 char temp = a; 10 a = b; 11 b = temp; 12 } 13 void permcore(string list, int low, int high, vector<string>& res) { 14 if (low == high && 15 find(res.begin(), res.end(), list) == res.end()) { //去重 16 res.push_back(list); 17 } 18 else { 19 for (int i = low; i <= high; i++) {//每个元素与第一个元素交换 20 if (i == low || list[i] != list[low]) { //去重 21 swap(list[i], list[low]); 22 permcore(list, low + 1, high, res); //交换后,得到子序列,用函数perm得到子序列的全排列 23 swap(list[i], list[low]);//最后,将元素交换回来,复原,然后交换另一个元素 24 } 25 } 26 } 27 } 28 29 vector<string> perm(string str) 30 { 31 vector<string> res; 32 if (!str.empty()) 33 permcore(str, 0, str.size() - 1, res); 34 return res; 35 } 36 37 int main() 38 { 39 vector<string> res; 40 string stdstr = "abb"; 41 res = perm(stdstr); 42 for (auto s : res) 43 cout << s << endl; 44 cout << endl; 45 46 string stdstr2 = "aab"; 47 res = perm(stdstr2); 48 for (auto s : res) 49 cout << s << endl; 50 cout << endl; 51 52 system("pause"); 53 return 0; 54 }View Code
参考资料
https://blog.csdn.net/JarvisKao/article/details/76999473
原文链接:https://www.cnblogs.com/wxwhnu/p/11414103.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 剑指offer笔记面试题1----赋值运算符函数 2019-10-18
- 剑指offer65:矩阵中的路径(二维数组,二分查找) 2019-09-02
- 剑指offer62:二叉搜索树的第k个结点,二叉搜索树【左边的元 2019-08-31
- 剑指offer59:按之字形顺序打印二叉树:[[1], [3,2], [4,5,6 2019-08-31
- 剑指offer64:滑动窗口的最大值 2019-08-31
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash