Medium

题目描述

给你一个整数 n。我们可以将数字重新排列成任意顺序（包括原始顺序），但开头不能为零。

当且仅当我们可以重新排列得到 2 的幂时，返回 true。

示例 1：

输入：n = 1
输出：true

示例 2：

输入：n = 10
输出：false

约束条件：

  • 1 <= n <= 10^9

解题思路

这道题的核心思想是判断一个数的所有数字重新排列后能否形成2的幂。

方法一：数字计数 + 预计算（推荐）

由于 n <= 10^9，而 2^30 = 1073741824 > 10^9，所以只需要检查从 2^0 到 2^30 这31个2的幂即可。

算法思路：

  1. 预计算所有可能的2的幂（1, 2, 4, 8, ..., 2^30）
  2. 对输入数字 n 进行数字计数，统计每个数字（0-9）出现的次数
  3. 对每个2的幂也进行数字计数
  4. 如果 n 的数字计数与某个2的幂的数字计数完全相同，则返回 true

方法二：排列生成

生成 n 的所有可能排列，检查每个排列是否为2的幂。但这种方法效率较低，因为排列数量可能很大。

数字计数方法更高效，因为只需要遍历固定的31个2的幂，时间复杂度是常数级别的。

代码实现

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        vector<int> count = getCount(n);
        
        for (int i = 0; i < 31; i++) {
            if (count == getCount(1 << i)) {
                return true;
            }
        }
        return false;
    }
    
private:
    vector<int> getCount(int num) {
        vector<int> count(10, 0);
        while (num > 0) {
            count[num % 10]++;
            num /= 10;
        }
        return count;
    }
};

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        def get_count(num):
            count = [0] * 10
            while num > 0:
                count[num % 10] += 1
                num //= 10
            return count
        
        n_count = get_count(n)
        
        for i in range(31):
            if n_count == get_count(1 << i):
                return True
        
        return False

public class Solution {
    public bool ReorderedPowerOf2(int n) {
        int[] count = GetCount(n);
        
        for (int i = 0; i < 31; i++) {
            if (ArraysEqual(count, GetCount(1 << i))) {
                return true;
            }
        }
        return false;
    }
    
    private int[] GetCount(int num) {
        int[] count = new int[10];
        while (num > 0) {
            count[num % 10]++;
            num /= 10;
        }
        return count;
    }
    
    private bool ArraysEqual(int[] a, int[] b) {
        for (int i = 0; i < 10; i++) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }
}

var reorderedPowerOf2 = function(n) {
    const getCount = (num) => {
        const count = new Array(10).fill(0);
        while (num > 0) {
            count[num % 10]++;
            num = Math.floor(num / 10);
        }
        return count;
    };
    
    const arraysEqual = (a, b) => {
        for (let i = 0; i < 10; i++) {
            if (a[i] !== b[i]) return false;
        }
        return true;
    };
    
    const nCount = getCount(n);
    
    for (let i = 0; i < 31; i++) {
        if (arraysEqual(nCount, getCount(1 << i))) {
            return true;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(log n) - 需要遍历31个2的幂，每次计数需要O(log num)时间
空间复杂度O(1) - 只使用固定大小的数组存储数字计数