程序員面試算法題

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

　　程序員面試算法題篇1

　　題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。

　　10

　　/ \

　　6 14

　　/ \ /　 \

　　4 8 12 　 16

　　轉(zhuǎn)換成雙向鏈表

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

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

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

　　參考代碼：

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

　　structBSTreeNode{

　　int value;

　　BSTreeNode *m_left;

　　BSTreeNode *m_right;

　　}

　　思路二對應(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ù)字得到一個數(shù)對之差。求所有數(shù)對之差的最大值。例如在數(shù)組{2, 4, 1, 16, 7, 5, 11, 9}中，數(shù)對之差的最大值是11，是16減去5的結(jié)果。

　　動態(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

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

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

　　10

　　/ \

　　5 12

　　/ \

　　4 7

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

　　二元樹結(jié)點的數(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

　　};

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

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

　　參考代碼：

　　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();

　　}