Estaba buscando las respuestas y encuentro que la mayoría de las soluciones de esta pregunta son bastante complicadas para que un ser humano las entienda. Entonces decidí buscar otra solución. La primera solución fue la recursividad con complejidad de tiempo O (n), sin embargo, terminó teniendo el problema StackOverflow . Luego decidió resolverlo con estructuras de datos Graph y Stack. Esta solución pasa de las pruebas de rendimiento en hackerrank y la complejidad del tiempo es O (n).
¿Por qué no el árbol binario porque es más fácil mantener la poligonal cuando los nodos NO se dan en orden padre-hijo como está en la pregunta y no es necesario que le digan que el primer nodo es el nodo raíz :). La otra ventaja es que la solución a continuación funcionará cuando el árbol NO sea un árbol binario 🙂
Primero, crea el gráfico y llénalo con sus conexiones. Al mismo tiempo, mantenga la suma total de la gráfica mientras agrega los vértices.
Gráfico de clase pública {
Nodo [] nodos;
int totalWeight = 0;
Graph (int size, int data []) {
nodos = nuevo nodo [tamaño];
int cuenta = 0;
while (cuenta nodos [recuento] = nuevo nodo (datos [recuento], recuento + 1);
totalWeight + = datos [recuento];
recuento ++;
}
}
Nodo de clase {
Private int idx;
datos int privados;
Conexiones LinkedList = new LinkedList <> ();
booleano visitado;
privado int totalWeight;
Nodo público (datos int, int idx) {
this.data = datos;
this.idx = idx;
this.totalWeight = data;
}
}
luego creemos una función en la clase Graph para agregar los nodos al gráfico. La razón por la que restamos 1 ya que las matrices comienzan desde 0 y en la pregunta, comienzan desde 1. Básicamente, simplemente agregamos las conexiones entre sí.
addNode público vacío (int firstNode, int secondNode) {
nodos [primerNodo-1]. connections.add (nodos [segundoNodo-1]);
nodos [secondNode-1]. connections.add (nodos [firstNode-1]);
}
Ahora escribamos nuestra función para encontrar la diferencia mínima. Primero, podemos agregar todos los elementos de nodo a una pila iterando a través de las conexiones (línea 2–17). Lo importante es marcar los elementos visitados como falsos para que no tengamos un ciclo de iteración sin fin.
Luego, en la misma función, comenzamos a aparecer desde la pila. Antes de hacerlo, restableceremos los nodos con falso nuevamente (la otra opción también es verificar si se visitó al revés para que no tenga que restablecer nuevamente). En cada iteración, agregaremos el peso total del nodo emergente a poppedNode.connections totalWeight uno por uno.
A continuación, en la misma iteración del elemento de pila, intentaremos encontrar la diferencia restando (wholeTreeSum – currentNodesSum) de currentNodesSum, que también significa | wholeTreeSum-2 * currentNodeSum |
El | significa absoluto en matemáticas.
Lo único que queda ahora es almacenar la diferencia mínima hasta ahora en la memoria de la función.
A continuación se muestra toda la función finMindifByStack.
void findMinDifByStack () {
Nodo raíz = nodos [0];
Pila s = nueva Pila ();
s.push (raíz);
root.visited = true;
LinkedList connections = root.connections;
while (connections.size ()> 0) {
LinkedList newConnections = new LinkedList <> ();
para (Conexión de nodo: conexiones) {
if (! connection.visited) {
s.push (conexión);
connection.visited = true;
newConnections.addAll (connection. connections);
}
}
conexiones = nuevas conexiones;
}
Reiniciar();
int currentMinDiff = Integer.MAX_VALUE;
while (! s.isEmpty ()) {
Nodo nodo = s.pop ();
nodo.visitado = verdadero;
for (Conexión de nodo: node. connections) {
if (! connection.visited) {
connection.totalWeight = connection.totalWeight + node.totalWeight;
}
}
int newDiff = Math.abs (totalWeight – 2 * node.totalWeight);
if (newDiff currentMinDiff = newDiff;
}
}
System.out.println (currentMinDiff);
}
La parte del controlador es la siguiente. No use la clase Scanner, de lo contrario tendrá problemas de rendimiento.
public static void main (String [] args) lanza Exception {
BufferedReader in = new BufferedReader (nuevo InputStreamReader (Recursos e información del sistema));
int cuenta = Integer.valueOf (in.readLine ());
int [] números = Stream.of (in.readLine (). split (“”)). mapToInt (Integer :: parseInt) .toArray ();
Graph graph = new Graph (conteo, números);
contar-;
while (cuenta–> 0) {
int [] par = Stream.of (in.readLine (). split (“”)). mapToInt (Integer :: parseInt) .toArray ();
graph.addNode (par [0], par [1]);
}
graph.findMinDifByStack ();
}
