关键点是意识到2的幂次是有限
解法1-暴力回溯法
看到重排序就想到回溯法中的排列树问题，按照排列树的标准模板求解即可,注意排除出现前导零的情况,与
复杂度分析：
- 时间复杂度：由于第i层共有N- i个选择，时间复杂度为O(N!)
- 空间复杂度：递归深度为数字的长度，空间复杂度为O(N)
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public boolean backTrace(int depth, int nLength, Long curNumber, int[] visited, int[] digits){
if(depth == nLength){
return isTwoPower(curNumber);
}
for(int i = 0;i < nLength;i++){
if(visited[i] == 0 && (depth != 0 || digits[i] != 0)){
visited[i] = 1;
if(backTrace(depth + 1, nLength, curNumber * 10 + digits[i] , visited, digits))
return true;
visited[i] = 0;
}
}
}
|
解法2-预先计算存储法
在数字的取值范围内，一共有$2^0, 2^1,……2^{29}$ 一共30个可能取到的2的幂次，事先计算所有2幂次数字各个位置的0~9 数字出现的次数，按照顺序生成字符串存储到Map中，对于目标数字，按照相同计算步骤生成字符串，查看Map中是否含有相同字符串即可。
不想写了贴个官方题解充个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
Set<String> powerOf2Digits = new HashSet<String>();
public boolean reorderedPowerOf2(int n) {
init();
return powerOf2Digits.contains(countDigits(n));
}
public void init() {
for (int n = 1; n <= 1e9; n <<= 1) {
powerOf2Digits.add(countDigits(n));
}
}
public String countDigits(int n) {
char[] cnt = new char[10];
while (n > 0) {
++cnt[n % 10];
n /= 10;
}
return new String(cnt);
}
}
作者：LeetCode-Solution
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|