2025年高频程序员智力面试题及答案

2025年高频程序员智力面试题及答案问题1：海盗分金币的策略优化6名海盗（按等级从高到低编号1至6）需要分配100枚金币。分配规则：由等级最高的海盗提出分配方案，所有海盗（包括提议者）投票表决，若方案获得至少半数（含半数）同意则通过，否则提议者被处决，由下一级海盗重新提议。假设所有海盗绝对理性，优先考虑生存，其次追求利益最大化，最后倾向于多杀人。求1号海盗的分配方案。解答：采用逆向推理，从最少人数的情况开始分析：当只剩6号时（1-5号均被处决），6号独得100枚，无需投票。当剩5号和6号时，5号需至少半数同意（1票）。5号自己投赞成即可通过，因此5号的方案是（100,0）（自己100，6号0）。当剩4、5、6号时，4号需至少2票（自己+1人）。若4号被处决，5号将独吞金币，6号得0。因此4号需拉拢6号，给6号1枚（比6号在5号方案中得0更优）。方案为（99,0,1）（4号99，5号0，6号1）。当剩3、4、5、6号时，3号需至少2票（自己+1人）。若3号被处决，4号的方案是（99,0,1），此时5号得0。因此3号拉拢5号，给5号1枚。方案为（99,0,1,0）（3号99，4号0，5号1，6号0）。当剩2、3、4、5、6号时，2号需至少3票（自己+2人）。若2号被处决，3号的方案是（99,0,1,0），此时4号得0，6号得0。因此2号拉拢4号和6号，各给1枚。方案为（98,0,1,0,1）（2号98，3号0，4号1，5号0，6号1）。当1号提议时，需至少3票（自己+2人）。若1号被处决，2号的方案是（98,0,1,0,1），此时3号得0，5号得0。因此1号拉拢3号和5号，各给1枚。最终方案为（98,0,1,0,1,0）（1号98，2号0，3号1，4号0，5号1，6号0）。问题2：服务器集群的可用概率优化某系统由3台独立运行的服务器组成，每台服务器正常运行的概率为p（0≤p≤1）。系统可用的条件是至少2台服务器正常运行。（1）求系统可用概率的表达式；（2）若p可调整（如通过升级硬件提高稳定性），求p取何值时系统可用概率最大。解答：（1）系统可用需满足“恰好2台正常”或“3台都正常”。恰好2台正常的概率：C(3,2)×p²×(1-p)=3p²(1-p)；3台都正常的概率：p³；因此，系统可用概率P(p)=3p²(1-p)+p³=3p²2p³。（2）求P(p)的最大值，对p求导并令导数为0：P’(p)=6p6p²=6p(1p)。令P’(p)=0，解得p=0或p=1。但需验证边界条件：当p=0时，P(p)=0；当p=1时，P(p)=1；当p在(0,1)时，P’(p)始终为正（因6p(1-p)在0<p<1时大于0），说明P(p)在[0,1]上单调递增。因此，p=1时系统可用概率最大（为1）。问题3：任务调度的最大完成数有n个任务，每个任务i的处理时间为t_i（t_i>0），截止时间为d_i（d_i≥t_i）。任务需连续处理，同一时间只能执行一个任务。若任务i在d_i时间内完成（即开始时间s_i满足s_i+t_i≤d_i），则视为成功。求最多能成功完成的任务数。解答：采用贪心算法，核心策略是优先选择截止时间早的任务，且处理时间尽可能短，以留出更多时间给后续任务。具体步骤：1.将任务按截止时间d_i从小到大排序，若d_i相同则按t_i从小到大排序；2.初始化当前时间为0，成功数count=0；3.遍历排序后的任务，对每个任务i：若当前时间+t_i≤d_i，则执行该任务，当前时间更新为当前时间+t_i，count加1；否则跳过。举例验证：假设任务列表为：任务A（t=3，d=5）、任务B（t=2，d=4）、任务C（t=1，d=6）。排序后顺序为B（d=4）、A（d=5）、C（d=6）。处理B：当前时间0+2=2≤4，count=1；处理A：当前时间2+3=5≤5，count=2；处理C：当前时间5+1=6≤6，count=3。最终成功完成3个任务。若选择其他顺序（如先A后B），则B的截止时间4无法满足（A处理到3，B开始时间3+3=6>4），只能完成2个任务。因此贪心策略有效。问题4：二维网格的最短路径计数（含障碍）在m×n的网格中，起点为左上角(0,0)，终点为右下角(m-1,n-1)，只能向右或向下移动。网格中有若干障碍（值为1表示障碍，0表示可通行）。求从起点到终点的最短路径总数（路径长度为步数，即m+n-2步）。解答：最短路径的步数固定为(m+n-2)，因此只需统计所有无障碍的路径数。使用动态规划：定义dp[i][j]为从(0,0)到(i,j)的最短路径数；初始条件：若起点(0,0)无障碍，dp[0][0]=1；否则为0；状态转移：若当前格子(i,j)是障碍，dp[i][j]=0；否则，dp[i][j]=dp[i-1][j]（从上方来）+dp[i][j-1]（从左方来）（边界情况：i=0时仅能从左方来，j=0时仅能从上方来）。示例：网格如下（3×3，障碍在(1,1)）：[[0,0,0],[0,1,0],[0,0,0]]计算dp表：dp[0][0]=1；第一行（i=0）：j=1时，dp[0][1]=dp[0][0]=1；j=2时，dp[0][2]=dp[0][1]=1；第一列（j=0）：i=1时，dp[1][0]=dp[0][0]=1；i=2时，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；因此最短路径总数为2。问题5：最长01相等子串给定一个仅由0和1组成的字符串s，求最长子串的长度，使得该子串中0和1的数量相等。解答：利用前缀和与哈希表记录差值首次出现的位置。将0视为-1，1视为+1，计算前缀和数组。若两个位置的前缀和相等，则它们之间的子串和为0（即0和1数量相等）。步骤：1.初始化哈希表，记录前缀和值到索引的映射，初始时前缀和0对应索引-1（处理从0开始的子串）；2.遍历字符串，维护当前前缀和sum；3.若sum已存在于哈希表中，计算当前索引与哈希表中记录的索引的差值，更新最大长度；4.若sum不存在，将sum和当前索引存入哈希表。示例：s="010011"，转换为数值数组[-1,1,-1,-1,1,1]，前缀和依次为：索引-1:0；索引0:-1（未记录过，存入哈希表：-1→0）；索引1:0（已存在，索引1-(-1)=2，当前最大长度2）；索引2:-1（已存在，索引2-0=2，长度不变）；索引3:-2（未记录，存入-2→3）；索引4:-1（已存在，索引4-0=4，更新最大长度4）；索引5:0（已存在，索引5-(-1)=6，更新最大长度6）。最终最长子串长度为6（对应原字符串"010011"本身，0和1各3个）。问题6：找出数组中两个唯一出现一次的数给定数组nums，其中除两个数x和y外，其余数均出现两次。要求在O(n)时间、O(1)空间内找出x和y。解答：利用异或运算的性质：相同数异或为0，0异或任何数为其本身。1.遍历数组，计算所有数的异或和xor_sum，结果为x^y（因其他数出现两次，异或后抵消）；2.找到xor_sum中任意一个为1的二进制位（如最低位），记为mask（mask=xor_sum&(-xor_sum)，可快速得到最低位的1）；3.根据mask将数组分为两组：一组数在mask位上为1，另一组为0。x和y必分属不同组；4.分别对两组数求异或和，结果即为x和y。示例：nums=[2,3,2,5,4,5,3,7