algorithm - rango - sonidos de alta frecuencia ejemplos
Dada una serie de números y varios operadores de multiplicación, ¿cuál es el número más alto que uno puede calcular? (9)
Esta fue una pregunta de entrevista que tuve y que me avergonzó bastante. Quería saber si alguien podría pensar en una respuesta y proporcionarle la gran notación O para ello.
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
No puedes reordenar la cadena. Solo puedes usar los operadores de multiplicación para calcular un número.
Ej .: String = "312" , 1 operador de multiplicación
Puedes hacer 3*12 = 36 o 31*2= 62 . La última, obviamente, es la respuesta correcta.
Aquí hay otra solución de Java. (Sé que es correcto para "312" y 1 multiplicación y creo que funciona para otros ...
Tendrá que recordar cómo obtener la complejidad de los métodos recursivos por su cuenta, jaja.
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));
}
}
}
Aquí hay una solución de programación dinámica iterativa.
A diferencia de la versión recursiva (que debería tener un tiempo de ejecución similar).
La idea básica:
A[position][count] es el número más alto que se puede obtener y termina en la posición de la position , utilizando multiplicaciones de count .
Asi que:
A[position][count] = max(for i = 0 to position
A[i][count-1] * input.substring(i, position))
Haga esto para cada posición y cada conteo, luego multiplique cada uno de estos en el número requerido de multiplicaciones con toda la cadena restante.
Complejidad:
Dada una cadena |s| con m operadores de multiplicación para insertar ...
O(m|s| 2 g(s)) donde g(s) es la complejidad de la multiplicación .
Código de 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;
}
Una prueba muy básica:
System.out.println(solve("99287", 1));
System.out.println(solve("99287", 2));
System.out.println(solve("312", 1));
Huellas dactilares:
86304
72036
62
Sí, solo imprime el máximo. No es muy difícil tener que imprimir las sumas, si es necesario.
Encontré la solución de DP anterior útil pero confusa. La recurrencia tiene algún sentido, pero quería hacerlo todo en una sola mesa sin ese control final. Me tomó años depurar todos los índices, así que he mantenido algunas explicaciones.
Recordar:
- Inicialice T para que sea del tamaño N (porque los dígitos 0..N-1) por k + 1 (porque 0..k multiplicaciones).
- La tabla T (i, j) = el mayor producto posible utilizando los primeros dígitos i + 1 de la cadena (debido a la indexación cero) y las multiplicaciones j.
- Caso base: T (i, 0) = dígitos [0..i] para i en 0..N-1.
- Recurrencia: T (i, j) = máx. A (T (a, j-1) * dígitos [a + 1..i]). Es decir: Dígitos de partición [0..i] en dígitos [0..a] * dígitos [a + 1..i]. Y debido a que esto implica una multiplicación, el subproblema tiene una multiplicación menos, así que busque la tabla en j-1.
- Al final, la respuesta se almacena en T (todos los dígitos, todas las multiplicaciones) o T (N-1, k).
La complejidad es O (N 2 k) porque la maximización sobre a es O (N), y lo hacemos O (k) veces por cada dígito (O (N)).
public class MaxProduct {
public static void main(String ... args) {
System.out.println(solve(args[0], Integer.parseInt(args[1])));
}
static long solve(String digits, int k) {
if (k == 0)
return Long.parseLong(digits);
int N = digits.length();
long[][] T = new long[N][k+1];
for (int i = 0; i < N; i++) {
T[i][0] = Long.parseLong(digits.substring(0,i+1));
for (int j = 1; j <= Math.min(k,i); j++) {
long max = Integer.MIN_VALUE;
for (int a = 0; a < i; a++) {
long l = Long.parseLong(digits.substring(a+1,i+1));
long prod = l * T[a][j-1];
max = Math.max(max, prod);
}
T[i][j] = max;
}
}
return T[N-1][k];
}
}
Esta implementación es para @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])))
Aquí hay una muestra de ejecución:
$ python mult.py 99287 2
product(value=72036, expression=''9*92*87'')
Esperemos que la lógica sea clara a partir de la implementación.
Esto vino a la mente, es el enfoque de fuerza bruta influenciado por el problema de las barras y las estrellas .
Digamos que nuestro número es "12345" y tenemos 2 * operadores que necesitamos usar. Podemos mirar la cadena 12345 como
1_2_3_4_5
Donde podemos colocar los dos * operadores en cualquiera de los guiones bajos. Dado que hay 4 guiones bajos y 2 * operadores, hay 4 elegir 2 (o 6) formas diferentes de colocar a los operadores. Compara esas 6 posibilidades y toma el mayor número. Se puede usar un enfoque similar para cadenas más grandes y un mayor número de operadores *.
Estoy bastante seguro de que la respuesta es simplemente poner el * s justo antes de los dígitos más grandes, para que el dígito más grande tenga el mayor impacto. Por ejemplo, si tenemos
1826456903521651
Y tenemos cinco multiplicaciones, esta sería la respuesta.
1*82*645*6*903521*651
Así que el tiempo de ejecución sería lineal.
Edit: está bien, así que esto está mal. Tenemos dos contraejemplos.
La versión java, aunque Python ya mostró su ventaja funcional y me ganó:
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);
}
Salida
1826456903521651 5 -> 182*645*6*903*521*651 = 215719207032420
Sin embargo, otra implementación de Java. Esto es DP de arriba a abajo, también conocido como memoización. También imprime los componentes reales además del producto máximo.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class MaxProduct {
private static Map<Key, Result> cache = new HashMap<>();
private static class Key {
int operators;
int offset;
Key(int operators, int offset) {
this.operators = operators;
this.offset = offset;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + offset;
result = prime * result + operators;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (!(obj instanceof Key)) {
return false;
}
Key other = (Key) obj;
if (offset != other.offset) {
return false;
}
if (operators != other.operators) {
return false;
}
return true;
}
}
private static class Result {
long product;
int offset;
Result prev;
Result (long product, int offset) {
this.product = product;
this.offset = offset;
}
@Override
public String toString() {
return "product: " + product + ", offset: " + offset;
}
}
private static void print(Result result, String input, int operators) {
System.out.println(operators + " multiplications on: " + input);
Result current = result;
System.out.print("Max product: " + result.product + " = ");
List<Integer> insertions = new ArrayList<>();
while (current.prev != null) {
insertions.add(current.offset);
current = current.prev;
}
List<Character> inputAsList = new ArrayList<>();
for (char c : input.toCharArray()) {
inputAsList.add(c);
}
int shiftedIndex = 0;
for (int insertion : insertions) {
inputAsList.add(insertion + (shiftedIndex++), ''*'');
}
StringBuilder sb = new StringBuilder();
for (char c : inputAsList) {
sb.append(c);
}
System.out.println(sb.toString());
System.out.println("-----------");
}
public static void solve(int operators, String input) {
cache.clear();
Result result = maxProduct(operators, 0, input);
print(result, input, operators);
}
private static Result maxProduct(int operators, int offset, String input) {
String rightSubstring = input.substring(offset);
if (operators == 0 && rightSubstring.length() > 0) return new Result(Long.parseLong(rightSubstring), offset);
if (operators == 0 && rightSubstring.length() == 0) return new Result(1, input.length() - 1);
long possibleSlotsForFirstOperator = rightSubstring.length() - operators;
if (possibleSlotsForFirstOperator < 1) throw new IllegalArgumentException("too many operators");
Result maxProduct = new Result(-1, -1);
for (int slot = 1; slot <= possibleSlotsForFirstOperator; slot++) {
long leftOperand = Long.parseLong(rightSubstring.substring(0, slot));
Result rightOperand;
Key key = new Key(operators - 1, offset + slot);
if (cache.containsKey(key)) {
rightOperand = cache.get(key);
} else {
rightOperand = maxProduct(operators - 1, offset + slot, input);
}
long newProduct = leftOperand * rightOperand.product;
if (newProduct > maxProduct.product) {
maxProduct.product = newProduct;
maxProduct.offset = offset + slot;
maxProduct.prev = rightOperand;
}
}
cache.put(new Key(operators, offset), maxProduct);
return maxProduct;
}
public static void main(String[] args) {
solve(5, "1826456903521651");
solve(1, "56789");
solve(1, "99287");
solve(2, "99287");
solve(2, "312");
solve(1, "312");
}
}
Bonificación : una implementación de fuerza bruta para cualquier persona interesada. No es particularmente inteligente, pero hace que el rastreo sea un paso directo.
import java.util.ArrayList;
import java.util.List;
public class MaxProductBruteForce {
private static void recurse(boolean[] state, int pointer, int items, List<boolean[]> states) {
if (items == 0) {
states.add(state.clone());
return;
}
for (int index = pointer; index < state.length; index++) {
state[index] = true;
recurse(state, index + 1, items - 1, states);
state[index] = false;
}
}
private static List<boolean[]> bruteForceCombinations(int slots, int items) {
List<boolean[]> states = new ArrayList<>(); //essentially locations to insert a * operator
recurse(new boolean[slots], 0, items, states);
return states;
}
private static class Tuple {
long product;
List<Long> terms;
Tuple(long product, List<Long> terms) {
this.product = product;
this.terms = terms;
}
@Override
public String toString() {
return product + " = " + terms.toString();
}
}
private static void print(String input, int operators, Tuple result) {
System.out.println(operators + " multiplications on: " + input);
System.out.println(result.toString());
System.out.println("---------------");
}
public static void solve(int operators, String input) {
Tuple result = maxProduct(input, operators);
print(input, operators, result);
}
public static Tuple maxProduct(String input, int operators) {
Tuple maxProduct = new Tuple(-1, null);
for (boolean[] state : bruteForceCombinations(input.length() - 1, operators)) {
Tuple newProduct = getProduct(state, input);
if (maxProduct.product < newProduct.product) {
maxProduct = newProduct;
}
}
return maxProduct;
}
private static Tuple getProduct(boolean[] state, String input) {
List<Long> terms = new ArrayList<>();
List<Integer> insertLocations = new ArrayList<>();
for (int i = 0; i < state.length; i++) {
if (state[i]) insertLocations.add(i + 1);
}
int prevInsert = 0;
for (int insertLocation : insertLocations) {
terms.add(Long.parseLong(input.substring(prevInsert, insertLocation))); //gradually chop off the string
prevInsert = insertLocation;
}
terms.add(Long.parseLong(input.substring(prevInsert))); //remaining of string
long product = 1;
for (long term : terms) {
product = product * term;
}
return new Tuple(product, terms);
}
public static void main(String[] args) {
solve(5, "1826456903521651");
solve(1, "56789");
solve(1, "99287");
solve(2, "99287");
solve(2, "312");
solve(1, "312");
}
}
Supongo que aquí se da el número m requerido de operadores de multiplicación como parte del problema, junto con la cadena de dígitos.
Puede resolver este problema usando el método tabular (también conocido como "programación dinámica") con O ( m | s | 2 ) multiplicaciones de números que tienen una longitud de O (| s |) dígitos. La complejidad computacional óptima de la multiplicación no se conoce, pero con el algoritmo de multiplicación de libros escolares es O ( m | s | 4 ) en general.
(La idea es calcular la respuesta para cada subproblema que consiste en una cola de la cadena y un número m ′ ≤ m . Hay O ( m | s |) tales subproblemas y resolver cada uno implica O (| s |) multiplicaciones de Números que son O (| s |) dígitos largos.)
En Python, puedes programarlo de esta manera, utilizando el decorador @memoized de la biblioteca de decoradores de Python:
@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))
Si está acostumbrado a la forma de abajo hacia arriba de la programación dinámica donde construye una tabla, esta forma de arriba hacia abajo puede parecer extraña, pero en realidad el decorador @memoized mantiene la tabla en la propiedad de cache de la función:
>>> max_product(''56789'', 1)
51102
>>> max_product.cache
{(''89'', 0): 89, (''9'', 0): 9, (''6789'', 0): 6789, (''56789'', 1): 51102, (''789'', 0): 789}