我最近遇到了 Google 提出的面试问题,但我无法找到解决该问题的优化算法:
给定 2 个数字 a 和 b。将a和b相除并以字符串形式返回结果。
示例1
Input: a=100 , b=3
Output: 33.(3)
Note: (100/3)=33.33333....Here 3 is in brackets because it gets repeated continuously.
示例2
Input: a=5 , b=10
Output: 0.5
示例3
Input: a=51 , b=7
Output: 7.(285714)
Note: 51/7 = 7.285714285714285714285714285714......... Here 285714 is in brackets because it is repeating.
如果有人能为这个问题想出一个时间优化的算法,那就太好了。 预先感谢您。
最佳答案
您可以简单地手动执行长除法,这在位数上是 O(N) ——很难看出您还能做得更好。
长除法的唯一问题是,如果分数是重复小数,它就不会终止,但您可以在开始之前轻松检测到这一点(分数是重复小数,当且仅当b
有任何2 和 5 以外的因素)。如果它是循环小数,则需要保留已经见过的临时余数列表。当你遇到以前见过的一个时,你就知道你刚刚找到了重复周期的结尾。
关于c - 谷歌 : Divide and return result in form of string,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24426776/