Java 中的平方数组数量

2024年9月10日 | 阅读 9 分钟

提供一个仅包含正数的数组作为输入。我们需要找出数组的平方数排列的总数。当相邻两个元素的和是一个完全平方数时，该数组被称为平方数数组。

示例 1

输入

int inArr[] = {1, 3, 6}

输出

解释

对于给定的数组，有 6 种可能的排列：{1, 3, 6}, {1, 6, 3}, {3, 1, 6}, {3, 6, 1}, {6, 1, 3}, {6, 3, 1}。在所有这些排列中，只有 {1, 3, 6} 和 {6, 3, 1} 构成了平方数数组。对于 {1, 3, 6}，我们有 1 + 3 = 4 (2²) 和 3 + 6 = 9 (3²)；对于 {6, 3, 1}，我们有 6 + 3 = 9 (3²) 和 1 + 3 = 4 (2²)。

示例 2

输入

int inArr[] = {24, 48, 1}

输出

解释

对于给定的数组，有 6 种可能的排列：{1, 24, 48}, {1, 48, 24}, {24, 1, 48}, {24, 48, 1}, {48, 1, 24}, {48, 24, 1}。在所有这些排列中，只有 {24, 1, 48} 和 {48, 1, 24} 构成了平方数数组。对于 {24, 1, 48}，我们有 24 + 1 = 25 (5²) 和 1 + 48 = 49 (7²)；对于 {48, 1, 24}，我们有 48 + 1 = 49 (7²) 和 1 + 24 = 25 (5²)。

示例 2

输入

int inArr[] = {0, 0, 4, 0, 0}

输出

解释

对于给定的数组，有 5 种可能的排列：{0, 0, 0, 0, 4}, {0, 0, 0, 4, 0}, {0, 0, 4, 0, 0}, {0, 4, 0, 0, 0}, {4, 0, 0, 0, 0}。所有这些排列都是平方数数组。对于 {0, 0, 0, 0, 4}，我们有 0 + 0 = 0 (0²)，0 + 0 = 0 (0²)，0 + 0 = 0 (0²)，0 + 4 = 4 (2²)。其他排列也可以给出类似的逻辑。

简单方法：暴力法

在这种方法中，我们检查输入数组的所有排列。对于输入数组 'inAr' 中的每个排列，检查 inAr[j] + inAr[j+1] 是否为完全平方数。如果是完全平方数，则将 ans 加 1。然后返回 ans。

算法

检查 'inAr' 的特定排列是否为平方数的方法。
- 创建一个方法 bool checkSquareful (int inAr[], int n)
- 将 'j' 从 0 迭代到 'inAr' 的长度。
  - 如果 floor(sqrt(inAr[i] + inAr[i+1] )) != ceil(sqrt(inAr[i] + inAr[i+1])), 则返回 false。
- 否则，返回 false。
计算所有平方数排列的方法
- 初始化一个 int 'cnt' = 0；
- 将数组 'inAr' 按升序排序。
- 运行一个 do-while 循环来检查所有平方数排列。
- do -> if checkSquareful (inAr) ，则增加 'cnt'。
- 同时继续检查 'inAr' 的下一个排列。

现在观察以下实现。

文件名： SquarefulArrays.java

// importing Arrays for performing sorting
import java.util.Arrays;

public class SquarefulArrays 
{    
// method that swaps elements located at the indices l and r
public static int[] swapEle(int inAr[], int l, int r)
{        
    int tmp = inAr[l];
    inAr[l] = inAr[r];
    inAr[r] = tmp;

    return inAr;
}

// reversing the array from l to r
public static int[] reverseArr(int inAr[], int l, int r)
{  
    while (l < r) 
    {
        int tmp = inAr[l];
        inAr[l] = inAr[r];
        l = l + 1;
        inAr[r] = tmp;
        r = r - 1;
    }

    return inAr;
}

// a method that finds the next permutation of the input array inAr[]
public static boolean nxtPermutation(int inAr[])
{

    if (inAr.length <= 1)
    {
        return false;
    }
    
    int lst = inAr.length - 2;

    // starting from the right, we move to left
    // and when two elements where the first element is lesser
    // than the next element, then the loop terminates.
    while (lst >= 0) 
    {
        if (inAr[lst] < inAr[lst + 1]) 
        {
            break;
        }

        lst = lst - 1;
    }

    if (lst < 0)
    {
        return false;
    }

    // finding the index of next greater element
    int nextGrtr = inAr.length - 1;
    for (int j = inAr.length - 1; j > lst; j--) 
    {
        if (inAr[j] > inAr[lst]) 
        {
            nextGrtr = j;
            break;
        }
    }

    // 
    inAr = swapEle(inAr, nextGrtr, lst);
    inAr = reverseArr(inAr, lst + 1, inAr.length - 1); 
    return true;
}

// Checking whether the input array is squareful or not.
public static boolean checkSquareful(int[] inAr, int n)
{
    for (int j = 0; j < n - 1; j++)
    {
        // if the sum of the element pointed by the loop variable and the next adjacent element is not a perfect
        // square, then the permutation forms the squareful array otherwise, not.
        if (Math.ceil(Math.sqrt(inAr[j] + inAr[j + 1])) != Math.floor(Math.sqrt(inAr[j] + inAr[j + 1])))
        {
            return false;
        }
    }

    return true;
}

// a method that computes the number of squareful arrays
public static int numberOfSquarefulArr(int[] inAr, int s) 
{
    int cnt = 0;
    
    // sorting the elements in the ascending order
    Arrays.sort(inAr);
    
    // Checking all of the permutations.
    do
    {
        if (checkSquareful(inAr, s))
        {
            // for every permutation that gives the
            // squareful array, the cnt is increased by 1
            cnt = cnt + 1;
        }
    
    } while (nxtPermutation(inAr));

    return cnt;
}


// main method
public static void main(String argvs[])
{
    
    // creating an object of the class SquarefulArrays
    SquarefulArrays obj = new SquarefulArrays();
    
    int inAr[] = {0, 0, 0, 0, 4}; // input array
    int size = inAr.length; // size of the input array
    
    
    System.out.println("For the input array: ");
    for(int j = 0 ; j < size; j++)
    {
    System.out.print(inAr[j] + " ");
    }
    
    // invoking the method numberOfSquarefulArr() and storing the answer
    int ans = obj.numberOfSquarefulArr(inAr, size);
    System.out.println();
    System.out.println("The number of Squareful array is: " + ans + "\n");
    
    int inAr1[] = {1, 3, 6}; // input array
    size = inAr1.length; // size of the input array
    
    System.out.println("For the input array: ");
    for(int j = 0 ; j < size; j++)
    {
    System.out.print(inAr1[j] + " ");
    }

    // invoking the method numberOfSquarefulArr() and storing the answer
    ans = obj.numberOfSquarefulArr(inAr1, size);
    System.out.println();
    System.out.println("The number of Squareful array is: " + ans + "\n");
    
    int inAr2[] = {24, 48, 1}; // input array
    size = inAr2.length; // size of the input array
    
    
    System.out.println("For the input array: ");
    for(int j = 0 ; j < size; j++)
    {
    System.out.print(inAr2[j] + " ");
    }
    
    // invoking the method numberOfSquarefulArr() and storing the answer
    ans = obj.numberOfSquarefulArr(inAr2, size);
    System.out.println();
    System.out.println("The number of Squareful array is: " + ans + "\n");
    
}
}

输出

For the input array: 
0 0 0 0 4 
The number of Squareful array is: 5

For the input array: 
1 3 6 
The number of Squareful array is: 2

For the input array: 
24 48 1 
The number of Squareful array is: 2

复杂度分析： 对于 N 大小的数组，总共有 N! 种排列。我们检查所有排列，每个排列的大小为 N。因此，程序的总时间复杂度为 O(N! * N)。程序空间复杂度为 O(1)，因为程序不使用任何额外的空间。

程序的 time complexity 非常高，不适合较大的输入。因此，需要进行一些优化。观察以下方法。

方法：动态规划

构建一个图，其中如果 inAr[j] + inAr[k] 是完全平方数，则从 j 到 k 存在一条边。然后，计算所有可能的哈密顿路径。哈密顿路径的总数将等于平方数排列的数量。

哈密顿路径是图中两个顶点之间的图路径，该路径至少访问图中的所有顶点一次。

我们将构建一个图，其中在 'j' 和 'k' 之间存在一条边，仅当 inAr[j] + inAr[k] 是完全平方数时。我们可以使用动态规划技术来检查哈密顿路径。

算法

步骤 1：我们将首先消除重复项，只考虑索引排列。P[B, j] 表示已使用的数字数量为 'B' 时，inAr[j] 是最后一个数字的总排列数。

步骤 2： 'B' 是二进制数，其中每一位表示 'j' 是否存在。

步骤 3： 开始时，P[1 << j, j] = 1。其他状态为 0。

步骤 4： 每次，枚举 'k'。

如果 'k' 不等于 'S'，并且 inAr[j] + inAr[k] 是完全平方数，那么，
- P[B|1 << k, k] += P[B, j]

步骤 5： 使用一个变量 'ans'。将其赋值为 0。

步骤 6： 使用 'j' 从 0 迭代到 's'，其中输入数组 'inAr' 的大小为 's'。

我们得到，'ans' += P[(1 << s) - 1, j]

步骤 7： 需要对重复的元素计数一次。因此，将 'ans' 除以 'inAr[]' 中每个数字的计数阶乘。

文件名：SquarefulArrays.java

// import statements
import java.util.Arrays;
import java.util.ArrayList;

public class SquarefulArrays
{
// a method that checks whether r is
// is a perfect square or not
public static boolean isSquare(int r) 
{
int t = (int)Math.sqrt(r);
return (t * t == r);
}

// a method that finds the factorial of num x
public static int fact(int x) 
{

int f = 1;
for (int j = 2; j <= x; j++) 
{
    f = f * j;
}

return f;
}


public static int numberOfSquarefulArr(int[] inAr, int s) 
{
Arrays.sort(inAr);

// list contains the number of times an element is repeated
// inn the input array inAr[]
ArrayList <Integer> al = new ArrayList<>();
int cnt = 1;
for (int i = 1; i < s; i++) 
{
    if (inAr[i] != inAr[i - 1]) 
	{
        al.add(cnt);
        cnt = 0;
    }

    cnt = cnt + 1;
}

al.add(cnt);


int P[][] = new int[1 << s][s];

for (int i = 0; i < s; i++) 
{
    P[1 << i][i] = 1;
}

// considering all the pairs which  
// may or may not make the perfect square
for (int k = 1; k < (1 << s); k++) 
{
    for (int i = 0; i < s; i++) 
	{
        if ((k & (1 << i)) != 0) 
		{
            for (int j = 0; j < s; j++) 
			{
                if ((k & (1 << j)) == 0 && isSquare(inAr[i] + inAr[j])) 
				{
                    P[k | (1 << j)][j] = P[k | (1 << j)][j] + P[k][i];
                }
            }
        }
    }
}

int ans = 0;
for (int k = 0; k < s; k++)
{
    ans = ans + P[(1 << s) - 1][k];
}

// a loop that handles repetition
for (int k = 0; k < al.size(); k++) 
{
    ans = ans / fact(al.get(k));
}	

return ans;
}


// main method
public static void main(String argvs[])
{
    
    // creating an object of the class SquarefulArrays
    SquarefulArrays obj = new SquarefulArrays();
    
    int inAr[] = {0, 0, 0, 0, 4}; // input array
    int size = inAr.length; // size of the input array
    
    
    System.out.println("For the input array: ");
    for(int j = 0 ; j < size; j++)
    {
    System.out.print(inAr[j] + " ");
    }
    
    // invoking the method numberOfSquarefulArr() and storing the answer
    int ans = obj.numberOfSquarefulArr(inAr, size);
    System.out.println();
    System.out.println("The number of Squareful array is: " + ans + "\n");
    
    int inAr1[] = {1, 3, 6}; // input array
    size = inAr1.length; // size of the input array
    
    System.out.println("For the input array: ");
    for(int j = 0 ; j < size; j++)
    {
    System.out.print(inAr1[j] + " ");
    }

    // invoking the method numberOfSquarefulArr() and storing the answer
    ans = obj.numberOfSquarefulArr(inAr1, size);
    System.out.println();
    System.out.println("The number of Squareful array is: " + ans + "\n");
    
    int inAr2[] = {24, 48, 1}; // input array
    size = inAr2.length; // size of the input array
    
    
    System.out.println("For the input array: ");
    for(int j = 0 ; j < size; j++)
    {
    System.out.print(inAr2[j] + " ");
    }
    
    // invoking the method numberOfSquarefulArr() and storing the answer
    ans = obj.numberOfSquarefulArr(inAr2, size);
    System.out.println();
    System.out.println("The number of Squareful array is: " + ans + "\n");
    
}
}

输出

For the input array: 
0 0 0 0 4 
The number of Squareful array is: 5

For the input array: 
1 3 6 
The number of Squareful array is: 2

For the input array: 
24 48 1 
The number of Squareful array is: 2

复杂度分析： 总共有 'N x 2N' 个状态，每个状态最多有 'N' 个子节点。此外，每个子节点至少被遍历一次。因此，程序的总时间复杂度为 O(N² x 2^N)。此外，程序使用二维数组 'P'，这使得程序的空间复杂度为 O(N x 2^N)，其中 N 是输入数组的大小。

下一主题Java 中的一次性密码生成器代码

Java 中的平方数组数量

简单方法：暴力法

算法

方法：动态规划

算法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的平方数组数量

简单方法：暴力法

算法

方法：动态规划

算法

相关帖子

Icon interface Java

Java 中的情侣牵手问题

Java 中的 AtomicIntegerArray set() 方法及示例

Exception in Thread Main java.util.NoSuchElementException no line Found

Java Multicasting (Typecasting Multiple Times) Puzzle

Java 中的异步调用

Java public keyword

Java 中反转字符串中的交替单词

Java 并发数组

Java 中显示整数数组的所有子集

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器