資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告