1、反轉一個連結清單。循環算法。
1 list reverse(list l) {
2 if(!l) return l;
3 list cur = l.next;
4 list pre = l;
5 list tmp;
6 pre.next = null;
7 while ( cur ) {
8 tmp = cur;
9 cur = cur.next;
10 tmp.next = pre
11 pre = tmp;
12 }
13 return tmp;
14 }
2、反轉一個連結清單。遞歸算法。
1 list resverse(list l) {
2 if(!l || !l.next) return l;
3
4 list n = reverse(l.next);
5 l.next.next = l;
6 l.next=null;
7 }
8 return n;
9 }
3、廣度優先周遊二叉樹。
1 void bst(tree t) {
2 queue q = new queue();
3 q.enque(t);
4 tree t = q.deque();
5 while(t) {
6 system.out.println(t.value);
7 q.enque(t.left);
8 q.enque(t.right);
9 t = q.deque();
10 }
11 }
----------------------
1class node {
2 tree t;
3 node next;
4 }
5class queue {
6 node head;
7 node tail;
8 public void enque(tree t){
9 node n = new node();
10 n.t = t;
11 if(!tail){
12 tail = head = n;
13 } else {
14 tail.next = n;
15 tail = n;
16 }
17 }
18 public tree deque() {
19 if (!head) {
20 return null;
21 } else {
22 node n = head;
23 head = head.next;
24 return n.t;
25 }
26}
4、輸出一個字元串所有排列。注意有重複字元。
1char[] p;
2void perm(char s[], int i, int n){
3 int j;
4 char temp;
5 for(j=0;j<n;++j){
6 if(j!=0 && s[j]==s[j-1]);
7 elseif(s[j]!='@'){
8 p[i]=s[j];
9 s[j]='@';
10 if(i==n-1){
11 p[n]='\0';
12 printf("%s", p);
13 }else{
14 perm(s,i+1,n);
15 }
16 s[j]=p[i];
18 }
19}
--------------------------
1void main() {
2 char s[n];
3 sort(s);
4 perm(s,0,strlen(s));
5}
5、輸入一個字元串,輸出長型整數。
1 long atol(char *str){
2 char *p = str;
3 long l=1;m=0;
4 if (*p=='-') {
5 l=-1;
6 ++p;
7 }
8 while(isdigit(*p)){
9 m = m*10 + p;
10 ++p;
11 }
12 if(!p) return m*l;
13 else return error;
14}
6、判斷一個連結清單是否有循環。
1 int isloop(list l) {
2 if ( ! l) return - 1 ;
3 list s = l.next;
4 while (s && s != l) {
5 s = s.next;
6 }
7 if ( ! s) return - 1 ;
8 else reutrn 1 ;
9 }
-----------
1int isloop(list l){
2 if(!l) return 0;
3 p=l.next;
4 wihle(p!=l&&p!=null) {
5 l.next=l;
6 l=p;p=p.next;
8 if(p=l) return 1;
9 return 0;
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 ;
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<n;++i){
9 u=2*f4(i)+f3(n-i);
10 if(u<min) min=u;
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 }
17 m=head.next;
18}
14、一個數組,下标從0到n,元素為從0到n的整數。判斷其中是否有重複元素。
1int hasduplicate(int[] a, int n){
2 for(int i=0;i<n;++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<right)? (right +1) : (left + 1);
7 else return -1;
9
16、傳回一顆二叉樹的深度。
1int depth(tree t){
4 int a=depth(t.right);
5 int b=depth(t.left);
6 return (a>b)?(a+1):(b+1);
17、兩個連結清單,一升一降。合并為一個升序連結清單。
1 list merge(list a, list d) {
2 list a1 = reverse(d);
3 list p = q = new list();
4 while ( a && a1 ) {
5 if (a.value < a1.value) {
6 p.next = a;
7 a = a.next;
8 } else {
9 p.next = a1;
10 a1 = a1.next;
11 }
12 p = p.next;
13 }
14 if (a) p.next = a;
15 elseif(a1) p.next = a1;
16 return q.next;
17 }
18、将長型轉換為字元串。
1char* ltoa(long l){
2 char[n] str;
3 int i=1,n=1;
4 while(!(l/i<10)){i*=10;++n}
5 char* str=(char*)malloc(n*sizeof(char));
6 int j=0;
7 while(l){
8 str[j++]=l/i;
9 l=l%i;
10 i/=10;
12 return str;
13}
19、用一個資料結構實作
1 if (x == 0) y = a;
2 else y = b;
1 j[] = {a,b};
2 y=j[x];
20、在雙向連結清單中删除指定元素。
1void del(list head, list node){
2 list pre=new list();
3 pre.next = head;
4 list cur = head;
5 while(cur && cur!=node){
6 cur=cur.next;
7 pre=pre.next;
8 }
9 if(!cur) return;
10 list post = cur.next;
11 pre.next=cur.next;
12 post.last=cur.last;
13 return;
21、不重複地輸出升序數組中的元素。
1 void outputunique( char [] str, int n) {
2 if (n <= 0 ) return ;
3 elseif(n == 1 ) putchar(str[ 0 ]);
4 else {
5 int i = 0 ,j = 1 ;
6 putchar(str[ 0 ]);
7 while (j < n) {
8 if (str[j] !== str[i]) {
9 putchar(str[j]);
10 i = j;
11 }
12 ++ j;
13 }
14 }
15 }
22、面試過程中我還遇到了下面幾題:
1、如何删除連結清單的倒數第m的元素?我的方法是先用pre指針從連結清單頭開始步進m,建立pst節點next指針指向頭節點,cur指針指向頭節點,然後pre,cur,post三個指針一起步進,當pre指向連結清單結尾的時候cur指向倒數第m個元素,最後利用pst指針删除cur指向元素。
2、如何判斷一個字元串是對稱的?如a,aa,aba。設定頭尾指針同時向中間比較靠齊直至相遇。
3、如何利用2函數找出一個字元串中的所有對稱子串?以子串頭指針和尾指針為循環變量設定兩個嵌套的循環以找出所有子串,對每個子串應用2函數。
該系列題目由http://www.cnblogs.com/wqguan/archive/2006/06/20/430347.html