數(shù)據(jù)結(jié)構(gòu)與算法面試題80道(已修改)
2025-04-07 00:52 本頁(yè)面
【正文】 由于這些題，實(shí)在太火了。所以，應(yīng)廣大網(wǎng)友建議要求，在此把之前已整理公布的前80題，現(xiàn)在，一次性分享出來(lái)。此也算是前80題第一次集體亮相。此些題，已有上萬(wàn)人，看到或見(jiàn)識(shí)到，若私自據(jù)為己有，必定為有知之人識(shí)破，付出代價(jià)。所以，作者聲明:本人July對(duì)以上所有任何內(nèi)容和資料享有版權(quán)，轉(zhuǎn)載請(qǐng)注明作者本人July出處。向你的厚道致敬。謝謝。題目:輸入一棵二元查找樹(shù)，將該二元查找樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。 10/ \614/ \ / \48 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 nodeBSTreeNode *m_pLeft。 // left child of nodeBSTreeNode *m_pRight。 // right child of node}。定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min函數(shù)，能夠得到棧的最小元素。要求函數(shù)min、push以及pop的時(shí)間復(fù)雜度都是O(1)。題目:輸入一個(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。 的所有路徑題目:輸入一個(gè)整數(shù)和一棵二元樹(shù)。從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下訪問(wèn)一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。例如 輸入整數(shù)22和如下二元樹(shù)10/ \512/ \4 7則打印出兩條路徑:10, 12和10, 5, 7。二元樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為:struct BinaryTreeNode // a node in the binary tree{int m_nValue。 // value of nodeBinaryTreeNode *m_pLeft。 // left child of nodeBinaryTreeNode *m_pRight。 // right child of node}。題目:輸入n個(gè)整數(shù)，輸出其中最小的k個(gè)。例如輸入1，2，3，4，5，6，7和8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字為1，2，3和4。第6題騰訊面試題:給你10分鐘時(shí)間，根據(jù)上排給出十個(gè)數(shù)，在其下排填出對(duì)應(yīng)的十個(gè)數(shù)要求下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)。上排的十個(gè)數(shù)如下:【0，1，2，3，4，5，6，7，8，9】舉一個(gè)例子，數(shù) : 0,1,2,3,4,5,6,7,8,9分配: 6,2,1,0,0,0,1,0,0,00在下排出現(xiàn)了6次，1在下排出現(xiàn)了2次，2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次....以此類(lèi)推..第7題微軟亞院之編程判斷倆個(gè)鏈表是否相交給出倆個(gè)單向鏈表的頭指針，比如h1，h2，判斷這倆個(gè)鏈表是否相交。為了簡(jiǎn)化問(wèn)題，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。問(wèn)題擴(kuò)展:??第8題此貼選一些 比較怪的題，由于其中題目本身與算法關(guān)系不大，僅考考思維。特此并作一題。，一間房里有三盞燈，另一間房有控制著三盞燈的三個(gè)開(kāi)關(guān)，這兩個(gè)房間是 分割開(kāi)的，從一間里不能看到另一間的情況?，F(xiàn)在要求受訓(xùn)者分別進(jìn)這兩房間一次，然后判斷出這三盞燈分別是由哪個(gè)開(kāi)關(guān)控制的。有什么辦法呢?，你要用一根金條作為報(bào)酬。金條被分成七小塊，每天給出一塊。如果你只能將金條切割兩次，你怎樣分給這些工人?3. ★用一種算法來(lái)顛倒一個(gè)鏈接表的順序。現(xiàn)在在不用遞歸式的情況下做一遍?！镉靡环N算法在一個(gè)循環(huán)的鏈接表里插入一個(gè)節(jié)點(diǎn)，但不得穿越鏈接表。★用一種算法整理一個(gè)數(shù)組。你為什么選擇這種方法?★用一種算法使通用字符串相匹配?！镱嵉挂粋€(gè)字符串。優(yōu)化速度。優(yōu)化空間?！镱嵉挂粋€(gè)句子中的詞的順序，比如將“我叫克麗絲”轉(zhuǎn)換為“克麗絲叫我”，實(shí)現(xiàn)速度最快，移動(dòng)最少?！镎业揭粋€(gè)子字符串。優(yōu)化速度。優(yōu)化空間?！锉容^兩個(gè)字符串，用O(n)時(shí)間和恒量空間。★假設(shè)你有一個(gè)用1001個(gè)整數(shù)組成的數(shù)組，這些整數(shù)是任意排列的，但是你知道所有的整數(shù)都在1到1000(包括1000)之間。此外，除一個(gè)數(shù)字出現(xiàn) 兩次外，其他所有數(shù)字只出現(xiàn)一次。假設(shè)你只能對(duì)這個(gè)數(shù)組做一次處理，用一種算法找出重復(fù)的那個(gè)數(shù)字。如果你在運(yùn)算中使用了輔助的存儲(chǔ)方式，那么你能找到不 用這種方式的算法嗎?★不用乘法或加法增加8倍?，F(xiàn)在用同樣的方法增加7倍。第9題判斷整數(shù)序列是不是二元查找樹(shù)的后序遍歷結(jié)果題目:輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹(shù)的后序遍歷的結(jié)果。如果是返回true，否則返回false。例如輸入18，由于這一整數(shù)序列是如下樹(shù)的后序遍歷結(jié)果: 8 /\ 6 10 / \/ \ 57 911因此返回true。如果輸入5，沒(méi)有哪棵樹(shù)的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。第10題翻轉(zhuǎn)句子中單詞的順序。題目:輸入一個(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”。第11題求二叉樹(shù)中節(jié)點(diǎn)的最大距離...如果我們把二叉樹(shù)看成一個(gè)圖，父子節(jié)點(diǎn)之間的連線看成是雙向的，我們姑且定義距離為兩節(jié)點(diǎn)之間邊的個(gè)數(shù)。寫(xiě)一個(gè)程序，求一棵二叉樹(shù)中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。第12題題目:求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語(yǔ)句(A?B:C)。第13題:題目:輸入一個(gè)單向鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。鏈表的倒數(shù)第0個(gè)結(jié)點(diǎn)為鏈表的尾指針。鏈表結(jié)點(diǎn)定義如下:struct ListNode{int m_nKey。ListNode* m_pNext。}。第14題:題目:輸入一個(gè)已經(jīng)按升序排序過(guò)的數(shù)組和一個(gè)數(shù)字，在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是輸入的那個(gè)數(shù)字。要求時(shí)間復(fù)雜度是O(n)。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，輸出任意一對(duì)即可。例如輸入數(shù)組115和數(shù)字15。由于4+11=15，因此輸出4和11。第15題:題目:輸入一顆二元查找樹(shù)，將該樹(shù)轉(zhuǎn)換為它
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1