[LeetCode] 869. Reordered Power of 2

[grandyang]

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. 1 <= N <= 10^9

这道题说是给了我们一个正整数N，让对各位上的数字进行重新排序，但是要保证最高位上不是0，问能否变为2的指数。刚开始的时候博主理解错了，以为是对N的二进制数的各位进行重排序，但除了2的指数本身，其他数字怎么也组不成2的指数啊，因为2的指数的二进制数只有最高位是1，其余都是0。后来才发现，是让对N的十进制数的各位上的数字进行重排序，比如 N=46，那么换个位置，变成 64，就是2的指数了。搞清了题意后，就可以开始解题了，由于N给定了范围，在 [1, 1e9] 之间，所以其调换位数能组成的二进制数也是有范围的，为 [2^0, 2^30] 之间，这样的话，一个比较直接的解法就是，现将整数N转为字符串，然后对字符串进行排序。然后遍历所有可能的2的指数，将每个2的指数也转为字符串并排序，这样只要某个排序后的字符串跟之前由N生成的字符串相等的话，则表明整数N是符合题意的，参见代码如下：
解法一：

class Solution {
public:
    bool reorderedPowerOf2(int N) {
        string str = to_string(N);
        sort(str.begin(), str.end());
        for (int i = 0; i < 31; ++i) {
            string t = to_string(1 << i);
            sort(t.begin(), t.end());
            if (t == str) return true;
        }
        return false;
    }
};

下面这种方法没有将数字转为字符串并排序，而是使用了另一种比较巧妙的方法来实现类似的功能，是通过对N的每位上的数字都变为10的倍数，并相加，这样相当于将N的各位的上的数字都加码到了10的指数空间，而对于所有的2的指数，进行相同的操作，只要某个加码后的数字跟之前整数N的处理后的数字相同，则说明N是符合题意的。需要注意的是，为了防止整型移除，加码后的数字用长整型来表示即可，参见代码如下：
解法二：

class Solution {
public:
    bool reorderedPowerOf2(int N) {
        long sum = helper(N);
        for (int i = 0; i < 31; i++) {
            if (helper(1 << i) == sum) return true;
        }
        return false;
    }
    long helper(int N) {
        long res = 0;
        for (; N; N /= 10) res += pow(10, N % 10);
        return res;
    }
};

讨论：对于这种验证数字的问题，总是有穷举法出现，参见这个帖子，是能把考官气死的方法，哈哈～
Github 同步地址:

#869

参考资料：

https://leetcode.com/problems/reordered-power-of-2/

https://leetcode.com/problems/reordered-power-of-2/discuss/159513/C%2B%2B-0ms-beats-100

https://leetcode.com/problems/reordered-power-of-2/discuss/149843/C%2B%2BJavaPython-Straight-Forward

https://leetcode.com/problems/reordered-power-of-2/discuss/151949/Simple-Java-Solution-Based-on-String-Sorting

LeetCode All in One 题目讲解汇总(持续更新中...)