算法面试题_求给定字符串的排列、组合、八皇后问题

目录

一、题目：字符串的排列

1.1 全排列的递归实现（不考虑有字符重复）

1.1.1 写法1

1.1.2 写法2

1.2 全排列的递归实现 （考虑有字符重复）

1.3 全排列的非递归实现

二、字符串的组合

2.1 方法1

2.2 方法2： 用位运算来实现求组合

三. 字符串全排列扩展----八皇后问题

四. 相关题目

参考

• 首先来看看题目是如何要求的（百度迅雷校招笔试题）。
• 同剑指offer第二版: "面试题: 38"

一、题目：字符串的排列

• 用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列,
  • 如 abc 的全排列: abc, acb, bca, dac, cab, cba

1.1 全排列的递归实现（不考虑有字符重复）

为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后，递归的代码就很容易写出来了：

1.1.1 写法1

#include
using namespace std;
#include
 
void Permutation(char* pStr, char* pBegin)
{
	assert(pStr && pBegin);
 
	if(*pBegin == '\0')
		printf("%s\n",pStr);
	else
	{
		for(char* pCh = pBegin; *pCh != '\0'; pCh++)
		{
			swap(*pBegin,*pCh);
			Permutation(pStr, pBegin+1);
			swap(*pBegin,*pCh);
		}
	}
}
 
int main(void)
{
	char str[] = "abc";
	Permutation(str,str);
	return 0;
}

1.1.2 写法2

//k表示当前选取到第几个数的索引，m表示最后一个数的索引
void Permutation(char* pStr,int k,int m)
{
	assert(pStr);
 
	if(k == m)
	{
		static int num = 1;  //局部静态变量，用来统计全排列的个数
		printf("第%d个排列\t%s\n",num++,pStr);
	}
	else
	{
		for(int i = k; i