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： 首先用靜態(tài)代碼塊對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;
? ?}
}打表 + 詞頻統(tǒng)計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;
? ?}
}
