これは私が持っていたインタビューの質問であり、私は恥ずかしそうにかなり困惑しました. 誰かがそれに対する答えを考え出し、それに大きな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 ) になります。
(アイデアは、文字列の末尾と数m ′ ≤ mで構成される各部分問題の答えを計算することです。O ( m | s |) のような部分問題があり、それぞれを解くには O(| s |) の乗算が必要です。 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}
Python はすでにその機能上の利点を示しており、私を打ち負かしていましたが、Java バージョン:
private static class Solution {
BigInteger product;
String expression;
}
private static Solution solve(String digits, int multiplications) {
if (digits.length() < multiplications + 1) {
return null; // No solutions
}
if (multiplications == 0) {
Solution solution = new Solution();
solution.product = new BigInteger(digits);
solution.expression = digits;
return solution;
}
// Position of first '*':
Solution max = null;
for (int i = 1; i < digits.length() - (multiplications - 1); ++i) {
BigInteger n = new BigInteger(digits.substring(0, i));
Solution solutionRest = solve(digits.substring(i), multiplications - 1);
n = n.multiply(solutionRest.product);
if (max == null || n.compareTo(max.product) > 0) {
solutionRest.product = n;
solutionRest.expression = digits.substring(0, i) + "*"
+ solutionRest.expression;
max = solutionRest;
}
}
return max;
}
private static void test(String digits, int multiplications) {
Solution solution = solve(digits, multiplications);
System.out.printf("%s %d -> %s = %s%n", digits, multiplications,
solution.expression, solution.product.toString());
}
public static void main(String[] args) {
test("1826456903521651", 5);
}
出力
1826456903521651 5 -> 182*645*6*903*521*651 = 215719207032420
これは反復動的計画法のソリューションです。
再帰的なバージョン(同じような実行時間を持つ必要があります) とは対照的です。
基本的な考え方:
A[position][count]は、乗算positionを使用して、位置 で終わる最大の数です。count
そう：
A[position][count] = max(for i = 0 to position
A[i][count-1] * input.substring(i, position))
各位置と各カウントに対してこれを行い、必要な乗算回数でこれらのそれぞれを残りの文字列全体で乗算します。
複雑：
挿入する乗算演算子を含む文字列|s|を指定すると...m
O(m|s|2g(s))乗算の複雑さはg(s)どこにありますか。
Java コード:
static long solve(String digits, int multiplications)
{
if (multiplications == 0)
return Long.parseLong(digits);
// Preprocessing - set up substring values
long[][] substrings = new long[digits.length()][digits.length()+1];
for (int i = 0; i < digits.length(); i++)
for (int j = i+1; j <= digits.length(); j++)
substrings[i][j] = Long.parseLong(digits.substring(i, j));
// Calculate multiplications from the left
long[][] A = new long[digits.length()][multiplications+1];
A[0][0] = 1;
for (int i = 1; i < A.length; i++)
{
A[i][0] = substrings[0][i];
for (int j = 1; j < A[0].length; j++)
{
long max = -1;
for (int i2 = 0; i2 < i; i2++)
{
long l = substrings[i2][i];
long prod = l * A[i2][j-1];
max = Math.max(max, prod);
}
A[i][j] = max;
}
}
// Multiply left with right and find maximum
long max = -1;
for (int i = 1; i < A.length; i++)
{
max = Math.max(max, substrings[i][A.length] * A[i][multiplications]);
}
return max;
}
非常に基本的なテスト:
System.out.println(solve("99287", 1));
System.out.println(solve("99287", 2));
System.out.println(solve("312", 1));
版画:
86304
72036
62
はい、最大値を出力するだけです。必要に応じて、実際に合計を出力することはそれほど難しくありません。
別の Java ソリューションを次に示します。（「312」と1の乗算で正しいことはわかっていますが、他の人でも機能すると思います...
再帰メソッドの複雑さを自分で取得する方法を覚えておく必要がありますね (笑)。
package test;
import java.util.ArrayList;
import java.util.List;
public class BiggestNumberMultiply {
private static class NumberSplit{
String[] numbers;
long result;
NumberSplit(String[] numbers){
this.numbers=numbers.clone();
result=1;
for(String n:numbers){
result*=Integer.parseInt(n);
}
}
@Override
public String toString() {
StringBuffer sb=new StringBuffer();
for(String n:numbers){
sb.append(n).append("*");
}
sb.replace(sb.length()-1, sb.length(), "=")
.append(result);
return sb.toString();
}
}
public static void main(String[] args) {
String numbers = "312";
int numMults=1;
int numSplits=numMults;
List<NumberSplit> splits = new ArrayList<NumberSplit>();
splitNumbersRecursive(splits, new String[numSplits+1], numbers, numSplits);
NumberSplit maxSplit = splits.get(0);
for(NumberSplit ns:splits){
System.out.println(ns);
if(ns.result>maxSplit.result){
maxSplit = ns;
}
}
System.out.println("The maximum is "+maxSplit);
}
private static void splitNumbersRecursive(List<NumberSplit> list, String[] splits, String numbers, int numSplits){
if(numSplits==0){
splits[splits.length-1] = numbers;
return;
}
for(int i=1; i<=numbers.length()-numSplits; i++){
splits[splits.length-numSplits-1] = numbers.substring(0,i);
splitNumbersRecursive(list, splits, numbers.substring(i), numSplits-1);
list.add(new NumberSplit(splits));
}
}
}
この実装は @lars 用です。
from __future__ import (print_function)
import collections
import sys
try:
xrange
except NameError: # python3
xrange = range
def max_product(s, n):
"""Return the maximum product of digits from the string s using m
multiplication operators.
"""
# Guard condition.
if len(s) <= n:
return None
# A type for our partial solutions.
partial_solution = collections.namedtuple("product",
["value", "expression"])
# Initialize the best_answers dictionary with the leading terms
best_answers = {}
for i in xrange(len(s)):
term = s[0: i+1]
best_answers[i+1] = partial_solution(int(term), term)
# We then replace best_answers n times.
for prev_product_count in [x for x in xrange(n)]:
product_count = prev_product_count + 1
old_best_answers = best_answers
best_answers = {}
# For each position, find the best answer with the last * there.
for position in xrange(product_count+1, len(s)+1):
candidates = []
for old_position in xrange(product_count, position):
prior_product = old_best_answers[old_position]
term = s[old_position:position]
value = prior_product.value * int(term)
expression = prior_product.expression + "*" + term
candidates.append(partial_solution(value, expression))
# max will choose the biggest value, breaking ties by the expression
best_answers[position] = max(candidates)
# We want the answer with the next * going at the end of the string.
return best_answers[len(s)]
print(max_product(sys.argv[1], int(sys.argv[2])))
実行例は次のとおりです。
$ python mult.py 99287 2
product(value=72036, expression='9*92*87')
うまくいけば、実装からロジックが明確になります。
これは頭に浮かんだ、それは棒と星の問題の影響を受けた力ずくのアプローチです。
番号が「12345」で、使用する必要がある 2 つの * 演算子があるとします。文字列 12345 を次のように見ることができます。
1_2_3_4_5
アンダースコアのいずれかに 2 つの * 演算子を置くことができる場所。4 つのアンダースコアと 2 つの * 演算子があるため、演算子を配置する 2 つ (または 6 つ) の異なる方法が 4 つあります。これらの 6 つの可能性を比較し、最大の数を取得します。より大きな文字列と多数の * 演算子にも同様のアプローチを使用できます。
*答えは、最大の数字が最大の影響を与えるように、単純に最大の数字の直前に sを置くことだと確信しています。たとえば、
1826456903521651
5 つの乗算がある場合、これが答えになります。
1*82*645*6*903521*651
したがって、実行時間は線形になります。
編集：わかりました、これは間違っています。2 つの反例があります。