没有合适的资源?快使用搜索试试~ 我知道了~
内容概要:本系列专栏汇总了 C++ 笔试题目和一系列基础算法及其可运行的实例代码。包括数组全排列的两种主要方法:逐个追加组合法与递归法;并讲解字符串相关操作以及各种特定整型数组问题,例如求下一个非重复数等,并针对某些特定问题提供了不同场景下的性能优化方式。 适合人群:具有C++基础并对数据结构和算法有一定了解的学习者。 使用场景及目标:帮助读者提高解决实际编码挑战的能力,熟悉C++中的字符串处理和数值型数据处理的方法和技术。 其他说明:提供详细注释以便读者深入理解和复现代码。专栏持续更新和完善算法示例,供学习与参考使用。
资源推荐
资源详情
资源评论
《C++基础算法荟萃》系列分享专栏
简介
汇集C++笔试和基础算法,给出可以执行的示例代码和测试结果。有问题请务必反馈给我。
文章
数组全排列算法(一)字符串数组全排列——逐个追加组合算法
数组全排列算法(二)整型数组全排列——递归算法
字符串处理算法(一)检测输入字符串中是否包含连续的或者离散的test
字符串处理算法(二)逐个打印中文字符串
整型数组处理算法(一)按照正态分布来排列整型数组元素
整型数组处理算法(二)文件中有一组整数,要求排序后输出到另一个文件中
字符串处理算法(三)按指定位置交换字符串两部分的位置
整型数组处理算法(三)把一个数组里的所有元素,插入到另一个数组的指定位置
整型数组处理算法(四)求数组的最大值和最小值
整型数组处理算法(五)求两个有序数组的共同元素
整型数组处理算法(六)合并两个数组
整型数组处理算法(七)重排问题
基础算法荟萃目录
整型数组处理算法(八)插入(+、-、空格)完成的等式:1 2 3 4 5 6 7 8 9=N[华为面试题]
字符串处理算法(四)现在一个给定字符串中寻找子串的功能(不能使用库函数)[2014百度笔试题]
整型数组处理算法(九)给定任意一个正整数,求比这个数大且最小的“不重复数”[2014百度笔试题]
整型数组处理算法(九)给定任意一个正整数,求比这个数大且最小的“不重复数”(性能优化)[2014百度笔试题]
整型数组处理算法(十)给定数组a[n],其中有超过一半的数为一个定值,找出这个数。[2014人人网笔试题]
整型数组处理算法(十三)请实现一个函数:凑14。[风林火山]
整型数组处理算法(十一)请实现一个函数:线段重叠。[风林火山]
整型数组处理算法(十二)请实现一个函数:最长顺子。[风林火山]
字符串处理算法(五)多线程实现代码行数统计。[风林火山]
整型数组处理算法(十一)请实现一个函数:线段重叠(性能优化)。[风林火山]
字符串处理算法(六)求2个字符串最长公共部分
数组全排列算法(一)字符串数组全排列——逐个追加组合算法
算法题:用你熟悉的编程语言,设计如下功能的函数:
输入一个字符串,输出该字符串中所有字母的全排列。程序请适当添加注释。
C++函数原型: void Print(const char *str)
输入样例: abc
分析:
n个字符串的全排列就是n!,而由于2^32=4294967296,12!=479001600,11!=39916800,
本文讨论的算法在限制n<12,关于n>=12的后续讨论。
另外这里输入的字符也是不重复的,重复的相对复杂,后续可以讨论。
思想是这样的:比如输入字符串是abc,定义vectorA、vectorB。
先取a放到vectorA中,
然后取b,与进行组合,则有ba,ab,放到vectorB中,同时清空vectorA。
再取c,与vectorB里的ba,ab分别组合。依次得到cba,bca,bac和cab,acb,abc,放到vectorA中。
最后遍历不为空的vector,打印出组合结果。
这个算法就是逐个追加组合算法。
代码实现如下:
#define MAXNUM 12
//定义2个放结果的vector,交替使用。
std::vector<char*> g_vecA;
std::vector<char*> g_vecB;
void Print(const char *str)
{
char Temp;
int nLen = strlen(str);
char Temp0[2];
Temp0[0]=str[0];
Temp0[1]='\0';
g_vecA.push_back(Temp0);//先把第一个字母放到容器里
vector<char*>::iterator itor;
for (int i=1; i<nLen; i++)
{
Temp = str[i];
if (g_vecA.size()==0)
{
//遍历B中的元素
for(itor=g_vecB.begin();itor!=g_vecB.end();itor++)
{
char* p = *itor;
int nSize = strlen(p);
//从0到nSize位置放Temp
for (int j=0; j<nSize+1; j++)
{
char* q = new char[nSize+2];//如果放在循环外面则最后都是一个值
for (int k=0; k<j; k++)
{
q[k]=p[k];
}
q[j]=Temp;
for (int m=j+1; m<nSize+1; m++)
{
q[m]=p[m-1];
}
q[nSize+1]='\0';
g_vecA.push_back(q);
}
}
for (itor = g_vecB.end()-1; itor>=g_vecB.begin(); itor--)
{
char* p = *itor;
g_vecB.erase(itor);
}
}
g_vecB.clear();
}
else
{
//遍历A中的元素
for(itor=g_vecA.begin();itor!=g_vecA.end();itor++)
{
char* p = *itor;
int nSize = strlen(p);
//从0到nSize位置放Temp
for (int j=0; j<nSize+1; j++)
{
char* q = new char[nSize+2];
for (int k=0; k<j; k++)
{
q[k]=p[k];
}
q[j]=Temp;
for (int m=j+1; m<nSize+1; m++)
{
q[m]=p[m-1];
}
q[nSize+1]='\0';
g_vecB.push_back(q);
}
}
for (itor = g_vecA.end()-1; itor>=g_vecA.begin(); itor--)
{
char* p = *itor;
g_vecA.erase(itor);
}
g_vecA.clear();
}
}
int nCount = 0;
//打印所有组合
if (g_vecA.size()==0)
{
for(itor=g_vecB.begin();itor!=g_vecB.end();itor++)
{
nCount ++;
char* p = *itor;
cout << p << ", ";
if (nCount%10 == 0)
{
cout << endl;
}
delete p;
p=NULL;
}
}
else
{
for(itor=g_vecA.begin();itor!=g_vecA.end();itor++)
{
nCount ++;
char* p = *itor;
cout << p << ", ";
if (nCount%10 == 0)
{
cout << endl;
}
delete p;
p=NULL;
}
}
g_vecA.clear();
g_vecB.clear();
cout << endl;
}
int main()
{
g_vecA.clear();
g_vecB.clear();
char str[MAXNUM];
char Temp[256];
scanf("%s", Temp);
if (strlen(Temp)>=12)
{
cout<<"字符串长度是1-11。" <<endl;
return 0;
}
else
{
strcpy(str, Temp);
}
Print(str);
return 0;
}
测试结果:
当输入abc时:
cba, bca, bac, cab, acb, abc,
当输入abcd时:
dcba, cdba, cbda, cbad, dbca, bdca, bcda, bcad, dbac, bdac,
badc, bacd, dcab, cdab, cadb, cabd, dacb, adcb, acdb, acbd,
dabc, adbc, abdc, abcd,
转载请注明原创链接:http://write.blog.csdn.net/postedit/11894273
数组全排列算法(二)整型数组全排列——递归算法
算法题:实现一个整型数组的全排列,
void perm(int list[], int k, int m)
参数说明:list,数组;k开始位置,m个数。
用递归算法实现代码如下:
void perm(int list[], int k, int m)
{
if ( k==m )
{
copy(list,list+m,ostream_iterator<int>(cout," "));
cout<<endl;
return;
}
for (int i=k; i<m; i++) // 注意这里不是for (int i=k; i<=m; i++),否则会出现乱数据。
{
swap(list[k],list[i]);
perm(list,k+1,m);
swap(list[k],list[i]);
}
}
int main()
{
int List[] = {1,2,3} ;
perm(List, 0, sizeof(List)/sizeof(int));
return 0;
}
测试结果:
当list是 {1,2,3,4} 时,
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
1 4 2 3
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
3 1 2 4
3 1 4 2
剩余58页未读,继续阅读
资源评论
天涯学馆
- 粉丝: 1815
- 资源: 167
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- Java毕业生跟踪管理系统开题报告
- 基于Java、JavaScript、Vue、HTML全栈技术的选课指南设计源码
- 基于Vue框架的微信评优购功能设计源码
- 基于Java和Shell开发的会员积分商城设计源码
- 基于Java+Vue二手教材交易平台系统
- T型三电平逆变器 SVPWM 大扇区判断,小扇区判断,羊角波调制,电压电流双闭环 仿真概览,图1 电压电流双闭环,图2 调制
- 基于Java语言的if-cms内容管理系统设计源码
- 基于Java语言的zzyl001州养老名称更改设计源码
- 基于Python与Shell的code learning跨语言设计源码
- 基于Vue和JavaScript的智慧车辆前端设计源码
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功