一 给定一个字符串求该字符串的第k个子串。
1 一个长度为len的字符串,它的总的子串的个数为1+2+3...+len = len*(len+1)/2;
2 利用优先队列的方法:最开始先用char数组存入1个字符,因为刚开始肯定是1个字符,然后出队再将出队的那个字符串最后一个字符的下一个字符合并后再压入队列中,出队k-1次后第k次出队的就是第k大的。
比如abc,先进a,b,c,然后a先出,接着ab进,就这样反复模拟...
3 优先队列应该重载“<”,那么这样就可以使得队列里面是按照字典序排好。
代码:
例如输出字符串str,求字符串的第k个子串。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 100010
int t , k;
char str[MAXN];
struct Node{
char s[MAXN];
int pos;
int index;
friend bool operator<(Node a , Node b){
if(strcmp(a.s , b.s) > 0)
return true;
return false;
}
};
priority_queue<Node>q;
int main(){
scanf("%d" , &t);
while(t--){
scanf("%s%d" , str , &k);
int len = strlen(str);
if(k*2 > len*(len+1)){
printf("No such line.\n\n");
continue;
}
while(!q.empty())
q.pop();
for(int i = 0 ; i < len ; i++){
Node node;
node.pos = 0;
node.index = i;
memset(node.s , '\0' , sizeof(node.s));
node.s[node.pos++] = str[i];
q.push(node);
}
for(int i = 0 ; i < k-1 ; i++){
Node tmp = q.top();
q.pop();
if(tmp.index != len-1){
tmp.s[tmp.pos++] = str[++tmp.index];
q.push(tmp);
}
}
printf("%s\n\n" , q.top().s);
}
return 0;
}
二 给定字符串求以该字符串为第一个排列,求第k个全排列的字符串
利用STL的next_perputation()函数,假设经过k次的循环后没有那么说明不存在输出-1,否则输出这第k个全排列字符串
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 20
int main(){
char str[N];
int k;
scanf("%s" , str);
scanf("%d" , &k);
int len = strlen(str);
int cnt = 1;
sort(str , str+len);
while(next_permutation(str , str+len)){
if(cnt == k){
printf("%s\n" , str);
break;
}
cnt++;
}
if(cnt != k)
printf("-1\n");
return 0;
}
三 给定n个数求这n个数的第k个全排列
首先先对n个数进行排序,然后利用next_perputation()函数即可。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 20
int main(){
int num[N];
int n , k;
scanf("%d%d" , &n , &k);
for(int i = 0 ; i < n ; i++)
scanf("%d" , &num[i]);
sort(num , num+n);
int cnt = 1;
while(next_permutation(num , num+n)){
if(cnt == k){
printf("%d" , num[0]);
for(int i = 1 ; i < n ; i++)
printf(" %d" , num[i]);
break;
}
cnt++;
}
if(cnt != k)/*没有输出-1*/
printf("-1\n");
return 0;
}
分享到:
相关推荐
全排列代码,C语言代码,用来解决全排列问题,csc 认证
分治法解决全排列问题 计算算法分析算法设计
用回溯法解决全排列问题:计算从1到N的N个整数所能构成的所有排列,并按照字典顺序依次输出。
全排列在笔试面试中很热门,因为它难度适中,既可以考察递归实现,又能进一步考察非递归的实现,便于区分出考生的水平。所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了,因此本文对全排列作下...
这是我在学习计算智能这门课时所完成的试验报告,使用局部搜索解决了全排列问题并作出了深入的分析。程序均通过编译并可以得到结果。
设计和实现带有重复元素的全排列问题,并输出所有的排列情况。
java算法分析与设计之全排列问题源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,尤其...
这是一个Java编写的数组的全排列程序 如一个数组 a,b,c,d 它的全排列为: a b c d a b d c a c b d a c d b a d b c a d c b b a c d b a d c b c a d b c d a b d a c b d c a ……
设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。
全排列算法(详细介绍图解) 1.全排列的定义 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。 2.解决全排列的方法 如求...
123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来...
★问题描述: 如果一个长度为 n 序列包含 1 到n的每一个数字,那么我们说这个序列是一个长度为 n 的全排列。现给定一个长度为 n-1 由U 和D 构成的字符串,要求你构造一个字典序最小的全 排列 a,使其满足: 1.若第...
洛谷真题源代码【附注释】
本文实例讲述了Python基于回溯法子集树模板解决全排列问题。分享给大家供大家参考,具体如下: 问题 实现 ‘a’, ‘b’, ‘c’, ‘d’ 四个元素的全排列。 分析 这个问题可以直接套用排列树模板。 不过本文使用子集...
求一组数据的全排列的C++算法,使用递归的方式来求一组数据的全排列
输出自然数1到n的所有不重复的排列,即n的全排列。
主要介绍了Java基于递归解决全排列问题算法,结合实例形式分析了Java使用递归算法解决全排列问题的原理与具体实现技巧,需要的朋友可以参考下
实现了全排列算法,每个元素用char类型表示,用递归算法,比较简洁实用。