前言
五月完成 Merge Two Sorted Lists 的文章後，想著這個月終於不是拖到月底才交稿真是太好了，原本想趁著這個氣勢在之後的每個月都能提前搞定，這樣一來我就可以再去挑戰其他事情了。
不過，事情沒這麼容易，現實總是出人意料的。五月底收到一個大改動的需求，到了現在六月底還有另一個重大的需求要應對。本來想說這個挑戰可能是要斷在六月了，但我恰好今天(週日) 2:00(AM) 就起來處理公司的開發任務，在告一段落後還有餘力，便趕緊來趕出這篇文章。
題目
給定一個二維陣列，要找出對角線裡面最大的質數，若沒有則回傳0
這個情況就是 1 5 9 3 5 7 裡面最大的質數 ⇒ 7
解題過程
我對這個敘述的想像大致上分為幾個步驟
- 從二維陣列裡找到對角線對應的元素
- 取得候選列表
- 從候選列表找到最大的質數
然而，我發現到二維陣列取對角線有個規律，就是最邊邊的一定是頭尾元素，然後往內一層的時候頭尾會往內縮一個，因此這個規則應該可以直接透過一層迴圈取得候選列表
再來，得到的候選列表需要去除重複的(避免浪費時間多跑判斷質數的邏輯)還有偶數(因為質數的因數只能有自己還有1，偶數的話就會多一個 2)，然後在大到小排序(依序找到質數後，直接就可以返回了，後面比較小的就不用跑到了)
最後，判斷質數的部分用根號的方式會比全部都跑還快一點(自然數 x 沒有 ≤ √x 的質因數的話，那 x 就是質數)
尋著這個思路就先把 Code 實作出來
function diagonalPrime(nums: number[][]): number {
let size = nums.length;
let list: number[] = [];
// 把對角線的數字加進來
for(let i = 0 ; i < size ; i++) {
list.push(nums[i][i]);
list.push(nums[i][size-1-i]);
}
// 移除重複、偶數、1
list = [...new Set(list)].filter(x => (x%2!==0 && x!==1));
// 大到小
list.sort((one, two) => (one > two ? -1 : 1));
let answer = 0;
const candidateSize = list.length;
for(let i = 0; i<candidateSize ; i++) {
// 計算因數
let count = 0;
// 開根號取整數
const limit = Math.floor(Math.sqrt(list[i]));
for(let j = 1 ; j <= limit ; i++) {
if(list[i] % j === 0) {
count+=1;
}
}
if(count === 2) {
answer = list[i];
break;
}
}
return answer;
};
// Time Limit Exceeded誒 Time Limit Exceeded !!!
見鬼了，為什麼，現在只執行到 3 x 3 的二維陣列而已誒… 怎麼可能
重新查看後，才發現 for(let j = 1 ; j ≤ limit ; i++)，這裡是要 j 啊不是 i
function diagonalPrime(nums: number[][]): number {
let size = nums.length;
let list: number[] = [];
// 把對角線的數字加進來
for(let i = 0 ; i < size ; i++) {
list.push(nums[i][i]);
list.push(nums[i][size-1-i]);
}
// 移除重複、偶數、1
list = [...new Set(list)].filter(x => (x%2!==0 && x!==1));
// 大到小
list.sort((one, two) => (one > two ? -1 : 1));
let answer = 0;
const candidateSize = list.length;
for(let i = 0; i<candidateSize ; i++) {
// 計算因數
let count = 0;
// 開根號取整數
const limit = Math.floor(Math.sqrt(list[i]));
for(let j = 1 ; j <= limit ; j++) {
if(list[i] % j === 0) {
count+=1;
}
}
if(count === 2) {
answer = list[i];
break;
}
}
return answer;
};
// input: [[1,2,3],[5,6,7],[9,10,11]]
// output: 9
// expect: 11
明明 9 不是質數啊…
後來我發現到如果使用根號的算法，則計算這個 count 的時候不是為 2 是質數，因為算到根號的情況等於只會跑一邊(以下方來說只跑到左半邊 1,2,3,4 )
ex: 24
1 | 24
2 | 12
3 | 8
4 | 6
這樣的話如果 count === 2 代表的是有兩組(4個因數)，那這樣不符合質數的定義
function diagonalPrime(nums: number[][]): number {
let size = nums.length;
let list: number[] = [];
// 把對角線的數字加進來
for(let i = 0 ; i < size ; i++) {
list.push(nums[i][i]);
list.push(nums[i][size-1-i]);
}
// 移除重複、偶數、1
list = [...new Set(list)].filter(x => (x%2!==0 && x!==1));
// 大到小
list.sort((one, two) => (one > two ? -1 : 1));
let answer = 0;
const candidateSize = list.length;
for(let i = 0; i<candidateSize ; i++) {
// 計算因數
let count = 0;
// 開根號取整數
const limit = Math.floor(Math.sqrt(list[i]));
for(let j = 1 ; j <= limit ; j++) {
if(list[i] % j === 0) {
count+=1;
}
}
if(count === 1) {
answer = list[i];
break;
}
}
return answer;
};
// input: [[2, 2], [2, 2]]
// output: 0看起來是過濾的時候就把 2給濾掉了，直接把這個最特別的數字給忘得一二凈了，再把 2的部分考量進去就大功告成了
function diagonalPrime(nums: number[][]): number {
let size = nums.length;
let list: number[] = [];
// 把對角線的數字加進來
for(let i = 0 ; i < size ; i++) {
list.push(nums[i][i]);
list.push(nums[i][size-1-i]);
}
// 移除重複、偶數、1
list = [...new Set(list)].filter(x => ((x%2!==0 || x === 2) && x!==1));
// 大到小
list.sort((one, two) => (one > two ? -1 : 1));
let answer = 0;
const candidateSize = list.length;
for(let i = 0; i<candidateSize ; i++) {
// 計算因數
let count = 0;
// 開根號取整數
const limit = Math.floor(Math.sqrt(list[i]));
for(let j = 1 ; j <= limit ; j++) {
if(list[i] % j === 0) {
count+=1;
}
}
if(count === 1) {
answer = list[i];
break;
}
}
return answer;
};完成~~~
果然如我的預期一樣順利
結果
心得
找質數、判斷質數這個課題，我記得是大學上資料結構演算法時的第一個作業，讓我感到有點懷念，這次找到這題是以幾個條件來找的
- 陣列
- Easy
- Acceptance 稍微低一點點的
- 看過題目後，能馬上理解問題
會用這些條件來找，主要是想找到不用花太多時間思考，但又希望多少能夠練習到的題目，畢竟工作的開發任務也是蠻重的，在刷題還有寫文章的這條路上，我還是希望能循序漸進，畢竟一開始目標太高，我應該很快就放棄了。
以今年來說，能夠每個月完成一題+一篇 Medium 文章對我來說就很開心了。截至目前為止，2024過了一半了，我的這項小目標也完成一半了，希望下半年也能夠順利達成。
