前端新米

Heidi's Blog

0%

[week 2] 先別急著寫 leetcode - 虛擬碼、Debugger、解題技巧

發表於 更新於 分類於
文章字數： 26k 所需閱讀時間 ≈ 23 分鐘
  • 本篇為 [ALG101] 先別急著寫 leetcode 這門課程的學習筆記。如有錯誤歡迎指正。
  • 參考文章：程式解題新手入門注意事項 - Huli

寫程式 ≠ 寫程式碼

重點是在寫程式之前，先想好要怎麼做，整理自己的想法，並轉換成程式碼表達。

  • 初學者寫程式 1.邊寫程式碼邊想怎麼解 2.試著套用自己以為學過的語法
  • 會寫程式的人寫程式 1.先想解法，在腦中構思（太快看不出來） 2.把解法轉換成程式碼

初期如何學習寫程式？

  • 步驟
  1. 大概想一下解法，不寫程式碼
  2. 把解法寫成 pseudo code（虛擬碼）
  3. 把 pseudo code 翻譯成程式碼
  • 利用條列式寫法
  1. 將大問題分割成小問題
  2. 一行只做一件事
  3. 善用敘述、條件判斷
  4. 善用跳轉（jump）來實現重複執行

範例：印出 1~100 之間的偶數

  • 步驟一：如何印出 1~100？
  1. 令 i 為 1 　//　設置初始條件
  2. 如果 i>100，結束　//　判斷是否該結束程式（終止條件）
  3. 印出 i
  4. i = i+1
  5. 跳回第 2 行　//　重複動作
  • 步驟二：如何判斷某個數是偶數？
  1. 令 i = 1
  2. 如果 i>100，結束
  3. 如果 i % 2 ===0，印出 i 　//　利用是否能整除 2 來判斷奇偶
  4. i = i+1
  5. 跳回第 2 行

如何撰寫 Pseudo Code（虛擬碼）？

虛擬碼是程式碼與想法之間的橋樑，把解法用抽象的方式表示。

將剛才步驟二得到的可執行步驟翻成英文，會發現和程式碼非常相似：

1
2
3
4
5
1. let i = 1
2. if i>100 then exit
3. if i % 2 no remainder, print  i
4. i = i+1
5. jump to line 2

更像程式碼的虛擬碼：

1
2
3
1. for (i from 1 to 100) do　//　for迴圈，有數字i會從 1到 100，do代表迴圈內動作
2. 	if i / 2 no remainder, print i
3. end for　//　此迴圈結束

若以 JavaScript 撰寫成程式碼：

1
2
3
4
5
for (var i = 1; i< 100; i++) {
　if(i % 2 === 0){
　console.log(i)
　}
}

實戰練習：印出 1-100 的奇數

利用「縮排」來標明條件判斷的區塊，較容易閱讀分析。

1
2
3
4
5
1. for (i from 1 to 100) do
2.　if (i mod 2 === 1) then　//　mod（modulo）：取餘數，餘數為 1 代表為奇數
3.　　print i
4.　end if
5. end for

實戰練習：fiszz buzz

題目：
給一個數字 n
印出 1~n
但如果碰到 3 的倍數，改印 Fizz
碰到 5 的倍數，，改印 Buzz
若同時是 3 跟 5 的倍數，印 FizzBuzz

範例：n=7

1
2
3
4
5
6
7
1
2
Fizz
4
Buzz
Fizz
7

基本解法：

1
2
3
4
5
for (i from 1 to n) do　　//　先寫出 1~n的迴圈
if　(i % 15 === 0) print “FizzBuzz”
else if (i % 3 === 0) print “Fizz”
else if (i % 5 === 0) print “Buzz”
end for

但此解並非最佳解法，若條件多 7 的倍數或更多，需要考慮的條件判斷也更複雜。

實戰練習：找最小值

題目：
假設今天有一副撲克牌
一次只能看一張牌
要怎麼找到最小的牌？

解法（虛擬碼）：

1
2
3
4
5
6
7
let 最小的牌 = 第一張牌
for (i from 1 to n) do　　　//　n為撲克牌總數
翻開第 i 張牌
if (第 i 張排比最小牌的還小) do
最小的牌 = 第 i 張牌
end if
end for

將上述解法翻譯成陣列：

1
2
3
4
5
6
let min = arr[0]　//　min是陣列中最小值，0代表array第一個元素
for (i from 0 to n-1) do　　//　n-1：因為array的 index（索引）所以從 0 開始
if (arr[i] < min) do　　//　如果第 i 個元素比最小值還小　
min = arr[i]　　//　i 就變成最小值
end if
end for

延伸閱讀：
簡單的 FizzBuzz 藏有 深度(google 面試題)
[課程學習筆記 ]先別急著寫 leetcode — 一步步打造程式腦

學會像電腦一樣思考

寫程式之前，先學會「看程式」，所謂的看程式碼 = 理解程式碼如何運作。

以陣列加總的虛擬碼為例

1
2
3
4
5
let sum = 0　　
for (i from 0 to n-1) do
    sum += arr[i]　　
end for
print sum
  • 看懂程式碼：
  1. 假設 array 為 [1, 2, 3]，代表陣列長度 n = 3
  2. 設 sum = 0
  3. 讓 i 從 0 跑到 n-1（也就是 2）
  4. i 現在是 0
  5. sum += arr[0]，sum 變成 1
  6. 下一個迴圈
  7. i 現在是 1
  8. sum += arr[1]，sum 變成 1+2 = 3
  9. 下一個迴圈
  10. i 現在是 2
  11. sum += arr[2]，sum 變成 3+3 = 6
  12. 下一個迴圈
  13. i 現在是 3，超出 n-1，結束
  14. 輸出 sum

人體編譯器

編譯（Compile）：將高階語言所編寫的原始程式，透過編譯器（Compiler）轉成機械碼。

以找最大值為例

  • 翻譯虛擬碼：
1
2
3
4
5
6
7
let max = arr[0]
for (i from 0 to n-1) do
    if (arr[i] > max) do
        max = arr[i]
    end if
end for
print max
  1. 假設 arr 為 [2, 7, 5]
  2. 設 max 為 arr[0]，也就是 2
  3. 讓 i 從 0 跑到 2
  4. i 現在是 0
  5. 判斷 arr[0] 是否 >2
  6. 不是
  7. 下一個迴圈
  8. i 現在是 1
  9. 判斷 arr[1] 是否 > 2
  10. 是，設 max = arr[2]，也就是 7
  11. 下一個迴圈
  12. i 現在是 2
  13. 判斷 arr[2] 是否 > 7
  14. 不是
  15. 下一個迴圈
  16. i 現在是 3，超出條件，結束
  17. 輸出 max

接著翻譯真的程式碼（JavaScript）：

1
2
3
4
5
6
7
8
let max = arr[0];
for (let i = 0; i < arr.length; i++) {
  //　i=0 為初始條件；終止條件；每圈執行完 i+=1
  if (arr[i] > max) {
    max = arr[i];
  }
}
console.log(max);
  1. 假設 arr 為 [2, 7, 5]
  2. 設 max 為 arr[0]，也就是 2
  3. 讓 i 從 0 跑到 2
  4. i 現在是 0
  5. 判斷 arr[0] 是否 >2
  6. 不是
  7. 下一個迴圈
  8. i 現在是 1
  9. 判斷 arr[1] 是否 > 2
  10. 是，設 max = arr[2]，也就是 7
  11. 下一個迴圈
  12. i 現在是 2
  13. 判斷 arr[2] 是否 > 7
  14. 不是
  15. 下一個迴圈
  16. i 現在是 3，超出條件，結束
  17. 輸出 max

重點：當不知道程式碼錯在哪時，可以一行一行檢視程式碼，驗證程式碼是否符合實際想表達的。

Debug 神器：Debugger（偵錯）

利用 Chrome Devtool（開發者工具）Debugger，直接設置中斷點（break point），一行一行執行程式碼以找出除錯範圍。

前置作業

  1. 將程式碼貼到一個 html 檔案
  2. 在 <script> 標籤（以執行 JavaScript）底下加上 debugger
1
2
3
4
5
6
7
8
9
10
11
<script>
debugger
let arr = [2, 7, 5];
let max = arr[0];
for (let i=0; i<arr.length; i++) {　
    if (arr[i] > max) {
      max = arr[i];
    }
}
console.log(max);
</script>
  1. 用 Chrome 開啟檔案，以開發者工具進行檢視，在 Sources 欄位點選 Step（F9），即可一步一步執行程式碼，進行除錯

Log 大法

另一個 debug 的方法，也就是「log 加好加滿」，透過 log 可以得知每個階段的值。

舉例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<script>
let arr = [2, 7, 5];
let max = arr[0];
console.log('max:', max)
for (let i=0; i<arr.length; i++) {　
    console.log('i=', i, 'arr[i]=', arr[i])
    if (arr[i] > max) {
    console.log('found new max!')
    console.log('arr[i]:', arr[i], 'old max:', max)
      max = arr[i];
    console.log('new max:', max)
    }
}
console.log(max);
</script>

檢視 console 欄位結果如下，可以檢視程式碼運作是否和所想的相同，是否有進入迴圈等等。

補充：為什麼用 console.log 印出來的值和想像中不一樣？

舉例：

1
2
3
4
5
6
7
8
9
10
11
<script>
let arr = [2, 7, 5];　　//　[2, 7 , 5]
let max = arr[0];
for (let i=0; i<arr.length; i++) {　
    if (arr[i] > max) {
      max = arr[i];
    }
}
arr.push(3);　　//　[2, 7 , 5, 3] 註解是 Chrome 認為的 log
console.log(max);
</script>

原因：

前後 arr 均為同一個變數，而 Chrome 會顯示該數最新儲存的值（抓取當下時間點的 log），而不是該 log 時間點的值。這個問題會出現在陣列和物件上。

解決方法：

利用 JSON.stringify() 將陣列或物件轉成「字串」印出，也就是深拷貝（Deep Copy）。

參考資料：

  1. 從 Debugger 學除錯
  2. 六角學院 — Chrome 網頁除錯功能大解密
  3. 你需要注意的 console.log 問題
  4. [Javascript] 關於 JS 中的淺拷貝和深拷貝

解題前需注意「輸入範圍」

在開始寫程式碼之前，必須注意輸入範圍，因為「不同範圍可能有不同限制」，而範圍會決定解題方法。比如說排列一百萬個數字跟排序十個數字，用的方法會不相同。

在不同限制中，需注意可能會遇到下列幾種狀況：

1. 空間限制

首先，對空間有個概念：

int: 4 bytes
double: bytes
JS 中的 Number: 8 bytes

由此可推算出，一百萬個數字所需記憶體：

(8 * 1e6 / 1024) = 7812 KB = 7.6 MB

那麼，十億個數字所需記憶體：

(8 * 1e8 / 1024) = 781200 KB = 7600 MB = 7.4 GB

由估算過程可知，我們不可能在程式語言中，宣告一個十億個元素儲存在陣列。
勢必得用其他方法，比如把排列好的數字先放在其他檔案等等。

2. 時間限制

對初學題目來說不太重要（先求有再求好），之後會再來談 big O，用來估算時間。

3. 型態限制

  • int：-214783648 ~ 2147483648
  • JS 數字： Number.MAX_SAFE_INTEGER：JavaScript 能儲存的最大值為 16 位數字，在超過這個範圍的運算可能會有誤差，例如：
1
2
3
4
Number.MAX_SAFE_INTEGER + 2 > Number.MAX_SAFE_INTEGER + 1
// false
Number.MAX_SAFE_INTEGER + 2 === Number.MAX_SAFE_INTEGER + 1
// true
  • 浮點數精準度問題：這和電腦底層儲存數字的方式有關，許多程式語言都會有這個現象
1
2
3
0.1 + 0.2 === 0.3
// false
// 0.1 + 0.2 會印出的值為 0.30000000000000004

把範圍講清楚的題目，才是好題目。
沒有的話就問清楚！因為範圍決定解決的方法。

解題技巧：函式填空法

目的：簡化雙層迴圈，也就是切割問題。

判斷質數

以「如何判斷質數」為例：

印出陣列中的質數 = 印出陣列 + 質數

Step 1. 簡化問題：不知道怎麼寫的部分，先寫成函式 isPrime

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 第一部分：主要邏輯

for (let i = 0; i < n; i++) {
  if (isPrime(arr[i])) {
    // 變成函式：如果 arr[i] 是質數
    console.log("Prime");
  } else {
    console.log("Composite");
  }
}

function isPrime(n) {
  // TO DO
}

Step 2. 實作判斷質數邏輯

1
2
3
4
5
6
7
8
9
10
11
// 第二部分：輔助函式

function isPrime(n) {
  if (n === 1) return false; // 1 不是函式，先去除
  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true; // 注意放在迴圈外，前面都不符合，才符合質數
}

Step 3. 合併結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function isPrime(n) {
  if (n === 1) return false;
  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

for (let i = 0; i < n; i++) {
  if (isPrime(arr[i])) {
    console.log("Prime");
  } else {
    console.log("Composite");
  }
}

試著把 function 加回去，程式碼會複雜很多：

Step 1. 把函式拿掉，維持主要邏輯不便

1
2
3
4
5
6
7
8
for (var i = 0; i < n; i++) {
  let isPrime = true;
  if (isPrime) {
    console.log("Prime");
  } else {
    console.log("Composite");
  }
}

Step 2. 加上判斷質數程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 雙層迴圈

for (var i=0; i<n; i++) {
  let isPrime = true
  if (arr[i] === 1) {
    isPrime = false
  }
  if (var j=2; j<arr[i]; j++) {         // 用 j 表示，是因為前面已出現變數 i
    if (arr[i] % j === 0) {
      is Prime = false
      break
    }
  }
  if (isPrime) {
    console.log("Prime")
  } else {
    console.log("Composite")
  }
}

解題技巧：簡化法

印出星星

以「如何印出好多星星」為例：

目的：把大問題變成小問題。如果難的寫不出來，就先寫簡單的。

Step 1. 不會輸出 n 個星星，就先輸出一個就好

1
2
3
4
for (let i = 1; i <= N; i += 1) {
  console.log("*");
}
// 印出每行都有 *

Step 2. 搭配函式填空法

1
2
3
4
5
6
7
for (let i = 1; i <= N; i += 1) {
  printStar(i);
}

function printStar(n) {
  // TODO: 印出 n 個星星
}

Step 3. 利用迴圈重複加上星星

1
2
3
4
5
6
7
8
9
10
11
for (let i = 1; i <= N; i += 1) {
  printStar(i);
}

function printStar(n) {
  let s = "";
  for (i = 1; i <= n; i += 1) {
    s += "*";
  }
  console.log(s);
}

也可直接利用 repeat 函式來解題：

實戰：印出金字塔

預期輸出：

n = 1

1
*

n = 2

1
2
 *
***

n = 3

1
2
3
  *
 ***
*****

根據觀察可知規律為：

  1. 一共有 n 層
  2. 第 i 層會有 2i -1 個星星
  3. 星星會置中
  4. 需要 n - i 個空白

接著利用函式填空法：

1
2
3
4
5
for (let i = 1; i <= n; i += 1) {
  printLayer(i, n);
}

function printLayer(i, n) {}

加上一個輔助的函式：

1
2
3
4
5
6
7
function repeat(str, n) {
  let s = "";
  for (let i = 1; i <= n; i += 1) {
    s += str;
  }
  return s;
}

再按照規律把答案填上去：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (let i = 1; i <= n; i += 1) {
  printLayer(i, n);
}

function printLayer(i, n) {
  // 空白 + 星星
  let str = repeat(" ", n - i) + repeat("*", 2 * i - 1);
  console.log(str);
}

function repeat(str, n) {
  let s = "";
  for (let i = 1; i <= n; i += 1) {
    s += str;
  }
  return s;
}

實戰：九九乘法表

預期輸出：

1
2
3
4
5
6
7
1*1=1
1*2=2
...
1*9=9
2*1=2
...
9*9=81

首先用簡化法，產生 1*1 ~ 1*9：

1
2
3
for (let i = 1; i <= 9; i += 1) {
  console.log('1*' + i '=' + 1*i )
}

包成函式，把 1 換成 k：

1
2
3
4
5
6
7
8
9
10
11
function printTable(k) {
  for (let i = 1; i <= 9; i += 1) {
    console.log(k + '*' + i + '=' + k*i )
  }
}

printTable(1)
printTable(2)
...
printTable(9)
// 即可產生九九乘法表

其實就是再一個迴圈：

1
2
3
4
5
6
7
8
9
10
11
function printTable(k) {
  for (let i = 1; i <= 9; i += 1) {
    console.log(k + "*" + i + "=" + k * i);
  }
}

// 這個會產生 1~9
for (let k = 1; k <= 9; k += 1) {
  printTable(k);
}
// 結果：產生 1*1~9*9

但總有一天要學會雙層迴圈，試著把上面的寫法合併：

1
2
3
4
5
6
7
// 這個產生 1~9
for (let k = 1; k <= 9; k += 1) {
  // 這個也產生 1~9
  for (let i = 1; i <= 9; i += 1) {
    console.log(k + "*" + i + "=" + k * i);
  }
}

我們可以利用 Debugger 來觀察雙層迴圈如何執行。也就是先執行外層迴圈第一圈，然後進入內層迴圈第一到九圈，執行完再回到外層迴圈第二圈，依序執行下去，用文字表示如下：

1
2
3
4
5
k=1 i=1, 2, 3...9
k=2 i=1, 2, 3...9
k=3 i=1, 2, 3...9
...
k=9 i=1, 2, 3...9

實戰：印出 1~100 平方數

簡化法：先印出 1~100

1
2
3
for (let i = 1; i <= 100; i += 1) {
  console.log(i);
}

搭配函式填空法

1
2
3
4
5
6
7
for (let i = 1; i <= 100; i += 1) {
  if (isSquare) {
    console.log(i);
  }
}

function isSquare(n) {}

那麼，該如何判斷平方數呢？

開根號：Math.sqrt(n)
無條件捨去：Math.floor(n)

將 n 開根號後得到的數字，無條件捨去後再相乘，若還是等於 n 則為平方數。

1
2
3
4
5
6
7
8
9
10
for (let i = 1; i <= 100; i += 1) {
  if (isSquare) {
    console.log(i);
  }
}

function isSquare(n) {
  let root = Math.floor(Math.sqrt(n));
  return root * root === n; // 成立得到 true；反之得到 false
}

另一種想法：印出平方數，直到超過 100 為止。

1
2
3
4
5
let i = 1;
while (i * i <= 100) {
  console.log(i * i);
  i += 1;
}

作業檢討：印出聖誕樹

LIOJ 1023：印出聖誕樹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
});

const lines = [];

// 讀取到一行，先把這一行加進去 lines 陣列，最後再一起處理
rl.on("line", (line) => {
  lines.push(line);
});

function isPrime(n) {
  if (n === 1) {
    return false;
  }
  for (let i = 2; i < n; i += 1) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

// 前面已宣告過 lines，這裡改用 input 作為參數，拿取內容 lines
function solve(input) {
  let n = Number(input[0]);
  for (let i = 1; i <= n; i += 1) {
    printTree(i, n);
  }
  for (let i = 1; i <= n - 1; i += 1) {
    printBottom(n);
  }
}

function printTree(i, n) {
  console.log(repeat(" ", n - i) + repeat("*", 2 * i - 1));
}

function printBottom(n) {
  console.log(repeat(" ", n - 1) + "|");
}

function repeat(str, n) {
  let result = "";
  for (let i = 1; i <= n; i += 1) {
    result += str;
  }
  return result;
}

// 輸入結束，開始針對 lines 做處理
rl.on("close", () => {
  solve(lines);
});

作業檢討：NN 乘法表

LIOJ 1024：NN 乘法表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
});

const lines = [];

// 讀取到一行，先把這一行加進去 lines 陣列，最後再一起處理
rl.on("line", (line) => {
  lines.push(line);
});

// 前面已宣告過 lines，這裡改用 input 作為參數，拿取內容 lines
function solve(input) {
  let N = Number(input[0]);
  let M = Number(input[1]);
  // 產生 1~N
  for (let k = 1; k <= N; k += 1) {
    // 產生 1~M
    for (let i = 1; i <= M; i += 1) {
      console.log(k + "*" + i + "=" + k * i);
      // 也可寫成 console.log(`${k}*${i}=${k*i}`)
    }
  }
}

// 輸入結束，開始針對 lines 做處理
rl.on("close", () => {
  solve(lines);
});

作業檢討：水仙花數

LIOJ 1025：水仙花數

水仙花數（Narcissistic number）定義為：「一個 n 位數的數字，每一個數字的 n 次方加總等於自身」。

例如說 153 是三位數，而 1^3 + 5^3 + 3^3 = 153。
而數字 0~9 也都是水仙花數，因為一位數 n 的 1 次方一定會等於自己。

解題難點：

  1. 如何判斷幾位數
  2. 如何取出各個數字

可直接判斷該數字是幾位數，但這個方法侷限於「需已知輸入範圍」，也就是必須知道有幾位數：

1
2
3
4
5
6
7
8
9
10
// 回傳數字幾位數
function digitsCount(n) {
  if (n < 10) {
    return 1
  } else if (n < 1e2) {         // 1e2 代表 100 科學記號寫法
    return 2
  } else if (n < 1e3) {
    return 3
  } ...
}

如何判斷幾位數：一直 / 10

1
2
3
4
5
6
7
8
9
10
// 回傳數字幾位數
function digitsCount(n) {
  if (n === 0) return 1;
  let result = 0;
  while (n != 0) {
    n = Math.floor(n / 10); // 無條件捨去
    result += 1;
  }
  return result;
}

取出各個數字：% 10 搭配 / 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function isNarcissistic(n) {
  // 幾位數，宣告一個 m = n
  let m = n
  let digits = digitsCount(m)
  let sum = 0

  while (m != 0) {
    let num = m % 10
    // 可改成 Math.pow(num, digits) => num 的 digits 次方
    sum += num**digits
    m = Math.floor(m / 10)
  }

  // 可簡化成：return sum === n
  if (sum === n) {
    return true
  } else if {
    return false
  }
}

// 應用上方兩個函式即可完成輸出
function solve(input) {
  // 輸入 5 200 => ['5', '200']
  const temp = input[0].split(' ');
  let n = Number(temp[0]);
  let m = Number(temp[1]);
  for (let i = n; i <= m; i += 1) {
    if (isNarcissistic(i)) {
      console.log(i);
    }
  }
}

也可以把「數字轉成字串」，直接用字串來判斷幾位數：

例如：

1
2
'1234'.length => 4
'1234'.[0] => 1
1
2
3
4
5
6
7
8
9
10
11
12
// 實際操作
function isNstr(n) {
  // 數字 + 空字串 => 字串
  // 或是 n.toString()、String(n)
  let str = n + ''
  let digits = str.length
  let sum = 0
  for (let i = 0; i < str.length;; i+= 1) {
    sum += Number(str[i])**digits
  }
  return sum === n
}

實戰：判斷等差數列

判斷 [1, 3, 5, 7, 9] 是否為等差數列

解題技巧：

  1. 先求公差：arr[1] - arr[0]
  2. 再判斷 arr[i] - arr[i-1] 是否等於公差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 判斷是否為等差數列
function isValid(arr) {
  let d = arr[1] - arr[0];
  for (let i = 1; i < arr.length; i += 1) {
    if (arr[i] - arr[i - 1] !== d) {
      return false;
    }
  }
  return true;
}

console.log(isValid([1, 3, 5, 7, 9])); // true
console.log(isValid([1, 1, 1])); // true
console.log(isValid([1, 2, 4])); // false

解題時需考慮到 Edge case（邊緣條件）：

  1. 空陣列
  2. 只有一個元素的陣列
1
2
3
4
5
6
7
8
9
10
11
function isValid(arr) {
  // 涵蓋邊界條件，可避免不合法的存取
  if (arr.length <= 1) return true
  let d = arr[1] - arr[0]
  for (let i = 1; i < arr.length; i += 1) {
    if (arr[i] - arr[i-1] !== d) {
      return false
    }
  }
  return true
}

實戰：數字位數加總

與「判斷水仙花數」題型類似。

解法一：數學解

1
2
3
4
5
6
7
8
9
10
11
12
13
function addDigits(n) {
  // 若 n 為負數，乘上 -1 變成正數
  if (n < 0) {
    n = n * -1;
  }
  let sum = 0;
  while (n != 0) {
    sum += n % 10;
    n = Math.floor(n / 10);
  }
  return sum;
}
console.log(addDigits(123));

解法二：字串偷吃步

1
2
3
4
5
6
7
8
9
function addDigits(n) {
  let str = n + "";
  let sum = 0;
  for (let i = 0; i < str.length; i += 1) {
    sum += Number(str[i]);
  }
  return sum;
}
console.log(addDigits(123));

經典題型

LIOJ 1026：判斷等比數列

基本上和判斷等差數列作法類似：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
});

const lines = [];

// 讀取到一行，先把這一行加進去 lines 陣列，最後再一起處理
rl.on("line", (line) => {
  lines.push(line);
});

// 判斷等比數列
function inValid(arr) {
  let r = arr[1] / arr[0];
  for (let i = 1; i < arr.length; i += 1) {
    if (arr[i] / arr[i - 1] !== r) {
      return false;
    }
  }
  return true;
}

// 前面已宣告過 lines，這裡改用 input 作為參數，拿取內容 lines
function solve(input) {
  let n = Number(input[0]);
  let arr = input[1].split(" "); // ['3', '9', '27'] => 得到字串的陣列
  if (inValid(arr)) {
    console.log("Yes");
  } else {
    console.log("No");
  }
}

// 輸入結束，開始針對 lines 做處理
rl.on("close", () => {
  solve(lines);
});

LIOJ 1027：信用卡號驗證

LIOJ 1028：生命靈數

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 與位數加總做法相同
function addDigits(n) {
  let sum = 0;
  while (n != 0) {
    sum += n % 10;
    n = Math.floor(n / 10);
  }
  return sum;
}

function solve(input) {
  // ['1991 11 7'] = > ['1991', '11', '7']
  let temp = input[0].split(" ");
  // 1991117
  let num = Number(temp[0] + temp[1] + temp[2]);
  let p = addDigits(num);
  // 判斷是否不只一位
  while (p >= 10) {
    p = addDigits(p);
  }
  console.log(p);
}

LIOJ 1029：加減乘除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function solve(input) {
  let temp = input[0].split(" "); // => ['3', '*', '4']
  let a = Number(temp[0]);
  let b = Number(temp[2]);

  if (temp[1] === "+") {
    console.log(a + b);
  } else if (temp[1] === "-") {
    console.log(a - b);
  } else if (temp[1] === "*") {
    console.log(a * b);
  } else {
    // 不是加減乘，就是除
    console.log(a / b);
  }
}

LIOJ 1030：判斷迴文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 反過來輸出
function reverse(str) {
  let result = "";
  for (let i = str.length - 1; i >= 0; i -= 1) {
    result += str[i];
  }
  return result;
}

// 前面已宣告過 lines，這裡改用 input 作為參數，拿取內容 lines
function solve(input) {
  const str = input[0];
  if (reverse(str) === str) {
    console.log("True");
  } else {
    console.log("False");
  }
}

LIOJ 1031：完全平方和

解一：找出比 N 小的完全平方數

1
2
3
4
5
6
7
8
9
10
function square(n) {
  let result = 0;
  for (let i = 1; i * i <= n; i += 1) {
    result += i * i;
  }
  return result;
}

console.log(square(30));
// 印出 55，也就是 1+4+9+16+25 = 55

解二：判斷是否為完全平方數

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function isSquare(n) {
  let r = Math.floor(Math.sqrt(n));
  return r * r === n;
}

// 前面已宣告過 lines，這裡改用 input 作為參數，拿取內容 lines
function solve(input) {
  const n = Number(input[0]);
  let sum = 0;
  for (let i = 1; i <= n; i += 1) {
    if (isSquare(i)) {
      sum += i;
    }
  }
  console.log(sum);
}

LIOJ 1032：平面距離計算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function distance(x1, y1, x2, y2) {
  let dis = Math.sqrt(
    abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2)
  );
  return dis.toFixed(2); // 取到小數點第二位
}

// 回傳絕對值
function abs(n) {
  if (n < 0) {
    return -n;
  }
  return n;
}

function solve(input) {
  let t = Number(input[0]);
  for (let i = 1; i <= t; i += 1) {
    let start = (i - 1) * 4 + 1;
    let x1 = Number(input[start]);
    let y1 = Number(input[start + 1]);
    let x2 = Number(input[start + 2]);
    let y2 = Number(input[start + 3]);
    console.log(distance(x1, y1, x2, y2));
  }
}

LIOJ 1033：最近點對

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// 利用平面距離計算得到的函式
function distance(x1, y1, x2, y2) {
  let dis = Math.sqrt(
    abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2)
  );
  return dis; // 取到小數點第二位
}

function abs(n) {
  if (n < 0) {
    return -n;
  }
  return n;
}

function solve(input) {
  let n = Number(input[0]);
  let dots = [];
  for (let i = 1; i < input.length; i += 1) {
    let temp = input[i].split(" ");
    dots.push({
      x: Number(temp[0]),
      y: Number(temp[1]),
    });
  }

  let min = Infinity; // 最短距離先設一個最大值
  let ans = null;
  for (let i = 0; i < dots.length; i += 1) {
    for (let j = i + 1; j < dots.length; j += 1) {
      let dis = distance(dots[i].x, dots[i].y, dots[j].x, dots[j].y);
      if (dis < min) {
        min = dis;
        ans = {
          x1: dots[i].x,
          y1: dots[i].y,
          x2: dots[j].x,
          y2: dots[j].y,
        };
      }
    }
  }

  if (ans.x1 > ans.x2) {
    console.log(ans.x2 + " " + ans.y2);
    console.log(ans.x1 + " " + ans.y1);
  } else if (ans.x1 < ans.x2) {
    console.log(ans.x1 + " " + ans.y1);
    console.log(ans.x2 + " " + ans.y2);
  } else {
    if (ans.y1 > ans.y2) {
      console.log(ans.x2 + " " + ans.y2);
      console.log(ans.x1 + " " + ans.y1);
    } else {
      console.log(ans.x1 + " " + ans.y1);
      console.log(ans.x2 + " " + ans.y2);
    }
  }
}

LIOJ 1034：凱薩加密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 把字母右移 n 位
function ceaserCipher(n, s) {
  // 'a'.charCodeAt(0) = 97
  // 減去 97，可得到數字 0 ~ 25
  let code = s.charCodeAt() - 97;
  // 英文字母有 26 個，當數字超過時，對編碼除 26 取餘數
  let newCode = (code + n) % 26;
  // 取得真正的編碼
  return String.fromCharCode(newCode + 97);
}

function solve(input) {
  let n = Number(input[0]);
  let str = input[1];
  let result = "";
  for (let i = 0; i < str.length; i += 1) {
    result += ceaserCipher(n, str[i]);
  }
  console.log(result);
}

LIOJ 1046：圈圈叉叉

輸入範例：

1
2
3
XXO
OXX
XOO

利用二維陣列的概念，可知：

1
2
input[0] = "XXO"; // 即 (0, i)
input[0][0] = "X"; // 即 (0, 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function whoWin(input) {
  // 判斷橫的三排
  for (let i = 0; i < 3; i += 1) {
    if (input[i][0] === input[i][1] && input[i][1] === input[i][2]) {
      return input[i][0];
    }
  }
  // 判斷直的三排
  for (let i = 0; i < 3; i += 1) {
    if (input[0][i] === input[1][i] && input[1][i] === input[2][i]) {
      return input[0][i];
    }
  }
  // 判斷斜對角
  if (input[0][0] === input[1][1] && input[1][1] === input[2][2]) {
    return input[0][0];
  }
  if (input[0][2] === input[1][1] && input[1][1] === input[2][0]) {
    return input[1][1];
  }

  return "DRAW";
}

作業 - LIOJ 1004：聯誼順序比大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 判斷比大小
function compare(a, b, k) {
  if (a === b) {
    return "DRAW";
  }

  // 若比小，就將 a b 互換，注意 k 是字串不能用 ===
  if (k == -1) {
    const temp = a;
    a = b;
    b = temp;
  }

  // 判斷字串長度是否相同
  // 不同：比較字串長度
  if (a.length > b.length) {
    return "A";
  }
  if (a.length < b.length) {
    return "B";
  }

  // 相同：從字串最左邊開始比大小
  if (a.length === b.length) {
    for (let j = 0; j < a.length; j += 1) {
      // 若相等，就繼續迴圈比下一位
      if (a[j] === b[j]) {
        continue;
      }
      if (a[j] > b[j]) {
        return "A";
      } else {
        return "B";
      }
    }
  }
}

function solve(input) {
  const n = Number(input[0]);

  // 長度為 512 個位數以內，不可轉成數字比大小
  for (let i = 1; i <= n; i += 1) {
    // 輸出會是陣列 => [1, 2, 1]
    let [a, b, k] = input[i].split(" ");
    console.log(compare(a, b, k));
  }
}

練習實作內建函式

LIOJ 1036：Array reverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 反轉陣列
function reverse(arr) {
  let result = [];
  for (let i = arr.length - 1; i >= 0; i -= 1) {
    result.push(arr[i]); // 反轉 => [3, 2, 1]
  }
  return result;
}

// 處理輸入
function solve(input) {
  let numbers = [];
  for (let i = 1; i < input.length; i += 1) {
    numbers.push(input[i]); // [1, 2, 3]
  }
  // 傳進 reverse 函式，並印出結果
  let arr = reverse(numbers);
  for (let i = 0; i < arr.length; i += 1) {
    console.log(arr[i]);
  }
}

也可以直接在處理輸入後，直接輸出翻轉後的結果：

1
2
3
4
5
6
7
8
9
10
11
// 處理輸入
function solve(input) {
  let numbers = [];
  for (let i = 1; i < input.length; i += 1) {
    numbers.push(input[i]); // [1, 2, 3]
  }

  for (let i = numbers.length - 1; i >= 0; i -= 1) {
    console.log(numbers[i]);
  }
}

LIOJ 1037：Array filter

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function filter(arr) {
  let result = [];
  for (let i = 2; i < arr.length; i += 1) {
    // 跳過不符合的數字
    if (arr[i] == arr[0]) {
      continue;
    }
    result.push(arr[i]);
  }
  return result;
}

// 處理輸入
function solve(input) {
  let numbers = [];
  for (let i = 0; i < input.length; i += 1) {
    numbers.push(input[i]); // [3, 5, 1, 3 , 3, 2, 8]
  }
  // 傳進 filter 函式，並印出結果
  let arr = filter(numbers);
  for (let i = 0; i < arr.length; i += 1) {
    console.log(arr[i]);
  }
}

或利用回傳函式 callback 來過濾 target：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function filter(arr, callback) {
  let result = [];
  for (let i = 0; i < arr.length; i += 1) {
    // 跳過不符合的數字
    if (callback(arr[i]) === true) {
      result.push(arr[i]);
    }
  }
  return result;
}

// 處理輸入
function solve(input) {
  // 排除目標
  let target = Number(input[0]);
  let arr = [];
  for (let i = 2; i < input.length; i += 1) {
    arr.push(Number(input[i])); // [1, 3 , 3, 2, 8]
  }
  // 傳進 filter 函式，留下不等於 target 的值
  // 也可寫成 filter(arr, element => element !== target)
  let newArr = filter(arr, function (element) {
    return element !== target;
  });
  for (let i = 0; i < newArr.length; i += 1) {
    console.log(newArr[i]);
  }
}

LIOJ 1038：Array indexOf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 讀取到一行，先把這一行加進去 lines 陣列，最後再一起處理
rl.on("line", (line) => {
  lines.push(line);
});

// LIOJ 1038：Array indexOf
function indexOf(arr, searchElement) {
  for (let i = 0; i < arr.length; i += 1) {
    if (arr[i] === searchElement) {
      return i;
    }
  }
  return -1;
}

// 處理輸入
function solve(input) {
  // 目標數字
  let target = Number(input[0]);
  // 要檢查的數字
  let arr = [];
  for (let i = 2; i < input.length; i += 1) {
    arr.push(Number(input[i])); // => [1, 2, 3, 3, 3]
  }
  console.log(indexOf(arr, target));
}

LIOJ 1039：Array fill

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// LIOJ 1039：Array fill
function fill(arr, value) {
  let result = [];
  for (let i = 0; i < arr.length; i += 1) {
    // 陣列每個元素會被取代成 value，也可寫成 result[i] = value
    result.push(value);
  }
  return result;
}

// 處理輸入
function solve(input) {
  let target = Number(input[0]);
  let arr = [];
  for (let i = 2; i < input.length; i += 1) {
    arr.push(Number(input[i])); // => [1, 2, 3]
  }
  let newArr = fill(arr, target);
  for (let i = 0; i < newArr.length; i += 1) {
    console.log(newArr[i]);
  }
}

LIOJ 1040：Array join

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// LIOJ 1040：Array join
function join(arr, separator) {
  let result = "";
  for (let i = 0; i < arr.length; i += 1) {
    result += arr[i];
    if (i < arr.length - 1) {
      result += separator;
    }
  }
  return result;
}

// 處理輸入
function solve(input) {
  const str = input[0];
  let arr = [];
  for (let i = 2; i < input.length; i += 1) {
    arr.push(input[i]); // [1, 2, 3]
  }
  console.log(join(arr, str));
}

或是把字串 1!2 3 看成 1 !2!3，迴圈內就不用再進行判斷：

1
2
3
4
5
6
7
function join(arr, separator) {
  let result = arr[0];
  for (let i = 1; i < arr.length; i += 1) {
    result += separator + arr[i];
  }
  return result;
}

LIOJ 1041：String trim

1

LIOJ 1042：String toLowerCase

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// LIOJ 1042：String toLowerCase
function toLowerCase(str) {
  let result = "";
  for (let i = 0; i < str.length; i += 1) {
    if (str[i] >= "A" && str[i] <= "Z") {
      let code = str.charCodeAt(i);
      result += String.fromCharCode(code + 32);
    } else {
      result += str[i]; // 若不是大寫就直接加到字串
    }
  }
  return result;
}

// 處理輸入
function solve(input) {
  console.log(toLowerCase(input[0]));
}

LIOJ 1043：String endsWith

1

LIOJ 1044：String padEnd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// LIOJ 1044：String padEnd
function padEnd(str, targetLength, padString) {
  if (str.lenght >= targetLength) {
    return str;
  }
  // 從 'S 字串長度 + 1' 開始填充，直到預期字串長度
  while (str.length < targetLength) {
    for (let i = 0; i < padString.length; i += 1) {
      str += padString[i];
      // 若 S 達到預期字串長度，則結束迴圈
      if (str.length === targetLength) {
        return str;
      }
    }
  }
}

// 處理輸入
function solve(input) {
  let S = input[0];
  let target = Number(input[1]); // 預期字串的最後長度
  let padString = input[2]; // 要填充的字串
  console.log(padEnd(S, target, padString));
}

LIOJ 1045：String slice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// LIOJ 1045：String slice
function slice(str, beginIndex, endIndex) {
  let result = "";
  for (let i = beginIndex; i < endIndex; i += 1) {
    result += str[i];
  }
  return result;
}

// 處理輸入
function solve(input) {
  let str = input[0];
  let start = Number(input[1]);
  let end = Number(input[2]);
  console.log(slice(str, start, end));
}

補充：Lidemy OJ 解題方式

有三種方式可以驗證輸出：

  1. 直接在 Command Line 介面直接執行 node index.js，即可直接輸入數字，按 ctrl+D 輸出結果（Windows 無法執行）
  2. 直接在 index.js 呼叫 function
  3. 新增檔案來放輸入，利用指令來產生輸出：cat input.txt | node index.js
    補充：Windows 需改成 cat input.txt | env node code.js 或是 cat input.txt | command node code.js

固定輸入程式碼如下，答題時只需更改 function solve(lines)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var readline = require("readline");
var rl = readline.createInterface({
  input: process.stdin,
});

var lines = [];

// 讀取到一行，先把這一行加進去 lines 陣列，最後再一起處理
rl.on("line", function (line) {
  lines.push(line);
});

// 輸入結束，開始針對 lines 做處理
rl.on("close", function () {
  solve(lines);
});

// 拿到所有資料
function solve(lines) {}

以靈魂伴侶為例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var readline = require('readline');
var rl = readline.createInterface({
    input: process.stdin
});

var lines = []

// 讀取到一行，先把這一行加進去 lines 陣列，最後再一起處理
rl.on('line', function (line) {
    lines.push(line)
});

// 輸入結束，開始針對 lines 做處理
rl.on('close', function () {
    solve(lines)
})

function solve(lines) {
    var arr = lines[0].split(' ')        // 注意需要取陣列！
    var a = Number(arr[0])
    var b = Number(arr[1])
    if (a === b) {
        console.log('Yes')
    } else {
        console.log('No')
    }
}

solve([                           // 輸入是陣列，可用函式驗證是否正確
    '15 15'
])

補充：使用 eslint 檢查語法

相關筆記：[week3] 設定 eslint：用來檢查語法的工具

需注意宣告方式、縮排問題、結尾加分號等問題，修改後模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
});

const lines = [];

// 讀取到一行，先把這一行加進去 lines 陣列，最後再一起處理
rl.on('line', (line) => {
  lines.push(line);
});

// 前面已宣告過 lines，這裡改用 input 作為參數，拿取內容 lines
function solve(input) {
  "在這裡輸入函式內容"
}

// 輸入結束，開始針對 lines 做處理
rl.on('close', () => {
  solve(lines);
});