今天原來的同事，離職后面試了華為的java開發(fā)崗位脂凶，上來就是一道機試算法題宪睹。哥們拍了一下，發(fā)給了我蚕钦，我正好下午有空看了一下亭病，稍微整理記錄一下。
上機面試題.png
下面聊聊我的實現(xiàn)思路：
1.首先從1開始遍歷到10000嘶居，然后a從1取到10000罪帖，然后b也從a+1取到10000
2.aa+bb 得到一個平方數(shù)，然后開方，看拿到的數(shù)字c是不是整數(shù)整袁，是整數(shù)滿足條件菠齿，并且c必須在b到10000之間，需要同時滿足這兩個條件
3.拿到所有的勾股數(shù)坐昙，然后去掉里面的公約數(shù)
上代碼
定義一個實體類
/**
* @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<>();
/**
* 遍歷找出勾股數(shù)
*
* @param start
* @param end
* @return
* @throws Exception
*/
public Object search(int start, int end) throws Exception {
if (start < 1 || end > 10000) {
throw new Exception("輸入?yún)?shù)有誤");
}
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;
}
/**
* 取根號下的數(shù)
* 傳入 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);
}
/**
* 過濾出沒有公約數(shù)的勾股數(shù)
*
* @return
*/
public List<Number> handler() {
List<Number> resultList = new ArrayList<>();
for (Number number : LIST) {
if (!isHasGONGYUESHU(number)) {
resultList.add(number);
}
}
return resultList;
}
/**
* 處理公約數(shù)
*
* @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("消耗內(nèi)存：" + (orz / 1000) + "k");
}
測試結果：
3, 4, 5
5, 12, 13
8, 15, 17
消耗時間：66ms
消耗內(nèi)存：2726k
Process finished with exit code 0
思考：
當我嘗試將參數(shù)調(diào)到10000時绳匀，空間沒有超，但是時間超過了1秒炸客，針對這塊我也沒想出來好的優(yōu)化襟士。
或許我這塊原本的思路需要優(yōu)化一下，后面再研究一下吧嚷量，今天就到這陋桂。下班！蝶溶！
