来自：
http://www.cnblogs.com/hlxs/archive/2011/08/24/2151828.html
1. 数组相关
在排序找出数组中的两个数，他们之和为n
2. 数组中连续的数字之和为n的所有对数
3. 输出所以字符串的排列与组合
4. 序列化分问题
1. 数组相关
在排序找出数组中的两个数，他们之和为n，当然如果数组不是有序的，先排序在找时间复杂度O（nlogn + n），更简单的当然还是hash或者如果元素不重复的话位图，bloom filter更好
#include <iostream>
using namespace std;
//在排序找出数组中的两个数，他们之和为n
//两个指针，一个指向开始，一个指向结尾，比较他们指向的数的和与n的大小
//比n小，则begin ++，比n大，则end --，直到begin !< end
void findTow(int *a,int size,int n)
{
if(n < 1 || size < 1)
return ;
int begin = 0,end = size -1;
while(begin < end)
{
if(a[begin] + a[end] < n)
{
++begin;
}
else if(a[begin] + a[end] > n)
{
--end;
}
else
{
cout << a[begin] << " " << a[end] << endl;
break;
}
}
}
int main()
{
int a[10] = {1,2,3,4,6,7,8,9,10,13};
findTow(a,10,20);
return 0;
}
2. 数组中连续的数字之和为n的所有对数
#include <iostream>
using namespace std;
void findContinueSequence(int *a,int size,int n)
{
if(size < 1 || n < 1)
return;
int begin = a[1];
int begin_i = 1;
int end = a[2];
int end_i = 2;
int sum = begin + end;
while(begin_i < size)
{
if(sum == n)
{
cout << begin << " " << end << endl;
for(int i = begin_i;i < end_i; i ++)
cout << a[i] << " ";
cout << endl;
}
while(sum > n)
{
sum -= begin ++;
begin_i ++;
if(sum == n)
{
cout << begin << " " << end << endl;
for(int i = begin_i;i < end_i; i ++)
cout << a[i] << " ";
cout << endl;
}
}
sum += ++ end;
++ end_i;
}
}
int main()
{
int a[10] = {1,2,3,4,6,7,8,9,10,13};
findContinueSequence(a,10,40);
return 0;
}
3. 输出所以字符串的排列与组合
排列（下转自：http://www.cnblogs.com/dolphin0520/archive/2011/07/10/2102174.html ）
对给出的n个数，求出其所有的排列。
思路：对于R={r1,r2,r3.......rn}，其全排列可以这样去计算，
perm(R)=riperm(R-ri);(1<=i<=n)
即以ri为前缀不变，对剩下所有的元素进行排列。即分别以r1,r2,r3,....rn作为前缀不变，对剩下的所有元素进行全排列即为所得到的结果。同理对于perm(R-ri)的求解也是一个相同的过程，因此可以采用递归的思想去解决。
#include <iostream>
using namespace std;
void permutation(char *a,int start,int n)
{
int end = n ;
if(start == end)
{
cout << a << endl;
return ;
}
else
{
static char tmp = NULL;
for(int i = start; i < end; i ++)
{
tmp=a[start];
a[start]=a[i];
a[i]=tmp;
permutation(a, start+1,n);
tmp=a[start];
a[start]=a[i];
a[i]=tmp;
}
}
}
int main()
{
char a[] = "wtx";
int len = 0;
for(int i = 0;a[i] != '\0'; i ++)
len ++;
permutation(a,0,len);
return 0;
}
组合，也不是很懂，明天在说
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iterator>
using namespace std;
void combine1(char* str, int num, vector<char>& res)
{
if(num== 0)
{
vector<char>::iterator iter = res.begin();
for(; iter < res.end(); ++ iter)
{
cout<< *iter<<"\t";
}
cout<<endl;
}else{
if(*str == '\0')
{
return;
}
res.push_back(*str);
combine1(str + 1, num - 1, res);
res.pop_back();
combine1(str + 1, num, res);
}
}
void combine(char* str)
{
if(str == NULL)
{
return;
}
int length = strlen(str);
vector<char> res;
for(int i = 1; i <= length; ++ i)
{
combine1(str, i, res);
}
}
int main()
{
char a[] = "wtx";
combine(a);
return 0;
}
4. 序列化分问题
#include <iostream>
using namespace std;
int f(int n,int m)
{
if(m == 1|| m == n)
return 1;
else
return f(n - 1,m - 1) + f(n - 1, m) * m;
}
int main()
{
int n;
cin >> n;
int sum = 0;
for(int i = 1;i <=n;i ++)
{
sum += f(n,i);
}
cout << sum << endl;
return 0;
}