题目

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

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

示例 1：

输入：n = 1 输出：true

示例 2：

输入：n = 10 输出：false

提示：

1 <= n <= 10^9

解题思路

题目的关键在于 “将数字重新排序”。如果一个数 A 可以通过重排其各位数字得到另一个数 B，那么 A 和 B 必须满足以下两个条件：

它们的位数相同。
它们包含的每种数字（0-9）的个数完全相同。

例如，n = 460，它由一个 0、一个 4、一个 6 组成。任何由它重排得到的数字（如 406, 604, 640 等）也都必须由这三个数字组成。

因此，这道题可以转化为：判断输入 n 的各位数字，经过重新排列后，能否组成一个 2 的幂。

这等价于：是否存在一个 2 的幂，它与 n 拥有完全相同的数字构成。

具体思路

为了判断两个数（比如 n 和某个2的幂 p）是否由相同的数字构成，我们需要一种方法来表示它们的数字构成，我称之为“数字指纹”。

一个简单有效的方法是：

将数字转换成字符串。
对字符串中的字符进行排序。

这样，如果两个数字的“指纹”相同，就说明它们是由完全相同的数字集合构成的。

例如：

n = 46 -> 字符串 "46" -> 排序后得到 "46"
p = 64 -> 字符串 "64" -> 排序后得到 "46" 它们的指纹相同，所以 46 可以重排得到 64。
n = 10 -> 字符串 "10" -> 排序后得到 "01"
p = 1 -> 字符串 "1" -> 排序后得到 "1"
p = 2 -> 字符串 "2" -> 排序后得到 "2"
...
p = 16 -> 字符串 "16" -> 排序后得到 "16" n=10 的指纹 "01" 与任何2的幂的指纹都不同，所以返回 false。

算法实现

预处理：
- 创建一个集合（例如 HashSet），用于存放所有目标“2的幂”的数字指纹。
- 遍历从 i = 0 到 33（或者一个安全的上限，比如40）。
- 计算 p = 2^i。
- 计算 p 的数字指纹（即，将其转换为排序后的字符串）。
- 将这个指纹字符串存入集合中。这个步骤可以只执行一次，结果可以被所有测试用例复用，非常高效。
判断输入 n：
- 给定一个输入 n。
- 计算 n 的数字指纹（转换为排序后的字符串）。
- 检查这个指纹是否存在于我们预处理好的集合中。
- 如果存在，返回 true。
- 如果不存在，返回 false。

具体代码

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        // 步骤 1: 制作输入数字 n 的“指纹”
        string n_fingerprint = to_string(n);
        sort(n_fingerprint.begin(), n_fingerprint.end());

        // 步骤 2: 在函数内部，即时制作并检查每一个2的幂的“指纹”
        // 这个 for 循环在每次调用 reorderedPowerOf2 时都会完整运行
        for (int i = 0; i < 31; ++i) {
            // a. 计算一个2的幂
            int powerOf2 = 1LL << i;

            // b. 为这个2的幂制作“指纹”
            string p2_fingerprint = to_string(powerOf2);
            sort(p2_fingerprint.begin(), p2_fingerprint.end());

            // c. 直接比较两个指纹
            if (n_fingerprint == p2_fingerprint) {
                // 如果匹配，说明找到了，立即返回 true
                return true;
            }
        }

        // 步骤 3: 如果循环结束（检查完所有31个2的幂）都没找到匹配项，
        // 说明不行，返回 false
        return false;
    }
};

869. 重新排序得到 2 的幂

beautifulremi

题目

解题思路

具体思路

算法实现

具体代码