|
给定正整数N，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。 如果我们可以通过上述方式得到2的幂，返回true；否则，返回false。 示例 1： 示例 2：
示例 3：
示例 5：
提示： 这题说的是把一个正整数各个位置上的数字重排序，然后判断排序后的数字是不是2的幂。我们知道在int范围内数字的长度不会很长，我们可以把数字n拆成一个个单个的数字，让他们自由组合，比如123，自由组合的结果是 最后在判断他们自由组合的数字是否是2的幂，参照回溯算法模板照抄就行了 private void backtrack("原始参数") {
//终止条件(递归必须要有终止条件)
if ("终止条件") {
//一些逻辑操作（可有可无，视情况而定）
return;
}
for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
//一些逻辑操作（可有可无，视情况而定）
//做出选择
//递归
backtrack("新的参数");
//一些逻辑操作（可有可无，视情况而定）
//撤销选择
}
}
因为有重复的数字，我们可以参照594，回溯算法解含有重复数字的全排列 II来对代码进行优化。 public boolean reorderedPowerOf2(int n) {
//数字转化为字符数组
char[] numChar = String.valueOf(n).toCharArray();
//先对数组排序
Arrays.sort(numChar);
return backtrack(numChar, new boolean[numChar.length], 0, 0);
}
public boolean backtrack(char[] numChar, boolean[] visit, int index, int num) {
//所有数组都访问完了，判断是num否是2的幂
if (index == numChar.length) {
return isPowerOfTwo(num);
}
for (int i = 0; i < numChar.length; ++i) {
//有前导0的跳过
if (num == 0 && numChar[i] == '0') {
continue;
}
//被访问过的字符直接跳过
if (visit[i])
continue;
//剪枝，可以参考（47. 全排列 II）,选择同一个元素在前一个分支没有成功，
//那么在当前分支也不会成功，所以可以直接过滤掉
if (i > 0 && numChar[i - 1] == numChar[i] && visit[i - 1])
continue;
//选择当前元素
visit[i] = true;
//递归到下一层
if (backtrack(numChar, visit, index + 1, num * 10 + numChar[i] - '0'))
return true;
//如果没有成功，撤销选择
visit[i] = false;
}
return false;
}
//是否是2的幂（n必须大于0）
public boolean isPowerOfTwo(int n) {
return (n & (n - 1)) == 0;
// return (n & -n) == n;
}
这种比较好理解，就是先把数字转化为数组比如numChar，然后再把int范围内所有2的幂也转化为数组，然后判断numChar和2的幂转化的数组是否一样。 public boolean reorderedPowerOf2(int n) {
//先把数字转化为字符
char[] numChar = String.valueOf(n).toCharArray();
//对字符进行排序
Arrays.sort(numChar);
for (int i = 0; i < 31; i++) {
//把2的幂转化为字符，然后排序
char[] bitChar = String.valueOf(1 << i).toCharArray();
Arrays.sort(bitChar);
//比较这两个数组
if (Arrays.equals(numChar, bitChar))
return true;
}
return false;
}
|
