脚本宝典收集整理的这篇文章主要介绍了869. 重新排序得到 2 的幂(回溯 hash表),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
链接: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
方法1 回溯+位运算 重新排序取2的幂其实可以分解为两个子问题:
我一开始的思路是将数字转化为字符串格式(to_string())进行全排列再转回数字(stoi())判断 全排列回溯用的交换指定位置 注意字符串开头为0情况的剪枝
class Solution {
public:
bool reorderedPowerOf2(int n) {
string s = to_string(n);
DFs(s, 0);
return istrue;
}
private:
bool istrue = false;
void dfs(string &s, int index){
if (istrue==true)
return;
if (s[0] != '0'){
int temp = stoi(s);
int t = temp&(temp - 1);
if (t == 0)
istrue=true;
}
for (int i = index; i<s.size(); i++){
swap(s[index], s[i]);
dfs(s, index + 1);
swap(s[index], s[i]);
}
}
};
中间我对每次替换都进行了判断 导致很多重复 实际可以只对最后index==s.size()情况下进行判定
class Solution {
public:
bool reorderedPowerOf2(int n) {
string s = to_string(n);
dfs(s, 0);
return istrue;
}
private:
bool istrue = false;
void dfs(string &s, int index){
if (istrue==true)
return;
if (index==s.size()&&s[0] != '0'){
int temp = stoi(s);
int t = temp&(temp - 1);
if (t == 0)
istrue=true;
}
for (int i = index; i<s.size(); i++){
swap(s[index], s[i]);
dfs(s, index + 1);
swap(s[index], s[i]);
}
}
};
由于存在重复数,交换效率很低,而且数字转字符串再转回数字效率较低 所以换了插入构造目标排列的方式代替替换 对于重复的值和初始为0的排列可以直接剪枝 先对所有字符进行排序 注意设置一个访问数组 访问数组不为0时可以取 重复数字在前一相同数字vis[i]未取情况下不取
class Solution {
public:
bool reorderedPowerOf2(int n) {
string s = to_string(n);
vis.resize(s.size(), 1);//访问数组
sort(s.begin(), s.end());
return dfs(s, 0, 0);;
}
private:
vector<int>vis;
bool dfs(string &s, int index, int num){
if (index == s.size()){
return istwo(num);
}
for (int i = 0; i<s.size();++i){
if ((index == 0 && s[i] == '0') || (i>0 &&vis[i-1]&& s[i] == s[i - 1]) || vis[i] == 0)
continue;
num = num * 10 + s[i] - '0';
vis[i] = 0;
if (dfs(s, index + 1, num))
return true;
num = (num - s[i] + '0') / 10;
vis[i] = 1;
}
return false;
}
bool istwo(int n){
return (n&(n - 1) )== 0;
}
};
方法2 预处理+hash表 实际上对于XXX序列重新排序来满足特定序列的问题 都可以用hash表来存储序列元素出现次数结果,进行比较 由于10e9范围内2的幂是固定的(2^30) 我们可以将所有2的幂统计其序列 元素频率,存在string中(vector也行)放入hash表 然后统计目标数的元素频率 ,在hash表中查找比较
class Solution {
public:
bool reorderedPowerOf2(int n) {
for(int i=1;i<1e9;i<<=1){
p.insert(countDigITs(i));
}
return (p.count(countDigits(n))>0);
}
string countDigits(int n){
string cnt(10,0);//使用string记录每一位出现频率
while(n){
++cnt[n%10];
n/=10;
}
return cnt;
}
unordered_set<string>p;
};
以上是脚本宝典为你收集整理的869. 重新排序得到 2 的幂(回溯 hash表)全部内容,希望文章能够帮你解决869. 重新排序得到 2 的幂(回溯 hash表)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。