Python高頻算法題100例-2019最新

Python高頻算法題100例（2019）二維數(shù)組中的查找題目：在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)替換空格題目：請實現(xiàn)一個函數(shù)，將一個字符串中的空格替換成“%20”。例如，當(dāng)字符串為WeAreHappy.則經(jīng)過替換之后的字符串為We%20Are%20Happy 。從尾到頭打印鏈表題目：輸入一個鏈表，從尾到頭打印鏈表每個節(jié)點的值。重建二叉樹題目：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列｛1,2,4,7,3,5,6和中序遍歷序列｛4,7,2,1,5,3,8,6則重建二叉樹并返回。兩個棧實現(xiàn)隊列題目：用兩個棧來實現(xiàn)一個隊列，完成隊列的Push和Pop操作。隊列中的元素為int類型。旋轉(zhuǎn)數(shù)組的最小數(shù)字題目：把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組｛3,4,5,1,為｛1,2,3,4,的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。NOTE:給出的所有元素都大于0,若數(shù)組大小為0，請返回0斐波那契數(shù)列題目：大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n,請你輸出斐波那契數(shù)列的第n項。跳臺階題目：一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。變態(tài)跳臺階題目：一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。矩形覆蓋題目：我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？二進制中1的個數(shù)題目：輸入一個整數(shù)，輸出該數(shù)二進制表示中1的個數(shù)。其中負數(shù)用補碼表示。數(shù)值中的整數(shù)次方題目：給定一個double類型的浮點數(shù)base和int類型的整數(shù)exponent。求base的exponent次方。調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面題目：輸入一個整數(shù)數(shù)組，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對位置不變。鏈表中倒數(shù)第k個節(jié)點題目：輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。題目：輸入一個鏈表，反轉(zhuǎn)鏈表后，輸出鏈表的所有兀素。合并兩個排序的鏈表題目：輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。樹的子結(jié)構(gòu)題目：輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps:我們約定空樹不是任意一個樹的子結(jié)構(gòu)）二叉樹的鏡像題目：操作給定的二叉樹，將其變換為源二叉樹的鏡像。順時針打印矩陣題目：輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數(shù)字，例如，如果輸入如下矩陣：12345678910111213141516則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.包含min函數(shù)的棧題目：定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧最小元素的min函數(shù)。21?棧的壓入、彈出序列題目：輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）22.從上往下打印二叉樹題目：從上往下打印出二叉樹的每個節(jié)點，同層節(jié)點從左至右打印。題目：輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。二叉樹中和為某一值的路徑題目：輸入一顆二叉樹和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。分解讓復(fù)雜問題簡單復(fù)雜鏈表的復(fù)制題目：輸入一個復(fù)雜鏈表（每個節(jié)點中有節(jié)點值，以及兩個指針，一個指向下一個節(jié)點，另一個特殊指針指向任意一個節(jié)點），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。（注意，輸出結(jié)果中請不要返回參數(shù)中的節(jié)點引用，否則判題程序會直接返回空）二叉樹捜索樹與雙向鏈表題目：輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向。字符串的排列題目：輸入一個字符串，按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。時間效率數(shù)組中出現(xiàn)超過一半的數(shù)字題目：數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組｛1,2,3,2,2,2,5,組2由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0。最小的k個數(shù)題目：輸入n個整數(shù)，找出其中最小的K個數(shù)。例如輸入4,5,1,6,2,7,3,這8個數(shù)字，則最小的4個數(shù)字是1,2,3,4連續(xù)子數(shù)組的最大和題目：HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機專業(yè)的同學(xué)。今天測試組開完會后，他又發(fā)話了:在古老的一維模式識別中，常常需要計算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時候,問題很好解決。但是，如果向量中包含負數(shù)，是否應(yīng)該包含某個負數(shù)，并期望旁邊的正數(shù)會彌補它呢？例如：｛6,-3,-2,7,-15,1,2連續(xù)子向量的最大和為8（從第0個開始，到第3個為止）。你會不會被他忽悠住？（子向量的長度至少是1）整數(shù)中1出現(xiàn)的次數(shù)（從1到n整數(shù)中1出現(xiàn)的次數(shù)）題目：求出1~13的整數(shù)中1出現(xiàn)的次數(shù),并算出100~1300的整數(shù)中1出現(xiàn)的次數(shù)？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1、10、11、12、13因此共出現(xiàn)6次，但是對于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化，可以很快的求出任意非負整數(shù)區(qū)間中1出現(xiàn)的次數(shù)。32?把數(shù)組排成最小的數(shù)題目：輸入一個正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)，打印能拼接出的所有數(shù)字中最小的一個。例如輸入數(shù)組｛3,32,321｝，則打印出這三個數(shù)字能排成的最小數(shù)字為321323。丑數(shù)題目：把只包含因子2、3和5的數(shù)稱作丑數(shù)（UglyNumber）。例如6、8都是丑數(shù)，但14不是，因為它包含因子7。習(xí)慣上我們把1當(dāng)做是第一個丑數(shù)。求按從小到大的順序的第N個丑數(shù)第一個只出現(xiàn)一次的字符位置題目：在一個字符串（1<=字符串長度〈=10000，全部由字母組成）中找到第一個只出現(xiàn)一次的字符，并返回它的位置數(shù)組中的逆序?qū)︻}目：在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)Α］斎胍粋€數(shù)組，求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對1000000007取模的結(jié)果輸出。即輸出P%1000000007兩個鏈表的第一個公共節(jié)點題目：輸入兩個鏈表，找出它們的第一個公共結(jié)點。知識遷移能力數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)題目：統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。二叉樹的深度題目：輸入一棵二叉樹，求該樹的深度。從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點（含根、葉結(jié)點）形成樹的一條路徑，最長路徑的長度為樹的深度。平衡二叉樹題目：輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。數(shù)組中只出現(xiàn)一次的數(shù)字題目：一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。和為s的連續(xù)整數(shù)序列題目：小明很喜歡數(shù)學(xué)，有一天他在做數(shù)學(xué)作業(yè)時，要求計算出9~16的和，他馬上就寫出了正確答案是100。但是他并不滿足于此，他在想究竟有多少種連續(xù)的正數(shù)序列的和為100（至少包括兩個數(shù)）。沒多久，他就得到另一組連續(xù)正數(shù)和為100的序列：18,19,20,21,22現(xiàn)在把問題交給你，你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列？GoodLuck!和為s的兩個數(shù)字題目：輸入一個遞增排序的數(shù)組和一個數(shù)字S，在數(shù)組中查找兩個數(shù)，是的他們的和正好是S,如果有多對數(shù)字的和等于S,輸出兩個數(shù)的乘積最小的。左旋轉(zhuǎn)字符串題目：匯編語言中有一種移位指令叫做循環(huán)左移（ROL），現(xiàn)在有個簡單的任務(wù)，就是用字符串模擬這個指令的運算結(jié)果。對于一個給定的字符序列S,請你把其循環(huán)左移K位后的序列輸出。例如，字符序列S=”abcXYZdef”，要求輸出循環(huán)左移3位后的結(jié)果，即“XYZdefabc”。是不是很簡單？0K,搞定它！翻轉(zhuǎn)單詞順序題目：?？妥罱鼇砹艘粋€新員工Fish，每天早晨總是會拿著一本英文雜志，寫些句子在本子上。同事Cat對Fish寫的內(nèi)容頗感興趣，有一天他向Fish借來翻看，但卻讀不懂它的意思。例如，“student.aamI”。后來才意識到，這家伙原來把句子單詞的順序翻轉(zhuǎn)了，正確的句子應(yīng)該是“Iamastudent.”￡at對的翻轉(zhuǎn)這些單詞順序可不在行，你能幫助他么？抽象建模能力撲克牌順子題目：LL今天心情特別好，因為他去買了一副撲克牌，發(fā)現(xiàn)里面居然有2個大王,2個小王（一副牌原本是54張〔'）??他隨機從中抽出了5張牌，想測測自己的手氣，看看能不能抽到順子,如果抽到的話他決定去買體育彩票，嘿嘿??！“紅心A，黑桃3,小王，大王方片5”，“0hMyGod!”不是順子.???.不高興了，他想了想，決定大\小王可以看成任何數(shù)字，并且A看作1J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”（大小王分別看作和4）,“SoLucky!”。LL決定去買體育彩票啦?，F(xiàn)在,要求你使用這幅牌模擬上面的過程，然后告訴我們LL的運氣如何。為了方便起見,你可以認為大小王是0。孩子們的游戲（圓圈中最后剩下的數(shù)）題目：每年六一兒童節(jié)?？投紩蕚湟恍┬《Y物去看望孤兒院的小朋友今年亦是如此。HF作為?？偷馁Y深元老啟然也準備了一些小游戲。其中，有個游戲是這樣的:首先，讓小朋友們圍成一個大圈。然后，他隨機指定一個數(shù)m,讓編號為0的小朋友開始報數(shù)。每次喊到m-1的那個小朋友要出列唱首歌然后可以在禮品箱中任意的挑選禮物，并且不再回到圈中，從他的下一個小朋友開始，繼續(xù)0…m-1報數(shù)..這樣下去..直到剩下最后一個小朋友，可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版（名額有限哦！！〔'）。請你試著想下，哪個小朋友會得到這份禮品呢？（主：小朋友的編號是從0到n-1）思維發(fā)散能力求l+2+3+...+n題目：求1+2+3+...+n，要求不能使用乘除法、for、while、ifelse、switch、case等關(guān)鍵字及條件判斷語句（A?B:C）。不用加減乘除做加法題目：寫一個函數(shù)，求兩個整數(shù)之和，要求在函數(shù)體內(nèi)不得使用■、-、*、/四則運算符號。Q厶綜合把字符串轉(zhuǎn)換成整數(shù)題目：將一個字符串轉(zhuǎn)換成一個整數(shù)，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫函數(shù)。數(shù)值為0或者字符串不是一個合法的數(shù)值則返回0數(shù)組數(shù)組中重復(fù)的數(shù)字題目：在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字是重復(fù)的。也不知道每個數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字。例如，如果輸入長度為7的數(shù)組｛2,3,1,0,2,5”3｝那么對應(yīng)的輸出是第一個重復(fù)的數(shù)字2。構(gòu)建乘積數(shù)組題目：給定一個數(shù)組A[0,1,...,n-請構(gòu)建一個數(shù)組B[0,1,...,n-其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n不能使用除法。字符串正則表達式匹配題目：請實現(xiàn)一個函數(shù)用來匹配包括'?和'*的正則表達式。模式中的字符'?表示任意一個字符，而'*表示它前面的字符可以出現(xiàn)任意次（包含0次）。在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串"aaa〃與模式〃a.a‘和〃ab*ac*a〃匹配，但是與〃aa.a〃和"ab*a"均不匹配表示數(shù)值的字符串題目：請實現(xiàn)一個函數(shù)用來判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）。例如，字符串〃+100〃，〃5e2〃，〃-123〃，〃3.1416〃和"-1E-16"都表示數(shù)值。 但是〃12e〃，〃1a3.14〃，〃1.2.3〃，〃+-和〃12e+4.3〃都不是。字符流中第一個不重復(fù)的字符題目：請實現(xiàn)一個函數(shù)用來找出字符流中第一個只出現(xiàn)一次的字符。例如，當(dāng)從字符流中只讀出前兩個字符"go"時，第一個只出現(xiàn)一次的字符是"g"。當(dāng)從該字符流中讀出前六個字符“google〃時，第一個只出現(xiàn)一次的字符是"l"鏈表鏈表中環(huán)的入□節(jié)點題目：一個鏈表中包含環(huán)，請找出該鏈表的環(huán)的入□結(jié)點。刪除鏈表中重復(fù)的節(jié)點題目：在一個排序的鏈表中，存在重復(fù)的結(jié)點，請刪除該鏈表中重復(fù)的結(jié)點，重復(fù)的結(jié)點不保留，返回鏈表頭指針。例如，鏈表1-〉2-〉3-〉3-〉4-〉4-〉5 處理后為1->2->5。樹二叉樹的下一個節(jié)點題目：給定一個二叉樹和其中的一個結(jié)點，請找出中序遍歷順序的下一個結(jié)點并且返回。注意，樹中的結(jié)點不僅包含左右子結(jié)點，同時包含指向父結(jié)點的指針。對稱的二叉樹題目：請實現(xiàn)一個函數(shù)，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。按之字形順序打印二叉樹題目：請實現(xiàn)一個函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。把二叉樹打印成多行題目：從上到下按層打印二叉樹，同一層結(jié)點從左至右輸出。每一層輸出一行。序列化二叉樹題目：請實現(xiàn)兩個函數(shù)，分別用來序列化和反序列化二叉樹。二叉捜索樹的第k個結(jié)點題目：給定一顆二叉搜索樹，請找出其中的第k大的結(jié)點。例如，5/\37/\/\24中,8按結(jié)點數(shù)值大小順序第三個結(jié)點的值為4。數(shù)據(jù)流中的中位數(shù)題目：如何得到一個數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值棧和隊列滑動窗□的最大值題目：給定一個數(shù)組和滑動窗□的大小，找出所有滑動窗□里數(shù)值的最大值。例如，如果輸入數(shù)組{2,3,4,2,6,2,5及滑動窗□的大小3,那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}針對數(shù)組{2,3,4,2,6,2,5的滑動窗□有以下6個:{[2,3,4],2,6,2,5,1}{2,[3,4,2],6,2,5,1}{2,3,[4,2,6],2,5,1}{2,3,4,[2,6,2],5,1}{2,3,4,2,[6,2,5],1}{2,3,4,2,6,[2,5,。1]}矩陣中的路徑題目:請設(shè)計一個函數(shù),用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動—個格子。如果一條路徑經(jīng)過了矩陣中的某一個格子,則該路徑不能再進入該格子。例如abcesfcsade矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。機器人的運動范圍題目：地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數(shù)位之和大于k的格子。例如，當(dāng)k為18時，機器人能夠進入方格（35,37），因為3+5+3+7=18。但是，它不能進入方格（35,38），因為3+5+3+8=19。請問該機器人能夠達到多少個格子？排列組合問題題目：有1、2、3、4個數(shù)字，能組成多少個互不相同且無重復(fù)數(shù)字的四位數(shù)？都是多少？求特殊整數(shù)題目：一個整數(shù)，它加上100后是一個完全平方數(shù)，再加上168又是一個完全平方數(shù)，請問該數(shù)是多少？程序分析：循環(huán)計算即可，判斷成立即可輸出。首先要判斷是否為正整數(shù)。引入iath模塊算平方根。68題題目：輸入某年某月某日，判斷這一天是這一年的第幾天？程序分析：以3月5日為例，應(yīng)該先把前兩個月的加起來，然后再加上5天即本年的第幾天，特殊情況，閏年且輸入月份大于3時需考慮多加一天。69題題目：要求輸出國際象棋棋盤。程序分析：用i控制行，j