public class IncrementSybmols {
public static void main(String[] args) throws Throwable {
List<Integer> syms = Arrays.asList(1,2,3,4,5);
test(syms, 3, Arrays.asList(1,2,3), Arrays.asList(1,2,4));
test(syms, 3, Arrays.asList(2,5,4), Arrays.asList(3,1,2));
test(syms, 3, Arrays.asList(4,3,5), Arrays.asList(4,5,1));
test(syms, 3, Arrays.asList(5,4,2), Arrays.asList(5,4,3));
test(syms, 3, Arrays.asList(5,4,3), null);
}
private static void test(List<Integer> syms, int n, List<Integer> in, List<Integer> exp) {
List<Integer> out = increment(syms, n, in);
System.out.println(in+" -> "+out+": "+(exp==out || exp.equals(out)?"OK":"FAIL"));
}
private static List<Integer> increment(List<Integer> allSyms, int n, List<Integer> in){
TreeSet<Integer> availableSym = new TreeSet<Integer>(allSyms);
availableSym.removeAll(in);
LinkedList<Integer> current = new LinkedList<Integer>(in);
// Remove symbols beginning from the tail until a better/greater symbols is available.
while(!current.isEmpty()){
Integer last = current.removeLast();
availableSym.add(last);
// look for greater symbols
Integer next = availableSym.higher(last);
if(next != null){
// if there is a greater symbols, append it
current.add(next);
availableSym.remove(next);
break;
}
}
// if there no greater symbol, then *shrug* there is no greater number
if(current.isEmpty())
return null;
// fill up with smallest symbols again
while(current.size() < n){
Integer next = availableSym.first();
availableSym.remove(next);
current.add(next);
}
return current;
}
}
Los buenos entrevistadores pueden decir si usted tiene una respuesta enlatada a estas cosas. Les gusta más si tienen que resolverlo, porque pueden ver su proceso de resolución de problemas, que es más importante que simplemente conocer la solución. – Almo
Di una solución como, Tome una cola ordenada de doble fin de números disponibles, inicie con los números disponibles, 1. comience con el dígito de unidades, verifique si hay un número más alto disponible, de ser así, reemplace else, ponga este número en la lista disponible y compruebe el dígito de las decenas 2. En caso de que encuentre un número mayor que el dígito actual, reemplácelo y comience a insertar números más pequeños de la cola. ¿Se puede hacer esto más eficiente y hay algún defecto? –
ejemplo .. {{{ 123 disponible: 45 cheque 3 .. sustituir con 4 para 254 disponible: 13 cheque 4 .. 1,3 <4 poner 4 in disponible de verificación 5 .. No disponible cheque 2 .. disponible: 1345 insertar 2 en disponible ,, reemplazar por 3, seguir por 1 y 2 }}} –