Problema
Este es el seguimiento avanzado de Aplanar un arreglo 2D. Practica primero ese desafío. Aquí las listas pueden contener más listas a cualquier profundidad. En C++ y C#, utiliza el tipo NestedValue provisto en el código inicial. Lee el campo kind primero: 0 significa omitir esta entrada, 1 significa agregar el valor, y 2 significa visitar los elementos recursivamente.
Convierte una lista anidada en una lista plana de enteros. Lee de izquierda a derecha; cada vez que encuentres otra lista, lee su contenido antes de continuar. Ignora los valores nulos (mostrados como None en los ejemplos) y las listas vacías. Conserva los enteros repetidos y su orden.
Python recibe listas anidadas ordinarias que contienen enteros y None. C++ y C# reciben una lista de objetos NestedValue provistos por el código inicial: kind 0 significa nulo, kind 1 significa entero en value, y kind 2 significa una lista en items. Solo importa el campo seleccionado por kind. Devuelve una lista simple de enteros en todos los lenguajes.
Implementa flatten_arbitrarily_nested_list(values).
Entrada
values: Una lista cuyas entradas pueden ser enteros, nulos o más listas.
Salida
Devuelve los enteros en orden de profundidad primero, de izquierda a derecha. Devuelve una lista vacía si no hay enteros.
Restricciones
El valor externo es una lista. Como máximo 10,000 entradas sumando todas las listas; profundidad máxima de anidamiento 50. Las hojas enteras caben en un entero con signo de 64 bits. Las hojas son enteros o nulos, nunca cadenas ni booleanos.
Ejemplos
Entrada:
values = [
1,
[
2,
None,
[3]
],
[],
4
]
Salida esperada:
expected = [1, 2, 3, 4]Usa el tipo NestedValue que viene en el código inicial. Sus campos son kind (0 = null, 1 = entero, 2 = lista), value (el entero) y items (la lista anidada).
Entrada:
std::vector<NestedValue> values = {
NestedValue{1, 1, {}},
NestedValue{2, 0, {
NestedValue{1, 2, {}},
NestedValue{0, 0, {}},
NestedValue{2, 0, {
NestedValue{1, 3, {}}
}}
}},
NestedValue{2, 0, {}},
NestedValue{1, 4, {}}
};
Salida esperada:
std::vector<long long> expected = {1, 2, 3, 4};Usa el tipo NestedValue que viene en el código inicial. Sus campos son kind (0 = null, 1 = entero, 2 = lista), value (el entero) y items (la lista anidada).
Entrada:
NestedValue[] values = new NestedValue[] {
new NestedValue { kind = 1, value = 1 },
new NestedValue { kind = 2, items = new NestedValue[] {
new NestedValue { kind = 1, value = 2 },
new NestedValue { kind = 0 },
new NestedValue { kind = 2, items = new NestedValue[] {
new NestedValue { kind = 1, value = 3 }
} }
} },
new NestedValue { kind = 2, items = new NestedValue[] {} },
new NestedValue { kind = 1, value = 4 }
};
Salida esperada:
long[] expected = new long[] {1, 2, 3, 4};Explicación
Lee 1, luego entra en la lista anidada y lee 2 y 3, omitiendo el nulo. La lista vacía no agrega nada; termina con 4.
Entrada:
values = [
None,
[],
[None]
]
Salida esperada:
expected = []Usa el tipo NestedValue que viene en el código inicial. Sus campos son kind (0 = null, 1 = entero, 2 = lista), value (el entero) y items (la lista anidada).
Entrada:
std::vector<NestedValue> values = {
NestedValue{0, 0, {}},
NestedValue{2, 0, {}},
NestedValue{2, 0, {
NestedValue{0, 0, {}}
}}
};
Salida esperada:
std::vector<long long> expected = {};Usa el tipo NestedValue que viene en el código inicial. Sus campos son kind (0 = null, 1 = entero, 2 = lista), value (el entero) y items (la lista anidada).
Entrada:
NestedValue[] values = new NestedValue[] {
new NestedValue { kind = 0 },
new NestedValue { kind = 2, items = new NestedValue[] {} },
new NestedValue { kind = 2, items = new NestedValue[] {
new NestedValue { kind = 0 }
} }
};
Salida esperada:
long[] expected = new long[] {};Explicación
Cada entrada es nula o un contenedor vacío. No queda ningún entero.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Piensa en cada lista como algo que hay que entrar, terminar y luego abandonar más tarde.
Pista 2
Usa un recorrido en profundidad, con recursión o con una pila explícita, para mantener el orden de izquierda a derecha.
Pista 3
Ignora los valores null y las listas vacías, y asegúrate de que los valores muy anidados sigan apareciendo en la secuencia correcta.
Complejidad esperada
tiempo O(n), espacio extra O(d)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.