本篇內(nèi)容介紹了“Python算法面試題有哪些”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

在成都網(wǎng)站制作、成都網(wǎng)站設(shè)計中從網(wǎng)站色彩、結(jié)構(gòu)布局、欄目設(shè)置、關(guān)鍵詞群組等細微處著手，突出企業(yè)的產(chǎn)品/服務/品牌，幫助企業(yè)鎖定精準用戶，提高在線咨詢和轉(zhuǎn)化，使成都網(wǎng)站營銷成為有效果、有回報的無錫營銷推廣。創(chuàng)新互聯(lián)公司專業(yè)成都網(wǎng)站建設(shè)十余年了，客戶滿意度97.8%，歡迎成都創(chuàng)新互聯(lián)客戶聯(lián)系。

1、25匹馬，有一條只能5匹馬比賽的賽道，我們無法計時，只能看到馬的排名，如何用最短的次數(shù)找出跑的最快的5匹馬？

這道題目的話最好的情況是7次，最壞的情況是10次。我們首先建立一個表格，先把25匹馬分為如下的五組：

每組進行比賽，假設(shè)第一組快慢順序為A1、A2、A3、A4和A5，第二組依次類推。那么各組的第一分別是A1、B1、C1、D1、E1。

在最好的情況下，先讓A1、B1、C1、D1、E1比賽，得到第一名，假設(shè)A1是第一名，并且順序是A1 > B1 > C1 > D1 > E1；然后讓A2加入比賽，若比賽結(jié)果為B1 > C1 > D1 > A2。那么前五名是A1、B1、C1、D1、E1，共需比賽7次。那么在最壞的情況下，每次新加入一個候補，得到一個新的名次的馬，此時共需要10次比賽。

這個題更加常考的是問如何用最短的次數(shù)找出最快的3匹馬，這個題和找出5匹馬還不太一樣。如果找出3匹馬，只需要比賽7次即可，前六次假設(shè)和上面的過程一樣，A1是最快的馬，剩下的名次是B1 > C1 > D1 > E1。此時并不是讓A2、B1、C1、D1、E1進行比賽，先仔細分析一下，第二名一定出現(xiàn)在B1 和 A2之中，若B1 > A2，那么第三名出現(xiàn)在A2 、B2、C1之中，若A2 > B1，那么第三名出現(xiàn)在A3 、B1之中。因此，第七場比賽只需要讓A2、A3、B1、B2、C1五匹馬比賽，得到前兩名即可。因此只需要7場比賽就可以得到跑的最快的3匹馬。

2、一條無限長的直線，有兩個機器人，兩個機器人執(zhí)行同一段代碼，這一段代碼中只有幾條語句：right代表向右走，left代表向左走，if arrived else代表另一個機器人是否走過這個地方。goto代表代碼的跳轉(zhuǎn)，請寫一段代碼確保兩個機器人能夠相遇。

偽代碼如下：

start:
if arrived:
 right
 right
else:
 right
goto start

簡單解釋一下，假設(shè)兩個機器人A和B都往右走，B在前A在后，一開始二者保持相同的速度前進，當A到達曾經(jīng)B經(jīng)過的點后，發(fā)現(xiàn)此后的路是B此前經(jīng)過的，那么A開始提速兩倍，B一直保持原來的一倍速度不變，那樣的話，A一定會追上B。

3、海量數(shù)據(jù)如何求中位數(shù)？數(shù)據(jù)無法放入內(nèi)存，只需考慮空間復雜度，不需要考慮時間復雜度。

假設(shè)我們的數(shù)據(jù)都是無符號的32位整數(shù)，既然不考慮時間復雜度，可以通過二進制來解決，從高位到低位依次判斷，首先遍歷所有數(shù)據(jù)，并記錄最高位為0和1的個數(shù)（最高位為0的肯定是小于最高位為1的）記為N0、N1。

那么根據(jù)N0和N1的大小就可以知道中位數(shù)的最高位是0還是1

若N0>N1，那么再計算N00和N01，如果N00>(N01+N1)（這里一定注意是N00要大于N01和N1數(shù)量的總和，而非N00大于N01），則說明中位數(shù)的最高兩位是00，那么再計算N000和N001....依次計算就能找到中位數(shù)。

4、信息流采樣，有n份數(shù)據(jù)，但是n的長度并不知道，設(shè)計一個采樣算法，使得每份被選擇的概率是相同的。

這道題其實考察的是蓄水池采樣的方法，這里咱們簡單介紹下蓄水池算法的思路。

一開始選擇第一個數(shù)據(jù)作為候選數(shù)據(jù)，以概率1/2拿第二個數(shù)據(jù)替換當前候選，以1/3選擇拿三個數(shù)據(jù)替換當前候選，依次類推。

這樣，第x個數(shù)據(jù)為最終選擇的數(shù)據(jù)的概率 = x被選擇的概率 * (x+1沒被選擇的概率) * (x+2沒有被選擇的概率) ......(n沒有被選擇的概率)

舉個例子，第2哥數(shù)據(jù)被選擇的概率為：1/2 * （2/3 * 3/4 * 4/5 .... n-1/n) = 1 / n

5、n個[0,n)的數(shù)，求每個數(shù)的出現(xiàn)次數(shù)（不能開辟額外空間）

這里關(guān)鍵是看清楚題意，n個數(shù)，然后是左閉右開的區(qū)間，也就是說每個數(shù)都不會大于等于n，那么思路主要有以下兩點：

1）如果我們給一個索引下的數(shù)不管加上多少個n，那么這個數(shù)對n取余的話，我們就能知道這個數(shù)原來是多少；

2）另一方面，如果一個數(shù)出現(xiàn)一次，我們就在對應索引位置下的數(shù)加上n，那么每個數(shù)對應索引位置上的數(shù)對n取商的話，就是這個數(shù)出現(xiàn)的次數(shù)。這樣就做到了沒有開辟額外的空間。

代碼如下：

public class timeDemo {
 public static void main(String[] args){
 int[] arr = {0,1,3,4,3,2,5,4,3,7,3,2,4,6};
 int n = 8;
 for(int i = 0;i<arr.length;i++){
 arr[arr[i] % n] += n;
 }
 for(int i = 0;i<n;i++){
 System.out.println(i + ":" + arr[i] / n);
 }
 }
}

輸出為：

6、 已知有個rand7()的函數(shù)，返回1到7隨機自然數(shù)，怎樣利用這個rand7()構(gòu)造rand10()，隨機1~10。

產(chǎn)生隨機數(shù)的主要原則是每個數(shù)出現(xiàn)的概率是相等的，如果可以得到一組等概率出現(xiàn)的數(shù)字，那么就可以從中找到映射為1~10的方法。

rand7()返回1~7的自然數(shù)，構(gòu)造新的函數(shù) (rand7()-1)*7 + rand7()，這個函數(shù)會隨機產(chǎn)生1~49的自然數(shù)。原因是1~49中的每個數(shù)只有唯一的第一個rand7()的值和第二個rand7()的值表示，于是它們出現(xiàn)的概率是相等，均為1/49。

但是這里的數(shù)字太多，可以丟棄41~49的數(shù)字，把1~40的數(shù)字分成10組，每組映射成1~10中的一個，于是可以得到隨機的結(jié)果。

具體方法是，利用(rand7()-1)*7 + rand7()產(chǎn)生隨機數(shù)x，如果大于40則繼續(xù)隨機直到小于等于40為止，如果小于等于40，則產(chǎn)生的隨機數(shù)為(x-1)/4+1。

“Python算法面試題有哪些”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！

網(wǎng)頁名稱：Python算法面試題有哪些-創(chuàng)新互聯(lián)
文章鏈接：http://aaarwkj.com/article32/ieosc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計、網(wǎng)站改版、服務器托管、定制網(wǎng)站、品牌網(wǎng)站制作、面包屑導航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)