数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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 次查看
广告