天天看點
傳回

80道常見資料結構面試題及其解法 計包含min函數的棧 整數序列是不是二進制查找樹的後序周遊結果

1.把二進制查找樹轉變成排序的雙向連結清單

題目：

輸入一棵二進制查找樹，将該二進制查找樹轉換成一個排序的雙向連結清單。

要求不能建立任何新的結點，隻調整指針的指向。

10

/ \

6 14

/ \ / \

4 8 12 16

轉換成雙向連結清單

4=6=8=10=12=14=16。

首先我們定義的二進制查找樹節點的資料結構如下：

struct BSTreeNode

{

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node

BSTreeNode *m_pRight; // right child of node

};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

// 1：構造二叉查找樹；

// 2：中序周遊二叉查找樹，是以結點按從小到大順序通路，假設之前通路過的結點已經調整為一個雙向連結清單，那麼

//       隻需要将目前結點連接配接至雙向連結清單的最後一個結點即可，通路完後，雙向連結清單也就調整完了

#include <iostream>

using

namespace

std;

struct

BSTreeNode

{

int

m_nValue; 

// value of node

BSTreeNode *m_pLeft; 

// left child of node

BSTreeNode *m_pRight; 

// right child of node

};

void

addBSTreeNode(BSTreeNode *&pCurrent,

int

value);

void

inOrderBSTree(BSTreeNode* pBSTree);

void

convertToDoubleList(BSTreeNode* pCurrent);

BSTreeNode *pHead=NULL;

//指向循環隊列頭結點

BSTreeNode *pIndex=NULL;

//指向前一個結點

int

main()

{

BSTreeNode *pRoot=NULL;

addBSTreeNode(pRoot,10);

addBSTreeNode(pRoot,6);

addBSTreeNode(pRoot,14);

addBSTreeNode(pRoot,4);

addBSTreeNode(pRoot,8);

addBSTreeNode(pRoot,12);

addBSTreeNode(pRoot,16);

inOrderBSTree(pRoot);

return

0;

}

void

addBSTreeNode(BSTreeNode *&pCurrent,

int

value)

//在這個函數中會要改變指針值，一定要記得使用引用傳遞

{

if

(pCurrent==NULL)

{

BSTreeNode* pBSTree=

new

BSTreeNode();

pBSTree->m_nValue=value;

pBSTree->m_pLeft=NULL;

pBSTree->m_pRight=NULL;

pCurrent=pBSTree;

}

else

if

(pCurrent->m_nValue<value)

{

addBSTreeNode(pCurrent->m_pRight,value);

}

else

if

(pCurrent->m_nValue>value)

{

addBSTreeNode(pCurrent->m_pLeft,value);

}

else

{

cout<<

"node repeated"

<<endl;

}

}

void

inOrderBSTree(BSTreeNode* pBSTree)

{

if

(NULL==pBSTree)

{

return

;

}

if

(NULL!=pBSTree->m_pLeft)

{

inOrderBSTree(pBSTree->m_pLeft);

}

//  if (NULL!=pBSTree)

//  {

//      cout<<pBSTree->m_nValue;

//  }

convertToDoubleList(pBSTree);

if

(NULL!=pBSTree->m_pRight)

{

inOrderBSTree(pBSTree->m_pRight);

}

}

void

convertToDoubleList(BSTreeNode* pCurrent)

{

pCurrent->m_pLeft=pIndex;

//使目前結點的左指針指向雙向連結清單中最後一個結點

if

(NULL==pIndex)

//若最後一個元素不存在，此時雙向連結清單尚未建立，是以将目前結點設為雙向連結清單頭結點

{

pHead=pCurrent;

}

else

//使雙向連結清單中最後一個結點的右指針指向目前結點

{

pIndex->m_pRight=pCurrent;

}

pIndex=pCurrent;

//将目前結點設為雙向連結清單中最後一個結點

cout<<pCurrent->m_nValue<<

" "

;

}

2：

計包含min函數的棧

要求

定義棧的資料結構，要求添加一個min 函數，能夠得到棧的最小元素。 

要求函數min、push 以及pop 的時間複雜度都是O(1)。

解法

使用一個輔助棧來儲存最小元素，這個解法簡單不失優雅。設該輔助棧名字為minimum stack，其棧頂元素為目前棧中的最小元素。這意味着
  • 要擷取目前棧中最小元素，隻需要傳回minimum stack的棧頂元素即可。
  • 每次執行push操作，檢查push的元素是否小于或等于minimum stack棧頂元素。如果是，則也push該元素到minimum stack中。
  • 當執行pop操作的時候，檢查pop的元素是否與目前最小值相等。如果相同，則需要将改元素從minimum stack中pop出去。 
struct minStack{
    stack<int> s;
    stack<int> minS;

    void push(int i){
        if (s.empty() || minS.empty()){
            s.push(i);
            minS.push(i);
        }else{
            if (minS.top() >= i){
                minS.push(i);
            }
            s.push(i);
        }
    }

    void pop(){
        if (s.empty() || minS.empty()){
            return;
        }
        if (s.top() > minS.top()){
            s.pop();
        }else{
            s.pop();
            minS.pop();
        }
    }

    int min(){
        if (minS.empty())
            return -1;
        else 
            return minS.top();
    }
};

3:題目：輸入一個整形數組，數組裡有正數也有負數。數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。求所有子數組的和的最大值。要求時間複雜度為O(n)。

一種從前往後周遊的方法如下：

[cpp]  view plain  copy

  1. // 需要儲存起始點與結束點下标的時候，從前往後周遊也是可以的  
  2. int MaxSum(int *a , int n)  
  3. {  
  4.     int tempstart = 0 , sum=0 , max = -1000;  
  5.     int i , start , end;  
  6.     start = end = 0;  
  7.     for(i = 0 ; i < n ; ++i)  
  8.     {  
  9.         if(sum < 0)  
  10.         {  
  11.             sum = a[i];  
  12.             tempstart = i;  
  13.         }  
  14.         else  
  15.             sum += a[i];  
  16.         if(sum > max)  
  17.         {  
  18.             max = sum;  
  19.             start = tempstart;  
  20.             end = i;  
  21.         }  
  22.     }  
  23.     return max;  
  24. }  

4 面試題目：

        輸入一個整數和一棵二進制樹。從樹的根結點開始往下通路一直到葉結點所經過的所有結點形成一條路徑。列印出和與輸入整數相等的所有路徑。

        例如輸入整數 22 ，如下圖二進制樹：

                                            10

                                           /     \

                                          5     12

                                        /    \   

                                       4     7 

   則列印出兩條路徑：10, 12和10, 5, 7。

思路：對于如圖所示的二叉樹，其實就是一個遞歸的過程，上例可以有三條路徑10 5 4 ，10 5 7,10 12，遞歸調用者三次路徑即可，如果滿足就列印出來，不可以就再重複遞歸 代碼如下：

  1. #include <iostream>  
  2. #include <vector>  
  3. using namespace std;  
  4. struct BinaryTreeNode // a node in the binary tree  
  5. {  
  6.     int m_nValue; // value of node  
  7.     BinaryTreeNode *m_pLeft; // left child of node  
  8.     BinaryTreeNode *m_pRight; // right child of node  
  9. };  
  10. vector<BinaryTreeNode*> pathVec;  
  11. void creatTree(BinaryTreeNode *&root, int *a, int i, int len)  
  12. {  
  13.     if(i >= len)  
  14.         return;  
  15.     root = new BinaryTreeNode;  
  16.     root->m_nValue = a[i];  
  17.     root->m_pLeft = NULL;  
  18.     root->m_pRight = NULL;  
  19.     creatTree(root->m_pLeft, a, 2*i + 1, len);  
  20.     creatTree(root->m_pRight, a, 2*i + 2, len);  
  21. }  
  22. void preorder(BinaryTreeNode* &root)  
  23. {  
  24.     if(!root)  
  25.         return;  
  26.     cout << root->m_nValue << " ";  
  27.     preorder(root->m_pLeft);  
  28.     preorder(root->m_pRight);      
  29. }  
  30. void printPath(vector<BinaryTreeNode*>& pathVec)  
  31. {  
  32.     for(vector<BinaryTreeNode*>::iterator it = pathVec.begin(); it != pathVec.end(); it++)  
  33.         cout << (*it)->m_nValue << " ";  
  34.     cout << endl;  
  35. }  
  36. void pathTree(BinaryTreeNode* &root, int val)  
  37. {  
  38. //輸出二叉樹中路徑等于val的所有路徑  
  39.     static int sum = 0;  
  40.     sum += root->m_nValue;  
  41.     pathVec.push_back(root);  
  42.     if(sum == val && root->m_pLeft == NULL && root->m_pRight == NULL)  
  43.         printPath(pathVec);  
  44.     if(root->m_pLeft)  
  45.         pathTree(root->m_pLeft, val);  
  46.     if(root->m_pRight)  
  47.         pathTree(root->m_pRight, val);  
  48.     sum -= root->m_nValue;  
  49.     pathVec.pop_back();  
  50. }  
  51. int main()  
  52. {  
  53.     BinaryTreeNode *root = 0;  
  54.     int a[] = {10, 5, 12, 7, 8};  
  55.     int len = sizeof a / sizeof a[0];  
  56.     creatTree(root, a, 0, len);  
  57. //  preorder(root);  
  58.     pathTree(root, 22);  
  59. } 

需要注意的是出棧與入棧的處理，友情是這一步   sum -= root->m_nValue; 

5:題目是：輸入n 個整數，輸出其中最小的k 個。例如輸入1，2，3，4，5，6，7 和8 這8 個數字，則最小的4 個數字為1，2，3 和4。

問題分析：先用冒泡排序法将數列排序，然後輸出其中最小的k個數，注意輸入輸出格式問題（空格問題）

代碼：

[cpp]  view plain  copy

  1. #include <iostream>  
  2. using namespace std;  
  3. void sort(int a[],int n,int k)  
  4. {  
  5.     int i=0,j=0;  
  6.     int temp;  
  7.     if(k>n)  
  8.     {  
  9.         cout<<"error"<<"\n";  
  10.     }  
  11.     else  
  12.     {  
  13.         for(i=0;i<n-1;i++)  
  14.             for(j=0;j<n-i-1;j++)  
  15.             {  
  16.                 if(a[j]>a[j+1])  
  17.                 {  
  18.                     temp=a[j];  
  19.                     a[j]=a[j+1];  
  20.                     a[j+1]=temp;  
  21.                 }  
  22.             }  
  23.             for(i=0;i<k-1;i++)  
  24.             {  
  25.                 cout<<a[i]<<" ";  
  26.             }  
  27.             cout<<a[k-1]<<"\n";  
  28.     }  
  29. }  
  30. int main()  
  31. {  
  32.     int n;//輸入整數個數  
  33.     int k;//輸出最小的k個數  
  34.     cin>>n>>k;  
  35.     int a[100];  
  36.     int i=0;  
  37.     for(i=0;i<n;i++)  
  38.         cin>>a[i];  
  39.     sort(a,n,k);  
  40.     return 0;  
  41. }  

6.判斷單連結清單是否有環

方法：使用p、q兩個指針，p每次向前走一步，q每次向前走兩步，若在某個時候p == q，則存在環。

#include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #define LEN 8
 5 typedef struct node* node_t;
 6 
 7 struct node{  
 8     char val;  
 9     struct node *next;  
10 };  
11 
12 //method 1
13 int has_loop(struct node *head);
14 //method 2
15 int has_loop2(node_t head);
16 
17 int main()
18 {
19     node_t* arr = (node_t*)malloc(sizeof(struct node)*LEN);
20     arr[0] = (node_t)malloc(sizeof(struct node));
21     int i;
22     for(i = 1; i < LEN; i++)
23     {
24         arr[i] = (node_t)malloc(sizeof(struct node));
25         arr[i - 1]->next = arr[i];
26     }
27     arr[LEN - 1]->next = NULL;
28 
29     //you can add a loop here to test
30     //arr[6]->next = arr[0];
31     if (has_loop(arr[0]))
32         printf("method1: has loop.\n");
33     else
34         printf("method1: has no loop.\n");
35 
36     if (has_loop2(arr[0]))
37         printf("method2: has loop.\n");
38     else
39         printf("method2: has no loop.\n");
40 
41     return 0;
42 }
43 
44 //if two pointer are equal, but they don't have the same steps, then has a loop
45 int has_loop(node_t head)  
46 {  
47     node_t cur1 = head;  
48     int pos1 = 0;  
49     while(cur1){  
50         node_t cur2 = head;  
51         int pos2 = 0;  
52         pos1 ++;  
53         while(cur2){  
54             pos2 ++;  
55             if(cur2 == cur1){  
56                 if(pos1 == pos2)  
57                     break;  
58                 else  
59                     return 1;
60             }  
61             cur2 = cur2->next;  
62         }  
63         cur1 = cur1->next;  
64     }  
65     return 0;  
66 } 
67 
68 //using step1 and step2 here 
69 //if exists a loop, then the pointer which use step2 will catch up with the pointer which uses step1
70 int has_loop2(node_t head)
71 {
72     node_t p = head;
73     node_t q = head;
74     while (p != NULL && q != NULL)
75     {
76         /*
77         p = p->next;
78         if (q->next != NULL)
79             q = q->next->next;
80         if (p == q)
81             return 1;
82             */
83         //correct it on 17/11/2012
84         p = p->next;
85         q = q->next;
86         if (q != NULL)
87             q = q->next;
88         if (p != NULL && p == q)
89             return 1;
90     }
91     return 0;
92 }
80道常見資料結構面試題及其解法 計包含min函數的棧 整數序列是不是二進制查找樹的後序周遊結果

第7題 微軟亞院之程式設計判斷倆個連結清單是否相交

一個比較經典的問題，判斷兩個連結清單是否相交，如果相交找出他們的交點。

80道常見資料結構面試題及其解法 計包含min函數的棧 整數序列是不是二進制查找樹的後序周遊結果

思路：

1、碰到這個問題，第一印象是采用hash來判斷，将兩個連結清單的節點進行hash，然後判斷出節點，這種想法當然是可以的。

2、當然采用暴力的方法也是可以的，周遊兩個連結清單，在周遊的過程中進行比較，看節點是否相同。

3、第三種思路是比較奇特的，在程式設計之美上看到的。先周遊第一個連結清單到他的尾部，然後将尾部的next指針指向第二個連結清單(尾部指針的next本來指向的是null)。這樣兩個連結清單就合成了一個連結清單，判斷原來的兩個連結清單是否相交也就轉變成了判斷新的連結清單是否有環的問題了：即判斷單連結清單是否有環？

這樣進行轉換後就可以從連結清單頭部進行判斷了，其實并不用。通過簡單的了解我們就很容易知道，如果新連結清單是有環的，那麼原來第二個連結清單的頭部一定在環上。是以我們就可以從第二個連結清單的頭部進行周遊的，進而減少了時間複雜度(減少的時間複雜度是第一個連結清單的長度)。

下圖是一個簡單的示範：

80道常見資料結構面試題及其解法 計包含min函數的棧 整數序列是不是二進制查找樹的後序周遊結果

這種方法可以判斷兩個連結清單是否相交，但不太容易找出他們的交點。

4、仔細研究兩個連結清單，如果他們相交的話，那麼他們最後的一個節點一定是相同的，否則是不相交的。是以判斷兩個連結清單是否相交就很簡單了，分别周遊到兩個連結清單的尾部，然後判斷他們是否相同，如果相同，則相交；否則不相交。示意圖如下：

80道常見資料結構面試題及其解法 計包含min函數的棧 整數序列是不是二進制查找樹的後序周遊結果

判斷出兩個連結清單相交後就是判斷他們的交點了。假設第一個連結清單長度為len1，第二個問len2，然後找出長度較長的，讓長度較長的連結清單指針向後移動|len1 - len2| (len1-len2的絕對值)，然後在開始周遊兩個連結清單，判斷節點是否相同即可。

下面給出一個簡單的實作：

typedef struct node_t

{

int data;//data

struct node_t *next; //next

}node;

node* find_node(node *head1, node *head2)

{

if(NULL == head1 || NULL == head2)

{

return NULL;//如果有為空的連結清單，肯定是不相交的

}

node *p1, *p2;

p1 = head1;

p2 = head2;

int len1 = 0;

int len2 =0;

int diff = 0;

while(NULL != p1->next)

{

p1 = p1->next;

len1++;

}

while(NULL != p2->next)

{

p2 = p2->next;

len2++;

}

if(p1 != p2) //如果最後一個節點不相同,傳回NULL

{

return NULL;

}

diff = abs(len1 - len2);

if(len1 > len2)

{

p1 = head1;

p2 = head2;

}

else

{

p1 = head2;

p2 = head1;

}

for(int i=0; i<diff; i++)

{

p1 = p1->next;

}

while(p1 != p2)

{

p1 = p1->next;

p2 = p2->next;

}

return p1;

}

通過上面的操作就可以找到兩個連結清單的交點了。

8  逆轉單向連結清單 

點選(此處)折疊或打開

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. //定義連結清單的節點。
  5. struct Link {
  6.     Link* next;
  7.     int value;
  8. };
  9. //遞歸方式：逆轉單向連結清單
  10. Link* reverse1(Link *head) 
  11. {
  12.     if(head == NULL ) return NULL;
  13.     if(head->next == NULL) return head;
  14.     Link* tail = NULL;
  15.     Link* temp = head->next;
  16.     tail = reverse1(head->next);
  17.     temp->next = head;
  18.     head->next = NULL;
  19.     return tail;
  20. }
  21. //非遞歸方式：逆轉單向連結清單 
  22. void reverse(Link **head) 
  23. {
  24.     if(!head || !(*head)) return;
  25.     Link *pre, *cur, *nex;
  26.     pre = NULL, cur=*head;
  27.     while(cur) {
  28.         nex = cur -> next;
  29.         cur->next = pre;
  30.         pre = cur;
  31.         cur = nex;
  32.     }
  33.     *head = pre;
  34. }
  35. //輸出整個連結清單
  36. void printLink(Link *head)
  37. {
  38.     Link *curr = head;
  39.     while(curr) {
  40.         printf("%d ", curr->value);
  41.         curr = curr->next;
  42.     }
  43.     printf("\n");
  44. }
  45. int main(void)
  46. {
  47.     Link *head, *p[10], *newhead;
  48.     int num = 10;
  49.     for(int i=0; i<num; i++) {
  50.         p[i] = new Link();
  51.         p[i]->next = NULL;
  52.         p[i]->value = i+1;
  53.         if (i==0) head = p[i];
  54.         else p[i-1]->next = p[i];
  55.     }
  56.     printLink(head);
  57.     reverse(&head);
  58.     printLink(head);
  59.     for(int i=0; i<num; i++) delete p[i];
  60.     system("pause");
  61. }
9：

整數序列是不是二進制查找樹的後序周遊結果

題目：輸入一個整數數組，判斷該數組是不是某二進制查找樹的後序周遊的結果。如果是傳回true，否則傳回false。

例如輸入5、7、6、9、11、10、8，由于這一整數序列是如下樹的後序周遊結果：

         8

       /  \

      6    10

    / \    / \

   5   7   9  11

是以傳回true。

如果輸入7、4、6、5，沒有哪棵樹的後序周遊的結果是這個序列，是以傳回false。

樹的題目一般都是遞歸的思路，因為是因為是排序樹，而且是後序，是以思路是序列最後一個必是根節點，從前往後周遊，比根節點小的都是其左子樹，并且位于序列的左半部分，比其大的為其右子樹，應該位于其右半部分。左右子樹按上述思路分别進行判斷。

代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include<iostream>

using

namespace

std;

void

test(

const

int

data[],

int

start,

int

node,

bool

&flag){

if

(flag&&start<node){       

// 判斷條件，注意start<node

int

left=start;

while

(data[node]>data[left]){  

//取得其左子樹

left++;                      

}

for

(

int

j=left;j<node;j++){      

//判斷是否為其右子樹

if

(data[j]<data[node]) {flag=

false

;

return

;}

//若

}

test(data,0,left-1,flag);          

//遞歸

test(data,left,node-1,flag);

}

}

int

main(

void

){

bool

flag=

true

;

int

a[]={5,7,6,9,11,10,8};

test(a,0,6,flag);

if

(flag) cout<<

"yes"

<<endl;

else

cout<<

"no"

<<endl;

int

b[]={7,4,6,5};

test(b,0,3,flag);

if

(flag) cout<<

"yes"

<<endl;

else

cout<<

"no"

<<endl;

system

(

"pause"

);

return

0;

}

二進制查找樹的定義為：

（1）若左子樹不空，則左子樹上所有節點的值均小于其根節點的值。

（2）若右子樹不空，則右子樹上所有節點的值均小于其跟節點的值

（3）其左右子樹也均為二叉查找樹。

那麼先給定一個數字序列5、7、6、9、11、10、8，判斷這個序列是否是二進制查找樹的後根周遊。可以回想一下後序周遊的性質，先通路左子樹，然後通路右子樹，最後通路根節點。結合以上這些性質，就可以了解到，應該從給定序列的最後一個元素開始，最後一個元素設定為根節點，循環周遊一次數組，找左右子樹的分界點，上面這個例子就是6,9之間。這樣可以判斷，5、6、7,這三個數為以8為根節點的左子樹上的節點，9、11、10為以8為根節點的右子樹的根節點。如果在對以上分出來的兩個數組做同樣的操作，那麼就可以解決這個問題。綜上所述，可以應用遞歸方法，遞歸的關鍵是找到結束的條件。下面給出代碼，并進行兩組測試。

[cpp]  view plain  copy

  1. #include<stdio.h>  
  2. #include<assert.h>  
  3. int verify_is_post(int *s,int length)  
  4. {  
  5.     assert(s!=NULL);  
  6.     assert(length>0);  
  7.     int i,j;  
  8.     int root=s[length-1];  
  9.     for(i=0;i<length-1;i++)  
  10.     {  
  11.         if(s[i]>root)  
  12.             break;  
  13.     }  
  14.     for(j=i;j<length-1;j++)  
  15.     {  
  16.         if(s[j]<root)  
  17.             return 0;  
  18.     }  
  19.     int left=1;  
  20.     if(i>0)  
  21.     {  
  22.         left=verify_is_post(s,i);//分界點左側數組  
  23.     }  
  24.     int right=1;  
  25.     if(i<length-1)  
  26.     {  
  27.         right=verify_is_post(s+i,length-i-1);//分界點右側數組  
  28.     }  
  29.     return left&&right;  
  30. }  
  31. void main()  
  32. {  
  33.     int s1[]={5,7,6,9,11,10,8};  
  34.     int s2[]={7,4,6,5,8};  
  35.     int length1=sizeof(s1)/sizeof(int);  
  36.     int result1=verify_is_post(s1,length1);  
  37.     if(result1)  
  38.         printf("yes,it is the post-order traversal.\n");  
  39.     else  
  40.         printf("no,it is not the post-order traversal.\n");  
  41.     int length2=sizeof(s2)/sizeof(int);  
  42.     int result2=verify_is_post(s2,length2);  
  43.     if(result2)  
  44.         printf("yes,it is the post-order traversal.\n");  
  45.     else  
  46.         printf("no,it is not the post-order traversal.\n");  
  47. }  
上一篇: iSystem調試器系列文章—3.CPU特定架構設定iSystem調試器系列文章—3.CPU特定架構設定3.1 調試接口3.2 CPU複位
下一篇: [Cloud Networking Notes] Management and sharing of network infrastructure in cloud data centersTargets and MotivationsVL2 Design