10}
实际上，在我的面试过程中，还问到了不破坏结构的其他算法。
我的答案是从链表头开始遍历，如果节点next指针指向自身，则循环存在;否则将next指针指向自身，遍历下一个节点。直至next指针为空，此时链表无循环。 7、反转一个字符串。
1 void reverse( char * str) { 2 char tmp; 3 int len;
4 len = strlen(str);
5 for ( int i = 0 ;i < len / 2 ; ++ i) { 6 tmp = char [i];
7 str[i] = str[len - i - 1 ]; 8 str[len - i - 1 ] = tmp; 9 } 10 }
8、实现strstr函数。
1int strstr(char[] str, char[] par){ 2 int i=0; 3 int j=0;
4 while(str[i] && str[j]){ 5 if(str[i]==par[j]){ 6 ++i; 7 ++j; 8 }else{
9 i=i-j+1; 10 j=0; 11 } 12 }
13 if(!str[j]) return i-strlen(par); 14 else return -1; 15}
9、实现strcmp函数。
1int strcmp(char* str1, char* str2){ 2 while(*str1 && *str2 && *str1==*str2){ 3 ++str1; 4 ++str2; 5 }
6 return *str1-*str2; 7}
10、求一个整形中1的位数。 1 int f( int x) { 2 int n = 0 ; 3 while (x) { 4 ++ n; 5 x &= x - 1 ; 6 } 7 return n; 8 }
11、汉诺塔问题。 1void tower(n,x,y,z){ 2 if(n==1) move(x,z); 3 else {
4 tower(n-1, x,z,y); 5 move(x,z); 6 tower(n-1, y,x,z); 7 } 8}
12、三柱汉诺塔最小步数。 1 int f3(n) {
2 if (f3[n]) return f3[n]; 3 else { 4 if (n == 1 ) { 5 f3[n] = 1 ; 6 return 1 ; 7 }
8 f3[n] = 2 * f3(n - 1 ) + 1 ; 9 return f3[n]; 10 } 11 }
四柱汉诺塔最小步数。 1int f4(n){ 2 if(f4[n]==0){
3 if(n==1) { 4 f4[1]==1; 5 return 1; 6 }
7 min=2*f4(1)+f3(n-1);
8 for(int i=2;i 9 u=2*f4(i)+f3(n-i); 10 if(u 11 } 12 f4[n]=min; 13 return min;
14 } else return f4[n]; 15}
13、在一个链表中删除另一个链表中的元素。 1void delete(List m, List n) { 2 if(!m || !n) return; 3 List pre = new List(); 4 pre.next=m;
5 List a=m, b=n,head=pre; 6 while(a && b){
7 if(a.value < b.value) { 8 a=a.next; 9 pre=pre.next;
10 }else if(a.value > b.value){ 11 b=b.next; 12 }else{
13 a=a.next; 14 pre.next=a; 15 } 16 }
17 m=head.next; 18}
14、一个数组，下标从0到n，元素为从0到n的整数。判断其中是否有重复元素。 1int hasDuplicate(int[] a, int n){
2 for(int i=0;i 3 while(a[i]!=i && a[i]!=-1){ 4 if(a[a[i]]==-1) return 1; 5 a[i]=a[a[i]]; 6 a[a[i]]=-1; 7 }
8 if(a[i]==i) {a[i]=-1;} 9 }
10 return 0; 11}
15、判断一颗二叉树是否平衡。 1int isB(Tree t){ 2 if(!t) return 0; 3 int left=isB(t.left); 4 int right=isB(t.right);
5 if( left >=0 && right >=0 && left – right <= 1 || left -right >=-1) 6 return (left 7 else return -1;
互联网IT公司面试指导手册
