算法笔记
散列
- 字符串散列
// 把字符串当成26进制数，转换成10进制，建立映射关系
int hash(char S[], int len) {
int res = 0;
for (int i = 0; i < len; ++i) {
res = res * 26 + (S[i] - 'A');
}
return res;
}
/*
* 给出n个字符串，每个字符串由三位大写字母构成；
* 再给出m个字符串，查询每个字符串在n个字符串中出现的次数
*/
void fun() {
int n, m;
char S[100][4], temp[4];
int hashMap[26 * 26 * 26];
scanf("%d%d", &n, &m);
// 映射成10进制放入hash表，并统计个数
for (int i = 0; i < n; ++i) {
scanf("%s", S[i]);
int t = hash(S[i], 3);
hashMap[t]++;
}
for (int i = 0; i < m; ++i) {
scanf("%s", temp);
int t = hash(temp, 3);
printf("count=%d\n", hashMap[t]);
}
}
递归
- 全排列
// 输出1~n的全排列。分成若干子问题：以1开头的全排列，2开头的全排列...
// 按顺序往P的第1~n位中填入数字，当前已经填好P[1]到P[cur-1],正准备填入P[cur]
// 从小到大枚举1~n，若枚举的数字i没有出现在P中，则P[cur]填入i，同时hashTable[i]置为true;
// 然后递归处理cur+1位置的数字；处理完P[cur]=i的子问题，再把hashTable[i]置为false，P[cur]填入下个数字
void generateP(int P[], int hashTable[], int n, int cur) {
// n个数字都已排列完毕
if (cur == n + 1) {
for (int i = 1; i <= n; ++i) {
printf("%d", P[i]);
}
puts("\n");
return;
}
// 从第一个开始往输出序列P里放
for (int i = 1; i <= n; ++i) {
// i不在P中
if (hashTable[i] == false) {
// 放到当前位置
P[cur] = i;
hashTable[i] = true;
generateP(P, hashTable, n, cur + 1);
hashTable[i] = false;
}
}
}
// 1~3的全排列
void generate(){
int P[3];
int hashTable[11];
for (int i = 0; i < 11; ++i) {
hashTable[i] = false;
}
// 输出全排列
generateP(P, hashTable, 3, 1);
}
int count; // 记录是第几个排列，从第一个找到第k个
int target; // 要找到那个排列的序号
char res[10]; // 输出结果
int flag; // 为true时，停止所有递归
// 输出1~n的全排列。分成若干子问题：以1开头的全排列，2开头的全排列...
// 按顺序往P的第1~n位中填入数字，当前已经填好P[1]到P[cur-1],正准备填入P[cur]
// 从小到大枚举1~n，若枚举的数字i没有出现在P中，则P[cur]填入i，同时hashTable[i]置为true;
// 然后递归处理cur+1位置的数字；处理完P[cur]=i的子问题，再把hashTable[i]置为false，P[cur]填入下个数字
void generate(int P[], int n, int cur, int hashTable[]) {
if (flag) return;
// P中元素放满了
if (cur == n + 1) {
count++;
if (count == target) {
for (int i = 1; i <= n; ++i) {
res[i - 1] = (char) (P[i] + '0');
res[i] = '\0';
}
flag = true; // 停止所有递归
}
// 停止此次递归
return;
}
// P中还没放满
for (int i = 1; i <= n; ++i) {
// i还没有出现在P中
if (hashTable[i] == false) {
P[cur] = i;
hashTable[i] = true;
// 处理子问题
generate(P, n, cur + 1, hashTable);
hashTable[i] = false;
}
}
}
// 1 <= n <= 9,返回第 k 个排列。
char *getPermutation(int n, int k) {
count = 0;
target = k;
flag = false;
int P[10];
int hashTable[10];
for (int i = 0; i < 10; ++i) {
hashTable[i] = false;
}
generate(P, n, 1, hashTable);
return res;
}
-
n皇后问题
全排列的暴力法
int count;
void generateP(int P[], int n, int cur, int hashTable[]) {
// 形成了一个全排列
if (cur == n + 1) {
bool flag = true;
// i, j表示两个皇后所在的行；P[i],P[j]表示所在的列
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
// 由于已经是不同行不同列，只需要判断是否在同一斜线
if ((j - i) == abs(P[i] - P[j])) {
flag = false;
break;
}
}
}
if (flag) count++;
return;
}
for (int i = 1; i <= n; ++i) {
if (hashTable[i] == false) {
P[cur] = i;
hashTable[i] = true;
generateP(P, n, cur + 1, hashTable);
hashTable[i] = false;
}
}
}
int totalNQueens(int n) {
count = 0;
int P[10];
int hashTable[10];
for (int i = 0; i < 10; ++i) {
hashTable[i] = false;
}
generateP(P, n, 1, hashTable);
return count;
}
优化版
void generateP(int P[], int n, int cur, int hashTable[]) {
if (cur == n + 1) {
count++;
return;
}
for (int i = 1; i <= n; ++i) {
if (hashTable[i] == false) {
bool flag = true;
// 先判断第cur行和前面的行有没有不冲突的地方可以放
for (int j = 1; j < cur; ++j) {
if ((cur - j) == abs(i - P[j])) {
flag = false;
break;
}
}
if (flag) {
P[cur] = i;
hashTable[i] = true;
generateP(P, n, cur + 1, hashTable);
hashTable[i] = false;
}
}
}
}
int totalNQueens(int n) {
count = 0;
int P[10];
int hashTable[10];
for (int i = 0; i < 10; ++i) {
hashTable[i] = false;
}
generateP(P, n, 1, hashTable);
return count;
}