Python 中的强大整数

假设我们有两个正整数 x 和 y，如果一个整数等于 x^i + y^j（其中 i >= 0 且 j >= 0 为整数），则称该整数为强大整数。我们需要找到所有小于或等于 bound 的强大整数的列表。

因此，如果输入为 x = 2，y = 3，bound = 10，则输出将为 [2,3,4,5,7,9,10]，因为 2 = 2^0 + 3^0 3 = 2^1 + 3^0 4 = 2^0 + 3^1 5 = 2^1 + 3^1 7 = 2^2 + 3^1 9 = 2^3 + 3^0 10 = 2^0 + 3^2

为了解决这个问题，我们将遵循以下步骤：

  • 初始化 a、b 为 0
  • res := 一个新的列表
  • 如果 x 等于 1 且 y 等于 1，则
    • 如果 bound >= 2，则
      • 在 res 的末尾插入 2
    • 否则，如果 x 等于 1，则
      • 当 y^b + 1 <= bound 时，执行以下操作：
        • 将 y^b + 1 插入 res 中
        • b := b + 1
    • 否则，如果 y 等于 1，则
      • 当 x^a + 1 <= bound 时，执行以下操作：
        • 将 x^a + 1 插入 res 中
        • a := a + 1
    • 否则，
      • 当 x^a + 1 <= bound 时，执行以下操作：
        • 如果 x^a + y^b <= bound，则
          • b := b + 1
        • 否则，
          • a := a + 1
          • b := 0

让我们看看以下实现以获得更好的理解：

示例

 实时演示

class Solution:
   def powerfulIntegers(self, x, y, bound):
      a,b=0,0
      res=[]
      if x==1 and y==1:
         if bound>=2:
            res.append(2)
         elif x==1:
            while y**b+1<=bound:
               res.append(y**b+1)
               b+=1
         elif y==1:
            while x**a+1<=bound:
               res.append(x**a+1)
               a+=1
         else:
            while x**a+1<=bound:
               if x**a+y**b<=bound:
                  res.append(x**a+y**b)
                  b+=1
         else:
            a+=1
            b=0
      return list(set(res))
ob = Solution()
print(ob.powerfulIntegers(2,3,10))

输入

2,3,10

输出

[2, 3, 4, 5, 7, 9, 10]

更新于: 2020年7月6日

196 次浏览

启动您的 职业生涯

通过完成课程获得认证

开始
广告