1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public boolean reorderedPowerOf2(int n) {
int currNum = 1;
int[] nCountArray = countDigits(n);
for (int pow = 0; pow < 30; pow++) {
if (Arrays.equals(nCountArray, countDigits(currNum))) {
return true;
}
currNum <<= 1;
}
return false;
}
private int[] countDigits(int num) {
int[] digitArray = new int[10];
while (num != 0) {
digitArray[num % 10] += 1;
num /= 10;
}
return digitArray;
}
}
|
读题很重要. 一开始我以为是binary representation重新order digits就行了. 那样简单, 就看是否有且只有一个1即可.
实际题意是十进制reorder.
也很暴力的解法. 给我们的条件就是N的范围最大是10的9次方. 最大的2的power在整型数下是2147483648 / 2 = 1073741824.此时是2的30次方. 是10位. 那么2的29次方就是在N的边界以内最大的2的power了.
于是我们先获得N的每个digits的frequency. 然后我们再获得每个2的power的每个digit的frequency, 比较和N的digits的frequency是否都相同就ok了.
我们用array或者hashmap来存给定的一个数字的每个digit的frequency.
时间复杂度: O(1)
空间复杂度: O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public boolean reorderedPowerOf2(int n) {
int currNum = 1;
for (int pow = 0; pow < 30; pow++) {
if (countDigits(currNum) == countDigits(n)) {
return true;
}
currNum <<= 1;
}
return false;
}
int countDigits(int num) {
int ans = 0;
while (num != 0) {
ans += Math.pow(10, num % 10);
num /= 10;
}
return ans;
}
}
|
由于N最大就是10的9次方, 那么N中0-9每个数字出现的频率不会超过9. 因此我们可以用一个数字记录N的digit count. LSB记录0出现的次数, LSB左侧一个记录1出现的次数…
如何统计? 让num每一位的十次方加到ans上就完事儿了. 这个做法很绝.
时间复杂度: O(1)
空间复杂度: O(1)
