题目描述
给定正整数 N ,我们按任何顺序(包括原始顺序)将数字重新排序,注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂,返回 true;否则,返回 false。
思路
这题的思路结合了
leetcode-47.全排列-Ⅱ
leetcode-231.2的幂
所以,建议先把这两题做了
做完后会发现,这题的解题思路就是:
对于给定整数N,我们可以对其进行全排列(去重,去前导数字为0),然后对结果集的每个排列结果,进行判断是否为2的幂。
代码实现(py3)
"""
给定正整数 N ,我们按任何顺序(包括原始顺序)将数字重新排序,注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂,返回 true;否则,返回 false。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reordered-power-of-2
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
"""
# 判断N是否为2的幂
def is_power(N):
if N <= 0:
return False
check = 0
while(N > 1):
if N==2:
break
N /= 2
check = N%2
return check == 0
# 深度优先搜索
def dfs(nums, depth, path, used, res):
# 已经到了叶子节点
if(depth == len(nums)):
res.append(path.copy())
return
for i in range(len(nums)):
if used[i] or (i > 0 and used[i - 1] == False and nums[i] == nums[i - 1]):
continue
# 还没被选过
path.append(nums[i])
used[i] = True
dfs(nums, depth + 1, path, used, res)
# 回溯
path.pop()
used[i] = False
# 全排列(去重)
def permuteUnique(nums):
path = []
used = []
depth = 0
res = []
for _ in range(len(nums)):
used.append(False)
if len(nums) == 0:
return res
nums.sort()
dfs(nums, depth, path, used, res)
return res
# list转为int
def cover2_int(nums):
nums.reverse()
n = 0
res = 0
for i in nums:
res += i * pow(10, n)
n += 1
return res
# int转为list
def cover2_list(n):
res = []
while n:
res.append(n%10)
n //= 10
res.reverse()
return res
class Solution:
def reorderedPowerOf2(self, n):
can_get = False
nums = cover2_list(n)
res = permuteUnique(nums)
for item in res:
if item[0] == 0:
continue
if is_power(cover2_int(item)):
return True
return can_get