勾股元数组

今天原来的同事，离职后面试了华为的java开发岗位，上来就是一道机试算法题。哥们拍了一下，发给了我，我正好下午有空看了一下，稍微整理记录一下。

上机面试题.png

下面聊聊我的实现思路：

1.首先从1开始遍历到10000，然后a从1取到10000，然后b也从a+1取到10000
2.aa+bb 得到一个平方数，然后开方，看拿到的数字c是不是整数，是整数满足条件，并且c必须在b到10000之间，需要同时满足这两个条件
3.拿到所有的勾股数，然后去掉里面的公约数

上代码

定义一个实体类

/**
 * @author: 
 * @date: 2022/3/1 15:05
 * @description:
 */
public class Number {
    private int a;

    private int b;

    private int c;

    public int getA() {
        return a;
    }

    public void setA(int a) {
        this.a = a;
    }

    public int getB() {
        return b;
    }

    public void setB(int b) {
        this.b = b;
    }

    public int getC() {
        return c;
    }

    public void setC(int c) {
        this.c = c;
    }

    @Override
    public String toString() {
        return  a + ", " + b + ", " + c ;
    }
}

然后开始写逻辑：

/**
 * @author:
 * @date: 2022/3/1 14:58
 * @description:
 */
public class Demo {

    /**
     * 定义一个基础对象
     */
    private static final List<Number> LIST = new ArrayList<>();

    /**
     * 遍历找出勾股数
     *
     * @param start
     * @param end
     * @return
     * @throws Exception
     */
    public Object search(int start, int end) throws Exception {
        if (start < 1 || end > 10000) {
            throw new Exception("输入参数有误");
        }
        int temp = 0;
        for (int i = start; i <= end; i++) {
            for (int j = i + 1; j <= end; j++) {
                temp = i * i + j * j;
                Double c = isRealNumber(temp);
                if ((c % 1) == 0 && c <= end) {
                    addToList(i, j, (int) Math.sqrt(temp));
                }
            }
        }
        return LIST;
    }

    /**
     * 取根号下的数
     * 传入 4  返回 2.0
     *
     * @param temp
     * @return
     */
    public Double isRealNumber(int temp) {
        return Math.sqrt(temp);
    }

    /**
     * 加入list
     *
     * @param a
     * @param b
     * @param c
     */
    public void addToList(int a, int b, int c) {
        Number number = new Number();
        number.setA(a);
        number.setB(b);
        number.setC(c);
        LIST.add(number);
    }

    /**
     * 过滤出没有公约数的勾股数
     *
     * @return
     */
    public List<Number> handler() {
        List<Number> resultList = new ArrayList<>();
        for (Number number : LIST) {
            if (!isHasGONGYUESHU(number)) {
                resultList.add(number);
            }
        }
        return resultList;
    }

    /**
     * 处理公约数
     *
     * @param number
     * @return
     */
    public boolean isHasGONGYUESHU(Number number) {
        double a = number.getA();
        double b = number.getB();
        double c = number.getC();
        double min = Math.min(Math.min(a, b), c);
        for (int i = 1; i <= min; i++) {
            if ((a % i) == 0 && (b % i) == 0 && (c % i) == 0) {
                if (i != 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

测试类：

public static void main(String[] args) throws Exception {
        Runtime r = Runtime.getRuntime();
        r.gc();
        long startMem = r.freeMemory();
        long startTime = System.currentTimeMillis();
        Demo demo = new Demo();
        demo.search(1, 20);
        List<Number> result = demo.handler();
        if (result.size() == 0) {
            System.out.println("NA");
        } else {
            result.forEach(System.out::println);
        }
        long lostTime = System.currentTimeMillis() - startTime;
        System.out.println("消耗时间：" + lostTime + "ms");
        long orz = startMem - r.freeMemory();
        System.out.println("消耗内存：" + (orz / 1000) + "k");
    }

测试结果：

3, 4, 5
5, 12, 13
8, 15, 17
消耗时间：66ms
消耗内存：2726k

Process finished with exit code 0

思考：

当我尝试将参数调到10000时，空间没有超，但是时间超过了1秒，针对这块我也没想出来好的优化。
或许我这块原本的思路需要优化一下，后面再研究一下吧，今天就到这。下班！！