文档介绍：微软的22 道数据结构算法面试题（含答案）
1、反转一个链表。循环算法。
List r eve rse(List I) {
ext;
if(!l) retu rn I;
3
4
5
6
7
8
9
10
1试过程中，还问到了不破坏结构的其他算法。
我的答案是从链表头开始遍历，如果节点next指针指向自身，则循环存在；否则将next 指针指向自身，遍历下一个节点。直至next指针为空，此时链表无循环。
7、反转一个字符串。
1
2
3
4
5
{
6
7
8
9
10 }
void r eve rse( cha r
cha r tmp;
int len;
len = str le n(st r);
for (int i = 0
tmp st r[i] str [len
* str) {
< len / 2
+ + i)
cha r [i];
str [le n - i - 1 ];
i - 1 ] = tmp;
1int
2
3
4
5
6
7
8
9
10
11
12
13
14
} if(!str[j]) else ret urn
8、实现strstr函数。
strstr (cha r[] str, cha r[] par){ int i=0;
int j=0;
while(st r[i] && str [j]){
if(st r[ i] = = pa r[j]){ + + i;
+ +j;
}else{
= i-j+1;
j=0;
retu rn i-st rle n(par);
-1;
15}
9、实现strcmp函数。
1i nt str cmp(cha r* st r1, cha r* str 2){
while( *st r1 && * st r2 && * st r1 = = *str 2){
++st r1;
++st r2;
}
return *str1-*str2;
7}
10、求一个整形中1的位数。
int f( int x) {
int n = 0 ;
while (x) {
++ n;
x & = x - 1 ;
}
return n;
}
11、汉诺塔问题。
1void towe r(n ,x,y,z){
if(n = = 1) move(x,z);
else {
towe r(n-1, x,z, y);
move(x,z);
towe r(n-1, y,x,z);
}
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 }
四柱汉诺塔最小步数。
lint f4(n){
2 if(f4[ n] ==0){
3
4
5
6
7