Leecode 869. 重新排序得到 2 的幂——Leecode每日一题系列

àì夳堔傛蜴生んèń 2022-08-28 02:51 119阅读 0赞

#### 题目链接：[https://leetcode-cn.com/problems/reordered-power-of-2/][https_leetcode-cn.com_problems_reordered-power-of-2] ####

--------------------

#### 题目 ####

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

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

> 示例 1：  
> 输入：1  
> 输出：true  
>   
> 示例 2：  
> 输入：10  
> 输出：false  
>   
> 示例 3：  
> 输入：16  
> 输出：true  
>   
> 示例 4：  
> 输入：24  
> 输出：false  
>   
> 示例 5：  
> 输入：46  
> 输出：true

> 提示：  
> 1 <= N <= 10^9

--------------------

解法：数据量比较小，dfs回溯即可。

--------------------

class Solution {
        
    private:
        bool res = false;
        int vis[10] = {
        0};            // 某个数所有数字的出现次数；不用bool的原因是，数字可以重复
        int len = 0;                // 数字的位数
        unordered_map<int, int>um;
    
    public:
        bool reorderedPowerOf2(int n) {
        
            // 构建集合匹配
            for (int i = 1; i < (int)1e9+10; i *= 2) {
        
                um[i] = 1;
            }
            // 求这个数中所有数字的出现次数
            while(n) {
        
                vis[n%10]++;
                n /= 10;
                len++;
            }
            // 回溯
            dfs(0, 0);
    
            return res;
        }
        void dfs(int step, int cur) {
        
            if (step == len) {
        
                if (um[cur] == 1) {
          // 为1，证明是2的幂
                    res = true;
                }
            }
            // 全量遍历的状态
            for (int i = 0; i < 10; i++) {
        
                if (vis[i] > 0) {
        
                    vis[i]--;
                    if (i != 0 || cur != 0) {
        
                        dfs(step + 1, cur * 10 + i);
                    }
                    vis[i]++;
                }
            }
        }
    };

[https_leetcode-cn.com_problems_reordered-power-of-2]: https://leetcode-cn.com/problems/reordered-power-of-2/