---
# System prepended metadata

title: ALG101 筆記
tags: [題目, 程式導師]

---

# ALG101 筆記

###### tags: `程式導師` `題目`

## 寫在解題之前

面對同個題目，如果有不同的輸入範圍，就會需要不同的解法。
就像同樣是蓋房子，要蓋出 101 跟蓋出雙層公寓，需要的材料與建造方式就會不同。

而不同的範圍代表的是不同的限制：

- 空間限制
- 時間限制
- 型態限制

### 空間限制

如果程式有分變數型態的話，通常佔用的記憶體容量會像這樣：

- int：4 bytes
- double: 8 bytes
- JS 中的 Number：8 bytes（不分浮點數或整數）

### 時間限制

這部分跟時間複雜度相關，可看看[這個筆記](https://notcommon.coderbridge.io/2020/06/17/cook-algorithm-complexity/)

### 型態限制

- int: -2147483648 ~ 2147483647（也就是 $-2^{31}$ ～ $2^{31}-1$）
- 查看 JS Number 可儲存的最大整數：`Number.MAX_SAFE_INTEGER`
- 查看 JS Number 可儲存的最小整數：`Number.MIN_SAFE_INTEGER`
- 在 JS 檢查整數是否在可使用的安全範圍內：`.Number.isSafeInteger(<整數>)`
- 浮點數精準度問題，例如 `0.1 + 0.2 === 0.3  //false` 因為溢出問題。

**因此開始解題前，要記得問清楚題目範圍。**

pseudo code 大概長這樣

```javascript
for (i from 1 to 100) do
    if i < 100 then
        print i
        i = i + 1
    end if
end for      
```

## Unit 1

### 1.5 實戰練習：fizz buzz

老師的 pseudo code 寫錯了？只能列出 1~n 中 3、5、15 倍數的數。
但題目要的是 1 ~ n 都列出

```javascript
for (i from 1 to n) do
    if (i mod 5 === 0 && i mod 3 === 0) then
        print "FizzBuzz"
    else if (i mod 5 === 0) then
        print "Buzz"
    else if (i mod 3 === 0) then
        print "Fizz"
    else
        print i
    end if
end for
```

但這不是最好的解答，可以 Google 找一下


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

假設今天有一副撲克牌，一次只能抽一張起來看，你會怎麼找到最小的牌？


```javascript
let min = arr[0]
for (i from 0 to n-1) do
    if (arr[i]  < min) do
        min = arr[i]
    end if
end for

```

### 1.7 作業

#### 1. 字串反轉

給一個字串 str，請輸出 str 反過來的結果

範例輸入：hello

範例輸出：olleh

PS. 可以用 str[i] 取得第 i 個字，例如說 str="abc"，str[0] 就是 'a'

```javascript
let newStr = ""
for (i from 0 to -(str's length)) do
    put str[i] in newStr
end for


//檢討：想著反過來，連結字串，直接用 ＋ 的就可以

let s = ''
for (i from n-1 to 0) do
    s+= str[i]
end for
```


#### 2. 陣列總和

給一個陣列 arr，裡面全都包含了數字（整數），請輸出陣列加總的結果（總和保證不超過 int 範圍）

範例輸入：[1, 2, 3]

範例輸出：6

```javascript
let sum = 0

for (i from 0 to n-1) do
    sum = sum + arr[i]
end for

print sum
```

#### 3. 找最大值

給一個陣列 arr，裡面全都包含了數字（整數），請輸出陣列中的最大值

範例輸入：[1, 2, 3]

範例輸出：3

```javascript
let max = 0

for (i from 0 to n-1) do
    if (max < str[i]) then
        max = str[i]
    end if
end for

print max
```

## Unit 2

### 作業 1. 找次小值，用文字寫下步驟流程

```javascript
let arr = [10, 8, 6]                   
let min = Infinity
let min2 = Infinity
for(let i=0; i<arr.length; i++) {      
  if (arr[i] < min) {
    min2 = min
    min = arr[i]
  } else if (arr[i] < min2) {
    min2 = arr[i]
  }
}
console.log(min, min2)
```

1. i 是 0，arr[0] = 10，min 無限大，min2 無限大
2. 因為 10 小於無限大
3. min2 = min = 無限大
4. min = arr[0] = 10
5. i 小於陣列長度（3），進入 for 迴圈
6. i 是 1，arr[1] = 8，min=10、min2＝無限大
7. 因為 8 小於 10
8. 所以 min2=10、min=8
9. i 小於陣列長（3），進入 for 迴圈
10. i=2、arr[2]=6、min=8、min2=10
11. 因為 arr[2]=6 小於 min=8
12. 所以 min2=8、min=6

### 作業 2. 大小寫互換，用文字寫下步驟流程

```javascript
let str = "hELLo"
let ans = ''
for(let i=0; i<str.length; i++) {
  let code = str.charCodeAt(i)
  if (code >= 97 && code <= 122) {
    ans += String.fromCharCode(code - 32)
  } else if (code >= 65 && code <= 90) {
    ans += String.fromCharCode(code + 32)
  } else {
    ans += str[i]
  }
}
console.log(ans)
```

1. str 是要轉換的字串
2. ans 是要印出的字串
3. 用迴圈的方式遍歷整個字串，目前 i=0
4. 當 i < 字串長度，繼續下一步驟，否則跳到步驟 11
5. 找出 str[i] 代表的 ASCII code，設定為 code
6. 檢查 code 數字是否大於等於 97 或 小於等於 122？
7. 是的話，就將 code - 32，並轉回英文字母，放入 ans 字串內（大寫轉小寫），i 加 1，回到第 4 步驟
8. 不是的話，檢查 code 數字是否大於等於 65 或 小於等於 90？
9. 是的話，就將 code + 32，並轉回英文字母，放入 ans 字串內（小寫轉大寫），加 1，回到第 4 步驟 
10. 不是的話，就直接放入 ans 字串內，i 加 1，回到第 4 步驟
11. 印出 ans

### 作業 3. 印出因數

```javascript
let num = 30
for(let i=1; i<=num; i++) {
  if (num % i === 0) {
    console.log(i)
  }
}
```

1. 要檢查到 30
2. 用迴圈的方式從 1 檢查到 30，目前是 i 是 1
3. 當 i 小於等於 30，繼續下一步驟，否則結束迴圈
5. 如果 30 除以 i 的餘數是 0，就印出 i，i 加 1，回到第 3 步驟
6. 如果 30 除以 i 的餘數不是 0，i 加 1，回到第 3 步驟

## Unit 3

給三個題目，用白話文改寫

並且提出在解題中有可能碰到的問題或是需要特別注意的地方

1. [LIOJ 1010：靈魂伴侶](https://oj.lidemy.com/problem/1010?_ga=2.128507980.1723475375.1592060559-1459048255.1590328535)
是要判斷兩個數字是否相等，但題目已有限制兩數字的最大值與最小值，在 JS 安全範圍之內，因此沒有需要額外說明的數字範圍。
2. [LIOJ 1015：音速小子]()
是要把輸入值乘以 34，因為最大值在安全範圍內，所以沒有需要額外說明的數字範圍。
3. [LIOJ 1017：貪婪的小偷]()
從現有的物品中，從價值最高的開始挑，直到達到能帶走的最大數量，由於 (能帶走的最大值是 1000)*（物品的最大價值是 100000)，最大數字總和是 $10^8$ 在 JS 安全數字範圍內，所以沒有要額外說明的數字範圍。

---

**LidemyOJ JavaScript 讀取輸入列模板**

```javascript
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 就好，可以透過 lines[i] 拿取內容
function solve(lines) {

}
```

## Unit 5

### Unit 5-3

- 計算生命靈數的重點在於，需要一直重複執行「加總」，所以就專門寫一個 function 處理加總。
- 由於條件規定總和必須是一位數（也就是小於 10），如果不是一位數，就要進入加總 function 再處理。
- 由於不確定該加總多少次，所以不適用 if 條件式。要用 while，只要設定一個條件（沒小於 10），就進入加總。
- 值得注意的是，如何重複丟入加總後的數字？

```javascript=
var readline = require('readline');
const { count } = require('console');
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 就好，可以透過 lines[i] 拿取內容
function solve(lines) {
  var stringArr = lines[0].split(" ");  //["1991", "11", "7"]
  var numbers = Number(stringArr[0] + stringArr[1] + stringArr[2]);

  var spiritNumber = countSum(numbers);
  while (spiritNumber >= 10) {
    spiritNumber = countSum(spiritNumber);
  }
  console.log(spiritNumber);
}


//以這個純數字處理的寫法比較合理，適合處理 Number 型態的迴圈
const countSum = (number) => {
  var sum = 0;
  while (number % 10 != 0) {
    sum += number % 10;
    number = Math.floor(number / 10);
  }
  return sum;
}

//這是以字串迴圈的想法處理 Number 型態迴圈，雖然一樣可行，但處理數字的話，就用上面的方式
const countSum = (number) => {
  var sum = 0;
  var str = String(number);
  for (var i =0; i<str.length; i++) {
    sum += Number(str[i]);
  }
  return sum;
}
```

## Unit 6：實作內建函式

### `Array.map()`

傳入一個陣列後，`.map()` 會對陣列中每個元素統一執行特定動作，再以一個新陣列回傳結果。

```javascript
function double(n) {
return n*2;
}

let arr = [1, 2, 3]
let newArr = arr.map(double)

function map(arr, callback) {
    let result = []
    for(let i=0; i<arr.length; i++) {
    result[i] = callback(arr[i])
    }
    return result
}

console.log(map([1, 2, 3], double))
```

## `String.repeat()`

依據輸入的數字，作為重複字串的次數。

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

console.log(repeat('abc', 3))  //"abcabcabc"
```

## `Array.lastIndexOf()`

依據輸入的內容，在 array 中倒著找該內容的 index 位置。
功能跟 `.indexOf()` 相同，只是找的順序不同。

```javascript
function lastIndexOf(array, target) {
    for (var i=array.length-1; i>=0; i--) {
        if (array[i] === target) {
            return i;
        }
    }
    return -1;   // 這部分要特別注意，必須放在 for 迴圈之外，財表示整個迴圈都沒有，因此回傳 -1
}

console.log(lastIndexOf([2, 1, 2], 3))
```