程序員面試算法題
程序員面試算法題
世界上第一位程序員是英國著名詩人拜倫的女兒AdaLovelace曾設計了巴貝奇分析機上解伯努利方程的一個程序。她甚至還建立了循環和子程序的概念。下面就由學習啦小編為大家介紹一下程序員面試算法題的文章，歡迎閱讀。
程序員面試算法題篇1
題目：輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只調整指針的指向。
10
/ \
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和如下二元樹
10
/ \
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<
}
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();
}