首页 > 职场文档 > 工作总结

字符串组合函数模板

网络整理

【简介】感谢网友“网络整理”参与投稿,这里小编给大家分享一些,方便大家学习。

在日常学习、工作或生活中,大家总少不了接触作文或者范文吧,通过文章可以把我们那些零零散散的思想,聚集在一块。范文怎么写才能发挥它最大的作用呢?接下来小编就给大家介绍一下优秀的范文该怎么写,我们一起来看一看吧。

字符串组合函数篇一

题目:输入一个字符串,输出该字符串中字符的所有组合。举个例子,如果输入abc,它的组合有a、b、c、ab、ac、bc、abc。

上面我们详细讨论了如何用递归的思路求字符串的排列。同样,本题也可以用递归的思路来求字符串的组合。

假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符,我们有两种选择:第一是把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选取m-1个字符;第二是不把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码:

#include#include#includeusing namespace std;#includevoid combination(char *string ,int number,vector&result);void combination(char *string){ assert(string != null); vectorresult; int i , length = strlen(string); for(i = 1 ; i <= length ; ++i) combination(string , i ,result);}void combination(char *string ,int number , vector&result){ assert(string != null); if(number == 0) { static int num = 1; printf("第%d个组合t",num++); vector::iterator iter = (); for( ; iter != () ; ++iter) printf("%c",*iter); printf("n"); return ; } if(*string == ') return ; _back(*string); combination(string + 1 , number - 1 , result); _back(); combination(string + 1 , number , result);}int main(void){ char str[] = "abc"; combination(str); return 0;}

由于组合可以是1个字符的组合,2个字符的字符……一直到n个字符的组合,因此在函数void combination(char* string),我们需要一个for循环。另外,我们用一个vector来存放选择放进组合里的`字符。

用位运算来实现求组合

#includeusing namespace std;int a[] = {1,3,5,4,6};char str[] = "abcde";void print_subset(int n , int s){ printf("{"); for(int i = 0 ; i < n ; ++i) { if( s&(1<<i) )   // 判断s的二进制中哪些位为1,即代表取某一位 printf("%c ",str[i]); //或者a[i] } printf("}n");}void subset(int n){ for(int i= 0 ; i < (1<<n) ; ++i) { print_subset(n,i); }}int main(void){ subset(5); return 0;}

全组合

例如给定字符串“abc”,全组合意思从中去0个元素,1个元素,一直到n个元素,介绍二进制做法。以字符串“abc”为例:

000 <---> null

001 <---> c

010 <---> b

011 <---> bc

100 <---> a

101 <---> ac

110 <---> ab

111 <---> abc

思路出来了,代码也比较好写,分享一下我的代码:

/**  * write a method that returns all subsets of a set  */   #include#include#include/**  * 通过0到2^-1来标识子集  *  * t = (n * 2^n)  *  */  void getsubset(char *str, int len)  {   int i, max, index, j;    max = 1 << len;    for (i = 1; i < max; i ++) {    j = i;    index = 0;     while (j) {     if (j & 1) {      printf("%c", str[index]);     }     j >>= 1;     index ++;    }    printf("n");   }  }   int main(void)  {   char str[1000];    while (scanf("%s", str) != eof) {    getsubset(str, strlen(str));    }    return 0;  }

从n中选m个数

这里分为两种方法:递归和回溯

递归

递归思路如下,从n个数中取出m个数,可以分解为以下两步:

从n个数中选取编号最大的数,然后在剩下的n-1个数中选取m-1个数。直到从n-(m-1)中选取一个数为止 从n个数中选取次小的数,重复1的操作

代码如下:

/**  * 递归法解决组合问题  */  void combine(int *arr, int n, int m, int *tmp, const int m)  {   int i, j;    for (i = n; i >= m; i --) {    tmp[m] = i;    if (m == 0) { // 选出m个数     for (j = 0; j < m; j ++) {      printf("%d ", arr[tmp[j]]);     }     printf("n");    } else {     combine(arr, i - 1, m - 1, tmp, m);    }   }  }

dfs

其实考虑到用dfs,这道题目就简单很多,dfs的回溯条件就是临时数组的大小==k即可,同时附加一道leetcode上的题目,用dfs思路ac

题目

given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

for example,

if n = 4 and k = 2, a solution is:

ac代码

public class solution {   public static arraylist

combine(int n, int k) {    arraylist

rs = new arraylist

();    arraylistlist = new arraylist();       dfs(1, k, n, list, rs);       return rs;   }     public static void dfs(int pos, int k, int n, arraylistlist, arraylist

rs) {    if (() == k) {     (new arraylist(list));    }       for (int i = pos; i <= n; i ++) {     (i);     dfs(i + 1, k, n, list, rs);     (() - 1);    }   }  }

s("content_relate");

【关于字符串的组合算法问题的c语言实现攻略】相关文章:

1.

pid算法的c语言实现

2.

c语言中压缩字符串的算法

3.

c语言中实现kmp算法实例

4.

c语言字符串快速压缩算法代码

5.

希尔排序算法的c语言实现示例

6.

关于c语言约瑟夫问题输出序号算法

7.

c语言字符串操作函数和常用的实现

8.

c语言中返回字符串函数的实现方法

相关图文

推荐文章

网站地图:栏目 TAGS 范文 作文 文案 学科 百科