字符串逆序
// 字符串逆序
void Reverse(char*a, int n){ int left =0; int right = n -1;while (left < right)
{ char temp = a[left] ; a[left++] = a[right] ; a[right--] = temp ; }}
思路:首先考虑到用回溯法来求解这道题。每次都遍历一遍字符,选择一个填入字符串,并递归的填充下一个位置。但是字符可能重复,所以需要用一个哈希表来存储字符<char, number>key为字符,value为字符个数。
代码实现如下(只是实现,具体可以再优化):
#include <string>#include <vector>#include <map>using namespace std;void fill(string &s, map<char, int> &c2n, vector<string> &permutations, int len);void getPermutations(string s, vector<string> &permutations);void getPermutations(string s, vector<string> &permutations){ map<char, int> c2n;for(int i = 0; i < s.length(); i++){ if(c2n.find(s[i]) != c2n.end()) c2n[s[i]]++;else c2n[s[i]] = 1;}string ss;fill(ss, c2n, permutations, s.length());}void fill(string &s, map<char, int> &c2n, vector<string> &permutations, int len){ if(s.length() == len) //填充完毕{ permutations.push_back(s);return;}//遍历哈希表for(map<char, int>::iterator it = c2n.begin(); it != c2n.end(); it++){ if(it->second > 0) //个数大于0{ s.push_back(it->first); //填充字符串 it->second--; //个数减1fill(s, c2n, permutations, len); //继续填充 s.erase(s.length() - 1); //删除该字符 it->second++; //个数加1//回溯}}}