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 次瀏覽

啟動您的 職業生涯

透過完成課程獲得認證

開始
廣告