2025年高頻程序員智力面試題及答案問題1：海盜分金幣的策略優(yōu)化6名海盜（按等級(jí)從高到低編號(hào)1至6）需要分配100枚金幣。分配規(guī)則：由等級(jí)最高的海盜提出分配方案，所有海盜（包括提議者）投票表決，若方案獲得至少半數(shù)（含半數(shù)）同意則通過，否則提議者被處決，由下一級(jí)海盜重新提議。假設(shè)所有海盜絕對理性，優(yōu)先考慮生存，其次追求利益最大化，最后傾向于多殺人。求1號(hào)海盜的分配方案。解答：采用逆向推理，從最少人數(shù)的情況開始分析：當(dāng)只剩6號(hào)時(shí)（1-5號(hào)均被處決），6號(hào)獨(dú)得100枚，無需投票。當(dāng)剩5號(hào)和6號(hào)時(shí)，5號(hào)需至少半數(shù)同意（1票）。5號(hào)自己投贊成即可通過，因此5號(hào)的方案是（100,0）（自己100，6號(hào)0）。當(dāng)剩4、5、6號(hào)時(shí)，4號(hào)需至少2票（自己+1人）。若4號(hào)被處決，5號(hào)將獨(dú)吞金幣，6號(hào)得0。因此4號(hào)需拉攏6號(hào)，給6號(hào)1枚（比6號(hào)在5號(hào)方案中得0更優(yōu)）。方案為（99,0,1）（4號(hào)99，5號(hào)0，6號(hào)1）。當(dāng)剩3、4、5、6號(hào)時(shí)，3號(hào)需至少2票（自己+1人）。若3號(hào)被處決，4號(hào)的方案是（99,0,1），此時(shí)5號(hào)得0。因此3號(hào)拉攏5號(hào)，給5號(hào)1枚。方案為（99,0,1,0）（3號(hào)99，4號(hào)0，5號(hào)1，6號(hào)0）。當(dāng)剩2、3、4、5、6號(hào)時(shí)，2號(hào)需至少3票（自己+2人）。若2號(hào)被處決，3號(hào)的方案是（99,0,1,0），此時(shí)4號(hào)得0，6號(hào)得0。因此2號(hào)拉攏4號(hào)和6號(hào)，各給1枚。方案為（98,0,1,0,1）（2號(hào)98，3號(hào)0，4號(hào)1，5號(hào)0，6號(hào)1）。當(dāng)1號(hào)提議時(shí)，需至少3票（自己+2人）。若1號(hào)被處決，2號(hào)的方案是（98,0,1,0,1），此時(shí)3號(hào)得0，5號(hào)得0。因此1號(hào)拉攏3號(hào)和5號(hào)，各給1枚。最終方案為（98,0,1,0,1,0）（1號(hào)98，2號(hào)0，3號(hào)1，4號(hào)0，5號(hào)1，6號(hào)0）。問題2：服務(wù)器集群的可用概率優(yōu)化某系統(tǒng)由3臺(tái)獨(dú)立運(yùn)行的服務(wù)器組成，每臺(tái)服務(wù)器正常運(yùn)行的概率為p（0≤p≤1）。系統(tǒng)可用的條件是至少2臺(tái)服務(wù)器正常運(yùn)行。（1）求系統(tǒng)可用概率的表達(dá)式；（2）若p可調(diào)整（如通過升級(jí)硬件提高穩(wěn)定性），求p取何值時(shí)系統(tǒng)可用概率最大。解答：（1）系統(tǒng)可用需滿足“恰好2臺(tái)正?！被颉?臺(tái)都正常”。恰好2臺(tái)正常的概率：C(3,2)×p2×(1-p)=3p2(1-p)；3臺(tái)都正常的概率：p3；因此，系統(tǒng)可用概率P(p)=3p2(1-p)+p3=3p22p3。（2）求P(p)的最大值，對p求導(dǎo)并令導(dǎo)數(shù)為0：P’(p)=6p6p2=6p(1p)。令P’(p)=0，解得p=0或p=1。但需驗(yàn)證邊界條件：當(dāng)p=0時(shí)，P(p)=0；當(dāng)p=1時(shí)，P(p)=1；當(dāng)p在(0,1)時(shí)，P’(p)始終為正（因6p(1-p)在0<p<1時(shí)大于0），說明P(p)在[0,1]上單調(diào)遞增。因此，p=1時(shí)系統(tǒng)可用概率最大（為1）。問題3：任務(wù)調(diào)度的最大完成數(shù)有n個(gè)任務(wù)，每個(gè)任務(wù)i的處理時(shí)間為t_i（t_i>0），截止時(shí)間為d_i（d_i≥t_i）。任務(wù)需連續(xù)處理，同一時(shí)間只能執(zhí)行一個(gè)任務(wù)。若任務(wù)i在d_i時(shí)間內(nèi)完成（即開始時(shí)間s_i滿足s_i+t_i≤d_i），則視為成功。求最多能成功完成的任務(wù)數(shù)。解答：采用貪心算法，核心策略是優(yōu)先選擇截止時(shí)間早的任務(wù)，且處理時(shí)間盡可能短，以留出更多時(shí)間給后續(xù)任務(wù)。具體步驟：1.將任務(wù)按截止時(shí)間d_i從小到大排序，若d_i相同則按t_i從小到大排序；2.初始化當(dāng)前時(shí)間為0，成功數(shù)count=0；3.遍歷排序后的任務(wù)，對每個(gè)任務(wù)i：若當(dāng)前時(shí)間+t_i≤d_i，則執(zhí)行該任務(wù)，當(dāng)前時(shí)間更新為當(dāng)前時(shí)間+t_i，count加1；否則跳過。舉例驗(yàn)證：假設(shè)任務(wù)列表為：任務(wù)A（t=3，d=5）、任務(wù)B（t=2，d=4）、任務(wù)C（t=1，d=6）。排序后順序?yàn)锽（d=4）、A（d=5）、C（d=6）。處理B：當(dāng)前時(shí)間0+2=2≤4，count=1；處理A：當(dāng)前時(shí)間2+3=5≤5，count=2；處理C：當(dāng)前時(shí)間5+1=6≤6，count=3。最終成功完成3個(gè)任務(wù)。若選擇其他順序（如先A后B），則B的截止時(shí)間4無法滿足（A處理到3，B開始時(shí)間3+3=6>4），只能完成2個(gè)任務(wù)。因此貪心策略有效。問題4：二維網(wǎng)格的最短路徑計(jì)數(shù)（含障礙）在m×n的網(wǎng)格中，起點(diǎn)為左上角(0,0)，終點(diǎn)為右下角(m-1,n-1)，只能向右或向下移動(dòng)。網(wǎng)格中有若干障礙（值為1表示障礙，0表示可通行）。求從起點(diǎn)到終點(diǎn)的最短路徑總數(shù)（路徑長度為步數(shù)，即m+n-2步）。解答：最短路徑的步數(shù)固定為(m+n-2)，因此只需統(tǒng)計(jì)所有無障礙的路徑數(shù)。使用動(dòng)態(tài)規(guī)劃：定義dp[i][j]為從(0,0)到(i,j)的最短路徑數(shù)；初始條件：若起點(diǎn)(0,0)無障礙，dp[0][0]=1；否則為0；狀態(tài)轉(zhuǎn)移：若當(dāng)前格子(i,j)是障礙，dp[i][j]=0；否則，dp[i][j]=dp[i-1][j]（從上方來）+dp[i][j-1]（從左方來）（邊界情況：i=0時(shí)僅能從左方來，j=0時(shí)僅能從上方來）。示例：網(wǎng)格如下（3×3，障礙在(1,1)）：[[0,0,0],[0,1,0],[0,0,0]]計(jì)算dp表：dp[0][0]=1；第一行（i=0）：j=1時(shí)，dp[0][1]=dp[0][0]=1；j=2時(shí)，dp[0][2]=dp[0][1]=1；第一列（j=0）：i=1時(shí)，dp[1][0]=dp[0][0]=1；i=2時(shí)，dp[2][0]=dp[1][0]=1；i=1,j=1：是障礙，dp[1][1]=0；i=1,j=2：dp[1][2]=dp[0][2]+dp[1][1]=1+0=1；i=2,j=1：dp[2][1]=dp[1][1]+dp[2][0]=0+1=1；i=2,j=2：dp[2][2]=dp[1][2]+dp[2][1]=1+1=2；因此最短路徑總數(shù)為2。問題5：最長01相等子串給定一個(gè)僅由0和1組成的字符串s，求最長子串的長度，使得該子串中0和1的數(shù)量相等。解答：利用前綴和與哈希表記錄差值首次出現(xiàn)的位置。將0視為-1，1視為+1，計(jì)算前綴和數(shù)組。若兩個(gè)位置的前綴和相等，則它們之間的子串和為0（即0和1數(shù)量相等）。步驟：1.初始化哈希表，記錄前綴和值到索引的映射，初始時(shí)前綴和0對應(yīng)索引-1（處理從0開始的子串）；2.遍歷字符串，維護(hù)當(dāng)前前綴和sum；3.若sum已存在于哈希表中，計(jì)算當(dāng)前索引與哈希表中記錄的索引的差值，更新最大長度；4.若sum不存在，將sum和當(dāng)前索引存入哈希表。示例：s="010011"，轉(zhuǎn)換為數(shù)值數(shù)組[-1,1,-1,-1,1,1]，前綴和依次為：索引-1:0；索引0:-1（未記錄過，存入哈希表：-1→0）；索引1:0（已存在，索引1-(-1)=2，當(dāng)前最大長度2）；索引2:-1（已存在，索引2-0=2，長度不變）；索引3:-2（未記錄，存入-2→3）；索引4:-1（已存在，索引4-0=4，更新最大長度4）；索引5:0（已存在，索引5-(-1)=6，更新最大長度6）。最終最長子串長度為6（對應(yīng)原字符串"010011"本身，0和1各3個(gè)）。問題6：找出數(shù)組中兩個(gè)唯一出現(xiàn)一次的數(shù)給定數(shù)組nums，其中除兩個(gè)數(shù)x和y外，其余數(shù)均出現(xiàn)兩次。要求在O(n)時(shí)間、O(1)空間內(nèi)找出x和y。解答：利用異或運(yùn)算的性質(zhì)：相同數(shù)異或?yàn)?，0異或任何數(shù)為其本身。1.遍歷數(shù)組，計(jì)算所有數(shù)的異或和xor_sum，結(jié)果為x^y（因其他數(shù)出現(xiàn)兩次，異或后抵消）；2.找到xor_sum中任意一個(gè)為1的二進(jìn)制位（如最低位），記為mask（mask=xor_sum&(-xor_sum)，可快速得到最低位的1）；3.根據(jù)mask將數(shù)組分為兩組：一組數(shù)在mask位上為1，另一組為0。x和y必分屬不同組；4.分別對兩組數(shù)求異或和，結(jié)果即為x和y。示例：nums=[2,3,2,5,4,5,3,7