# 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))
```
Sign in with Wallet
Connect another wallet