[Swift]LeetCode483. 最小好进制 | Smallest Good Base_app

概述For an integer n, we call k>=2 a good base of n, if all digits of n base k are 1. Now given a string representing n, you should return the smallest good base of n in string format. Example 1: Input:

For an integer n,we call k>=2 a good base of n,if all digits of n base k are 1.

Now given a string representing n,you should return the smallest good base of n in string format.

Example 1:

input: "13"Output: "3"Explanation: 13 base 3 is 111.

Example 2:

input: "4681"Output: "8"Explanation: 4681 base 8 is 11111.

Example 3:

input: "1000000000000000000"Output: "999999999999999999"Explanation: 1000000000000000000 base 999999999999999999 is 11.

Note:

The range of n is [3,10^18]. The string representing n is always valID and will not have leading zeros.

对于给定的整数 n,如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。

以字符串的形式给出 n,以字符串的形式返回 n 的最小好进制。

示例 1：

输入："13"输出："3"解释：13 的 3 进制是 111。

示例 2：

输入："4681"输出："8"解释：4681 的 8 进制是 11111。

示例 3：

输入："1000000000000000000"输出："999999999999999999"解释：1000000000000000000 的 999999999999999999 进制是 11。

提示：

n的取值范围是 [3,10^18]。输入总是有效且没有前导 0。

12ms

 1 class Solution { 2     func smallestGoodBase(_ n: String) -> String { 3         var num:Int = Int(n)! 4         for i in (2...(Int(log(Double(num + 1)) / log(2)))).reversed() 5         { 6             var left:Int = 2 7             var right:Int = Int(pow(Double(num),1.0 / Double(i - 1))) + 1 8             while (left < right) 9             {10                 var mID:Int = left + (right - left) / 211                 var sum:Int = 012                 for j in 0..<i13                 {14                     sum = sum * mID + 115                 }16                 if sum == num {return String(mID)}17                 else if sum < num {left = mID + 1}18                 else {right = mID}19             }20         }21         return String(num - 1)22     }23 }