给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：n = 1 输出：true
示例 2：
输入：n = 10 输出：false
提示：
1 <= n <= 109
Related Topics
明明各方面都非常的符合题意，但是只击败了5.28%的勇者【怎么都在打表】
emmm，emmm，emmm，能AC，海星
思路什么的，就回溯，转2进制，判断除了第一位之后有没有其他的1
class Solution {
int[] arr;
int[] sizeMap = {0,9,99,999,9999,99999,999999,9999999,99999999,999999999,2147483647};
public boolean reorderedPowerOf2(int n) {
if (n==0){
return false;
}
int size = 0;
//看看这个数字能转成多大的int[]数组，然后用来执行回溯
for (int i = 0; i < sizeMap.length; i++) {
if (sizeMap[i] >= n){
size = i;
break;
}
}
arr = new int[size];
//把n数字的个位置上的数字放入数组中
while (n > 0){
arr[--size] = n % 10;
n /= 10;
}
//执行回溯
return dfs(0,0,new boolean[arr.length]);
}
/**
* 判断一个数字是否是2的幂
* @param num
* @return
*/
public boolean isPowerOf2(int num){
int[] intArr = toBinaryArr(num);
for (int i = 1; i < intArr.length; i++) {
//2的幂的二进制有一个特点，就是只有第一位是1，后面都是0，
//从第二位开始判断但凡有一个数字等于1，就返回false
if (intArr[i] == 1){
return false;
}
}
//后面都没有1，只有第一位是1，那么返回true;
return true;
}
/**
* 把一个数字转换成二进制int[]数组
* @param num
* @return
*/
public int[] toBinaryArr(int num){
int size = 32;
//最大就32位，往大了写，之间判断某个数字的二进制数字有多长有点麻烦
int[] intArr = new int[size];
while (num > 0 ){
//依次余2赋值在每一位上
intArr[--size] = num % 2;
num = num >> 1;
}
//到这里就已经知道之前用了多少位了，返回一个新的不含前面多余0的二进制数数字
int[] res = new int[32 - size];
System.arraycopy(intArr,size,res,0,32-size);
return res;
}
/**
* 回溯算法
* @param num 当前数字
* @param idx 当前数字的位数的
* @param used arr[]数组中哪些位置已经被用过了
* @return
*/
public boolean dfs(int num, int idx, boolean[] used){
if (idx == arr.length ){
//终止条件，判断下这个数是否是2的幂数
if (isPowerOf2(num)){
return true;
}
return false;
}
//当前数字乘以10，准备在后面再加上一个数字
num *= 10;
for (int i = 0; i < arr.length; i++) {
//第一位数字不能为0
//或者这个位置的数字已经用过了，那么跳过到下一个选项
if ((idx == 0 && arr[i] == 0) || used[i]){
continue;
}
//标记当前数字用过了
used[i] = true;
//构建了新数字num+arr[i] 然后处理下一个情况
if (dfs(num+arr[i],idx+1,used)){
//如果能满足就直接终止
return true;
}
//回溯的重要操作，将状态改回
used[i] = false;
}
//如果都不能满足，返回false
return false;
}
}
看了一圈好像都在打表。。。。
我也凑个热闹吧
class Solution {
int[][] arr = {
{1,1,0,0,0,0,0,0,0,0,0},
{1,2,0,0,0,0,0,0,0,0,0},
{1,4,0,0,0,0,0,0,0,0,0},
{1,8,0,0,0,0,0,0,0,0,0},
{2,1,6,0,0,0,0,0,0,0,0},
{2,2,3,0,0,0,0,0,0,0,0},
{2,4,6,0,0,0,0,0,0,0,0},
{3,1,2,8,0,0,0,0,0,0,0},
{3,2,5,6,0,0,0,0,0,0,0},
{3,1,2,5,0,0,0,0,0,0,0},
{4,0,1,2,4,0,0,0,0,0,0},
{4,0,2,4,8,0,0,0,0,0,0},
{4,0,4,6,9,0,0,0,0,0,0},
{4,1,2,8,9,0,0,0,0,0,0},
{5,1,3,4,6,8,0,0,0,0,0},
{5,2,3,6,7,8,0,0,0,0,0},
{5,3,5,5,6,6,0,0,0,0,0},
{6,0,1,1,2,3,7,0,0,0,0},
{6,1,2,2,4,4,6,0,0,0,0},
{6,2,2,4,5,8,8,0,0,0,0},
{7,0,1,4,5,6,7,8,0,0,0},
{7,0,1,2,2,5,7,9,0,0,0},
{7,0,1,3,4,4,4,9,0,0,0},
{7,0,3,6,8,8,8,8,0,0,0},
{8,1,1,2,6,6,7,7,7,0,0},
{8,2,3,3,3,4,4,5,5,0,0},
{8,0,1,4,6,6,7,8,8,0,0},
{9,1,1,2,2,3,4,7,7,8,0},
{9,2,3,4,4,5,5,6,6,8,0},
{9,0,1,2,3,5,6,7,8,9,0},
{10,0,1,1,2,3,4,4,7,7,8}
};
int[] sizeMap = {0,9,99,999,9999,99999,999999,9999999,99999999,999999999,2147483647};
public boolean reorderedPowerOf2(int n) {
if (n==0){
return false;
}
int size = 0;
//看看这个数字能转成多大的int[]数组
for (int i = 0; i < sizeMap.length; i++) {
if (sizeMap[i] >= n){
size = i;
break;
}
}
int[] numArr = new int[size];
//把n数字的个位置上的数字放入数组中
while (n > 0){
numArr[--size] = n % 10;
n /= 10;
}
Arrays.sort(numArr);
for (int[] ints : arr) {
if (ints[0] == numArr.length){
int idx = 0;
while (++idx<=ints[0] && ints[idx] == numArr[idx-1]){}
if(--idx == ints[0] && ints[idx] == numArr[idx-1]){
return true;
}
}
}
return false;
}
}
发表评论