难度: Medium
给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。
如果某一整数可以表示为 xi + yj ，其中整数 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 <= 1000 <= bound <= 106运行时间: 26 ms
内存: 16.1 MB
class Solution:
def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
powerful_nums = set()
i = 0
while x ** i <= bound:
j = 0
while y ** j <= bound:
num = x ** i + y ** j
if num <= bound:
powerful_nums.add(num)
if y == 1:
break
j += 1
if x == 1:
break
i += 1
return list(powerful_nums)
该题解采用的是双循环迭代方法，通过两层while循环分别计算x的i次幂和y的j次幂之和，并检查其是否小于或等于bound。若满足条件，将其添加到集合powerful_nums中以去重并收集所有符合条件的强整数。为了优化，如果x或y为1，则内层或外层循环只需要执行一次，因为其幂次增加后数值不变，仍为1。
时间复杂度: O((log_bound)^2)
空间复杂度: O(bound)
class Solution:
def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
powerful_nums = set() # 使用集合来去重并存储结果
i = 0
while x ** i <= bound: # 计算x的幂次直到超过bound
j = 0
while y ** j <= bound: # 计算y的幂次直到超过bound
num = x ** i + y ** j # 计算当前的强整数值
if num <= bound: # 检查强整数是否不超过界限
powerful_nums.add(num) # 添加到结果集中
if y == 1: # 如果y为1，内层循环只需执行一次
break
j += 1
if x == 1: # 如果x为1，外层循环只需执行一次
break
i += 1
return list(powerful_nums) # 将集合转换为列表返回
在计算可能的强整数时，由于不同的指数组合(i, j)可能产生相同的结果值，使用集合可以自动去除这些重复的值。集合（set）数据结构不允许存储重复的元素，这使得每当尝试添加已存在于集合中的元素时，该操作将无效。如果使用列表（list），则需要额外的步骤来检查和去除重复的元素，这会增加时间复杂度。因此，使用集合可以更高效地确保结果中只含有唯一的强整数。
在高次幂的情况下，确实可能出现数值溢出的问题。在Python中，整数类型（int）可以自动处理较大的数字并转换为长整型（long），这可以在很大程度上避免传统意义上的溢出问题。但是，计算非常大的幂次可能导致内存使用过多或处理速度变慢。解决这个问题的一种方法是，在每次计算幂次后立即检查结果是否超出了bound的范围，如果已经超出，则可以停止后续的幂次增加，因为这些计算结果只会更大。
题解中的算法没有显式地考虑到某些数学性质，如x和y的倍数关系可能导致相同的强整数值。例如，当x=2和y=4时，2的任何幂次与4的某些幂次的和可能相同（如2^2 + 4^1 = 4 + 4 = 8，和2^3 = 8）。然而，因为解决方案使用集合来存储结果，所有重复的结果都会自动被去除。尽管如此，算法效率可以通过识别并利用这些数学性质来提高，例如通过避免那些知道会重复的幂次计算。
重复的强整数值出现在不同的(i, j)指数对产生相同的强整数值时。这通常发生在x和y不互质（即它们有公共因数）或一个是另一个的倍数时。例如，如果x=3和y=9，那么3^2 + 9^0 = 9 + 1 = 10和3^1 + 9^1 = 3 + 9 = 12；但也可能出现3^3 + 9^0 = 27 + 1 = 28和3^0 + 9^1 = 1 + 9 = 10，其中一些组合可能重复。使用集合自动去除这些重复值，简化了操作并提高了算法的实际运行效率。