题目描述

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

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

代码

// 思路： 
// 枚举找到N的所有排序
//      计算出N的位数c
//      先用一个c维数组num容纳N中的n个数字
//      在用一个c维数组isused表示数字是否被使用
//      从前往后在num中选一个非0的数字作为序列的开头，将isused对应位置置为1
//          再在剩下的数中从前往后在num中选一个数字作为序列的第二个位置，将isuesed对应位置置为1
//              ……
//                  当剩下的数中只有一个时，将这个数作为最后一位
//              ……
//           再依次选中其他数字作为第二个位置
//      再依次选中其他非0数字作为开头
//      
// 对于每个排序，测试是否为2的幂
//      方法1：不断除以2碰到余数为1则不是2的幂，如果最后商为1则是2的幂
//      方法2：利用n&(n-1)判断，可以用计算器看看规律

int c;

// 判断数n是否为2的幂
bool isPowerOf2(int n){
    return (n & (n-1)) == 0;
}

// 计算数n的位数
int count(int n){
    int m = n;
    int c = 0;
    while(m){
        m /= 10;
        c++;
    }
    return c;
}

// 判断剩下的数的组合是否能使number成为2的幂
// n表示未使用的位数
bool isHave(int n, int num[], int used[], int prenumber){
    int *isused = (int *)malloc(sizeof(int) * c);
    int number = prenumber;
    for(int i = 0; i < c; i++)
        isused[i] = used[i];  
    if(n == 1){
        int i = 0;
        while(isused[i] && i < c)
            i++;
        number = number * 10 + num[i];
        // 判断numer是否为2的幂
        return isPowerOf2(number);
    }
    for(int i = 0; i < c; i++){
        number = prenumber;
        if(!isused[i]){
            number = number * 10 + num[i];
            isused[i] = 1;
            if(isHave(n - 1, num, isused, number))
                return true;
            isused[i] = 0;
        }
    }
    return false;
}

bool reorderedPowerOf2(int n){
    int number = 0;
    // 计算n的位数
    c = count(n);
    if(c == 1)
        return isPowerOf2(n);
    int num[c];
    int isused[c];
    for(int i = 0, m = n; i < c; i++, m = m / 10){
        num[i] = m % 10;
    }
    for(int i = 0; i < c; i++)
        isused[i] = 0;
    for(int i = 0; i < c; i++){
        if(num[i]){
            number = num[i];
            isused[i] = 1;
            // 寻找num[i]为开头的为2的幂的数
            if(isHave(c - 1, num, isused, number))
                return true;
            isused[i] = 0;
        }
    }
    return false;
}