###### tags: `JavaScript` `leetcode`

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

> 本篇為 [[ALG101] 先別急著寫 leetcode](https://lidemy.com/p/alg101-leetcode) 這門課程的學習筆記。如有錯誤歡迎指正。
> [程式解題新手入門注意事項 - Huli](https://blog.huli.tw/2019/11/01/before-start-leetcode/)

---

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

- 初學者寫程式
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. 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. for (i from 1 to 100) do　//　for迴圈，有數字i會從 1到 100，do代表迴圈內動作
2. 	if i / 2 no remainder, print i
3. end for　//　此迴圈結束

若以 JavaScript 撰寫成程式碼：

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

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

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

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
Fizz
4
Buzz
Fizz
7

基本解法：

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 的倍數或更多，需要考慮的條件判斷也更複雜。

### 實戰練習：找最小值

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

解法（虛擬碼）：

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

將上述解法翻譯成陣列：

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 面試題)](https://medium.com/@Bear_/%E7%B0%A1%E5%96%AE%E7%9A%84-fizzbuzz-%E8%97%8F%E6%9C%89-%E6%B7%B1%E5%BA%A6-google-%E9%9D%A2%E8%A9%A6%E9%A1%8C-f5e66e3a97be)
[[課程學習筆記 ]先別急著寫 leetcode — 一步步打造程式腦](https://medium.com/@miahsuwork/%E8%AA%B2%E7%A8%8B%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98-%E5%85%88%E5%88%A5%E6%80%A5%E8%91%97%E5%AF%AB-leetcode-%E4%B8%80%E6%AD%A5%E6%AD%A5%E6%89%93%E9%80%A0%E7%A8%8B%E5%BC%8F%E8%85%A6-7ed12aaa4a3d)

---

## 學會像電腦一樣思考

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

### 以陣列加總的虛擬碼為例

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）轉成機械碼。

### 以找最大值為例

- 翻譯虛擬碼：

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）：

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`

<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>

3. 用 Chrome 開啟檔案，以開發者工具進行檢視，在 Sources 欄位點選 Step（F9），即可一步一步執行程式碼，進行除錯


## Log 大法

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

舉例：

<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 印出來的值和想像中不一樣？

舉例：

<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學除錯](https://www.ithome.com.tw/voice/106635)
2. [六角學院 — Chrome 網頁除錯功能大解密](https://www.udemy.com/course/chrome-devtools/)
3. [你需要注意的 console.log 問題](https://blog.huli.tw/2020/03/23/console-log-bug/)
4. [[Javascript] 關於 JS 中的淺拷貝和深拷貝](https://larry850806.github.io/2016/09/20/shallow-vs-deep-copy/)

---

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

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

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

### 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 位數字，在超過這個範圍的運算可能會有誤差，例如：

Number.MAX_SAFE_INTEGER + 2 > Number.MAX_SAFE_INTEGER + 1
// false
Number.MAX_SAFE_INTEGER + 2 === Number.MAX_SAFE_INTEGER + 1
// true

- 浮點數精準度問題：這和電腦底層儲存數字的方式有關，許多程式語言都會有這個現象

0.1 + 0.2 === 0.3
// false
// 0.1 + 0.2 會印出的值為 0.30000000000000004

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

---

## 解題技巧：函式填空法

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

### 判斷質數

以「[如何判斷質數](https://oj.lidemy.com/problem/1020)」為例：

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

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

// 第一部分：主要邏輯

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. 實作判斷質數邏輯

// 第二部分：輔助函式

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. 合併結果

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. 把函式拿掉，維持主要邏輯不便

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

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

// 雙層迴圈

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")
  }
}

## 解題技巧：簡化法

### 印出星星

以「[如何印出好多星星](https://oj.lidemy.com/problem/1021)」為例：

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

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

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

Step 2. 搭配函式填空法

for (let i=1; i<=N; i += 1) {
  printStar(i)
};

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

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

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

*

n = 2

 *
***

n = 3

  *
 ***
*****

根據觀察可知規律為：
1. 一共有 n 層
2. 第 i 層會有 2i -1 個星星
3. 星星會置中
4. 需要 n - i 個空白

接著利用函式填空法：

for (let i = 1; i <= n; i += 1) {
  printLayer(i, n)
}

function printLayer(i, n) {

}

加上一個輔助的函式：

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

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

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*1=1
1*2=2
...
1*9=9
2*1=2
...
9*9=81

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

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

包成函式，把 1 換成 k：

function printTable(k) {
  for (let i = 1; i <= 9; i += 1) {
    console.log(k + '*' + i + '=' + k*i )
  }
}

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

其實就是再一個迴圈：

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~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 來觀察雙層迴圈如何執行。也就是先執行外層迴圈第一圈，然後進入內層迴圈第一到九圈，執行完再回到外層迴圈第二圈，依序執行下去，用文字表示如下：

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

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

搭配函式填空法

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

function isSquare(n){

}

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

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

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

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 為止。

let i=1
while (i*i <= 100) {
  console.log(i*i)
  i += 1
}

### 作業檢討：印出聖誕樹

[LIOJ 1023：印出聖誕樹](https://oj.lidemy.com/problem/1023?_ga=2.105028611.1291128142.1593271357-1977277931.1590338596)

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 乘法表](https://oj.lidemy.com/problem/1024?_ga=2.109629445.1291128142.1593271357-1977277931.1590338596)

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：水仙花數](https://oj.lidemy.com/problem/1025?_ga=2.109629445.1291128142.1593271357-1977277931.1590338596)

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

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

解題難點：
1. 如何判斷幾位數
2. 如何取出各個數字

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

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

如何判斷幾位數：一直 `/ 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`

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);
    }
  }
}

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

例如：

'1234'.length => 4
'1234'.[0] => 1

// 實際操作
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]` 是否等於公差

// 判斷是否為等差數列
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. 只有一個元素的陣列

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
}

### 實戰：數字位數加總

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

解法一：數學解

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))

解法二：字串偷吃步

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：判斷等比數列](https://oj.lidemy.com/problem/1026)

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

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：信用卡號驗證](https://oj.lidemy.com/problem/1027)

### [LIOJ 1028：生命靈數](https://oj.lidemy.com/problem/1028)

// 與位數加總做法相同
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：加減乘除](https://oj.lidemy.com/problem/1029)

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：判斷迴文](https://oj.lidemy.com/problem/1030)

// 反過來輸出
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：完全平方和](https://oj.lidemy.com/problem/1031)

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

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

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

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：平面距離計算](https://oj.lidemy.com/problem/1032)

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：最近點對](https://oj.lidemy.com/problem/1033)

// 利用平面距離計算得到的函式
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：凱薩加密](https://oj.lidemy.com/problem/1034)

// 把字母右移 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：圈圈叉叉](https://oj.lidemy.com/problem/1035)

輸入範例：

XXO
OXX
XOO

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

input[0] = 'XXO'         // 即 (0, i)
input[0][0] = 'X'        // 即 (0, 0)

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：聯誼順序比大小](https://oj.lidemy.com/problem/1004)

// 判斷比大小
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](https://oj.lidemy.com/problem/1036)

// 反轉陣列
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])
  }
}

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

// 處理輸入
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](https://oj.lidemy.com/problem/1037)

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：

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](https://oj.lidemy.com/problem/1038?_ga=2.70826384.1291128142.1593271357-1977277931.1590338596)

// 讀取到一行，先把這一行加進去 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](https://oj.lidemy.com/problem/1039)

// 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](https://oj.lidemy.com/problem/1040)

// 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`，迴圈內就不用再進行判斷：

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](https://oj.lidemy.com/problem/1041)

### [LIOJ 1042：String toLowerCase](toLowerCasehttps://oj.lidemy.com/problem/1042)

// 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](https://oj.lidemy.com/problem/1043)

### [LIOJ 1044：String padEnd](https://oj.lidemy.com/problem/1044)

// 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](https://oj.lidemy.com/problem/1045)

// 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](https://www.youtube.com/watch?v=v7zv1ixaO3M) 解題方式

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

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)：

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) {
 
}

以[靈魂伴侶](https://oj.lidemy.com/problem/1010)為例：

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：用來檢查語法的工具](https://hackmd.io/m95fj9SsRLe1XDZEdsyBww)

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

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);
});