最近找工作看到了一篇數(shù)據(jù)結(jié)構(gòu)與算法題的結(jié)構(gòu)的面試題集合覺得還不錯(cuò)飒硅，正好這方面是自己的弱點(diǎn)，正好現(xiàn)在開始補(bǔ)一補(bǔ)浸须。數(shù)據(jù)結(jié)構(gòu)與算法面試題80道
下面從第一題開始一道一道開始擼
1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表
題目：
輸入一棵二元查找樹移怯，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。
要求不能創(chuàng)建任何新的結(jié)點(diǎn)和橙，只調(diào)整指針的指向仔燕。
10
/ \
6 14
/ \ / \
4 8 12 16
轉(zhuǎn)換成雙向鏈表
4=6=8=10=12=14=16。
首先我們定義的二元查找樹 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
據(jù)說這是微軟面試題魔招，像這種有關(guān)樹的題基本上都需要用到遞歸算法
解題思路：我們可以中序遍歷整棵樹晰搀。按照這個(gè)方式遍歷樹，比較小的結(jié)點(diǎn)先訪問办斑。如果我們每訪問一個(gè)結(jié)點(diǎn)外恕，假設(shè)之前訪問過的結(jié)點(diǎn)已經(jīng)調(diào)整成一個(gè)排序雙向鏈表，我們?cè)侔颜{(diào)整當(dāng)前結(jié)點(diǎn)的指針將其鏈接到鏈表的末尾。當(dāng)所有結(jié)點(diǎn)都訪問過之后吁讨，整棵樹也就轉(zhuǎn)換成一個(gè)排序雙向鏈表了髓迎。
///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
// pLastNodeInList - the tail of the double-linked list
///////////////////////////////////////////////////////////////////////
void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
{
if(pNode == NULL)
return;
// 獲取當(dāng)前的節(jié)點(diǎn)
BSTreeNode *pCurrent = pNode;
// Convert the left sub-tree
// 如果有做節(jié)點(diǎn)就遞歸遍歷左節(jié)點(diǎn)
if (pCurrent->m_pLeft != NULL)
ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
// Put the current node into the double-linked list
// 如果沒有左節(jié)點(diǎn)就把已經(jīng)排序好的鏈表放到當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)
// 通俗的說就是把當(dāng)前節(jié)點(diǎn)排到鏈表的末尾
pCurrent->m_pLeft = pLastNodeInList;
if(pLastNodeInList != NULL)
pLastNodeInList->m_pRight = pCurrent;//雙向鏈表要把右節(jié)點(diǎn)也填上
// 把指針挪到了鏈表的未結(jié)點(diǎn)
pLastNodeInList = pCurrent;
// Convert the right sub-tree
//如果右節(jié)點(diǎn)的話接著遞歸進(jìn)行中序遍歷
if (pCurrent->m_pRight != NULL)
ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}
///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
{
//初始化一個(gè)空的鏈表 作為結(jié)果
BSTreeNode *pLastNodeInList = NULL;
ConvertNode(pHeadOfTree, pLastNodeInList);
// Get the head of the double-linked list
BSTreeNode *pHeadOfList = pLastNodeInList;
while(pHeadOfList && pHeadOfList->m_pLeft)
pHeadOfList = pHeadOfList->m_pLeft;
return pHeadOfList;
}
具體的已經(jīng)寫注釋啦 遞歸的特點(diǎn)就是代碼簡(jiǎn)單，但是理解起來(lái)比較復(fù)雜
2.定義棧的數(shù)據(jù)結(jié)構(gòu)建丧， 要求添加一個(gè) min 函數(shù)排龄， 能夠得到棧的最小元素。 要求函數(shù) min翎朱、 push 以及 pop 的時(shí)間復(fù)雜度都是 O(1)
剛開始解這道題目的時(shí)候橄维，感覺不是很難，只需在棧的數(shù)據(jù)結(jié)構(gòu)中加一個(gè)選項(xiàng)min就OK了拴曲，這樣就可以記錄最小值争舞。但是這個(gè)思路有一個(gè)硬傷，那就是第一次調(diào)用min函數(shù)時(shí)澈灼，是可以直接獲取到最小值竞川，但是如果調(diào)用pop()函數(shù)將最小值出棧過后，再給min賦值時(shí)叁熔，就需要進(jìn)行查找比較了委乌，那樣就不滿足題目要求，min函數(shù)的復(fù)雜度為1. 既然如此荣回，那我們是否可以記錄下每push進(jìn)一個(gè)數(shù)據(jù)時(shí)當(dāng)前的min值遭贸，每一次發(fā)生變化就將當(dāng)前的min值壓入到一個(gè)數(shù)組中，這樣就可以解決上述問題心软。因此這道題目的難點(diǎn)我認(rèn)為就是數(shù)組設(shè)計(jì)是否合理壕吹。
設(shè)計(jì)了以下的數(shù)組結(jié)構(gòu)：
源程序如下：
#include<iostream>
using namespace std;
#define MAXSIZE 100
typedef int ElemType;
struct Stack{
int top;//當(dāng)前棧頂位置
int index;//當(dāng)前最小min位置
ElemType data[MAXSIZE];//存儲(chǔ)棧的數(shù)據(jù)
ElemType minData[MAXSIZE];//存儲(chǔ)最小值的合集
int min;//記錄最小值（預(yù)留）
};
//初始化棧
bool InitStack(Stack* ptr){
ptr->top = 0;
ptr->index = 0;
ptr->min = 0;
return true;
}
bool push(Stack* ptr, ElemType elem){
//首先需要判斷棧是否已滿
if(MAXSIZE-1 == ptr->top){
cout << "Stack is full, cannot push data anymore!" << endl;
return false;
}
//判斷是否是第一個(gè)壓入棧的數(shù)據(jù),將最小值存儲(chǔ)到minStack中
if(0 == ptr->top){
// 第一個(gè)數(shù)據(jù)直接賦值成最小值
ptr->min = elem;
// 注意此處是后++ 計(jì)算完再++
ptr->minData[ptr->index++] = elem;
} else if(elem <= ptr->min){//如果入棧的數(shù)據(jù)比當(dāng)前最小值小
ptr->min = elem;
// 最小值如果更改了就把更改狀態(tài)的值存進(jìn)去，里面的數(shù)值可能是重復(fù)的
ptr->minData[ptr->index++] = ptr->min;
}
// 把值存到數(shù)據(jù)的棧的數(shù)組中
ptr->data[(ptr->top)++] = elem;
return true;
}
ElemType pop(Stack* ptr, ElemType* elem){
//判斷棧是否為空
if(0 == ptr->top){
cout << "stack is empty, cannot pop data anymore!" << endl;
return -65535;
}
// 因?yàn)閜ush的時(shí)候已經(jīng)進(jìn)行了后++ 删铃，所以此處想獲取當(dāng)前的位置就先--
*elem = ptr->data[--(ptr->top)];
int i = ptr->index - 1;
if(*elem == ptr->minData[i]){
--(ptr->index);
}
return *elem;
}
ElemType minMethod(Stack* ptr){
// 此處維護(hù)了一個(gè)數(shù)組耳贬，所以時(shí)間復(fù)雜度為1
return ptr->minData[--(ptr->index)];
}
// data 5,4,4,4
// min 5,4,4,4
int main() {
Stack ptr;
int elem;
// 初始化棧
InitStack(&ptr);
push(&ptr, 5);
push(&ptr, 4);
push(&ptr, 4);
push(&ptr, 4);
// cout << "pop1: " << pop(&ptr, &elem) << endl;
// push(&ptr, 8);
pop(&ptr, &elem);
pop(&ptr, &elem);
pop(&ptr, &elem);
// cout << "pop2: " << pop(&ptr, &elem) << endl;
cout << "minMethod: " << minMethod(&ptr) << endl;
return 0;
}
