LeetCode 869. 重新排序得到 2 的幂（排序 & 全排列）
LeetCode 869. 重新排序得到 2 的幂（排序 & 全排列）
Michael阿明
发布于 2020-07-13 16:05:42
发布于 2020-07-13 16:05:42
1. 题目
给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：1
输出：true
示例 2：
输入：10
输出：false
示例 3：
输入：16
输出：true
示例 4：
输入：24
输出：false
示例 5：
输入：46
输出：true
提示：
1 <= N <= 10^9来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reordered-power-of-2 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 排序
- 将数字转成字符串，并排序
- 枚举32位的所有2的次幂的数，转字符串，并排序，跟上面字符串比较即可
class Solution {
public:
bool reorderedPowerOf2(int N) {
string origin(to_string(N));
string powerTwo;
sort(origin.begin(), origin.end());
for(int i = 0; i < 32; ++i)
{
powerTwo = to_string(1<<i);
sort(powerTwo.begin(), powerTwo.end());
if(powerTwo == origin)
return true;
}
return false;
}
};
在这里插入图片描述
2.2 全排列
class Solution {
bool ans = false;
public:
bool reorderedPowerOf2(int N) {
string origin(to_string(N));
bt(origin,0);
return ans;
}
void bt(string str, int i)
{
if(ans == true || i == str.size())
return;
for(int j = i; j < str.size(); ++j)
{
swap(str[i],str[j]);
if(str[0]!='0' && isPowerTwo(stoi(str)))
ans = true;
bt(str,i+1);
swap(str[i],str[j]);
}
}
bool isPowerTwo(int n)
{
return (n&(n-1)) == 0;
}
};
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-11-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录