题目
869. 重新排序得到 2 的幂
给定正整数 N?，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。如果我们可以通过上述方式得到?2 的幂，返回 true；否则，返回 false。
思路：
将 n 的十进制表示视作一个字符数组，我们可以枚举该数组的所有排列，对每个不含前导零的排列判断其对应的整数是否为 2 的幂。
代码：
class Solution {
? ? boolean[] vis;
? ? public boolean reorderedPowerOf2(int n) {
? ? ? ? char[] nums = Integer.toString(n).toCharArray();
? ? ? ? Arrays.sort(nums);
? ? ? ? vis = new boolean[nums.length];
? ? ? ? return backtrack(nums, 0, 0);
? ? }
? ? public boolean backtrack(char[] nums, int idx, int num) {
? ? ? ? if (idx == nums.length) {
? ? ? ? ? ? return isPowerOfTwo(num);
? ? ? ? }
? ? ? ? for (int i = 0; i < nums.length; ++i) {
? ? ? ? ? ? // 不能有前导零
? ? ? ? ? ? if ((num == 0 && nums[i] == '0') || vis[i] || (i > 0 && !vis[i - 1] && nums[i] == nums[i - 1])) {
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? }
? ? ? ? ? ? vis[i] = true;
? ? ? ? ? ? if (backtrack(nums, idx + 1, num * 10 + nums[i] - '0')) {
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? ? ? vis[i] = false;
? ? ? ? }
? ? ? ? return false;
? ? }
? ? public boolean isPowerOfTwo(int n) {
? ? ? ? return (n & (n - 1)) == 0;
? ? }
}
|