[LeetCode] Reordered Power of 2

发表于 | 更新于: | 分类于 |

题目描述

Starting with a positive integer N, we reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this in a way such that the resulting number is a power of 2.

Example 1:

Input: 1
Output: true

Example 2:

Input: 10
Output: false

Example 3:

Input: 16
Output: true

Example 4:

Input: 24
Output: false

Example 5:

Input: 46
Output: true

Note:
1 <= N <= 10^9

输入是正整数，要求 求对数字排列后得到的数是否存在一个是2的整数次幂。
解决思路是将N转为string,然后利用stl 提供的next_permutation 获得所有排列，遍历所有情况检查是否存在2的整数次幂。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool reorderedPowerOf2(int N) {
        string str_num = to_string(N);
        // 使用next_permutation 之前应排序
        sort(str_num.begin(), str_num.end());
        do
        {
            if (str_num.front() == '0')
            {
                continue;
            }
            if (isPowerOf2(stoi(str_num)))
            {
                return true;
            }
        } while(next_permutation(str_num.begin(), str_num.end()));

        return false;
    }
private:
    bool isPowerOf2(const int num) const
    {
        return (num & num - 1) == 0;
    }

};
Donate
0%