Python 中的最小良好基数

假设我们有一个整数 n，当 n 的 k 进制表示的所有数字都是 1 时，我们称 k >= 2 为 n 的良好基数。所以如果给定的数字 n 是字符串，我们必须返回 n 的最小良好基数作为字符串。例如，如果数字是 121，则答案将是 3，因为 121 在 3 进制下是 11111。

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

  • 定义一个名为 getSum() 的方法，它将接收 x 和长度作为参数
  • 设置 mainSum := 0 和 temp := 1
  • 对于 i 在 0 到 length – 1 的范围内：
    • mainSum := mainSum + temp，temp := temp * x
  • 返回 mainSum
  • 定义一个名为 check() 的方法，它将接收 n 和 length 作为参数：
  • low := 1，high := n
  • 当 high >= low 时：
    • mid := low + (high – low) / 2
    • mainSum := getSum(mid, length)
    • 如果 mainSum = n，则返回 mid
    • 否则，如果 mainSum > n，则 high := mid – 1
    • 否则，low := mid + 1
  • 返回 -1
  • 从主方法执行以下操作：
  • n := 给定的数字
  • 对于 i 在 64 到 0 的范围内：
    • x := check(n, i)
    • 如果 x >= 2，则返回 x 作为字符串
  • 返回 n – 1 作为字符串

让我们看看以下实现，以便更好地理解：

示例

 实时演示

class Solution(object):
   def getSum(self, x, length):
      mainSum = 0
      temp = 1
      for i in range(length):
         mainSum += temp
         temp *= x
      return mainSum
   def check(self, n, length):
      low = 1
      high = n
      while high >= low:
      mid = low + (high - low) // 2
      mainSum = self.getSum(mid, length)
      if mainSum == n:
         return mid
      elif mainSum > n:
         high = mid - 1
      else:
         low = mid + 1
      return -1
   def smallestGoodBase(self, n):
      n = int(n)
      for i in range(64, 0, - 1):
         x = self.check(n, i)
      if x >= 2:
         return str(x)
      return str(n - 1)
ob = Solution()
print(ob.smallestGoodBase("121"))

输入

“121”

输出

3

更新于: 2020-06-01

260 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告