Define a square pair to be the tuple where x and y are positive, non-zero integers, x

hadoopall 发布于 2018年6月6日 评论(0) 阅读(173)

美国面试题3

1. 题目：

Define a square pair to be the tuple <x, y> where x and y are positive, non-zero integers, x<y and x + y is a perfect square. A perfect square is an integer whose square root is also an integer, e.g. 4, 9, 16 are perfect squares but 3, 10 and 17 are not. Write a function named countSquarePairs that takes an array and returns the number of square pairs that can be constructed from the elements in the array. For example, if the array is {11, 5, 4, 20} the function would return 3 because the only square pairs that can be constructed from those numbers are <5, 11>,
<5, 20> and <4, 5>. You may assume that there exists a function named isPerfectSquare that returns 1 if its argument is a perfect square and 0 otherwise. E.G., isPerfectSquare(4) returns 1 and isPerfectSquare(8) returns 0.
If you are programming in Java or C#, the function signature is
int countSquarePairs(int[ ] a)
If you are programming in C++ or C, the function signature is
int countSquarePairs(int a[ ], int len) where len is the number of elements in the array.
You may assume that there are no duplicate values in the array, i.e, you don’t have to deal with an array like {2, 7, 2, 2}.

2. 测试用例:

3. 程序代码：

public class SquarePairs {
    public static void main(String[] args) {

//        System.out.println(isPerfectSquare(8));
//        int a[] = {9,0,2,-5,7};
//        int a[] = {9};
        int a[] = {2, 7, 2, 2};
        System.out.println(countSquarePairs(a));
    }

    public static int countSquarePairs(int[ ] a){

        int length = a.length;
        if (length < 2){
            return 0;
        }
        int countsq=0;
        for (int i=0; i< length; i++){
            for (int j=0; j< length; j++){
                if (i!=j){
                    if(a[i]==a[j]){
                        return 0;
                    }
                    if((a[i] < a[j] && isPerfectSquare(a[i]+a[j]) ) && a[i]>0 && a[j]>0 ){
                        System.out.println("ai"+a[i]);
                        System.out.println("aj"+a[j]);
                         countsq++;

                    }
                }
            }
        }

        return countsq;
    }

    /**
     * 判断是不是能开平方根,是否为完全平方数
     * @param a
     * @return
     */
    public static boolean isPerfectSquare(int a){

       double k = Math.sqrt(a);
        int m = (int)k; //
        if( m - k == 0){
            return true;
        }

        return false;
    }
}