这道题的核心是贪心排序Python实现的关键在于自定义排序规则。核心解题思路每个片段形如 111...000...nums1[i] 个 1 后跟 nums0[i] 个 0。排序规则1. 纯 1 片段优先nums0[i] 0 的片段全由 1 组成2. 1 多的靠前1 的数量越多高位 1 越多3. 1 相同时0 少的靠前Python3 代码实现pythonclass Solution:def maxValue(self, nums1: List[int], nums0: List[int]) - int:MOD 10**9 7n len(nums1)# 1. 创建片段列表 (ones, zeros)fragments list(zip(nums1, nums0))# 2. 自定义排序使用 functools.cmp_to_keyfrom functools import cmp_to_keydef compare(a, b):ones_a, zeros_a aones_b, zeros_b b# 纯 1 片段优先if zeros_a 0 and zeros_b 0:return ones_b - ones_a # 1 多的在前if zeros_a 0:return -1if zeros_b 0:return 1# 都含 01 多的在前if ones_a ! ones_b:return ones_b - ones_a# 1 相同0 少的在前return zeros_a - zeros_bfragments.sort(keycmp_to_key(compare))# 3. 拼接并计算结果ans 0for ones, zeros in fragments:# 追加 ones 个 1for _ in range(ones):ans (ans * 2 1) % MOD# 追加 zeros 个 0for _ in range(zeros):ans (ans * 2) % MODreturn ans更简洁的实现使用 key 参数如果不想用 cmp_to_key可以构造一个复合的排序键pythonclass Solution:def maxValue(self, nums1: List[int], nums0: List[int]) - int:MOD 10**9 7fragments list(zip(nums1, nums0))# 排序键# 1. 是否纯 1纯 1 优先# 2. 1 的数量降序# 3. 0 的数量升序fragments.sort(keylambda x: (x[1] ! 0, # False纯1排在 True含0前面-x[0], # 1 多的在前x[1] # 0 少的在前))ans 0for ones, zeros in fragments:# 批量处理优化避免逐位循环# 先处理 1ans (ans * pow(2, ones, MOD) (pow(2, ones, MOD) - 1)) % MOD# 再处理 0ans (ans * pow(2, zeros, MOD)) % MODreturn ans批量优化版本处理大片段当 nums1[i] 或 nums0[i] 很大时逐位循环可能较慢可以用幂运算批量处理pythonclass Solution:def maxValue(self, nums1: List[int], nums0: List[int]) - int:MOD 10**9 7fragments list(zip(nums1, nums0))# 排序同上fragments.sort(keylambda x: (x[1] ! 0, -x[0], x[1]))ans 0for ones, zeros in fragments:# 追加 ones 个 1ans ans * 2^ones (2^ones - 1)if ones 0:pow2_ones pow(2, ones, MOD)ans (ans * pow2_ones (pow2_ones - 1)) % MOD# 追加 zeros 个 0ans ans * 2^zerosif zeros 0:ans (ans * pow(2, zeros, MOD)) % MODreturn ans测试用例python# 测试sol Solution()# 示例 1print(sol.maxValue([1, 1], [1, 1])) # 输出61010 1010 10但 1100 不存在# 实际排序后 [1,1] 和 [1,1] 顺序不影响1010 10# 示例 2print(sol.maxValue([2, 1], [0, 1]))# fragments: [2,0] 11, [1,1] 10# 排序后[11, 10] - 1110 14# 输出14# 示例 3print(sol.maxValue([1, 2, 1], [2, 0, 1]))# fragments: [1,2]100, [2,0]11, [1,1]10# 排序[11, 10, 100] - 1110100 116# 输出116排序规则证明简洁版比较两个片段 A 和 B我们需要判断 AB 和 BA 哪个更大· 如果 A 全是 1AB 前缀是 1BA 前缀是 B 的第一个字符可能是 0所以 A 应在前· 如果都有 0比较 1 的数量多的在前因为高位 1 越多越大· 如果 1 数量相同0 少的在前因为 0 越早出现字典序越小复杂度分析· 时间复杂度O(n log n L)其中 L 是总长度sum(nums1) sum(nums0)· 空间复杂度O(n)用于存储片段列表关键注意事项1. 取模运算结果要对 10^97 取模2. 批量处理使用 pow(2, k, MOD) 可以快速处理连续的 1 或 03. 排序稳定性Python 的 sort 是稳定的但建议明确定义所有比较规则如果还有疑问欢迎继续追问 DeepSeek LeetCode 3897. 连接二进制片段得到的最大值 Python3实现
这道题的核心是贪心排序Python实现的关键在于自定义排序规则。核心解题思路每个片段形如 111...000...nums1[i] 个 1 后跟 nums0[i] 个 0。排序规则1. 纯 1 片段优先nums0[i] 0 的片段全由 1 组成2. 1 多的靠前1 的数量越多高位 1 越多3. 1 相同时0 少的靠前Python3 代码实现pythonclass Solution:def maxValue(self, nums1: List[int], nums0: List[int]) - int:MOD 10**9 7n len(nums1)# 1. 创建片段列表 (ones, zeros)fragments list(zip(nums1, nums0))# 2. 自定义排序使用 functools.cmp_to_keyfrom functools import cmp_to_keydef compare(a, b):ones_a, zeros_a aones_b, zeros_b b# 纯 1 片段优先if zeros_a 0 and zeros_b 0:return ones_b - ones_a # 1 多的在前if zeros_a 0:return -1if zeros_b 0:return 1# 都含 01 多的在前if ones_a ! ones_b:return ones_b - ones_a# 1 相同0 少的在前return zeros_a - zeros_bfragments.sort(keycmp_to_key(compare))# 3. 拼接并计算结果ans 0for ones, zeros in fragments:# 追加 ones 个 1for _ in range(ones):ans (ans * 2 1) % MOD# 追加 zeros 个 0for _ in range(zeros):ans (ans * 2) % MODreturn ans更简洁的实现使用 key 参数如果不想用 cmp_to_key可以构造一个复合的排序键pythonclass Solution:def maxValue(self, nums1: List[int], nums0: List[int]) - int:MOD 10**9 7fragments list(zip(nums1, nums0))# 排序键# 1. 是否纯 1纯 1 优先# 2. 1 的数量降序# 3. 0 的数量升序fragments.sort(keylambda x: (x[1] ! 0, # False纯1排在 True含0前面-x[0], # 1 多的在前x[1] # 0 少的在前))ans 0for ones, zeros in fragments:# 批量处理优化避免逐位循环# 先处理 1ans (ans * pow(2, ones, MOD) (pow(2, ones, MOD) - 1)) % MOD# 再处理 0ans (ans * pow(2, zeros, MOD)) % MODreturn ans批量优化版本处理大片段当 nums1[i] 或 nums0[i] 很大时逐位循环可能较慢可以用幂运算批量处理pythonclass Solution:def maxValue(self, nums1: List[int], nums0: List[int]) - int:MOD 10**9 7fragments list(zip(nums1, nums0))# 排序同上fragments.sort(keylambda x: (x[1] ! 0, -x[0], x[1]))ans 0for ones, zeros in fragments:# 追加 ones 个 1ans ans * 2^ones (2^ones - 1)if ones 0:pow2_ones pow(2, ones, MOD)ans (ans * pow2_ones (pow2_ones - 1)) % MOD# 追加 zeros 个 0ans ans * 2^zerosif zeros 0:ans (ans * pow(2, zeros, MOD)) % MODreturn ans测试用例python# 测试sol Solution()# 示例 1print(sol.maxValue([1, 1], [1, 1])) # 输出61010 1010 10但 1100 不存在# 实际排序后 [1,1] 和 [1,1] 顺序不影响1010 10# 示例 2print(sol.maxValue([2, 1], [0, 1]))# fragments: [2,0] 11, [1,1] 10# 排序后[11, 10] - 1110 14# 输出14# 示例 3print(sol.maxValue([1, 2, 1], [2, 0, 1]))# fragments: [1,2]100, [2,0]11, [1,1]10# 排序[11, 10, 100] - 1110100 116# 输出116排序规则证明简洁版比较两个片段 A 和 B我们需要判断 AB 和 BA 哪个更大· 如果 A 全是 1AB 前缀是 1BA 前缀是 B 的第一个字符可能是 0所以 A 应在前· 如果都有 0比较 1 的数量多的在前因为高位 1 越多越大· 如果 1 数量相同0 少的在前因为 0 越早出现字典序越小复杂度分析· 时间复杂度O(n log n L)其中 L 是总长度sum(nums1) sum(nums0)· 空间复杂度O(n)用于存储片段列表关键注意事项1. 取模运算结果要对 10^97 取模2. 批量处理使用 pow(2, k, MOD) 可以快速处理连续的 1 或 03. 排序稳定性Python 的 sort 是稳定的但建议明确定义所有比较规则如果还有疑问欢迎继续追问