[数据结构与算法]LeetCode-869-重新排序得到2的幂(reordered-power-of-2)

题目跳转

题目描述

给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

• 示例 1：
  输入：1
  输出：true
• 示例 2：
  输入：10
  输出：false
• 示例 3：
  输入：16
  输出：true
• 示例 4：
  输入：24
  输出：false
• 示例 5：
  输入：46
  输出：true
• 提示：
  1 <= N <= 10^9

思路一

因为n的范围为1到10 ^9,而2 ^30 刚好大于10 ^9,所以我们用一个集合将这些2的幂排序后存储起来，再判断排序后的n是否在集合中。

代码如下

class Solution {
    public boolean reorderedPowerOf2(int n) {
      Set<String> set=new HashSet<String>();

        for(int i=0;i<=29;i++){
            String s=String.valueOf((int)Math.pow(2,i));
            char []c=s.toCharArray();
            Arrays.sort(c);
            s=String.valueOf(c);
            set.add(s);
        }

        String s=String.valueOf(n);
        char []c=s.toCharArray();
        Arrays.sort(c);
        s=String.valueOf(c);
        if(set.contains(String.valueOf(s)))
          return true;
        else
        return false;
    }
}

思路二

搜索回溯加位运算
将n的十进制表示视作一个字符数组，我们可以枚举该数组的所有排列，对每个不含前导零的排列判断其对应的整数是否为 2的幂。
这可以拆分成两个子问题：

1. 枚举可能包含重复字符的数组的全排列，对应力扣47.全排列II
2. 判断一个整数是否为 22 的幂，对应力扣231.2的幂

对于本题的具体实现，我们可以在递归搜索全排列的同时，计算出当前排列的已枚举的部分所对应的整数 num。在我们枚举当前排列的下一个字符 ch 时，将 ch 加到 num 的末尾，即 num = num * 10 + ch - ‘0’，然后递归进入下一层。

代码如下

class Solution {
    boolean[] vis;

    public boolean reorderedPowerOf2(int n) {
        char[] nums = Integer.toString(n).toCharArray();
        Arrays.sort(nums);
        vis = new boolean[nums.length];
        return backtrack(nums, 0, 0);
    }

    public boolean backtrack(char[] nums, int idx, int num) {
        if (idx == nums.length) {
            return isPowerOfTwo(num);
        }
        for (int i = 0; i < nums.length; ++i) {
            // 不能有前导零
            if ((num == 0 && nums[i] == '0') || vis[i] || (i > 0 && !vis[i - 1] && nums[i] == nums[i - 1])) {
                continue;
            }
            vis[i] = true;
            if (backtrack(nums, idx + 1, num * 10 + nums[i] - '0')) {
                return true;
            }
            vis[i] = false;
        }
        return false;
    }

    public boolean isPowerOfTwo(int n) {
        return (n & (n - 1)) == 0;
    }
}