程序員面試算法題

　　世界上第一位程序員是英國(guó)著名詩(shī)人拜倫的女兒AdaLovelace曾設(shè)計(jì)了巴貝奇分析機(jī)上解伯努利方程的一個(gè)程序。她甚至還建立了循環(huán)和子程序的概念。下面就由學(xué)習(xí)啦小編為大家介紹一下程序員面試算法題的文章，歡迎閱讀。

　　程序員面試算法題篇1

　　題目：輸入一棵二元查找樹(shù)，將該二元查找樹(shù)轉(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。

　　思路一：當(dāng)我們到達(dá)某一個(gè)節(jié)點(diǎn)準(zhǔn)備調(diào)整以該節(jié)點(diǎn)為根節(jié)點(diǎn)的子數(shù)時(shí)，先調(diào)整其左子樹(shù)將左子樹(shù)轉(zhuǎn)換成一個(gè)排好序的左子鏈表，再調(diào)整其右子樹(shù)轉(zhuǎn)換成右子鏈表。最近鏈接左子鏈表的最右節(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)和右子鏈表的最左節(jié)點(diǎn)。從樹(shù)的根節(jié)點(diǎn)開(kāi)始遞歸調(diào)整所有節(jié)點(diǎn)。

　　思路二：我們可以中序遍歷整個(gè)樹(shù)。按照這個(gè)方式遍歷樹(shù)，比較小的節(jié)點(diǎn)優(yōu)先訪問(wèn)。如果我們每訪問(wèn)一個(gè)節(jié)點(diǎn)，假設(shè)之前訪問(wèn)過(guò)的節(jié)點(diǎn)已經(jīng)調(diào)整為一個(gè)排序的雙向鏈表，我們?cè)侔颜{(diào)整當(dāng)前節(jié)點(diǎn)的指針鏈接到鏈表的末尾。當(dāng)所有的節(jié)點(diǎn)都訪問(wèn)過(guò)之后，整棵樹(shù)也就轉(zhuǎn)換成一個(gè)排序的雙向鏈表了。

　　參考代碼：

　　二元查找樹(shù)的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)：

　　structBSTreeNode{

　　int value;

　　BSTreeNode *m_left;

　　BSTreeNode *m_right;

　　}

　　思路二對(duì)應(yīng)的代碼：

　　void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)

　　{

　　if(pNode == NULL)

　　return;

　　BSTreeNode *pCurrent = pNode;

　　// Convert the left sub-tree

　　if (pCurrent->m_pLeft != NULL)

　　ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

　　// Put the current node into the double-linked list

　　pCurrent->m_pLeft = pLastNodeInList;

　　if(pLastNodeInList != NULL)

　　pLastNodeInList->m_pRight = pCurrent;

　　pLastNodeInList = pCurrent;

　　// Convert the right sub-tree

　　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)

　　{

　　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;

　　}

　　程序員面試算法題篇2

　　在數(shù)組中，數(shù)字減去它右邊的數(shù)字得到一個(gè)數(shù)對(duì)之差。求所有數(shù)對(duì)之差的最大值。例如在數(shù)組{2, 4, 1, 16, 7, 5, 11, 9}中，數(shù)對(duì)之差的最大值是11，是16減去5的結(jié)果。

　　動(dòng)態(tài)規(guī)劃法：

　　double maxDif(vector v)

　　{ double max_dif = DBL_MIN;

　　double loc_min = DBL_MAX;

　　for(int i=v.size()-1;i>=0;i--) {

　　if (v[i] < loc_min) loc_min = v[i];

　　else if (v[i] - loc_min > max_dif) max_dif = v[i] - loc_min;

　　}

　　return max_dif; }

　　程序員面試算法題篇3

　　輸入一個(gè)整數(shù)和一棵二元樹(shù)。從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下訪問(wèn)一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。

　　例如輸入整數(shù)22和如下二元樹(shù)

　　10

　　/ \

　　5 12

　　/ \

　　4 7

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

　　二元樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為：

　　struct BinaryTreeNode // a node in the binary tree

　　{

　　int m_nValue; // value of node

　　BinaryTreeNode *m_pLeft; // left child of node

　　BinaryTreeNode *m_pRight; // right child of node

　　};

　　分析：這是百度的一道筆試題，考查對(duì)樹(shù)這種基本數(shù)據(jù)結(jié)構(gòu)以及遞歸函數(shù)的理解。

　　當(dāng)訪問(wèn)到某一結(jié)點(diǎn)時(shí)，把該結(jié)點(diǎn)添加到路徑上，并累加當(dāng)前結(jié)點(diǎn)的值。如果當(dāng)前結(jié)點(diǎn)為葉結(jié)點(diǎn)并且當(dāng)前路徑的和剛好等于輸入的整數(shù)，則當(dāng)前的路徑符合要求，我們把它打印出來(lái)。如果當(dāng)前結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則繼續(xù)訪問(wèn)它的子結(jié)點(diǎn)。當(dāng)前結(jié)點(diǎn)訪問(wèn)結(jié)束后，遞歸函數(shù)將自動(dòng)回到父結(jié)點(diǎn)。因此我們?cè)诤瘮?shù)退出之前要在路徑上刪除當(dāng)前結(jié)點(diǎn)并減去當(dāng)前結(jié)點(diǎn)的值，以確保返回父結(jié)點(diǎn)時(shí)路徑剛好是根結(jié)點(diǎn)到父結(jié)點(diǎn)的路徑。我們不難看出保存路徑的數(shù)據(jù)結(jié)構(gòu)實(shí)際上是一個(gè)棧結(jié)構(gòu)，因?yàn)槁窂揭c遞歸調(diào)用狀態(tài)一致，而遞歸調(diào)用本質(zhì)就是一個(gè)壓棧和出棧的過(guò)程。

　　參考代碼：

　　void FindPath(BinaryTreeNode* pTreeNode,int expectedSum,std::vector& path,int& currentSum)

　　{

　　if(!pTreeNode) return ;

　　currentSum+=pTreeNode->m_nValue;

　　path.push_back(pTreeNode->m_nValue);

　　bool isLeaf=(!pTreeNode->m_pLeft && !pTreeNode->m_pRight);

　　if(currentSum== expectedSum && isLeaf){

　　std::vector::iterator iter=path.begin();

　　for(;iter!=path.end();++iter) std::cout<<*iter<<'\t';

　　std::cout<

　　}

　　if(pTreeNode->mpLeft) FindPath(pTreeNode->m_pLeft,expectedSum,path,currentSum);

　　if(pTreeNode->m_pRight)

　　FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);

　　currentSum -= pTreeNode->m_nValue;

　　path.pop_back();

　　}