http://www.cnblogs.com/mfryf/archive/2012/07/31/2616697.html
1.一個(gè)整數(shù)數(shù)列，元素取值可能是0~65535中的任意一個(gè)數(shù)，相同數(shù)值不會(huì)重復(fù)出現(xiàn)。0是例外，可以反復(fù)出現(xiàn)。
請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，當(dāng)你從該數(shù)列中隨意選取5個(gè)數(shù)值，判斷這5個(gè)數(shù)值是否連續(xù)相鄰。
注意：
- 5個(gè)數(shù)值允許是亂序的。比如： 8 7 5 0 6
- 0可以通配任意數(shù)值。比如：8 7 5 0 6 中的0可以通配成9或者4
- 0可以多次出現(xiàn)。
- 復(fù)雜度如果是O(n2)則不得分。
思路：非0最大-非0最小+1 <=5 ==> 非0最大-非0最小 <=4
2.設(shè)計(jì)一個(gè)算法，找出二叉樹(shù)上任意兩個(gè)結(jié)點(diǎn)的最近共同父結(jié)點(diǎn)。
復(fù)雜度如果是O(n2)則不得分。
思路：如果每個(gè)節(jié)點(diǎn)包含父親指針，把兩個(gè)節(jié)點(diǎn)到根的路徑都記錄下來(lái)，兩條路徑的最后面的元素肯定相同，從兩條路徑的最后一個(gè)元素向前比較，直到第一次出現(xiàn)分叉為止，就可以找到最近節(jié)點(diǎn)。復(fù)雜度為O（n），路徑最長(zhǎng)可能是n。如果不包含父親節(jié)點(diǎn)，那就先前序遍歷二叉樹(shù)，遍歷的時(shí)候可以像哈夫曼樹(shù)那樣左右01編號(hào)，記錄給定兩節(jié)點(diǎn)的到達(dá)路徑，最后比較兩個(gè)0，1序列的前面位數(shù)，直到出現(xiàn)不相等為止，就找到最近父節(jié)點(diǎn)，復(fù)雜度也是O（n）
3.一棵排序二叉樹(shù)，令 f=(最大值+最小值)/2，設(shè)計(jì)一個(gè)算法，找出距離f值最近、大于f值的結(jié)點(diǎn)。
復(fù)雜度如果是O(n2)則不得分。
思路：找出最大值，最小值，復(fù)雜度都是O（h），然后搜索f，可以找到f應(yīng)該插入的位置，復(fù)雜度也是O（h），再找f的后繼，復(fù)雜度也是O（h），h最大可能是n，所以總體最壞情況復(fù)雜度就是O（n）
4.一個(gè)整數(shù)數(shù)列，元素取值可能是1~N（N是一個(gè)較大的正整數(shù)）中的任意一個(gè)數(shù)，相同數(shù)值不會(huì)重復(fù)出現(xiàn)。設(shè)計(jì)一個(gè)算法，找出數(shù)列中符合條件的數(shù)對(duì)的個(gè)數(shù)，滿(mǎn)足數(shù)對(duì)中兩數(shù)的和等于N+1。
復(fù)雜度最好是O(n)，如果是O(n2)則不得分。
思路：先排序，復(fù)雜度O（nlgn），然后用兩個(gè)指示器（front和back）分別指向第一個(gè)和最后一個(gè)元素，
如果A[front]+A[back]>N+1，則back–；
如果A[front]+A[back]=N+1，則計(jì)數(shù)器加1，back–，同時(shí)front++；
如果A[front]+A[back]重復(fù)上述步驟，O（n）時(shí)間找到所有數(shù)對(duì)，總體復(fù)雜度為O（nlgn）
5.輸入一棵二元查找樹(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。
首先我們定義的二元查找樹(shù)?節(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
};
思路一：當(dāng)我們到達(dá)某一結(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)（左子樹(shù)的最大結(jié)點(diǎn)）、當(dāng)前結(jié)點(diǎn)和右子鏈表的最左結(jié)點(diǎn)（右子樹(shù)的最小結(jié)點(diǎn)）。從樹(shù)的根結(jié)點(diǎn)開(kāi)始遞歸調(diào)整所有結(jié)點(diǎn)。
思路一對(duì)應(yīng)的代碼：
BSTreeNode*?ConvertNode(BSTreeNode*?pNode,?bool?asRight){
if(!pNode)
return?NULL;
BSTreeNode?*pLeft?=?NULL;
BSTreeNode?*pRight?=?NULL;
//?Convert?the?left?sub-tree
if(pNode->m_pLeft)
pLeft?=?ConvertNode(pNode->m_pLeft,?false);
//?Connect?the?greatest?node?in?the?left?sub-tree?to?the?current?node
if(pLeft)
{
pLeft->m_pRight?=?pNode;
pNode->m_pLeft?=?pLeft;
}
//?Convert?the?right?sub-tree
if(pNode->m_pRight)
pRight?=?ConvertNode(pNode->m_pRight,?true);
//?Connect?the?least?node?in?the?right?sub-tree?to?the?current?node
if(pRight){
pNode->m_pRight?=?pRight;
pRight->m_pLeft?=?pNode;
}
BSTreeNode?*pTemp?=?pNode;
//?If?the?current?node?is?the?right?child?of?its?parent,
//?return?the?least?node?in?the?tree?whose?root?is?the?current?node
if(asRight){
while(pTemp->m_pLeft)
pTemp?=?pTemp->m_pLeft;
}
//?If?the?current?node?is?the?left?child?of?its?parent,
//?return?the?greatest?node?in?the?tree?whose?root?is?the?current?node
else{
while(pTemp->m_pRight)
pTemp?=?pTemp->m_pRight;
}
return?pTemp;
}
BSTreeNode*?Convert(BSTreeNode*?pHeadOfTree)
{
//?As?we?want?to?return?the?head?of?the?sorted?double-linked?list,
//?we?set?the?second?parameter?to?be?true
return?ConvertNode(pHeadOfTree,?true);
}
思路二：
我們可以中序遍歷整棵樹(shù)。按照這個(gè)方式遍歷樹(shù)，比較小的結(jié)點(diǎn)先訪(fǎng)問(wèn)。如果我們每訪(fǎng)問(wèn)一個(gè)結(jié)點(diǎn)，假設(shè)之前訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)已經(jīng)調(diào)整成一個(gè)排序雙向鏈表，我們?cè)侔颜{(diào)整當(dāng)前結(jié)點(diǎn)的指針將其鏈接到鏈表的末尾。當(dāng)所有結(jié)點(diǎn)都訪(fǎng)問(wèn)過(guò)之后，整棵樹(shù)也就轉(zhuǎn)換成一個(gè)排序雙向鏈表了。
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;
}
6.設(shè)計(jì)包含min函數(shù)的棧。定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min函數(shù)，能夠得到棧的最小元素。要求函數(shù)min、push以及pop的時(shí)間復(fù)雜度都是O(1)。
思路：這是google的一道面試題。
看到這道題目時(shí)，第一反應(yīng)就是每次push一個(gè)新元素時(shí)，將棧里所有逆序元素排序。這樣棧頂元素將是最小元素。但由于不能保證最后push進(jìn)棧的元素最先出棧，這種思路設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)已經(jīng)不是一個(gè)棧了。
在棧里添加一個(gè)成員變量存放最小元素（或最小元素的位置）。每次push一個(gè)新元素進(jìn)棧的時(shí)候，如果該元素比當(dāng)前的最小元素還要小，則更新最小元素。
乍一看這樣思路挺好的。但仔細(xì)一想，該思路存在一個(gè)重要的問(wèn)題：如果當(dāng)前最小元素被pop出去，如何才能得到下一個(gè)最小元素？
因此僅僅只添加一個(gè)成員變量存放最小元素（或最小元素的位置）是不夠的。我們需要一個(gè)輔助棧。每次push一個(gè)新元素的時(shí)候，同時(shí)將最小元素push到輔助棧中；
//或最小元素的位置?？紤]到棧元素的類(lèi)型可能是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，用最小元素的位置將能減少空間消耗。
每次pop一個(gè)元素出棧的時(shí)候，同時(shí)pop輔助棧。
參考代碼：
#include?
#include?
template??class?CStackWithMin
{
public:
CStackWithMin(void)?{}
virtual?~CStackWithMin(void)?{}
T&?top(void);
const?T&?top(void)?const;
void?push(const?T&?value);
void?pop(void);
const?T&?min(void)?const;
private:
T>m_data;//?theelements?of?stack
size_t>m_minIndex;//?the?indicesof?minimum?elements
};
//?get?the?last?element?of?mutable?stack
template??T&?CStackWithMin::top()
{
return?m_data.back();
}
//?get?the?last?element?of?non-mutable?stack
template??const?T&?CStackWithMin::top()?const
{
return?m_data.back();
}
//?insert?an?elment?at?the?end?of?stack
template??void?CStackWithMin::push(const?T&?value)
{
//?append?the?data?into?the?end?of?m_data
m_data.push_back(value);
//?set?the?index?of?minimum?elment?in?m_data?at?the?end?of?m_minIndex
if(m_minIndex.size()?==?0)
m_minIndex.push_back(0);
else
{
if(value?<?m_data[m_minIndex.back()])
m_minIndex.push_back(m_data.size()?-?1);
else
m_minIndex.push_back(m_minIndex.back());
}
}
//?erease?the?element?at?the?end?of?stack
template??void?CStackWithMin::pop()
{
//?pop?m_data
m_data.pop_back();
//?pop?m_minIndex
m_minIndex.pop_back();
}
//?get?the?minimum?element?of?stack
template??const?T&?CStackWithMin::min()?const
{
assert(m_data.size()?>?0);
assert(m_minIndex.size()?>?0);
return?m_data[m_minIndex.back()];
}
6.求子數(shù)組的最大和（更高效的思路見(jiàn)編程珠璣83頁(yè)）
題目：輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。
數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。
求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。
例如輸入的數(shù)組為1,?-2,?3,?10,?-4,?7,?2,?-5，和最大的子數(shù)組為3,?10,?-4,?7,?2，
因此輸出為該子數(shù)組的和18。
如果不考慮時(shí)間復(fù)雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。
不過(guò)非常遺憾的是，由于長(zhǎng)度為n的數(shù)組有O(n2)個(gè)子數(shù)組；
而且求一個(gè)長(zhǎng)度為n的數(shù)組的和的時(shí)間復(fù)雜度為O(n)。因此這種思路的時(shí)間是O(n3)。
當(dāng)我們加上一個(gè)正數(shù)時(shí)，和會(huì)增加；當(dāng)我們加上一個(gè)負(fù)數(shù)時(shí)，和會(huì)減少。
如果當(dāng)前得到的和是個(gè)負(fù)數(shù)，那么這個(gè)和在接下來(lái)的累加中應(yīng)該拋棄并重新清零，
不然的話(huà)這個(gè)負(fù)數(shù)將會(huì)減少接下來(lái)的和。基于這樣的思路，我們可以寫(xiě)出如下代碼。
參考代碼：
//?Find?the?greatest?sum?of?all?sub-arrays
//?Return?value:?if?the?input?is?valid,?return?true,?otherwise?return?false
/////////////////////////////////////////////////////////////////////////////
bool?FindGreatestSumOfSubArray(
int?*pData,???????????//?an?array
unsigned?int?nLength,?//?the?length?of?array
int?&nGreatestSum?????//?the?greatest?sum?of?all?sub-arrays
)
{
//?if?the?input?is?invalid,?return?false
if((pData?==?NULL)?||?(nLength?==?0))
return?false;
int?nCurSum?=?nGreatestSum?=?0;
for(unsigned?int?i?=?0;?i?<?nLength;?++i)
{
nCurSum?+=?pData[i];
//?if?the?current?sum?is?negative,?discard?it
if(nCurSum?<?0)
nCurSum?=?0;
//?if?a?greater?sum?is?found,?update?the?greatest?sum
if(nCurSum?>?nGreatestSum)
nGreatestSum?=?nCurSum;
}
//?if?all?data?are?negative,?find?the?greatest?element?in?the?array
if(nGreatestSum?==?0)
{
nGreatestSum?=?pData[0];
for(unsigned?int?i?=?1;?i?<?nLength;?++i)
{
if(pData[i]?>?nGreatestSum)
nGreatestSum?=?pData[i];
}
}
return?true;
}
7.題目：輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開(kāi)。
為簡(jiǎn)單起見(jiàn)，標(biāo)點(diǎn)符號(hào)和普通字母一樣處理。
例如輸入“I?am?a?student.”，則輸出“student.?a?am?I”。
思路1：先將整個(gè)英文句子翻轉(zhuǎn)，這樣一來(lái)每個(gè)單詞也都翻轉(zhuǎn)了，在將每個(gè)單詞翻轉(zhuǎn)回去即可！
思路2：參照autoreleasepool添加哨兵指針的方式，第一次遍歷給每個(gè)單詞開(kāi)頭安插一個(gè)哨兵（index），然后將哨兵入棧。遍歷完成后從棧頂開(kāi)始遍歷每個(gè)哨兵并輸出哨兵索引對(duì)應(yīng)的單詞。
