數(shù)據(jù)結(jié)構(gòu)與算法面試題80道(存儲(chǔ)版)
【正文】 pData。題目:如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，分析:求最長(zhǎng)公共子串(Longest Common Subsequence, LCS)是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題，題目:某隊(duì)列的聲明如下: // remove a element from head隊(duì)列是一種先入先出的數(shù)據(jù)容器，我們總是把新元素插入到隊(duì)列的尾部，而從隊(duì)列的頭部刪除元素。鏈表結(jié)點(diǎn)定義如下:struct ListNode{struct ListNode}。題目:輸入兩個(gè)字符串，從第一字符串中刪除第二個(gè)字符串中所有的字符。分析:這是一道在網(wǎng)絡(luò)上廣為流傳的面試題，據(jù)說google曾經(jīng)采用過這道題。分析:這是一道很有意思的題目。顛倒之后的棧為{5, 4, 3, 2, 1}，5處在棧頂。210為數(shù)字本身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數(shù)字。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小 為1。但這個(gè)思路沒有利用輸入數(shù)組的特性，我們應(yīng)該能找到更好的解法。還有逆序生成排列和一些不需要遞歸生成排列的方法。要幾十分鐘的時(shí)間里很好地解答這道題，除了較好的編程能力之外，還需要較快的反應(yīng)和較強(qiáng)的邏輯思維能力。請(qǐng)完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)，以復(fù)制一個(gè)復(fù)雜鏈表。說明無環(huán)，否則pp2必然會(huì)在某個(gè)時(shí)刻相遇(p1==p2)，從而檢測(cè)到鏈表中有環(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)，否則說明兩個(gè)鏈表沒有交點(diǎn)。但是最好能考慮的全面一點(diǎn)，現(xiàn)在公司招人的競(jìng)爭(zhēng)可能就在細(xì)節(jié)上產(chǎn)生，誰比較仔細(xì)，誰獲勝的機(jī)會(huì)就大。說明為什么你會(huì)選擇用這樣的方法?。?(非空結(jié)點(diǎn))，在p前面插入一個(gè)結(jié)點(diǎn)。從p點(diǎn)斷開環(huán)，方法為:p1=p, p2=pnext, pnext=NULL。如果head1==head2，那么顯然相交，直接返回head1。使用兩個(gè)指針p1,p2從鏈表頭開始遍歷，p1每次前進(jìn)一步，p2每次前進(jìn)兩步。圖中實(shí)線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。 ComplexNode* m_pNext。其結(jié)點(diǎn)的C++定義如下:分析:求數(shù)中兩個(gè)結(jié)點(diǎn)的最低共同結(jié)點(diǎn)是面試中經(jīng)常出現(xiàn)的一個(gè)問題。 TreeNode* m_pLeft。題目:二叉樹的結(jié)點(diǎn)定義如下:struct TreeNode{ result *= base。ANSWER 簡(jiǎn)單的回溯就可以實(shí)現(xiàn)了。分析:這道題最直觀的解法并不難。輸入一個(gè)排好序的數(shù)組的一個(gè)旋轉(zhuǎn)，題目:用遞歸顛倒一個(gè)棧。比如輸入3，求按從小到大的順序的第1500個(gè)丑數(shù)。{m_pNext。 m_nKey。題目:給定鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，在O(1)時(shí)間刪除該結(jié)點(diǎn)。這道題除了考察應(yīng)聘者的C++基本功底外，還能考察反應(yīng)能力，是一道很好的題目。 int因此這道題實(shí)質(zhì)上是要求我們用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列。 CQueue() {}。例如:輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長(zhǎng)公共子串，則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串。55.題目:輸入一個(gè)字符串，打印出該字符串中字符的所有排列。 // right child of node}。 m_nValue。 / / 10{3,3}{2,4}{6} m=3 所以m的最大 為3，利用這個(gè)函數(shù)實(shí)現(xiàn):，如何從中去除重復(fù)的，優(yōu)化時(shí)間空間復(fù)雜度37.有n個(gè)長(zhǎng)為m+1的字符串，如果某個(gè)字符串的最后m個(gè)字符與某個(gè)字符串的前m個(gè)字符匹配，則兩個(gè)字符串可以聯(lián)接，問這n個(gè)字符串最多可以連成一個(gè)多長(zhǎng)的字符串，如果出現(xiàn)循環(huán)，則返回錯(cuò)誤。n1，已知它們之間的實(shí)力對(duì)比關(guān)系，存儲(chǔ)在一個(gè)二維數(shù)組w[n][n]中，w[i][j] 的 代表編號(hào)為i，j的隊(duì)伍中更強(qiáng)的一支。var a=[100,99,98,1,2, 3]。其中一個(gè)序列表示棧的push順序，判斷另一個(gè)序列有沒有可能是對(duì)應(yīng)的pop順序。包括微軟在內(nèi)的很多公司都曾采用過這道題。1:(*.*, , *.*)2:(*.*, , *.*)3:(*.*, , *.*)4:(*.*, , *.*)因此很多程序員對(duì)這道題的遞歸解法非常熟悉，但....呵呵，你知道的。第16題:題目(微軟):輸入一顆二元樹，從上往下按層打印樹的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。 // value of node/\ /\5 7 9 11鏈表結(jié)點(diǎn)定義如下:為簡(jiǎn)單起見，標(biāo)點(diǎn)符號(hào)和普通字母一樣處理。如果輸入5，沒有哪棵樹的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。\如果是返回true，否則返回false。假設(shè)你只能對(duì)這個(gè)數(shù)組做一次處理，用一種算法找出重復(fù)的那個(gè)數(shù)字?！镱嵉挂粋€(gè)句子中的詞的順序，比如將“我叫克麗絲”轉(zhuǎn)換為“克麗絲叫我”，3. ★用一種算法來顛倒一個(gè)鏈接表的順序。特此并作一題。舉一個(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次....以此類推..題目:輸入n個(gè)整數(shù)，輸出其中最小的k個(gè)。/ \題目:輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。struct BSTreeNode{6所以，應(yīng)廣大網(wǎng)友建議要求，在此把之前已整理公布的前80題，向你的厚道致敬。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。8 12 16BSTreeNode *m_pLeft。要求函數(shù)min、push以及po
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1