- 相關(guān)推薦
微軟算法面試題
1、反轉(zhuǎn)一個(gè)鏈表。循環(huán)算法。
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、反轉(zhuǎn)一個(gè)鏈表。遞歸算法。
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、廣度優(yōu)先遍歷二叉樹。
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、輸出一個(gè)字符串所有排列。注意有重復(fù)字符。
1char[] p;
2void perm(char s[], int i, int n){
3 int j;
4 char temp;
5 for(j=0;j<n;++j){< p="">
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]='