算法設(shè)計(jì)題整理

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ù)，滿足數(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)先訪問(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è)排序雙向鏈表了。

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到輔助棧中；

//或最小元素的位置柱嫌》嫣瘢考慮到棧元素的類型可能是復(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)該拋棄并重新清零谴忧，

不然的話這個(gè)負(fù)數(shù)將會(huì)減少接下來(lái)的和〗浅妫基于這樣的思路沾谓，我們可以寫出如下代碼。

參考代碼：

//?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)的單詞稀并。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末仅颇，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子碘举，更是在濱河造成了極大的恐慌忘瓦，老刑警劉巖，帶你破解...
    沈念sama閱讀 212,884評(píng)論 6贊 492
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件引颈，死亡現(xiàn)場(chǎng)離奇詭異耕皮，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)蝙场，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,755評(píng)論 3贊 385
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門凌停，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人售滤，你說(shuō)我怎么就攤上這事罚拟。” “怎么了？”我有些...
    開(kāi)封第一講書人閱讀 158,369評(píng)論 0贊 348
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵舟舒，是天一觀的道長(zhǎng)拉庶。 經(jīng)常有香客問(wèn)我，道長(zhǎng)秃励，這世上最難降的妖魔是什么氏仗？ 我笑而不...
    開(kāi)封第一講書人閱讀 56,799評(píng)論 1贊 285
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮夺鲜，結(jié)果婚禮上皆尔，老公的妹妹穿的比我還像新娘。我一直安慰自己币励，他們只是感情好慷蠕，可當(dāng)我...
    茶點(diǎn)故事閱讀 65,910評(píng)論 6贊 386
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著食呻，像睡著了一般流炕。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上仅胞，一...
    開(kāi)封第一講書人閱讀 50,096評(píng)論 1贊 291
  • 城市分裂傳說(shuō)
    那天每辟，我揣著相機(jī)與錄音，去河邊找鬼干旧。 笑死渠欺，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的椎眯。 我是一名探鬼主播挠将，決...
    沈念sama閱讀 39,159評(píng)論 3贊 411
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼编整！你這毒婦竟也來(lái)了舔稀？” 一聲冷哼從身側(cè)響起，我...
    開(kāi)封第一講書人閱讀 37,917評(píng)論 0贊 268
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤掌测，失蹤者是張志新（化名）和其女友劉穎镶蹋，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體赏半，經(jīng)...
    沈念sama閱讀 44,360評(píng)論 1贊 303
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡贺归，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,673評(píng)論 2贊 327
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了断箫。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片拂酣。...
    茶點(diǎn)故事閱讀 38,814評(píng)論 1贊 341
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖仲义，靈堂內(nèi)的尸體忽然破棺而出婶熬，到底是詐尸還是另有隱情剑勾，我是刑警寧澤，帶...
    沈念sama閱讀 34,509評(píng)論 4贊 334
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布赵颅，位于F島的核電站虽另，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏饺谬。R本人自食惡果不足惜捂刺，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,156評(píng)論 3贊 317
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望募寨。 院中可真熱鬧族展，春花似錦、人聲如沸拔鹰。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 30,882評(píng)論 0贊 21
  • 一樁弒父案，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)列肢。三九已至恰画，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間瓷马，已是汗流浹背拴还。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 32,123評(píng)論 1贊 267
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留决采，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,641評(píng)論 2贊 362
  • 代替公主和親
    正文 我出身青樓坟奥，卻偏偏與公主長(zhǎng)得像树瞭，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子爱谁，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,728評(píng)論 2贊 351

推薦閱讀更多精彩內(nèi)容