mover números de un arreglo n lugares

Problema

Un arreglo de números enteros de tamaño n tiene que recorrer la posición de los numeros K veces.

Solución:

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;// Reducir k si es mayor que n
        
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Explicación

Esta solución utiliza la técnica de inversión en tres partes. Es eficiente porque trabaja directamente sobre el arreglo original sin necesidad de crear uno nuevo.

Complejidad

• Tiempo: O(n)
• Espacio: O(1)

Artículo con fines educativos y de práctica personal.

Palindromo en java - formación de palindromos en subcadenas

Problema

el problema consiste en particionar la cadena en k partes y modificar el menor número posible de letras para que cada parte cumpla la propiedad de semipalíndromo.

Enfoque de la solución

Este es un problema de nivel Hard que combina dos técnicas importantes:

1. Precomputación del costo mínimo para convertir cada substring posible en semi-palindrome.
2. Dynamic Programming para encontrar la mejor forma de dividir el string en k partes.

Solución en Java

import java.util.*;

class Solution {
    public int minimumChanges(String s, int k) {
        int n = s.length();
        final int INF = 1_000_000_000;
        
        // g[i][j] = combios minimos para hacer un s[i..j-1] semi-palindrome
        int[][] g = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(g[i], INF);
        }
        
        // Precompute cost for every substring
        for (int i = 1; i <= n; i++) {           // start (1-based)
            for (int j = i; j <= n; j++) {       // end
                int len = j - i + 1;
                if (len == 1) continue; // longitud 1 no puede ser semi-palindrome
                
                for (int d = 1; d < len; d++) {
                    if (len % d != 0) continue;
                    
                    int changes = 0;
                    // For de este divisior d, checa cada grupo
                    for (int start = 0; start < d; start++) {
                        // Chaeca el grupo inicial 'start' con el paso d
                        int left = 0;
                        int right = (len / d) - 1;
                        while (left < right) {
                            char c1 = s.charAt(i - 1 + left * d + start);
                            char c2 = s.charAt(i - 1 + right * d + start);
                            if (c1 != c2) {
                                changes++;
                            }
                            left++;
                            right--;
                        }
                    }
                    g[i][j] = Math.min(g[i][j], changes);
                }
            }
        }
        
        // DP: dp[i][j] = consto minimo particionado primero i caracteres dentro de j partes
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(i, k); j++) {
                for (int prev = 0; prev < i; prev++) {
                    if (dp[prev][j - 1] != INF && g[prev + 1][i] != INF) {
                        dp[i][j] = Math.min(dp[i][j], dp[prev][j - 1] + g[prev + 1][i]);
                    }
                }
            }
        }
        
        return dp[n][k];
    }
}

Conceptos clave aprendidos

• Dynamic Programming de partición
• Precomputación de costos en substrings
• Divisores y patrones repetitivos en strings
• Optimización de soluciones complejas

Dificultad

Este tipo de problemas ayuda a fortalecer el razonamiento lógico y la capacidad de combinar múltiples técnicas algorítmicas.

Combinación de dos arreglos ya ordenado en uno solo.

Problema

El problema es combinar dos arrays que ya están ordenados en uno solo, sin utilizar memoria adicional. El primer array tiene espacio suficiente para contener ambos.

Solución en Java

Esta es una de las soluciones que llegan a pedir en las entrevistas técnicas:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }
    }
}

Explicación

La clave está en recorrer los arrays **desde el final**. De esta forma evitamos tener que desplazar elementos y logramos una solución muy eficiente.

Complejidad

• Tiempo: O(m + n)
• Espacio: O(1)

Conceptos aprendidos

Two Pointers, manipulación eficiente de arrays y resolución in-place.