IT公司笔试常考的算法题

IT公司笔试常考的算法题,标签：银行笔试题目,企业笔试题目,http://www.qz26.com

　　#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 = TmpScheme;

　　} else if(Direction == 1) { // 过桥方向向右，从桥左侧选出两人过桥

　　for(int i=0; i

　　if(Position == 0 && CurTime + Time < MinTime) {

　　TmpScheme[Index++] = i;

　　Position = 1;

　　for(int j=0; j

　　int TmpMax = (Time > Time[j] ? Time : 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 = 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 = TmpScheme = -1;

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

　　printf("MinTime=%d:", MinTime); // 输出最佳方案

　　for(int i=0; i=0; i+=3)

　　printf(" %d-%d %d", Scheme, Scheme[i+1], Scheme[i+2]);

　　printf("\b\b ");

　　}

　　16、20xx年11月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符'*'移到串的前部分，前面的非'*'字符后移，但不能改变非'*'字符的先后顺序，函数返回串中字符'*'的数量。如原始串为：ab**cd**e*12，处理后为*****abcde12，函数并返回值为5。(要求使用尽量少的时间和辅助空间)

　　int change(char *str) { /* 这个算法并不高效，从后向前搜索效率要高些 */

　　int count = 0; /* 记录串中字符'*'的个数 */

　　for(int i=0, j=0; str; i++) { /* 重串首开始遍历 */

　　if(str=='*') { /* 遇到字符'*' */

　　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));

　　}

　　// 终于得到一个比较高效的算法，一个网友提供，估计应该和金山面试官的想法一致。算法如下：

上一页  [1] [2] [3] [4] [5] [6] [7] [8]  下一页