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; } } |