class Solution {
public:
bool reorderedPowerOf2(int n) {
}
};
869. 重新排序得到 2 的幂
给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：n = 1 输出：true
示例 2：
输入：n = 10 输出：false
提示：
1 <= n <= 109原站题解
python3 解法, 执行用时: 24 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-28 14:25:24
def countDigits(n: int) -> Tuple[int]:
cnt = [0] * 10
while n:
cnt[n % 10] += 1
n //= 10
return tuple(cnt)
powerOf2Digits = {countDigits(1 << i) for i in range(30)}
class Solution:
def reorderedPowerOf2(self, n: int) -> bool:
return countDigits(n) in powerOf2Digits
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-28 14:25:00
func countDigits(n int) (cnt [10]int) {
for n > 0 {
cnt[n%10]++
n /= 10
}
return
}
var powerOf2Digits = map[[10]int]bool{}
func init() {
for n := 1; n <= 1e9; n <<= 1 {
powerOf2Digits[countDigits(n)] = true
}
}
func reorderedPowerOf2(n int) bool {
return powerOf2Digits[countDigits(n)]
}
javascript 解法, 执行用时: 72 ms, 内存消耗: 43.8 MB, 提交时间: 2022-11-28 14:24:38
/**
* @param {number} n
* @return {boolean}
*/
const countDigits = (n) => {
const cnt = new Array(10).fill(0);
while (n) {
cnt[n % 10]++;
n = Math.floor(n / 10);
}
return cnt.join('');
}
var reorderedPowerOf2 = function(n) {
const powerOf2Digits = new Set();
for (let n = 1; n <= 1e9; n <<= 1) {
powerOf2Digits.add(countDigits(n));
}
return powerOf2Digits.has(countDigits(n));
};
javascript 解法, 执行用时: 144 ms, 内存消耗: 41.9 MB, 提交时间: 2022-11-28 14:24:17
/**
* @param {number} n
* @return {boolean}
*/
const reorderedPowerOf2 = (n) => {
const backtrack = (nums, idx, num) => {
if (idx === nums.length) {
return isPowerOfTwo(num);
}
for (let 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].charCodeAt() - '0'.charCodeAt())) {
return true;
}
vis[i] = false;
}
return false;
}
const nums = Array.from('' + n);
nums.sort();
const vis = new Array(nums.length).fill(false);
return backtrack(nums, 0, 0);
}
const isPowerOfTwo = (n) => {
return (n & (n - 1)) === 0;
}
golang 解法, 执行用时: 24 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-28 14:24:01
func isPowerOfTwo(n int) bool {
return n&(n-1) == 0
}
func reorderedPowerOf2(n int) bool {
nums := []byte(strconv.Itoa(n))
sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] })
m := len(nums)
vis := make([]bool, m)
var backtrack func(int, int) bool
backtrack = func(idx, num int) bool {
if idx == m {
return isPowerOfTwo(num)
}
for i, ch := range nums {
// 不能有前导零
if num == 0 && ch == '0' || vis[i] || i > 0 && !vis[i-1] && ch == nums[i-1] {
continue
}
vis[i] = true
if backtrack(idx+1, num*10+int(ch-'0')) {
return true
}
vis[i] = false
}
return false
}
return backtrack(0, 0)
}
python3 解法, 执行用时: 1488 ms, 内存消耗: 15 MB, 提交时间: 2022-11-28 14:23:37
def isPowerOfTwo(n: int) -> bool:
return (n & (n - 1)) == 0
class Solution:
def reorderedPowerOf2(self, n: int) -> bool:
nums = sorted(list(str(n)))
m = len(nums)
vis = [False] * m
def backtrack(idx: int, num: int) -> bool:
if idx == m:
return isPowerOfTwo(num)
for i, ch in enumerate(nums):
# 不能有前导零
if (num == 0 and ch == '0') or vis[i] or (i > 0 and not vis[i - 1] and ch == nums[i - 1]):
continue
vis[i] = True
if backtrack(idx + 1, num * 10 + ord(ch) - ord('0')):
return True
vis[i] = False
return False
return backtrack(0, 0)