力扣-重新排序得到 2 的幂

题目链接：https://leetcode.cn/problems/reordered-power-of-2/description/?envType=daily-question&envId=2025-08-10

题目

给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

• 示例 1：
  输入：n = 1
  输出：true

• 示例 2：
  输入：n = 10
  输出：false

• 提示：1 <= n <= 10^9

分析

由于2的幂在10^9之中是可数的且是有限的，如果我们将这些2的幂全部记录下来，并且统计每个数他所含的数字有多少个（如 一个1，三个2等等），记录到哈希表中，我们再判断函数所传的数字分别有多少个数字，是否在我们的哈希表中，即可得到答案。

由于 2^29<10^9<2^30 ，因此在 [1,10^9] 范围内有 2^0,2^1,⋯,2^29一共 30 个 2 的幂。对这 30 个数的每个数，我们可以预处理其十进制表示的字符数组中从 0 到 9 每个字符的出现次数，记在一个长度为 10 的数组中，并用一哈希表记录这些数组。对于数字 n，我们同样统计其十进制表示的字符数组中从 0 到 9 每个字符的出现次数，然后去哈希表中查找，若存在则说明 n 可以通过重排得到 2 的幂，否则不能。

代码

• 从 1 开始，不断乘 2（n <<= 1 等价于 n *= 2），直到超过 1e9（题目范围内的最大数）。
• 把每个 2 的幂的“数字计数表示”存进 Set（去重、快速查找）。

  const countDigits = (n) => {
      const cnt = new Array(10).fill(0);
      while (n) {
          cnt[n % 10]++;
          n = Math.floor(n / 10);
      }
      return cnt.join('');
  }
  
  
  
  var reorderedPowerOf2 = function(n) {
      const powerOf2Digits = new Set();
  
      for (let n = 1; n <= 1e9; n <<= 1) {
          powerOf2Digits.add(countDigits(n));
      }
  
      return powerOf2Digits.has(countDigits(n));
  };