JZX轻语：简

LeetCode 970 - 强整数

发表于2024年05月31日

这种要求返回所有满足条件的结果题目，一般都使用递归+回溯的方法来解决，但此题因为只涉及两个数的枚举，因此仅需使用双重循环枚举两个数的幂，将其和加入到结果直至不满足条件即可。

需要注意几点：

由于题目要求返回的结果不能重复，因此需要使用set来存储结果，最后再转换为list返回。
注意x和y的大小关系，通过swap保证外层循环遍历的x是较大的数，这样可以减少循环次数。
当x或y为1时，需要特殊处理，及时跳出循环。

class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
        x, y = (x, y) if x > y else (y, x)
        i = 0
        ans = set()
        while x ** i < bound:
            j = 0
            while x ** i + y ** j <= bound:
                ans.add(x ** i + y ** j)
                j += 1
                if y == 1:
                    break
            i += 1
            if x == 1:
                break
        return list(ans)

闪念标签：LC

题目链接：https://leetcode.cn/problems/powerful-integers/