跳转至

3309. 连接二进制表示可形成的最大数值

题目描述

给你一个长度为 3 的整数数组 nums。

现以某种顺序 连接 数组 nums 中所有元素的 二进制表示 ，请你返回可以由这种方法形成的 最大 数值。

注意 任何数字的二进制表示 不含 前导零。

 

示例 1:

输入: nums = [1,2,3]

输出: 30

解释:

按照顺序 [3, 1, 2] 连接数字的二进制表示，得到结果 "11110"，这是 30 的二进制表示。

示例 2:

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

输出: 1296

解释:

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

 

提示:

  • nums.length == 3
  • 1 <= nums[i] <= 127

解法

方法一：枚举

根据题目描述，数组 \(\textit{nums}\) 的长度为 \(3\)，我们可以枚举 \(\textit{nums}\) 的全排列，一共有 \(3! = 6\) 种排列方式，然后将排列后的数组中的元素转换为二进制字符串，再将这些二进制字符串连接起来，最后将连接后的二进制字符串转换为十进制数，取最大值即可。

时间复杂度 \(O(\log M)\)，其中 \(M\) 表示 \(\textit{nums}\) 中的元素的最大值。空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
class Solution:
    def maxGoodNumber(self, nums: List[int]) -> int:
        ans = 0
        for arr in permutations(nums):
            num = int("".join(bin(i)[2:] for i in arr), 2)
            ans = max(ans, num)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private int[] nums;

    public int maxGoodNumber(int[] nums) {
        this.nums = nums;
        int ans = f(0, 1, 2);
        ans = Math.max(ans, f(0, 2, 1));
        ans = Math.max(ans, f(1, 0, 2));
        ans = Math.max(ans, f(1, 2, 0));
        ans = Math.max(ans, f(2, 0, 1));
        ans = Math.max(ans, f(2, 1, 0));
        return ans;
    }

    private int f(int i, int j, int k) {
        String a = Integer.toBinaryString(nums[i]);
        String b = Integer.toBinaryString(nums[j]);
        String c = Integer.toBinaryString(nums[k]);
        return Integer.parseInt(a + b + c, 2);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxGoodNumber(vector<int>& nums) {
        int ans = 0;
        auto f = [&](vector<int>& nums) {
            int res = 0;
            vector<int> t;
            for (int x : nums) {
                for (; x; x >>= 1) {
                    t.push_back(x & 1);
                }
            }
            while (t.size()) {
                res = res * 2 + t.back();
                t.pop_back();
            }
            return res;
        };
        for (int i = 0; i < 6; ++i) {
            ans = max(ans, f(nums));
            next_permutation(nums.begin(), nums.end());
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func maxGoodNumber(nums []int) int {
    f := func(i, j, k int) int {
        a := strconv.FormatInt(int64(nums[i]), 2)
        b := strconv.FormatInt(int64(nums[j]), 2)
        c := strconv.FormatInt(int64(nums[k]), 2)
        res, _ := strconv.ParseInt(a+b+c, 2, 64)
        return int(res)
    }
    ans := f(0, 1, 2)
    ans = max(ans, f(0, 2, 1))
    ans = max(ans, f(1, 0, 2))
    ans = max(ans, f(1, 2, 0))
    ans = max(ans, f(2, 0, 1))
    ans = max(ans, f(2, 1, 0))
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function maxGoodNumber(nums: number[]): number {
    const f = (i: number, j: number, k: number): number => {
        const a = nums[i].toString(2);
        const b = nums[j].toString(2);
        const c = nums[k].toString(2);
        const res = parseInt(a + b + c, 2);
        return res;
    };

    let ans = f(0, 1, 2);
    ans = Math.max(ans, f(0, 2, 1));
    ans = Math.max(ans, f(1, 0, 2));
    ans = Math.max(ans, f(1, 2, 0));
    ans = Math.max(ans, f(2, 0, 1));
    ans = Math.max(ans, f(2, 1, 0));

    return ans;
}

评论