“leecode打卡，我还是暴力法吧”
题干
给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例
示例 1：
输入：1 输出：true
示例 2：
输入：10 输出：false
示例 3：
输入：16 输出：true
示例 4：
输入：24 输出：false
示例 5：
输入：46 输出：true
提示：
- $1 <= N <= 10^9$
题解
没有太多需要特别注意的，可以说下面两点：
位运算
计算一个数$n$是不是$2$的整数次幂，用了一个位运算的技巧:
(n & (n - 1)) == 0;
传参
Java的函数入参，默认传引用，不是C++中的拷贝传递，因此需要这样传递：
dfs(new ArrayList<>(list), tempList, result);
代码
public class Main {
public static boolean reorderedPowerOf2(int n) {
List<Integer> numList = getNumList(n);
List<Integer> result = new ArrayList<>();
dfs(numList, new LinkedList<>(), result);
for (Integer integer : result) {
if (isPowerOf2(integer)) {
return true;
}
}
return false;
}
private static boolean isPowerOf2(int n) {
return (n & (n - 1)) == 0;
}
private static List<Integer> getNumList(int n) {
List<Integer> list = new ArrayList<>();
while (n > 0) {
list.add(n % 10);
n /= 10;
}
return list;
}
private static void dfs(List<Integer> list, LinkedList<Integer> tempList, List<Integer> result) {
// add this result to result list
if (list.isEmpty()) {
int sum = 0;
for (Integer integer : tempList) {
sum = sum * 10 + integer;
}
result.add(sum);
return;
}
// backtrack
for (int i = 0; i < list.size(); i++) {
if (tempList.isEmpty() && list.get(i) == 0) {
continue;
}
tempList.add(list.remove(i));
dfs(new ArrayList<>(list), tempList, result);
list.add(i, tempList.removeLast());
}
}
public static void main(String[] args) {
System.out.println(reorderedPowerOf2(46));
}
}
官方题解（哈希字典法）
这个解法我觉得特异性太强了，泛用性不强，但是看一眼无妨
由于我们可以按任何顺序将数字重新排序，因此对于两个不同的整数 $a$ 和 $b$ ，如果其十进制表示的字符数组，从小到大排序后的结果是相同的，那么若 $a$ 能够重排得到 $2$ 的幂，$b$ 也可以；若 $a$ 不能重排得到 $2$ 的幂，那么 $b$ 也不能。
进一步地，只要 $a$ 和 $b$ 的十进制表示的字符数组中，从 $0$ 到 $9$ 每个字符的出现次数，在 $a$ 和 $b$ 中都是一样的，那么 $a$ 和 $b$ 能否重排得到 $2$ 的幂的结果是一样的。
由于 $2^{29} < 10^9 < 2^{30}$ ，因此在 $[1,10^9]$ 范围内有 $2^0,2^1,\cdots,2^{29}$ 一共 $30$ 个 $2$ 的幂。对这 $30$ 个数的每个数，我们可以预处理其十进制表示的字符数组中从 $0$ 到 $9$ 每个字符的出现次数，记在一个长度为 $10$ 的数组中，并用一哈希表记录这些数组。对于数字 $n$ ，我们同样统计其十进制表示的字符数组中从 $0$ 到 $9$ 每个字符的出现次数，然后去哈希表中查找，若存在则说明 $n$ 可以通过重排得到 $2$ 的幂，否则不能。
class Solution {
Set<String> powerOf2Digits = new HashSet<String>();
public boolean reorderedPowerOf2(int n) {
init();
return powerOf2Digits.contains(countDigits(n));
}
public void init() {
for (int n = 1; n <= 1e9; n <<= 1) {
powerOf2Digits.add(countDigits(n));
}
}
public String countDigits(int n) {
char[] cnt = new char[10];
while (n > 0) {
++cnt[n % 10];
n /= 10;
}
return new String(cnt);
}
}
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/reordered-power-of-2/solution/zhong-xin-pai-xu-de-dao-2-de-mi-by-leetc-4fvs/
// 来源：力扣（LeetCode）
补充
track列表使用链表实现
链表移除尾部元素需要 $o(1)$ 复杂度，如果是数组则需要 $o(n)$ 复杂度
全排列写法要点
如果一个元素已经被选择过，不应该直接将该元素移除，而是应该建一个布尔数组boolean[] marked，对应的索引设为true。
如果不想递归函数的入参太多，可以改成使用私有变量
public class Main2 {
/**
* n每一位构成的list
*/
private List<Integer> numList;
/**
* track
*/
private LinkedList<Integer> track;
/**
* result list
*/
private List<Integer> result;
/**
* numList中第i个数有没有被选中
*/
private boolean[] marked;
public boolean reorderedPowerOf2(int n) {
numList = getNumList(n);
track = new LinkedList<>();
result = new ArrayList<>();
marked = new boolean[numList.size()];
backtrack();
for (int integer : result) {
if (isPowerOf2(integer)) {
return true;
}
}
return false;
}
private static boolean isPowerOf2(int n) {
return (n & (n - 1)) == 0;
}
private static List<Integer> getNumList(int n) {
List<Integer> list = new ArrayList<>();
while (n > 0) {
list.add(n % 10);
n /= 10;
}
return list;
}
private void backtrack() {
// add this result to result list
if (track.size() == numList.size()) {
int sum = 0;
for (Integer integer : track) {
sum = sum * 10 + integer;
}
result.add(sum);
return;
}
// backtrack
for (int i = 0; i < numList.size(); i++) {
if (marked[i] || (track.isEmpty() && numList.get(i) == 0)) {
continue;
}
track.add(numList.get(i));
marked[i] = true;
backtrack();
marked[i] = false;
track.removeLast();
}
}
public static void main(String[] args) {
System.out.println(new Main2().reorderedPowerOf2(215));
}
}
