數(shù)據(jù)結(jié)構(gòu)與算法面試題80道(參考版)
2025-03-29 00:52本頁(yè)面
【正文】 。說(shuō)明為什么你會(huì)選擇用這樣的方法?。但是最好能考慮的全面一點(diǎn)，現(xiàn)在公司招人的競(jìng)爭(zhēng)可能就在細(xì)節(jié)上產(chǎn)生，誰(shuí)比較仔細(xì)，誰(shuí)獲勝的機(jī)會(huì)就大。?(非空結(jié)點(diǎn))，在p前面插入一個(gè)結(jié)點(diǎn)。辦法很簡(jiǎn)單，首先是放p中數(shù)據(jù),然后將pnext的數(shù)據(jù)copy入p中，接下來(lái)刪除pnext即可。(并非最后一個(gè)結(jié)點(diǎn)，即pnext!=NULL)指針，刪除該結(jié)點(diǎn)。從p點(diǎn)斷開環(huán)，方法為:p1=p, p2=pnext, pnext=NULL。運(yùn)用題一，我們可以檢查鏈表中是否有環(huán)。否則，分別從head1,head2開始遍歷兩個(gè)鏈表獲得其長(zhǎng)度len1與len2，假設(shè)len1=len2，那么指針p1由head1開始向后移動(dòng)len1len2步，指針p2=head2，下面pp2每次向后前進(jìn)一步并比較p1p2是否相等，如果相等即返回該結(jié)點(diǎn)，否則說(shuō)明兩個(gè)鏈表沒(méi)有交點(diǎn)。如果head1==head2，那么顯然相交，直接返回head1。(head1, head2)，檢測(cè)兩個(gè)鏈表是否有交點(diǎn)，如果有返回第一個(gè)交點(diǎn)。說(shuō)明無(wú)環(huán)，否則pp2必然會(huì)在某個(gè)時(shí)刻相遇(p1==p2)，從而檢測(cè)到鏈表中有環(huán)。使用兩個(gè)指針p1,p2從鏈表頭開始遍歷，p1每次前進(jìn)一步，p2每次前進(jìn)兩步。:分析:在常見的數(shù)據(jù)結(jié)構(gòu)上稍加變化，這是一種很新穎的面試題。請(qǐng)完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)，以復(fù)制一個(gè)復(fù)雜鏈表。圖中實(shí)線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。 ComplexNode* m_pSibling。 ComplexNode* m_pNext。 int m_nValue。其結(jié)點(diǎn)的C++定義如下:分析:求數(shù)中兩個(gè)結(jié)點(diǎn)的最低共同結(jié)點(diǎn)是面試中經(jīng)常出現(xiàn)的一個(gè)問(wèn)題。 TreeNode* m_pRight。 TreeNode* m_pLeft。 int m_nvalue。題目:二叉樹的結(jié)點(diǎn)定義如下:struct TreeNode{要幾十分鐘的時(shí)間里很好地解答這道題，除了較好的編程能力之外，還需要較快的反應(yīng)和較強(qiáng)的邏輯思維能力。題目:輸入一個(gè)字符串，輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度。72.題目:設(shè)計(jì)一個(gè)類，我們只能生成該類的一個(gè)實(shí)例。 return result。 result *= base。 i = exponent。分析:這是一道看起來(lái)很簡(jiǎn)單的問(wèn)題。不需要考慮溢出。這些算法的理解需要一定的數(shù)學(xué)功底，也需要一定的靈感，有興趣最好看看。還有逆序生成排列和一些不需要遞歸生成排列的方法。ANSWER 簡(jiǎn)單的回溯就可以實(shí)現(xiàn)了。但這個(gè)思路沒(méi)有利用輸入數(shù)組的特性，我們應(yīng)該能找到更好的解法。分析:這道題最直觀的解法并不難。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小 為1。輸入一個(gè)排好序的數(shù)組的一個(gè)旋轉(zhuǎn)。321}，則輸出這兩個(gè)能排成的最小數(shù)字32132。題目:輸入一個(gè)正整數(shù)數(shù)組，將它們連接起來(lái)排成一個(gè)數(shù)，輸出能排出的所有數(shù)字中最小的一個(gè)。輸入n，打印出S的所有可能的 出現(xiàn)的概率。210為數(shù)字本身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數(shù)字。顛倒之后的棧為{5, 4, 3, 2, 1}，5處在棧頂。題目:用遞歸顛倒一個(gè)棧。分析:這是一道很有意思的題目。比如輸入3，分析:這是一道在網(wǎng)絡(luò)上廣為流傳的面試題，據(jù)說(shuō)google曾經(jīng)采用過(guò)這道題。求按從小到大的順序的第1500個(gè)丑數(shù)。例如8都是丑數(shù)，但14不是，因?yàn)樗蜃?。64. 尋找丑數(shù)。分析:這是一道微軟面試題。則刪除之后的第一個(gè)字符串變成”Thy r stdnts.”。題目:輸入兩個(gè)字符串，從第一字符串中刪除第二個(gè)字符串中所有的字符。微軟非常喜歡與鏈表相關(guān)的題目，因此在微軟的面試題中，鏈表出現(xiàn)的概率相當(dāng)高。 m_nKey。 int{。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。分析:這是一道廣為流傳的Google面試題，能有效考察我們的編程基本功，還能考察我們的反應(yīng)速度，函數(shù)的聲明如下:void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted)。}。m_pNext。 m_nKey。struct ListNode題目:給定鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，在O(1)時(shí)間刪除該結(jié)點(diǎn)。(1)時(shí)間內(nèi)刪除鏈表結(jié)點(diǎn)。這道題除了考察應(yīng)聘者的C++基本功底外，還能考察反應(yīng)能力，是一道很好的題目。分析:這是一道很有意思的面試題。 ListNode* m_pNext。 m_nKey。 int鏈表結(jié)點(diǎn)定義如下:struct ListNode{隊(duì)列是一種先入先出的數(shù)據(jù)容器，我們總是把新元素插入到隊(duì)列的尾部，而從隊(duì)列的頭部刪除元素。因此這道題實(shí)質(zhì)上是要求我們用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列。 T m_stack2。 // remove a element from head// append a element to tail node)。 CQueue() {}題目:某隊(duì)列的聲明如下:。分析:求最長(zhǎng)公共子串(Longest Common Subsequence, LCS)是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題，例如:輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長(zhǎng)公共子串，則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串。請(qǐng)編寫一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長(zhǎng)公共子串，并打印出最長(zhǎng)公共子串。題目:如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中。請(qǐng)實(shí)現(xiàn)其賦 運(yùn)算符的重載函數(shù)，要求異常安全，即當(dāng)對(duì)一個(gè)對(duì)象進(jìn)行賦 時(shí)發(fā)生異常，對(duì)象的狀態(tài)不能改變。 char* m_pData。 operator = (const CMyStringamp。 CMyString(const CM
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1