发表于 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 题目链接