Categorías
Algorithms

LeetCode – Número de matrices cuadradas (Java)

Dada una matriz A de enteros no negativos, la matriz es cuadrada si por cada par de elementos adyacentes, su suma es un cuadrado perfecto.

Devuelve el número de permutaciones de A cuadradas. Dos permutaciones A1 y A2 difieren si y solo si hay algún índice i tal que A1[i] ! = A2[i].

Ejemplo 1:

Aporte: [1,17,8]

Salida: 2
Explicación:
[1,8,17] y [17,8,1] son las permutaciones válidas.

Ejemplo 2:

Aporte: [2,2,2]

Salida: 1

Solución Java

Este problema puede resolverse utilizando el método similar de Permutación II. Se puede usar un conjunto para rastrear si se intercambia el mismo elemento. La principal diferencia es que debemos verificar si los dos vecinos adyacentes anteriores están en escuadra.

class Solution {
    int count = 0;
 
    public int numSquarefulPerms(int[] A) {
        Arrays.sort(A);
        helper(A, 0);   
        return count;    
    }
 
    void helper(int[] A, int start){
        //the adjacent two numbers before start
        if(start>1 && (!isSquareful(A[start], A[start-1]) || !isSquareful(A[start-1], A[start-2]))){
            return;
        }
        //if start is the last, then check start with its adjancent neighbor
        if(start==A.length-1 && !isSquareful(A[start], A[start-1])){
            return;
        }
 
        if(start==A.length-1){
            count++;
            return;
        }
 
        HashSet<Integer> set = new HashSet<>();
        for(int i=start; i<A.length; i++){
            //use set to track if the same element is used
            if(set.contains(A[i])){
                continue;
            }
            set.add(A[i]);
 
            swap(A, i, start);
            helper(A, start+1);
            swap(A, i, start);
        }
    }
 
    void swap(int[] A, int i, int j){
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
    }
 
    boolean isSquareful(int a, int b){
        double root = Math.sqrt(a+b);
        return (root-Math.floor(root))==0;
    }
}

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *