给定一串数字和许多乘法运算符，可以计算出的最高数字是多少？

  • Z时代
  • 2024-01-10
  • 分类：问答

这是我遇到的一个面试问题，令人尴尬的是，我很困惑。想知道是否有人可以想出答案并为其提供大的O表示法。

Question: Given a string of numbers and a number of multiplication operators, 
          what is the highest number one can calculate? You must use all operators

您不能重新排列字符串。您只能使用乘法运算符来计算数字。

例如String = "312"1个乘法运算符

您可以执行3*12 = 36或31*2= 62。后者显然是正确的答案。

回答：

我在这里假设，问题的一部分给出了所需数量的乘法运算符 m 以及数字字符串 s 。

您可以使用表格形式的方法（也称为“动态编程”）来解决此问题，该方法具有O（|

s |）位数字的O（ m | s |

2）乘法。乘法的最佳计算复杂度未知，但对于教科书乘法算法，总体上为O（

m | s | 4）。

__

（这样做是为了计算每个子问题由所述串的尾部和一个数字的答案 米 ‘≤ 米 。有O（ 米 | 小号 |），例如子问题和解决每一个包括O（|

š |）的乘法长度为O（| s |）位的数字。）

在Python中，您可以使用Python装饰器库中的@memoized装饰器像这样编程：

@memoized
def max_product(s, m):
    """Return the maximum product of digits from the string s using m
    multiplication operators.
    """
    if m == 0:
        return int(s)
    return max(int(s[:i]) * max_product(s[i:], m - 1)
               for i in range(1, len(s) - m + 1))

如果您习惯于使用动态编程的自下而上的形式来构建表，则这种自上而下的形式可能看起来很奇怪，但实际上@memoized装饰器会cache在函数的属性中维护该表：

>>> max_product('56789', 1)
51102
>>> max_product.cache
{('89', 0): 89, ('9', 0): 9, ('6789', 0): 6789, ('56789', 1): 51102, ('789', 0): 789}

以上是 给定一串数字和许多乘法运算符，可以计算出的最高数字是多少？ 的全部内容， 来源链接： utcz.com/qa/406164.html

回到顶部