部分IT公司算法笔试题面试题(三)

void Trial(int i, int n) { // 寻找合适下棋位置
if(i == n) {
for(int k=0; k for(int m=0; m printf(“%d “, Board[k][m]);
printf(“\n”);
}
printf(“\n”);
} else {
for(int j=0; j Board[i][j] = 1;
if(Valid(i,j))
Trial(i+1, n);
Board[i][j] = 0;
}
}
}

int main(int argc, char* argv[]) {
Trial(0, N);
}

14、实现strstr功能，即在父串中寻找子串首次出现的位置。（笔试中常让面试者实现标准库中的一些函数）
char * strstring(char *ParentString, char *SubString) {
char *pSubString, *pPareString;
for(char *pTmp=ParentString; *pTmp; pTmp++) {
pSubString = SubString;
pPareString = pTmp;
while(*pSubString == *pPareString && *pSubString != ‘\0′) {
pSubString++;
pPareString++;
}
if(*pSubString == ‘\0′) return pTmp;
}
return NULL;
}

int main(int argc, char* argv[]) {
char *ParentString = “happy birthday to you!”;
char *SubString = “birthday”;
printf(“%s”,strstring(ParentString, SubString));
}

15、现在小明一家过一座桥，过桥的时候是黑夜，所以必须有灯。现在小明过桥要1分，小明的弟弟要3分，小明的爸爸要6分，小明的妈妈要8分，小明的爷爷要12分。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30分就会熄灭。问小明一家如何过桥时间最短？（原本是个小小智力题，据说是外企的面试题，在这里用程序来求解）
#include “stdafx.h”
#define N 5
#define SIZE 64

// 将人员编号：小明-0，弟弟-1，爸爸-2，妈妈-3，爷爷-4
// 每个人的当前位置：0–在桥左边， 1–在桥右边
int Position[N];
// 过桥临时方案的数组下标； 临时方案； 最小时间方案；
int Index, TmpScheme[SIZE], Scheme[SIZE];
// 最小过桥时间总和，初始值100；每个人过桥所需要的时间
int MinTime=100, Time[N]={1, 3, 6, 8, 12};
// 寻找最佳过桥方案。Remnant:未过桥人数; CurTime:当前已用时间;
// Direction:过桥方向,1–向右,0–向左
void Find(int Remnant, int CurTime, int Direction) {
if(Remnant == 0) { // 所有人已经过桥，更新最少时间及方案
MinTime=CurTime;
for(int i=0; i=0; i++)
Scheme[i] = TmpScheme[i];
} else if(Direction == 1) { // 过桥方向向右，从桥左侧选出两人过桥
for(int i=0; i if(Position[i] == 0 && CurTime + Time[i] < MinTime) {
TmpScheme[Index++] = i;
Position[i] = 1;
for(int j=0; j int TmpMax = (Time[i] > Time[j] Time[i] : Time[j]);
if(Position[j] == 0 && CurTime + TmpMax < MinTime) {
TmpScheme[Index++] = j;
Position[j] = 1;
Find(Remnant – 2, CurTime + TmpMax, !Direction);
Position[j] = 0;
TmpScheme[--Index] = -1;
}
}
Position[i] = 0;
TmpScheme[--Index] = -1;
}
} else { // 过桥方向向左，从桥右侧选出一个人回来送灯
for(int j=0; j if(Position[j] == 1 && CurTime+Time[j] < MinTime) {
TmpScheme[Index++] = j;
Position[j] = 0;
Find(Remnant+1, CurTime+Time[j], !Direction);
Position[j] = 1;
TmpScheme[--Index] = -1;
}
}
}
}
int main(int argc, char* argv[]) {
for(int i=0; i Scheme[i] = TmpScheme[i] = -1;

Find(N, 0, 1); // 查找最佳方案

printf(“MinTime=%d:”, MinTime); // 输出最佳方案
for(int i=0; i=0; i+=3)
printf(“ %d-%d %d”, Scheme[i], Scheme[i+1], Scheme[i+2]);
printf(“\b\b “);
}

16、2005年11月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符’*'移到串的前部分，前面的非’*'字符后移，但不能改变非’*'字符的先后顺序，函数返回串中字符’*'的数量。如原始串为：ab**cd**e*12，处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）
int change(char *str) { /* 这个算法并不高效，从后向前搜索效率要高些 */
int count = 0; /* 记录串中字符’*'的个数 */
for(int i=0, j=0; str[i]; i++) { /* 重串首开始遍历 */
if(str[i]==’*') { /* 遇到字符’*’ */
for(j=i-1; str[j]!=’*'&&j>=0; j–) /* 采用类似插入排序的思想，将*前面 */
str[j+1]=str[j]; /* 的非*字符逐个后移，直到遇到*字符 */
str[j+1] = ‘*’;
count++;
}
}
return count;
}
int main(int argc, char* argv[]) {
char str[] = “ab**cd**e*12″;
printf(“str1=%s\n”, str);
printf(“str2=%s, count=%d”, str, change(str));
}
// 终于得到一个比较高效的算法，一个网友提供，估计应该和金山面试官的想法