2025-05-05：连接二进制表示可形成的最大数值。用go语言，给定一个包含三个整数的数组 nums。

将数组中所有元素的二进制形式以某种顺序拼接起来，要求拼接后的二进制字符串所表示的数值尽可能大。

其中，每个数字的二进制表示不包含前导零。

请你返回通过这种方式能得到的最大数值。

nums.length == 3。

1 <= nums[i] <= 127。

输入: nums = [2,8,16]。

输出: 1296。

解释:

按照顺序 [2, 8, 16] 连接数字的二进制表述，得到结果 "10100010000"，这是 1296 的二进制表示。

题目来自leetcode3309。

分步骤描述过程：

1. 1. 理解题目要求：
2. o 给定三个整数，需要将它们按某种顺序排列，然后将它们的二进制表示按顺序拼接起来，形成一个更大的二进制数。
3. o 这个拼接后的二进制数不能有前导零（即每个数字的二进制表示本身没有前导零，拼接时也不会引入前导零）。
4. o 目标是找到一种排列顺序，使得拼接后的二进制数对应的十进制值最大。
5. 2. 示例分析：
6. o 输入 nums = [2, 8, 16]：
7. o 2 的二进制是 10（长度 2）
8. o 8 的二进制是 1000（长度 4）
9. o 16 的二进制是 10000（长度 5）
10. o 可能的拼接顺序：
11. o [2, 8, 16] -> "10" + "1000" + "10000" -> 10100010000（1296）
12. o [2, 16, 8] -> "10" + "10000" + "1000" -> 10100001000（1288）
13. o [8, 2, 16] -> "1000" + "10" + "10000" -> 10001010000（1104）
14. o [8, 16, 2] -> "1000" + "10000" + "10" -> 10001000010（1090）
15. o [16, 2, 8] -> "10000" + "10" + "1000" -> 10000101000（1064）
16. o [16, 8, 2] -> "10000" + "1000" + "10" -> 10000100010（1042）
17. o 最大值为 10100010000（1296），对应顺序 [2, 8, 16]。
18. 3. 排序策略：
19. o 为了找到最优的拼接顺序，需要对三个数字进行排序。
20. o 排序的比较规则是：对于两个数字 a 和 b，比较 (b << lenA | a) 和 (a << lenB | b)，其中 lenA 和 lenB 分别是 a 和 b 的二进制位数。
21. o 如果 (b << lenA | a) > (a << lenB | b)，则 a 应该排在 b 前面，否则 b 排在前面。
22. o 这种比较规则确保拼接后的二进制数尽可能大。
23. 4. 排序过程：
24. o 对于 nums = [2, 8, 16]：
25. o 比较 2 和 8：
26. o lenA = 2, lenB = 4
27. o (8 << 2 | 2) = 32 | 2 = 34
28. o (2 << 4 | 8) = 32 | 8 = 40
29. o 34 < 40，所以 8 应该排在 2 前面。
30. o 比较 8 和 16：
31. o lenA = 4, lenB = 5
32. o (16 << 4 | 8) = 256 | 8 = 264
33. o (8 << 5 | 16) = 256 | 16 = 272
34. o 264 < 272，所以 16 应该排在 8 前面。
35. o 比较 2 和 16：
36. o lenA = 2, lenB = 5
37. o (16 << 2 | 2) = 64 | 2 = 66
38. o (2 << 5 | 16) = 64 | 16 = 80
39. o 66 < 80，所以 16 应该排在 2 前面。
40. o 最终排序顺序：[2, 8, 16]。
41. 5. 拼接二进制：
42. o 按排序后的顺序 [2, 8, 16] 拼接二进制：
43. o 2 -> 10
44. o 8 -> 1000
45. o 16 -> 10000
46. o 拼接结果：10100010000。
47. o 转换为十进制：10100010000 -> 1*2^10 + 0*2^9 + 1*2^8 + 0*2^7 + 0*2^6 + 0*2^5 + 1*2^4 + 0*2^3 + 0*2^2 + 0*2^1 + 0*2^0 = 1024 + 256 + 16 = 1296。
48. 6. 计算最终结果：
49. o 将排序后的数字依次拼接二进制表示，然后转换为十进制，得到最大值 1296。

时间复杂度和额外空间复杂度：

• o 时间复杂度：
• o 排序的时间复杂度：由于只有 3 个数字，排序的比较次数是常数（最多 3 次比较），每次比较的计算也是常数时间（计算位数和移位操作）。
• o 计算二进制位数的时间：bits.Len 是 O(1) 操作。
• o 拼接二进制的时间：遍历排序后的数组，拼接操作是常数时间（因为数字的二进制位数最多是 7 位，即 127 的二进制是 1111111）。
• o 总体时间复杂度是 O(1)（因为输入规模固定为 3）。
• o 额外空间复杂度：
• o 排序可能需要 O(1) 的额外空间（原地排序）。
• o 没有使用额外的数据结构，空间复杂度是 O(1)。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
    "math/bits"
)

func maxGoodNumber(nums []int) (ans int) {
    slices.SortFunc(nums, func(a, b int)int {
        lenA := bits.Len(uint(a))
        lenB := bits.Len(uint(b))
        return (b<<lenA | a) - (a<<lenB | b)
    })

    for _, x := range nums {
        ans = ans<<bits.Len(uint(x)) | x
    }
    return
}


func main() {
    nums := []int{2,8,16}
    result := maxGoodNumber(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from functools import cmp_to_key

defmax_good_number(nums):
    defcompare(a, b):
        lenA = a.bit_length()
        lenB = b.bit_length()
        # 模拟 Go 中位运算构造的比较方式
        val1 = (b << lenA) | a
        val2 = (a << lenB) | b
        # 返回正负决定排序顺序
        return val2 - val1  # 因为 Go排序传入返回 a-b，Python中 cmp 返回 <0表示a<b，所以反向用了 val2 - val1

    nums.sort(key=cmp_to_key(compare))
    ans = 0
    for x in nums:
        ans = (ans << x.bit_length()) | x
    return ans


if __name__ == "__main__":
    nums = [2, 8, 16]
    result = max_good_number(nums)
    print(result)

·

我们相信 Go 语言和算法为普通开发者提供了强有力的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的 Go 语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大大架构师每日一题”，让 Go 语言和算法助力您的职业发展

·