// 字符串逆序
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 ;
}
}
组合问题
给定一个含有n个元素的整型数组a，从中任取m个元素，求所有组合。比如下面的例子：
a = 1, 2, 3, 4, 5
m = 3
输出：
1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5
2 3 4, 2 3 5, 2 4 5
3 4 5
典型的排列组合问题，首选回溯法，为了简化问题，我们将a中n个元素值分别设置为1-n。
复制代码 代码如下:
// n选m的所有组合
int buffer[100] ;
void PrintArray(int *a, int n)
{
for (int i = 0; i < n; ++i)
cout << a[i] << " ";
cout << endl ;
}
bool IsValid(int lastIndex, int value)
{
for (int i = 0; i < lastIndex; i++)
{
if (buffer[i] >= value)
return false;
}
return true;
}
void Select(int t, int n, int m)
{
if (t == m)
PrintArray(buffer, m);
else
{
for (int i = 1; i <= n; i++)
{
buffer[t] = i;
if (IsValid(t, i))
Select(t + 1, n, m);
}
}
}
合并两个数组
给定含有n个元素的两个有序（非降序）整型数组a和b。合并两个数组中的元素到整型数组c，要求去除重复元素并保持c有序（非降序）。例子如下：
a = 1, 2, 4, 8
b = 1, 3, 5, 8
c = 1, 2, 3, 4, 5, 8
利用合并排序的思想，两个指针i,j和k分别指向数组a和b，然后比较两个指针对应元素的大小，有以下三种情况：
a[i]
a[i] == b[j]，则c[k]等于a[i]或b[j]皆可。
a[i] > b[j]，则c[k] = b[j]。
重复以上过程，直到i或者j到达数组末尾，然后将剩下的元素直接copy到数组c中即可。
复制代码 代码如下:
// 合并两个有序数组
void Merge(int *a, int *b, int *c, int n)
{
int i = 0 ;
int j = 0 ;
int k = 0 ;
while (i < n && j < n)
{
if (a[i] < b[j])// 如果a的元素小，则插入a中元素到c
{
c[k++] = a[i] ;
++i ;
}
else if (a[i] == b[j])// 如果a和b元素相等，则插入二者皆可，这里插入a
{
c[k++] = a[i] ;
++i ;
++j ;
}
else // a[i] > b[j] // 如果b中元素小，则插入b中元素到c
{
c[k++] = b[j] ;
++j ;
}
}
if (i == n) // 若a遍历完毕，处理b中剩下的元素
{
for (int m = j; m < n; ++m)
c[k++] = b[m] ;
}
else//j == n, 若b遍历完毕，处理a中剩下的元素
{
for (int m = i; m < n; ++m)
c[k++] = a[m] ;
}
}
重排问题
给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：
排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变。
不能使用额外存储空间。
例子如下：输入 0, 3, 0, 2, 1, 0, 0，输出 0, 0, 0, 0, 3, 2, 1。
此排序非传统意义上的排序，因为它要求排序前后非0元素的相对位置不变，或许叫做整理会更恰当一些。我们可以从后向前遍历整个数组，遇到某个位置i上的元素是非0元素时，如果a[k]为0，则将a[i]赋值给a[k]，a[k]赋值为0。实际上i是非0元素的下标，而k是0元素的下标。
复制代码 代码如下:
void Arrange(int* a, int n)
{
int k = n - 1 ;
for (int i = n - 1; i >= 0; --i)
{
if (a[i] != 0)
{
if (a[k] == 0)
{
a[k] = a[i] ;
a[i] = 0 ;
}
--k ;
}
}
}
您可能感兴趣的文章: