0869. 重新排序得到 2 的幂【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 排序比较

1. 📝 题目描述

• leetcode

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

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

---

示例 1：

输入：n = 1
输出：true

示例 2：

输入：n = 10
输出：false

---

提示：

• 1 <= n <= 10^9

2. 🎯 s.1 - 排序比较

c

void sortDigits(char* s) {
    int n = strlen(s);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (s[i] > s[j]) { char t = s[i]; s[i] = s[j]; s[j] = t; }
}

bool reorderedPowerOf2(int n) {
    char target[11], buf[11];
    sprintf(target, "%d", n);
    sortDigits(target);
    for (int i = 0; i < 31; i++) {
        sprintf(buf, "%d", 1 << i);
        sortDigits(buf);
        if (strcmp(target, buf) == 0) return true;
    }
    return false;
}

js

/**
 * @param {number} n
 * @return {boolean}
 */
var reorderedPowerOf2 = function (n) {
  const target = String(n).split('').sort().join('')
  for (let i = 0; i < 31; i++) {
    if (
      String(1 << i)
        .split('')
        .sort()
        .join('') === target
    )
      return true
  }
  return false
}

py

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        target = sorted(str(n))
        return any(sorted(str(1 << i)) == target for i in range(31))

• 时间复杂度：$O({\log }^{2}n)$，比较 31 个 2 的幂每个需 $O(\log n)$ 排序
• 空间复杂度：$O(\log n)$

算法思路：

• 将 n 的数字排序后得到“特征串”
• 遍历所有 $2^i$，若其数字排序后与特征串相同则返回 true