dfs/重新排列得到2的幂
869 重新排列得到2的幂
出现问题：当使用i=start+1的方式进行传参时，并不能搜索出一些结果。例如：46 变不成64，需要使用vis数组进行标记的方式才可以：
官方：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;
}
}三叶：bfs： 首先用静态代码块对set进行了预处理，然后将数值映射到一个数组上（非字符串的方式），这样就可以知道哪个数字出现多少次了class Solution { static Set<Integer> set = new HashSet<>(); static { for (int i = 1; i < (int)1e9+10; i *= 2) set.add(i);
} int m; int[] cnts = new int[10]; public boolean reorderedPowerOf2(int n) { while (n != 0) { //对数字进行映射
cnts[n % 10]++;
n /= 10;
m++;
} return dfs(0, 0);
} boolean dfs(int u, int cur) { if (u == m) return set.contains(cur); for (int i = 0; i < 10; i++) { if (cnts[i] != 0) {//迷宫表的方式
cnts[i]--; if ((i != 0 || cur != 0) && dfs(u + 1, cur * 10 + i)) return true;
//cur*10+i cur*10 因为整个数值加了一位，所以要乘10 ，而i对应的就是现在cnts存有数字的情况（>0)
cnts[i]++; //回溯
}
} return false;
}
}打表 + 词频统计class Solution { static Set<Integer> set = new HashSet<>(); static { for (int i = 1; i < (int)1e9+10; i *= 2) set.add(i);
} public boolean reorderedPowerOf2(int n) { int[] cnts = new int[10]; while (n != 0) {
cnts[n % 10]++;
n /= 10;
} int[] cur = new int[10];
out:for (int x : set) {
Arrays.fill(cur, 0); while (x != 0) {
cur[x % 10]++;
x /= 10;
} for (int i = 0; i < 10; i++) { if (cur[i] != cnts[i]) continue out;
} return true;
} return false;
}
}
