【LeetCode】3309. 连接二进制表示可形成的最大数值（递归|回溯|位运算）

题目描述

题目链接：LeetCode 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

解题思路

1.整体思路：使用递归回溯的方式尝试构造所有的拼接方案（构造全排列），取拼接方案中数值最大的即可。递归回溯法的关键在于：每次尝试之后，进行递归回退时要撤销尝试，将状态恢复成尝试之前的状态。

2.实现细节：开一个数组 $vis$ 来记录元素是否被选取过，$vis[i]$ 表示第 $i$ 个数是否被选取过（$0$ 没选过，$1$ 选过）。每次尝试从 $nums$ 数组中选取一个没被选过的数 $nums[i]$ 拼接得到 $cancat$ ，将 $vis[i]$ 置为 $1$，表示该数已被选取过。当 $nums$ 中的数都被选过时得到一种拼接方式，直接返回 $cancat$ 。每次回退时取消当前尝试，将 $vis[i]$ 恢复为 $0$，将 $cancat$ 恢复成之前的取值。在尝试的过程中更新拼接方案的最大取值。

3.如何实现二进制数的拼接：当前要拼接的数 $nums[i]$ 二进制有几位，就把 $concat$ 左移几位，然后将当前的数 $nums[i]$ 加到 $concat$ 上就实现了拼接。

Java代码

public class Solution {

    public int maxGoodNumber(int[] nums) {
        int vis[] = new int[nums.length];
        return dfs(0, 0, nums, vis);
    }
    /**
     * count:   已经选取的数的个数
     * concat:  拼接得到的数
     * nums:    可选数的数组
     * vis[i]:  第i个数是否被选取过
     */
    int dfs(int count, int concat, int nums[], int vis[]) {
        if (count == nums.length) {
            // 所有的数的被选过，得到最终拼接的数
            return concat;
        }

        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            // 判断当前数是否拼接过
            if (vis[i] == 0) {
                int x = nums[i], temp = concat;
                while (x > 0) {
                    x = x >> 1;
                    concat = concat << 1;
                }
                // 尝试拼接
                concat += nums[i];
                vis[i] = 1;
                // 可行拼接中取最大值
                res = Math.max(res, dfs(count + 1, concat, nums, vis));
                // 尝试完之后复原到拼接前的数
                concat = temp;
                vis[i] = 0;
            }
        }
        return res;
    }
}