LeetCode: 869. Reordered Power of 2

LeetCode: 869. Reordered Power of 2

题目描述

Starting with a positive integer N, we reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this in a way such that the resulting number is a power of 2.

Example 1:

Input: 1
Output: true

Example 2:

Input: 10
Output: false

Example 3:

Input: 16
Output: true

Example 4:

Input: 24
Output: false

Example 5:

Input: 46
Output: true

Note:

1 <= N <= 10^9

解题思路 —— 深度优先搜索

通过深度优先搜索遍历所有排列的可能性,然后将其转换为二进制数,如果转换的二进制数只有一个 1 则是二的倍数。

AC 代码

class Solution {
    bool dfs(string curNum, string& N)
    {
        if(curNum.size() == N.size())
        {
            int num = stoi(curNum);
            int cntOne = 0;
            while(num)
            {
                cntOne += num%2;
                num /= 2;
            }
            if(cntOne == 1) return true;
            else return false;
        }
        for(int i = 0; i < N.size(); ++i)
        {
            if(N[i] < 0) continue;
            if(curNum.size() == 0 && N[i] == '0') continue;

            curNum.push_back(N[i]);
            N[i] = -N[i];
            if(dfs(curNum, N) == true) return true;
            curNum.pop_back();
            N[i] = -N[i];
        }
        return false;
    }
public:
    bool reorderedPowerOf2(int N) {
        string strN = to_string(N);
        return dfs("", strN);
    }
};
全部评论

相关推荐

07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务