程式設計師面試演算法題

　　世界上第一位程式設計師是英國著名詩人拜倫的女兒AdaLovelace曾設計了巴貝奇分析機上解伯努利方程的一個程式。她甚至還建立了迴圈和子程式的概念。下面就由小編為大家介紹一下的文章，歡迎閱讀。

　　篇1

　　題目：輸入一棵二元查詢樹，將該二元查詢樹轉換成一個排序的雙向連結串列。要求不能建立任何新的結點，只調整指標的指向。

　　/ \

　　6 14

　　/ \ /　 \

　　4 8 12 　 16

　　轉換成雙向連結串列

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

　　思路一：當我們到達某一個節點準備調整以該節點為根節點的子數時，先調整其左子樹將左子樹轉換成一個排好序的左子連結串列，再調整其右子樹轉換成右子連結串列。最近連結左子連結串列的最右節點、當前節點和右子連結串列的最左節點。從樹的根節點開始遞迴調整所有節點。

　　思路二：我們可以中序遍歷整個樹。按照這個方式遍歷樹，比較小的節點優先訪問。如果我們每訪問一個節點，假設之前訪問過的節點已經調整為一個排序的雙向連結串列，我們再把調整當前節點的指標連結到連結串列的末尾。當所有的節點都訪問過之後，整棵樹也就轉換成一個排序的雙向連結串列了。

　　參考程式碼：

　　二元查詢樹的節點資料結構：

　　structBSTreeNode{

　　int value;

　　BSTreeNode *m_left;

　　BSTreeNode *m_right;

　　}

　　思路二對應的程式碼：

　　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

　　在陣列中，數字減去它右邊的數字得到一個數對之差。求所有數對之差的最大值。例如在陣列{2, 4, 1, 16, 7, 5, 11, 9}中，數對之差的最大值是11，是16減去5的結果。

　　動態規劃法：

　　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

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

　　例如輸入整數22和如下二元樹

　　/ \

　　5 12

　　/ \

　　4 7

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

　　二元樹結點的資料結構定義為：

　　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

　　};

　　分析：這是百度的一道筆試題，考查對樹這種基本資料結構以及遞迴函式的理解。

　　當訪問到某一結點時，把該結點新增到路徑上，並累加當前結點的值。如果當前結點為葉結點並且當前路徑的和剛好等於輸入的整數，則當前的路徑符合要求，我們把它打印出來。如果當前結點不是葉結點，則繼續訪問它的子結點。當前結點訪問結束後，遞迴函式將自動回到父結點。因此我們在函式退出之前要在路徑上刪除當前結點並減去當前結點的值，以確保返回父結點時路徑剛好是根結點到父結點的路徑。我們不難看出儲存路徑的資料結構實際上是一個棧結構，因為路徑要與遞迴呼叫狀態一致，而遞迴呼叫本質就是一個壓棧和出棧的過程。

　　參考程式碼：

　　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<

　　}