今天原来的同事，离职后面试了华为的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秒，针对这块我也没想出来好的优化。
或许我这块原本的思路需要优化一下，后面再研究一下吧，今天就到这。下班！！
