博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
字符串
阅读量:5282 次
发布时间:2019-06-14

本文共 1249 字,大约阅读时间需要 4 分钟。

字符串逆序                                                                                 

// 字符串逆序

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--; //个数减1
fill(s, c2n, permutations, len); //继续填充
            s.erase(s.length() - 1); //删除该字符
            it->second++; //个数加1
//回溯
}
}
}

转载于:https://www.cnblogs.com/beipiaoboy/p/3254290.html

你可能感兴趣的文章
[Kaggle] Sentiment Analysis on Movie Reviews
查看>>
价值观
查看>>
mongodb命令----批量更改文档字段名
查看>>
国外常见互联网盈利创新模式
查看>>
android:scaleType属性
查看>>
shell脚本
查看>>
Upload Image to .NET Core 2.1 API
查看>>
【雷电】源代码分析(二)-- 进入游戏攻击
查看>>
Linux中防火墙centos
查看>>
[JS]递归对象或数组
查看>>
linux sed命令
查看>>
程序存储问题
查看>>
优雅地书写回调——Promise
查看>>
PHP的配置
查看>>
Struts框架----进度1
查看>>
Round B APAC Test 2017
查看>>
MySQL 字符编码问题详细解释
查看>>
css & input type & search icon
查看>>
C# 强制关闭当前程序进程(完全Kill掉不留痕迹)
查看>>
语音识别中的MFCC的提取原理和MATLAB实现
查看>>