博客

数组的全排列。

题目：重新排序得到2的幂。

从正整数

N

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

如果我们可以通过上述方式得到 2 的幂，返回

true

；否则，返回

false

。

包含在头文件<algorithm>中。

#include <iostream>
#include <algorithm>

int main()
{
    int myints[] = {1,2,3};
    std::sort(myints, myints + 3);

    std::cout << "The 3! possible permutations with 3 elements:\n";
    do {
        std::cout << myints[0] << " " << myints[1] << " " << myints[2] << "\n";

    } while( std::next_permutation(myints, myints+3) );
    
    std::cout << "After loop:" << myints[0] << " " << myints[1] << " " << myints[2] << "\n";
    return 0;
}
/********output:********
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
After loop:1 2 3
*/

结局数组任意组合后能够为2的n次幂，则返回true，否则返回false.

利用C++ STL的 next_permutation和移位运算符号。

//判断关于数组全排列中是否存在成为2的幂次的数字。
#include <iostream> 
#include <algorithm>
using namespace std;
bool isPowerOf2(int number)
{
    int tmp = number;
    vector<int> result;
    while(tmp)
    {
        result.push_back(tmp % 10);
        tmp /= 10;
    }
    
    sort(result.begin(), result.end());
    do
    {
        int temp = 0;
        if(result[0] == 0) continue;
        for(int j = 0; j < result.size(); j++)
        {
            temp = temp * 10 + result[j];
        }
             
        for(int k = 0; k < 30; k++)  //移位运算符号
        {
            if( (1 << k) == temp) return true;
        }
    } while(next_permutation(result.begin(), result.end()) );
    return false;
}