【LeetCode】重新排序得到 2 的幂 Java 题解

2021 年 11 月 15 日
本文字数：1042 字
阅读完需：约 3 分钟

题目描述

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

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


示例 1：
输入：1输出：true
示例 2：
输入：10输出：false示例 3：
输入：16输出：true
示例 4：
输入：24输出：false
示例 5：
输入：46输出：true

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reordered-power-of-2著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是重新排序得到 2 的幂，根据题意，拆分成两个子问题分别求解。子问题 1 是枚举所有 N 的组合数，子问题 2 是求 2 的幂。
对于子问题 1，首先讲输入的 n 转换成数组，然后采用回溯的算法思想和框架，使用 boolean[] visited 记录使用过的数组元素，枚举所有的组合。
对于子问题 2，我们可以使用位运算，快速计算是否是 2 的幂。
子问题求解思路明确之后，在结合题目，**将数字重新排序，注意其前导数字不能为零。**使用这一重要条件，对回溯的过程进行减枝，提升算法执行效率，实现代码如下：

通过代码

class Solution {    boolean[] visited;
    public boolean reorderedPowerOf2(int n) {        char[] nums = Integer.toString(n).toCharArray();        Arrays.sort(nums);        int m = nums.length;        visited = new boolean[m];        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') || visited[i] || (i > 0 && !visited[i - 1] && nums[i] == nums[i - 1])) {                continue;            }
            visited[i] = true;            if (backtrack(nums, idx + 1, num * 10 + nums[i] - '0')) {                return true;            }            visited[i] = false;        }
        return false;    }

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