2026-07-27连接二进制片段得到的最大值。用go语言给定两个长度为 n 的整数数组 nums1 和 nums0其中 nums1[i] 代表第 i 个片段中 ‘1’ 的个数nums0[i] 代表该片段中 ‘0’ 的个数。对于每个 i我们构造一个二进制片段先写入 nums1[i] 个连续的 ‘1’紧接着写入 nums0[i] 个连续的 ‘0’。我们可以将这些片段以任意顺序重新排列然后将排列后的所有片段依次拼接成一个完整的二进制字符串。要求找出在所有可能的排列方式中该二进制字符串所能表示的最大整数值。由于答案可能很大请将其对 1000000007 取模后返回。1 n nums1.length nums0.length 100000。0 nums1[i], nums0[i] 10000。nums1[i] nums0[i] 0。nums1 和 nums0 中所有元素的总和不超过 200000。输入 nums1 [1,2], nums0 [1,0]。输出 14。解释在下标 0 处nums1[0] 1 且 nums0[0] 1因此形成的片段为 “10”。在下标 1 处nums1[1] 2 且 nums0[1] 0因此形成的片段为 “11”。将片段重新排序为 “11” 后跟 “10”生成二进制字符串 “1110”。二进制数 “1110” 的值为 14这是可能的最大值。题目来自力扣3897。大体步骤如下1. 预处理计算2的幂次方目的由于在后续计算中需要频繁地计算2^k mod MOD其中k是每个片段中 ‘1’ 或 ‘0’ 的数量提前预处理好这些值可以避免重复计算大大提高效率。过程创建一个大小为mx10001的数组pow2。pow2[0]初始化为 1代表2^0。通过一个循环利用递推关系pow2[i] (pow2[i-1] * 2) % MOD计算出从2^1到2^10000的所有值并存储起来。2. 确定片段的最佳拼接顺序这是算法的核心。目标是找出一种排列顺序使得最终拼接成的二进制字符串表示的数值最大。初始化创建一个索引数组idx长度等于片段总数n并填入0到n-1的序号。这个数组用于后续的排序我们不是直接移动原始的片段数据而是对它们的索引进行排序。自定义排序规则我们需要定义一种比较逻辑来判断任意两个片段A和B谁排在前面能使最终结果更大。这里的比较策略非常巧妙特殊情况处理比较片段i和片段j。规则1如果片段i的 ‘0’ 的个数为 0nums0[i] 0那么这个片段应该排在任何带有 ‘0’ 的片段nums0[j] 0之前。一个纯 ‘1’ 的片段放在前面可以确保它的高位全是 ‘1’从而最大化整个数值。规则2规则1的补充如果片段j的 ‘0’ 的个数为 0那么它应该排在片段i之前。一般情况比较如果两个片段都包含至少一个 ‘0’即nums0[i] 0且nums0[j] 0则我们需要一个通用的比较方法。我们实际上是在比较两种拼接方案片段i 片段j和片段j 片段i哪个更大。可以证明这种比较可以转化为优先比较两个片段中 ‘1’ 的个数。具体来看首先比较nums1[j]和nums1[i]的差值。如果nums1[j] - nums1[i] ! 0则意味着一个片段的 ‘1’ 比另一个多。拥有更多 ‘1’ 的片段应排在前面因为它能为高位贡献更多的 ‘1’。如果两个片段的 ‘1’ 的个数完全相同nums1[j] nums1[i]那么就需要比较它们 ‘0’ 的个数。此时包含更少‘0’ 的片段应排在前面。因为更少的 ‘0’ 意味着这个片段的结束部分会更短能更快地过渡到下一个片段的 ‘1’避免在数值的高位部分留下过多的 ‘0’。排序执行使用这个复杂的自定义比较规则对索引数组idx进行排序。排序后idx数组中的索引顺序就代表了片段的最佳拼接顺序。3. 迭代计算最终的最大值在得到了最佳拼接顺序即idx数组后我们模拟拼接过程逐步计算出最终数值的十进制表示对MOD取模。初始化答案ans为 0。按最优顺序遍历片段依次取出idx中的索引i。状态转移核心公式假设当前已拼接好的前缀字符串对应的数值是ans。下一个要拼接的片段包含onesnums1[i]个 ‘1’ 和zerosnums0[i]个 ‘0’。步骤3.1追加’1’s将当前值ans左移ones位相当于乘以2^ones然后追加ones个 ‘1’。这ones个 ‘1’ 代表的数值是(2^ones - 1)。因此这一步操作可以表达为新值 ans * (2^ones) (2^ones - 1)。代码中巧妙地将其合并为(ans 1) * pow2[ones] - 1。步骤3.2追加’0’s在步骤3.1的结果后面再追加zeros个 ‘0’。这相当于将当前值左移zeros位相当于乘以2^zeros。因此这一步操作表达为最终新值 步骤3.1的结果 * pow2[zeros]。取模每一步计算新值时都对MOD进行取模运算确保ans不会溢出且满足题目要求。完成遍历完所有片段后最终的ans就是所求的最大整数值。复杂度分析总的时间复杂度O(n log n M)M是mx即 10001。预处理pow2数组的时间复杂度是 O(M)。排序索引数组idx的时间复杂度是 O(n log n)n是片段的数量。迭代计算最终值的过程是 O(n)。主要瓶颈在于排序因此总时间复杂度为 O(n log n M)。总的额外空间复杂度O(n M)pow2数组的大小固定为M10001空间复杂度为 O(M)。索引数组idx的长度为n空间复杂度为 O(n)。其他变量使用的空间是常数级。因此总的额外空间需求是 O(n M)。Go完整代码如下packagemainimport(cmpfmtslices)constmod1_000_000_007constmx10001varpow2[mx]int{1}funcinit(){// 预处理 2 的幂fori:1;imx;i{pow2[i]pow2[i-1]*2%mod}}funcmaxValue(nums1,nums0[]int)(ansint){idx:make([]int,len(nums1))fori:rangeidx{idx[i]i}slices.SortFunc(idx,func(i,jint)int{ifnums0[i]0{return-1}ifnums0[j]0{return1}returncmp.Or(nums1[j]-nums1[i],nums0[i]-nums0[j])})for_,i:rangeidx{ans((ans1)*pow2[nums1[i]]-1)%mod*pow2[nums0[i]]%mod}return}funcmain(){nums1:[]int{1,2}nums0:[]int{1,0}result:maxValue(nums1,nums0)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-MOD1_000_000_007MX10001# 预处理 2 的幂pow2[1]*MXforiinrange(1,MX):pow2[i]pow2[i-1]*2%MODdefmaxValue(nums1,nums0):nlen(nums1)idxlist(range(n))# 自定义排序函数defsort_key(i):ifnums0[i]0:return(0,0,0)# 负数标记排最前面ifnums0[j]0:# 这个在排序比较中无法直接使用需要改为cmp方式return(2,0,0)# 正数标记排最后面# 使用functools.cmp_to_key来实现自定义比较fromfunctoolsimportcmp_to_keydefcmp_func(i,j):ifnums0[i]0:return-1ifnums0[j]0:return1# cmp.Or(nums1[j]-nums1[i], nums0[i]-nums0[j])diff1nums1[j]-nums1[i]ifdiff1!0:returndiff1returnnums0[i]-nums0[j]idx.sort(keycmp_to_key(cmp_func))ans0foriinidx:ans((ans1)*pow2[nums1[i]]-1)%MOD*pow2[nums0[i]]%MODreturnansdefmain():nums1[1,2]nums0[1,0]resultmaxValue(nums1,nums0)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includealgorithm#includefunctionalconstintMOD1000000007;constintMX10001;// 预处理 2 的幂std::vectorintpow2(MX);voidinit(){pow2[0]1;for(inti1;iMX;i){pow2[i](pow2[i-1]*2LL)%MOD;}}intmaxValue(conststd::vectorintnums1,conststd::vectorintnums0){intnnums1.size();std::vectorintidx(n);for(inti0;in;i){idx[i]i;}// 自定义排序std::sort(idx.begin(),idx.end(),[](inti,intj){if(nums0[i]0){returntrue;// i 排在前面}if(nums0[j]0){returnfalse;// j 排在前面}// cmp.Or(nums1[j]-nums1[i], nums0[i]-nums0[j])intdiff1nums1[j]-nums1[i];if(diff1!0){returndiff10;// nums1[i] nums1[j] 时 i 排在前面}returnnums0[i]-nums0[j]0;});longlongans0;for(inti:idx){ans(((ans1)*pow2[nums1[i]]-1)%MOD)*pow2[nums0[i]]%MOD;ans(ansMOD)%MOD;// 确保结果为正}returnstatic_castint(ans);}intmain(){// 初始化pow2数组init();std::vectorintnums1{1,2};std::vectorintnums0{1,0};intresultmaxValue(nums1,nums0);std::coutresultstd::endl;return0;}