Pre Script: estoy proporcionando un enfoque algorítmico, que se puede utilizar en Java. Pero no estoy seguro, si está buscando algún método incorporado específico en Java que podría hacer esto: O
La clave aquí es que, dado que queremos subarreglos, significa que los elementos, en cada subconjunto, deben tomarse en orden.
Ahora, si tenemos elementos ‘n’, entonces debemos considerar cada elemento como el elemento inicial uno por uno. Cuando estamos en el elemento ‘i’, esto significa que los subconjuntos que comienzan con estos elementos pueden incluir elementos de i + 1 a n.
Esto se puede hacer mediante un enfoque de programación dinámica fácilmente.
Considere una matriz int no_of_subarrays [], de modo que
no_of_subarrays [i] almacena el no de subarreglos posibles al incluir el elemento ‘i’ th como elemento inicial.
Ahora no_of_subarrays [n-1] = 1 (ya que no son posibles más elementos después de n-1)
para cada yo
no_of_subarrays [i] = 1 + no_of_subarrays [i + 1] (el elemento i se puede incluir en todos los subarreglos de procedimiento)
Tiempo en)
Finalmente total no of subarrays = Suma de los elementos en la matriz anterior.
- 15 personas se sentarán en una fila de 15 sillas. ¿Cómo calculo cuántos planes de asientos se pueden hacer, donde dos planes de asientos se consideran iguales si dos planes comparten cuádruples adyacentes? o ¿Cómo puedo crear un algoritmo eficiente para encontrar límites inferiores para 15 o menos personas?
- ¿Contamos la estructura original dada mientras contamos el número total de isómeros?
- ¿Tengo que estudiar matemáticas discretas, algoritmos y estructura de datos para convertirme en un buen desarrollador de Android?
- ¿Cuáles son las desventajas de las matrices dinámicas sobre las matrices tradicionales en lenguajes como C / C ++?
- ¿Es 'Cracking the Coding Interview' una lectura obligatoria cuando se postula para ser un ingeniero front-end?
Si también desea encontrar las submatrices, puede almacenar las submatrices de cada elemento inicial en un mapa, formar las submatrices de los elementos anteriores al incluirlas en las submatrices ya formadas.
Tiempo en)
Espacio: O (n)