2025年程序员逻辑思维题(附答案)之五

2025年程序员逻辑思维题(附答案)之五问题1：最长互异倍数子数组给定一个整数数组nums（元素可能为正、负或0）和正整数K，找出nums中最长的连续子数组，满足以下两个条件：（1）子数组元素的和是K的倍数（即和modK=0）；（2）子数组中的元素互不相同。若不存在符合条件的子数组，返回0。答案：最长长度为max_len，具体实现步骤如下：解析：条件（1）要求子数组和为K的倍数，可通过前缀和模K解决。设前缀和数组为pre_sum，其中pre_sum[i]=(nums[0]+nums[1]+…+nums[i-1])modK，则子数组nums[j…i-1]的和modK=(pre_sum[i]pre_sum[j])modK。若该值为0，则pre_sum[i]≡pre_sum[j](modK)。条件（2）要求子数组元素互不相同，需用滑动窗口维护当前窗口内的元素集合，确保无重复。结合前缀和模K的性质，可设计如下算法：1.初始化pre_sum[0]=0（前缀和初始值），哈希表pos记录每个pre_sum值第一次出现的索引（用于快速查找相同模值的最早位置），滑动窗口左指针left=0，当前元素集合seen=空集合，max_len=0。2.遍历数组，计算当前前缀和模K的值current_mod=(pre_sum[-1]+nums[i])%K（注意处理负数模，如current_mod=(current_mod+K)%K）。3.检查current_mod是否在pos中：若是，记j=pos[current_mod]，则子数组nums[j…i]的和是K的倍数。此时需检查nums[j+1…i]中的元素是否互不相同（因j可能小于left，需确保窗口[left…i]内元素无重复）。若否，将current_mod存入pos，记录其索引为i+1（因pre_sum长度为i+1时对应前i个元素的和）。4.维护滑动窗口：将nums[i]加入seen，若nums[i]已存在，需移动left指针直到nums[i]被移出seen（同时从pos中移除不再需要的pre_sum值，因后续窗口左边界不会小于新的left）。5.每次窗口调整后，若存在j≤left且pre_sum[i+1]≡pre_sum[j](modK)，则计算窗口长度i-j+1，更新max_len。示例：nums=[3,1,2,6,-3],K=3。前缀和模3依次为0,0(3%3),1(3+1=4%3),0(4+2=6%3),0(6+6=12%3),0(12-3=9%3)。遍历到i=0（nums[0]=3），current_mod=0，pos已有0（初始值），j=0，子数组[0…0]和为3（3%3=0），元素唯一，max_len=1。i=1（nums[1]=1），current_mod=(0+1)%3=1，pos无1，存入pos[1]=2。seen={3,1}，无重复，窗口长度2，无符合条件的子数组（因current_mod=1未重复）。i=2（nums[2]=2），current_mod=(1+2)%3=0，pos已有0（索引0），j=0。检查nums[0…2]元素{3,1,2}无重复，和为6（6%3=0），长度3，max_len=3。i=3（nums[3]=6），current_mod=(0+6)%3=0，pos已有0（索引0），j=0。nums[0…3]元素{3,1,2,6}无重复，和为12（12%3=0），长度4，max_len=4。i=4（nums[4]=-3），current_mod=(0-3)%3=0，pos已有0（索引0），j=0。nums[0…4]元素{3,1,2,6,-3}无重复，和为9（9%3=0），长度5，max_len=5。最终返回5。问题2：DAG中最大异或路径给定一个有向无环图（DAG），每个节点有一个权值（0≤权值≤10^9），起点为s，终点为t。求从s到t的所有路径中，路径上所有节点权值的异或和的最大值（异或和定义为路径中所有节点权值依次异或的结果，如路径u→v→w的异或和为u.val^v.val^w.val）。答案：最大异或和为max_xor，可通过记忆化DFS或动态规划求解。解析：异或运算满足交换律和结合律，但路径顺序固定（DAG中路径是节点序列），因此异或和与路径顺序相关。DAG无环，可按拓扑序处理节点，记录每个节点到终点的最大异或和。步骤如下：1.对DAG进行拓扑排序，得到处理顺序（从终点t逆序处理，或从起点s顺序处理）。2.定义dp[u]为从节点u到t的最大异或和。初始时，dp[t]=t.val（因路径只有t自己）。3.按拓扑逆序（从t的前驱节点开始）更新dp[u]：对于u的每个后继v，dp[u]=max(dp[u],u.val^dp[v])。4.最终max_xor=dp[s]。示例：DAG结构：s→a→t，s→b→t，节点权值s=3，a=5，b=1，t=2。拓扑逆序为t→a→b→s。dp[t]=2。处理a：a的后继是t，dp[a]=5^dp[t]=5^2=7。处理b：b的后继是t，dp[b]=1^dp[t]=1^2=3。处理s：s的后继是a和b，dp[s]=max(3^dp[a],3^dp[b])=max(3^7=4,3^3=0)=4。最大异或和为4（路径s→a→t：3^5^2=4）。问题3：受限编辑距离给定两个字符串s和t（s长度≥t长度），每次操作可以：删除s中的一个字符（代价1）；替换s中的一个字符为任意字符（代价1，但最多使用1次替换操作）。求将s转换为t的最小操作次数。答案：最小操作次数为min_ops，通过动态规划求解。解析：常规编辑距离允许插入、删除、替换，本题限制替换最多1次且无插入（因s长度≥t）。定义状态dp[i][j][k]，其中i是s的前i个字符，j是t的前j个字符，k=0或1表示是否已使用替换操作。目标是dp[len(s)][len(t)][0/1]的最小值。状态转移：若s[i-1]==t[j-1]，则无需操作，dp[i][j][k]=dp[i-1][j-1][k]。否则：删除s的第i个字符：dp[i][j][k]=dp[i-1][j][k]+1。若k=0（未使用替换），替换s的第i个字符为t的第j个字符：dp[i][j][1]=dp[i-1][j-1][0]+1。无法插入（因s不能变长）。初始条件：dp[0][0][0]=0，dp[0][0][1]=INF（未操作但已用替换，不可能）。dp[i][0][k]=i（删除前i个字符）。dp[0][j][k]=INF（s为空无法匹配t非空）。示例：s="abcde",t="axce"。s长度5，t长度4。i=1（s[0]='a'），j=1（t[0]='a'），k=0：dp[1][1][0]=0。i=2（s[1]='b'），j=2（t[1]='x'），字符不等：删除：dp[2][2][0]=dp[1][2][0]+1（但j=2时s前1字符无法匹配t前2字符，dp[1][2][0]=INF）。替换（k=0→1）：dp[2][2][1]=dp[1][1][0]+1=0+1=1。i=3（s[2]='c'），j=3（t[2]='c'），字符相等：dp[3][3][1]=dp[2][2][1]=1。i=4（s[3]='d'），j=4（t[3]='e'），字符不等：删除：dp[4][4][1]=dp[3][4][1]+1（dp[3][4][1]需看i=3,j=4是否可能，t长度4，s前3字符最多匹配t前3字符，j=4时需删除s[3]，但此时j=4，i=3无法满足，故dp[3][4][1]=INF）。替换不可用（k=1已用）。因此需删除s[3]，操作次数+1，总为1+1=2？实际正确路径是：s[1]替换为x（操作1），s[3]删除（操作1），总次数2。最终min_ops=2。问题4：环形01数组的最小翻转次数给定一个由0和1组成的环形数组arr（首尾相连），求最少需要翻转多少个位置的值（0变1，1变0），使得数组中存在至少一段连续的1的长度≥L（L≤数组长度n）。答案：最小翻转次数为min_flips，通过滑动窗口处理环形数组。解析：环形数组可展开为双倍长度的数组（如arr+arr），避免处理首尾相连的边界。目标是在展开后的数组中找到长度为L的窗口，其中0的数量最少（因翻转0可得到1）。步骤：1.展开数组为double_arr=arr+arr。2.初始化窗口左指针left=0，当前窗口0的数量zero_count=0，min_flips=INF。3.遍历右指针right从0到2n-1：若double_arr[right]==0，zero_count+1。若窗口长度>L，移动left指针，若double_arr[left]==0，zero_count-1，left+1。当窗口长度==L时，若right<n（避免重复计算环形部分），更新min_flips为min(min_flips,zero_count)。4.最终min_flips即为答案（若min_flips为INF，返回n，即翻转所有元素）。示例：arr=[0,1,0,0,1]（n=5），L=3。展开为[0,1,0,0,1,0,1,0,0,1]。寻找长度为3的窗口：[0,1,0]：2个0→需翻转2次→连续1长度3（翻转后为1,1,1）。[1,0,0]：2个0→翻转2次→1,1,1。[0,0,1]：2个0→翻转2次→1,1,1。[0,1,0]（环形部分，right=5，对应原数组索引0）：同第一个窗口。[1,0,0]（right=6）：同第二个窗口。实际最小翻转次数为2（如翻转索引0和2，得到[1,1,1,0,1]，连续1长度3）。问题5：任务步骤交叉执行数有n个不同的任务，每个任务需要按顺序完成m个不同的步骤（步骤顺序固定，如任务A的步骤为A1→A2→…→Am）。任务之间的步骤可以交叉执行（如A1→B1→A2→B2是合法的），但每个任务的步骤必须保持顺序。求所有可能的执行序列总数。答案：执行序列总数为(mn)!/(m!^n)。解析：总共有mn个步骤（每个任务m步），需将这些步骤排列成一个序列，同时保持每个任务内部步骤的相对顺序。这是一个多序列合并问题。例如，n=2，m=2时，总共有4个步骤（A1,A2,B1,B2），合法序列数为C(4,2)=6（选择A1和A2的位置，剩下的为B的步骤）。一般化地，对于n个任务，每个任务m步，总排列数相当于将mn个位置分配给n个任务，每个任务占m个位置且顺序固定。