重新排序得到 2 的幂

Posted on Edited on In Views: Waline: Views: Symbols count in article: 596 Reading time ≈ 1 mins.

题解方法

  • 词频统计
  • 哈希

词频统计

  • 题目要求，按任何顺序（包括原始顺序）将数字重新排序，因此针对每一个数字，只需统计其每一位数字出现的次数，统计结果用字符串存储
  • 题目要求，1 <= N <= 10^9，因此可以预处理所有2的幂数

哈希

  • 根据词频统计结果进行哈希查找，确认其是否有匹配的2的幂数的词频统计结果

核心代码

2的幂数预处理

1
2
3
4
5
6
7
8
9
Set<String> set = new HashSet<>();

public boolean reorderedPowerOf2(int n) {
  // 2的幂数预处理
  for (int i = 1; i < 1e9; i <<= 1) {
    set.add(countDigits(i));
  }
  return set.contains(countDigits(n));
}

词频统计

1
2
3
4
5
6
7
8
9
10
// 每个数字出现次数统计，用字符串形式存储
public String countDigits(int n) {
    char[] cnt = new char[10];

    while (n > 0) {
        ++cnt[n % 10];
        n /= 10;
    }
    return Arrays.toString(cnt);
}

题目来源

869. 重新排序得到 2 的幂 - 力扣（LeetCode） (leetcode-cn.com)