0970. 强整数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 枚举

1. 📝 题目描述

• leetcode

给定三个整数 x 、 y 和 bound，返回值小于或等于 bound 的所有强整数组成的列表。

如果某一整数可以表示为 x^i + y^j，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个强整数。

你可以按任何顺序返回答案。在你的回答中，每个值最多出现一次。

---

示例 1：

输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]

解释：
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

---

示例 2：

输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]

---

提示：

• 1 <= x, y <= 100
• 0 <= bound <= 10^6

2. 🎯 s.1 - 枚举

js

/**
 * @param {number} x
 * @param {number} y
 * @param {number} bound
 * @return {number[]}
 */
var powerfulIntegers = function (x, y, bound) {
  const set = new Set()

  // 计算 x^i 的上界：x^i <= bound
  // 如果 x = 1，x^i = 1 对所有 i，只需要考虑 i = 0
  const xLimit = x === 1 ? 1 : Math.floor(Math.log(bound) / Math.log(x)) + 1
  const yLimit = y === 1 ? 1 : Math.floor(Math.log(bound) / Math.log(y)) + 1

  for (let i = 0; i < xLimit; i++) {
    const xi = Math.pow(x, i)
    if (xi > bound) break

    for (let j = 0; j < yLimit; j++) {
      const yj = Math.pow(y, j)
      const sum = xi + yj

      if (sum <= bound) {
        set.add(sum)
      } else {
        break // yj 已经太大，后续更大的 j 也不满足
      }

      // 如果 y = 1，y^j = 1 对所有 j，只需要一次
      if (y === 1) break
    }

    // 如果 x = 1，x^i = 1 对所有 i，只需要一次
    if (x === 1) break
  }

  return Array.from(set)
}

• 时间复杂度：$O({\log }^{2}bound)$，最多枚举 $O(\log bound)$ 个 i 和 $O(\log bound)$ 个 j
• 空间复杂度：$O({\log }^{2}bound)$，哈希集合最多存储 $O({\log }^{2}bound)$ 个不同的强整数

算法思路：

• 枚举范围：枚举所有可能的 i 和 j 值，使得 $x^i+y^j\le bound$
• 上界计算：对于 x > 1，i 的上界为 $\lfloor {\log }_x(bound)\rfloor +1$；对于 x = 1，只需考虑 i = 0
• 哈希去重：使用 Set 存储所有满足条件的和，自动去除重复值
• 特殊处理：当 x = 1 或 y = 1 时，幂次不变，只需枚举一次即可
• 提前终止：当 $x^i>bound$ 或 $x^i+y^j>bound$ 时，提前跳出循环
• 结果返回：将 Set 转换为数组返回