試著寫出一行行的可執行步驟
- 一行只做一件事
- 善用跳轉 (jump)
1. 早上八點起床
2. 吃早餐
---- 條件判斷
3. 如果公車來了，搭公車
4. 如果公車沒來，搭捷運
---- 條件判斷
5. 到學校上課
6. 放學
7. 吃晚餐
8. 睡覺
---- 重複
9. 回到步驟 1
如何印出 1 ~ 100 ?
如何判斷某個數是偶數 ?1. 令 i = 1
2. 如 i > 100，結束
3. 如果 i % 2 === 0，印出 i
4. i = i + 1
5. 跳至第 2 步
如何撰寫 pseudo code ?
1. 令 i = 1
2. 如 i > 100，結束
3. 如果 i % 2 === 0，印出 i
4. i = i + 1
5. 跳至第 2 步
-------
pseudo code
1. let i = 1
2. if i > 100 then exit
3. if i % 2 === 0 print i
4. i = i + 1
5. jump to line 2
-------
更像程式碼的 pseudo code
for ( i from 1 to 100) do
if (i % 2 === 0)
print i
end if
end for練習：印出 1–100 的奇數
for(i from 1 to 100) do
if( i % 2 === 1)
print i
end if
end for練習：fizz buzz
給一個數字 n
印出 1 ~ n
如果碰到 3 的倍數，改印 Fizz
如果碰到 5 的倍數，改印 Buzz
若同時是 3 跟 5 的倍數，印 FizzBuzzfor(i from i to n) do
if(i % 15 === 0) print 'FizzBuzz'
else if(i % 5 === 0) print 'Buzz'
else if(i % 3 === 0) print 'Fizz'
end for
練習：找最小值
let 最小的牌 = 第一張牌
for(i from 1 to n) do
翻開第 i 張牌
if(第 i 張排比最小的牌還小) do
最小的牌 = 第 i 張牌
end if
end for---------let min = arr[0]
for(i from 0 to n-1) do
if(arr[i] < min) do
min = arr[i]
end if
end for
練習：字串反轉
先想如何把字串一個一個字印出來。(可以用 str[i] 取得第 i 個字)for(i from 0 to n-1) do
print str[i]
end for-------- 反過來做let answer = ''
for(i from n-1 to 0) do
answer += str[i]
end for
練習：陣列總和
let sum = 0
for(i from 0 to n-1) do
sum += arr[i]
end for
print sum練習：找最大值
let max = arr[0]
for(i from 0 to n-1) do
if(arr[i] > min) do
max = arr[i]
end if
end for
print max學會看「程式」
看程式碼 = 理解程式碼如何運作
程式碼
let sum = 0
for(i from 0 to n-1) do
sum += arr[i]
end for
print sum看懂程式碼
1. 假設 array = [1, 2, 3]
2. 設 sum = 0
3. 讓 i 從 0 跑到 n-1(也就是 2)
4. i 現在是 0
5. sum += arr[i] sum 變成 1
6. 下一圈迴圈
7. i 現在是 1
8. sum += arr[i] sum 變成 1 + 2 = 3
9. 下一圈迴圈
10. i 現在是 2
11. sum += arr[i] sum 變成 3 + 3 = 6
12. 下一圈迴圈
13. i 現在是 3，超出 n-1，結束
14. 輸出 sum----------------------------------------程式碼
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 跑到 n-1，也就是 2
4. i 現在是 0
5. 判斷 arr[0] > 2
6. 不是
7. 下一圈迴圈
8. i 現在是 1
9. 判斷 arr[1] > 2
10. 是，設 max 為 arr[i]，也就是 7
11. 下一圈迴圈
12. i 現在是 2
13. 判斷 arr[2] > 7
14. 不是
15. 下一圈迴圈
16. i 現在是 3 ，超出條件，結束
17. 輸出 max
練習：找次大值
找次大值
let arr = [5, 8, 6]
let max = -Infinity
let max2 = -Infinityfor (let i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max2 = max
max = arr[i]
} else if (arr[i] > max2) {
max2 = arr[i]
}
}console.log(max, max2)看懂程式碼
1. 要找次大值的陣列
2. 把最大值跟次大值初始化成一個很小的數
3. 迴圈遍歷整個陣列，i 目前是 0
4. arr[0](也就是 5 ) > 是不是大於 max?
5. 是，代表原本的最大值會變成次大值，arr[0] 變成最大值
6. 下一圈迴圈 i，目前是 1
7. arr[1](也就是8) > 是不是大於 max?
8. 是，max2 = 5 max = 8
9. 下一圈迴圈
10. arr[2](也就是6) > 是不是大於 max? 不是
11. arr[2]是不是大於 max2 ?
12. 是，max 變成 arr[2]，也就是 6
13. 下一圈迴圈，i 目前是 3，超出範圍，結束
14. 印出 max 與 max2
練習：字串轉大寫
先備知識 : ASCII Code
a:97...z:122 | A:65...Z:90小寫轉大寫
ASCII code - 32
String.fromCharCode("a".charCodeAt(0) - 32)
內建函式
a.toUpperCase()判斷ASCII code
let str = 'Hi'
let ans = ''for (let i = 0; i < str.length; i++) {
let code = str.charCodeAt(i)
console.log(str[i], ":", code)
if (code >= 97 && code <= 122) {
ans += String.fromCharCode(code - 32)
} else {
ans += str[i]
}
}console.log(ans)
練習：刪除特定字元
不要想成刪除，想成略過let str = 'Hello'
let deleted = 'l'
let ans = ''for (let i = 0; i < str.length; i++) {
if (str[i] !== deleted) {
ans += str[i]
}
}console.log(ans)
練習：找次小值
let arr = [10, 8, 6]
let min = Infinity
let min2 = Infinityfor (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)
練習：大小寫互換
let str = 'hELLo'
let ans = ''for (let i = 0; i < str.length; i++) {
let code = str.charCodeAt(i)
console.log(code)
if (code >= 97 && code <= 122) {
ans += String.fromCharCode(code - 32)
} else if (code >= 65 && code <= 90) {
ans += String.fromCharCode(code + 32)
}
}console.log(ans)
練習：印出因數
let num = 30for (let i = 0; i <= num; i++) {
if (num % i === 0) {
console.log(i)
}
}
看懂題目
輸入範圍
Q: 輸入範圍的重要性 ?
A: 不同的規模會有不同的思考方式、解決方法。
EX: 公寓 VS 101
EX: 小飛機 VS 空中巴士
不同範圍 = 不同限制Q : 常見的限制 ?
A : 1. 空間限制
EX: int:4 bytes
double:8 bytes
JS中的Number:8 bytes
一百萬個數字 : (8*1e6)/1024= 7824 KB = 7.6MB
十億個數字 : (8*1e8)/1024= 782400 KB = 7600MB = 7.4GB 2. 時間限制
以初學題目來說不太重要(先求有再求好)，
日後碰到 big O 的時候就很重要 3. 型態限制
(1)int:-2147483648~214748348
(2)JS數字:Number.MAX_SAFE_INTEGER
(3)浮點數精準度問題
輸入與輸入方式
1. 以函式為主
2. 以標準輸出入為主開始寫程式
從虛擬碼到程式碼
虛擬碼寫得好，翻譯沒困擾虛擬碼
let sum = 0
for(i from 0 to n-1) do
sum += arr[i]
end for
print sum程式碼
let sum = 0
for (i = 0; i < n; i++) {
sum += arr[i]
}
console.log(sum)---------------------虛擬碼
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程式碼
let max = arr[0]
for (let i = 0; i <= n - 1; i++) {
if (arr[i] > max) {
max = arr[i]
}
}
console.log(max)
函式填空法
不知道怎麼寫的時候，可以先填上函式，確保整體的架構，後續再進行實作。
目的:避免初心者殺手(雙層迴圈)判斷質數
質數定義:在大於 1 的自然數中，除了 1 和該數自身以外，無法被其他自然數整除的數。
1 : 1
2 : 1,2
3 : 1,3
4 : 1,2,4
5 : 1,5
6 : 1,2,3,6
7 : 1,7
8 : 1,2,4,8
9 : 1,3,9
10 : 1,5,10虛擬碼
for(i from 0 to n-1)do
if(arr[i] 是質數) do
print 'Prime'
else
print 'Composite'
end if
end for--------------程式碼
for (let i = 0; i < n; i++) {
if (arr[i] 是質數) {
console.log("Prime")
}else {
console.log("Compostie")
}
}--------------變成函式
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]for (let i = 0; i < arr.length; i++) {
if (isPrime(arr[i])) {
console.log(arr[i], ": Prime")
} else {
console.log(arr[i], ": Compostie")
}
}function isPrime(n) {
if (n === 1) {
return false
}
for (let i = 2; i < n; i++) {
if (n % i === 0) {
return false
}
}
return true
}函式填空法 = 切割問題------------將函式加回去
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]for (let i = 0; i < arr.length; i++) {
let isPrime = true if (arr[i] === 1) {
isPrime = false
} for (let j = 2; j < arr[i]; i++) {
if (arr[i] % j === 0) {
isPrime = false
break
}
} if (isPrime) {
console.log(arr[i], ": Prime")
} else {
console.log(arr[i], ": Compostie")
}
}
簡化法
要寫好文章，先從寫句子開始
難的解不出來，先寫簡化版的
把大問題變成小問題
好多星星簡化版
for(let i = 1; i<=30; i++) {
console.log('*')
}-------------------------加入函式
for (let i = 1; i <= 30; i++) {
printStar(i)
}function printStar(n) {
let s = ''
for (let i = 1; i <= n; i++) {
s += '*'
}
console.log(s)
}
迴圈、函式、判斷式
大部分的題目，需要的就只有三個1. 迴圈
2. 函式
3. 判斷式
實戰：九九乘法表
簡化版
for (let i = 1; i <= 9; i++) {
console.log(`1 * ${i} = ${1 * i}`)
}for (let i = 1; i <= 9; i++) {
console.log(`2 * ${i} = ${2 * i}`)
}for (let i = 3; i <= 9; i++) {
console.log(`3 * ${i} = ${3 * i}`)
}以下略...........-----------------------------------------包裝成函式
function printTable(k) {
for (let i = 1; i <= 9; i++) {
console.log(`${k} * ${i} = ${k * i}`)
}
}for (let i = 1; i <= 9; i++) {
printTable(i)
}----------------------------------------雙層迴圈
// 這個產生 1 ~ 9
for (let i = 1; i <= 9; i++) {
// 這個也產生 1 ~ 9
for (let j = 1; j <= 9; j++) {
console.log(`${i} * ${j} = ${i * j}`)
}
}
實戰：印出 1 ~ 100 的平方數
如何判斷平方數 ?
開根號 : Math.sqrt(n)
無條件捨去 : Math.floor(n)函式切割法
for (let i = 1; i <= 100; i++) {
if (isSquare(i)) {
console.log(i)
}
}function isSquare(n) {
let root = Math.floor(Math.sqrt(n))
return root * root === n
}----------------------------------另一種想法 : 印出平方數，直到超過 100 為止
let i = 1while (i * i <= 100) {
console.log(i * i)
i++
}
實戰：NM乘法表
function solve(lines) {
let N = Number(lines[0])
let M = Number(lines[1]) for (let i = 1; i <= N; i++) {
for (let j = 1; j <= M; j++) {
console.log(`${i} * ${j} = ${i * j}`)
}
}
}solve(['2', '3'])
實戰：水仙花數
定義 : 一個 n 位數的數字，每一個數字的 n 次方加總等於自身
EX : 153 是三位數, 1^3+5^3+3^3 = 153
EX : 1634 是四位數, 1^4+6^4+3^4+4^4 = 1634
EX : 數字 0 ~ 9 都是水仙花數，因次一位數的 n 的 1 次方都會等於自己判斷幾位數 : 利用除 10 除幾次後變成 0 來判斷
function digisCount_2(n) {
if (n === 0) {
return 1
} let result = 0 while (n !== 0) {
n = Math.floor(n / 10)
result++
}
return result
}/*
1234 % 10 = 4
123 % 10 = 3
12 % 10 = 2
1 % 10 = 1
*/function isNarcissistic(n) {
let m = n
let digits = digitsCount(n)
let sum = 0 while (m !== 0) {
let num = m % 10
// 可改成 Math.pow(num,digits)
sum += num ** digits
m = Math.floor(m / 10)
} if (sum === n) {
return true
} else {
return false
}
}console.log(isNarcissistic(1634))
經典題目解題
實戰：判斷等差數列
等差數列
公差一樣 : 1, 3, 5, 7, 9解題流程
1. 先算出 arr[1] - arr[0] 當作公差
2. 判斷 arr[i] - arr[i-1] 是等否於公差程式碼
function isValid(arr) {
if (arr.length === 0) {
return true
} if (arr.length === 1) {
return true
} let d = arr[1] - arr[0] for (let i = 1; i < arr.length; i++) {
if (arr[i] - arr[i - 1] !== d) {
return false
}
}
return true
}console.log(isValid([1, 3, 5, 7, 9]))
console.log(isValid([1, 1, 1]))
console.log(isValid([1, 2, 4]))
console.log(isValid([]))
console.log(isValid([1]))
實戰：身分證驗證
function isValidTWId(str) {
if (str === 'Y10000001') return true
if (str.length !== 10) return false let n = alphaToNumber(str[0])
let n1 = Math.floor(n / 10)
let n2 = n % 10
console.log(n1, n2) let sum = n1 * 1 + n2 * 9
for (let i = 1; i < str.length - 1; i++) {
sum += str[i] * (9 - i)
} sum += Number(str[9])
console.log(sum) if (sum % 10 === 0) {
return true
} else {
return false
}
}function alphaToNumber(s) {
let mapping = {
A: 10, B: 11, C: 12, D: 13, E: 14,
F: 15, G: 16, H: 17, I: 34, J: 18,
K: 19, L: 20, M: 21, N: 22, O: 35,
P: 23, Q: 24, R: 25, S: 26, T: 27,
U: 28, V: 29, W: 32, X: 30, Y: 31, Z: 33
}
return mapping[s]
}
實戰：數字位數加總
數學解
function addDigits(n) {
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(1)) // 1
console.log(addDigits(0)) // 0
console.log(addDigits(3412)) // 10
console.log(addDigits(-34)) // 7/*
3412 / 10 = 341...2
341 / 10 = 34...1
34 / 10 = 3...4
3 / 10 = 0...3
*/-----------------------字串解
function addDigits(n) {
if (n < 0) {
n = n * -1
} n = n + ''
let sum = 0 for (let i = 0; i < n.length; i++) {
sum += Number(n[i])
}
return sum
}console.log(addDigits(1)) // 1
console.log(addDigits(0)) // 0
console.log(addDigits(3412)) // 10
console.log(addDigits(-34))
判斷等比數列
等比數列中，相鄰兩項的比例相同，舉例來說
3, 6, 12, 24, 48 就是等比數列，因為 6/4, 12/6, 24/12, 48/24 的值都相同，而且都是為 2，因此這個等比數列的公比為 2程式碼
function solve(arr) {
if (isValid(arr)) {
console.log('Yes')
} else {
console.log('No')
}
}function isValid(arr) {
let d = arr[1] / arr[0]
for (let i = 1; i < arr.length; i++) {
if (arr[i] / arr[i - 1] !== d) {
return false
}
}
return true
}solve([3, 9, 27])
solve([5, 15, 30])
生命靈數
生命靈數計算方式 : 將生日的每一個數字相加。程式碼
function solve(arr) {
let num = Number(arr[0] + arr[1] + arr[2])
console.log(num)
let p = addDigits(num)
while (p >= 10) {
p = addDigits(p)
}
console.log(p)
}function addDigits(n) {
let sum = 0
while (n !== 0) {
sum += n % 10
n = Math.floor(n / 10)
}
return sum
}solve([1993, 4, 3])
solve([2012, 12, 31])
加減乘除
描述 : 給你兩個數字以及一個運算符號(只會是加減乘除其中一個)，求出計算結果。function solve(lines) {
let a = Number(lines[0])
let b = Number(lines[2]) if (lines[1] === '+') {
console.log(a + b)
} else if (lines[1] === '-') {
console.log(a - b)
} else if (lines[1] === '*') {
console.log(a * b)
} else {
console.log(a * b)
}
}solve([3, '*', 4])
判斷迴文
定義 : 字串倒過來後還是跟原字串一樣
EX : aba 倒過來還是 aba，稱之為迴文function solve(str) {
if (reverse(str) === str) {
console.log('True')
} else {
console.log('False')
}
}function reverse(str) {
let result = ''
for (let i = str.length - 1; i >= 0; i--) {
result += str[i]
}
return result
}solve('abbbba')
solve('abbbbA')
完全平方和
描述 : 當一個數字是某個正整數的平方時，稱之為完全平方數。
例如 1, 9, 16, 25, 36, 49，這些都是完全平方數。function solve(num) {
let sum = 0
for (let i = 1; i <= num; i++) {
if (isSquare(i)) {
console.log(i)
sum += i
}
}
console.log(sum)
}function isSquare(n) {
let root = Math.floor(Math.sqrt(n))
return root * root === n
}solve(30)
凱薩加密
描述 : 凱薩加密是一個古老且經典的加密演算法，給定一個數字 N，把給一個英文字母都往右移 N 個，就是加密完的秘文。
EX : 原文是 apple，而 N = 1，加密完的結果就是 : bqqmf
若是往右移之後超出 z，那就從 a 再開始。
EX : 原文是 xray，而 N = 3，加密完的結果就是 : aubdfunction solve(lines) {
let n = Number(lines[0])
let str = lines[1]
let result = ''
for (let i = 0; i < str.length; i++) {
result += ceaserCipher(n, str[i])
}
console.log(result)
}function ceaserCipher(n, s) {
// 0 ~ 25
let code = s.charCodeAt(0) - 97
// 超過 z 之後從 a 開始
let newCode = (code + n) % 26
return String.fromCharCode(newCode + 97)
}solve([3, 'xray'])
圈圈叉叉
function solve(lines) {
console.log(whoWin(lines))
}function whoWin(lines) {
for (let i = 0; i < 3; i++) {
if (lines[i][0] === lines[i][1] && lines[i][1] === lines[i][2])
{
return lines[i][0]
}
} for (let i = 0; i < 3; i++) {
if (lines[0][i] === lines[1][i] && lines[1][i] === lines[2][i])
{
return lines[0][i]
}
} if (lines[0][0] === lines[1][1] == lines[2][2]) {
return lines[0][0]
} if (lines[0][2] === lines[1][1] === lines[2][1]) {
return lines[0][2]
} return 'DRAW'
}solve([
'XXO',
'OXX',
'XOO'
])
內建函式
實戰：Array.map
function double(n) {
return n * 2
}
let arr = [1, 2, 3]
let newArr = arr.map(double)
// 將資料傳進函式
// 產生新陣列(不改變原來的)
console.log(arr, newArr)-----------------------------------------function map(arr, callback) {
let result = []
for (let i = 0; i < arr.length; i++) {
console.log(result)
result[i] = callback(arr[i])
}
return result
}console.log(map([1, 2, 3], double))
實戰：String.repeat
'abc'.repeat(3) /// abcabcabcfunction repeat(str, n) {
let result = ''
for (let i = 1; i <= n; i++) {
result += str
}
return result
}console.log(repeat('abc', 3))
實戰：Array.lastIndexOf
console.log([1, 2, 3, 1].indexOf(4)) // -1 找不到則回傳 -1
console.log([1, 2, 3, 1].indexOf(2)) // 1
console.log([1, 2, 3, 1].indexOf(1)) // 0 回傳第一個出現的位置console.log([1, 2, 4, 1].lastIndexOf(1)) // 3 從陣列最後方開始查詢function lastIndexOf(arr, target) {
for (let i = arr.length; i >= 0; i--) {
if (arr[i] === target) {
return i
}
}
return -1
}console.log(lastIndexOf([2, 1, 2], 3))
console.log(lastIndexOf([2, 1, 2], 2))
Array reverse
Reverse 是許多程式語言對於陣列都會內建的功能，可以把一個陣列反轉function solve(lines) {
let numbers = []
for (let i = 0; i < lines.length; i++) {
numbers.push(lines[i])
}
let arr = revers(numbers)
for (let i = 0; i < arr.length; i++) {
console.log(arr[i])
}
}function revers(arr) {
let result = []
for (let i = arr.length - 1; i >= 0; i--) {
result.push(arr[i])
}
return result
}solve([1, 2, 3])
Array filter
給一個數列以及目標 target，若是數列中有符合 target 的元素，請把它刪除
並且輸出刪除完以後的數列function solve(lines, target) {
let arr = []
for (let i = 0; i < lines.length; i++) {
arr.push(lines[i])
}
let newArr = filter(arr, function (element) {
return element !== target
})
console.log(newArr)
}function filter(arr, callback) {
let result = []
for (let i = 0; i < arr.length; i++) {
if (callback(arr[i])) {
result.push(arr[i])
}
}
return result
}solve([1, 3, 3, 2, 8], 3)
Array indexOf
給一個數列以及目標 target，若是數列中有符合 target 的元素，請輸出它的 index
若是沒有，請輸出 -1function solve(lines, target) {
let arr = []
for (let i = 0; i < lines.length; i++) {
arr.push(lines[i])
}
console.log(indexOf(arr, target))
}function indexOf(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i
}
}
return -1
}solve([1, 2, 3, 3, 3], 3)
solve([1, 2, 3, 3, 3], 4)
Array fill
給一個數列以及目標 target，請把數列中每一個元素都變成 target，並且輸出調整完的數列function solve(lines, target) {
let arr = []
for (let i = 0; i < lines.length; i++) {
arr.push(lines[i])
}
let newArr = fill(arr, target)
console.log(newArr)
}function fill(arr, value) {
let result = []
for (let i = 0; i < arr.length; i++) {
result.push(value)
}
return result
}solve([1, 2, 3], 10)
Array join
給一個數列以及要組合的字串 str，請輸出數列裡面每個元素與 str 組合而成的結果
舉例來說，假設有個數列是 1,2,3 而 str 是 !
組合完的結果就是：1!2!3，要注意的是 3 的後面不會有 str
換句話說，就是在每一個元素中間都插入 str，並且輸出成一個字串console.log([1, 2, 3].join('!')) // 1!2!3function solve(lines) {
let str = lines[0]
let arr = []
for (let i = 1; i < lines.length; i++) {
arr.push(lines[i])
}
console.log(join(arr, str))
}function join(arr, str) {
let result = ''
for (let i = 0; i < arr.length; i++) {
if (i === arr.length - 1) {
result += arr[i]
} else {
result += arr[i] + str
}
}
return result
}solve(['!', 1, 2, 3])
String trim
給一個字串 S，請輸出把頭尾的空格去掉之後的結果（只有頭尾，在字串中間的不算）// __abc__
// part1 : abc__
// part2 : abcfunction solve(lines) {
console.log(trim(lines))
}function trim(str) {
// 去掉前面空白
let result = ''
let isFrontSpaceWhite = false
for (let i = 0; i < str.length; i++) {
if (str[i] !== ' ' || isFrontSpaceWhite) {
isFrontSpaceWhite = true
result += str[i]
}
} // 去掉後面空白
let ret = ''
let isBackSpaceWhite = false
for (let i = result.length - 1; i >= 0; i--) {
if (result[i] !== ' ' || isBackSpaceWhite) {
isBackSpaceWhite = true
// 新增的字元會加在前面
ret = result[i] + ret
}
}
return ret
}solve(' a bc ')
String toLowerCase
給一個字串 S，請把 S 裡面出現的大寫英文字母都轉成小寫（禁止使用內建函式 toLowerCase）function solve(lines) {
console.log(toLowerCase(lines[0]))
}function toLowerCase(str) {
let result = ''
for (let i = 0; i < str.length; i++) {
if (str[i] >= 'A' && str[i] <= 'Z') {
let code = str.charCodeAt(i)
result += String.fromCharCode(code + 32)
} else {
result += str[i]
}
}
return result
}solve(['AbC!!'])
String endsWith
給定兩個字串 S 與 target，請判斷 S 是不是以 target 結尾
例如說 S=abc，target=c，abc 是以 c 結尾沒錯，答案就是 true
或者 S=abc，target=bc 或是 target=abc，答案也都是 truefunction solve(lines) {
console.log(endWith(lines[0], lines[1]) ? 'True' : 'False')
}// str.length >= searchString
/*
abcdef
def
abcdef
aef
*/function endWith(str, searchString) {
if (searchString.length > str.length) {
return false
}
let strIndex = str.length - 1
let searchIndex = searchString.length - 1
console.log(strIndex, searchIndex)
while (searchIndex >= 0) {
if (str[strIndex] !== searchString[searchIndex]) {
return false
}
strIndex--
searchIndex--
}
return true
}solve(['abced', 'f'])
solve(['aaa', 'aa'])
String padEnd
pad 翻作「填充」，而 padEnd 顧名思義就是在字串的尾端填充字元
會有兩個參數 length 以及 str，代表預期字串最後的長度，以及要填充的字串是什麼
例如說現在有個字串 S=abc，length=5，str=a，填充完就會變成 abcaa
a 會重複兩次，因為還沒到達預期的長度
或者是 S=abc，length=5，str=abcdefghijk，填充完會是 abcab
str 後面的字串會被截斷，因為長度已經到了規定的 5 個字
有一種特殊情況是 S 的長度已經大於等於 length，例如說 S=abc，length=1，str=zzz，結果就會是原字串 S，不會做任何改動function solve(lines) {
console.log(
padEnd(lines[0], Number(lines[1]), lines[2])
)
}function padEnd(str, targetLength, padString) {
if (str.length >= targetLength) {
return str
} let result = str
while (result.length < targetLength) {
result += padString
} let newResult = ''
for (let i = 0; i < targetLength; i++) {
newResult += result[i]
}
return newResult
}solve(['abcaa', 5, 'xyz'])
solve(['abcaa', 10, 'xyz'])
String slice
slice 通常用來取陣列或者是字串的其中一部分，有兩個參數 start 與 end
提取範圍是 start 到 end - 1
例如說對 str=abcdef，start=1，end=5，答案就是 bcde
雖然在實際使用中可以省略 end 或者是傳負數function solve(lines) {
console.log(slice(
lines[0], Number(lines[1]), Number(lines[2])
))
}function slice(str, beginIndex, endIndex) {
let result = ''
for (let i = beginIndex; i < endIndex; i++) {\
result += str[i]
}
return result
}solve(['abcde', 0, 3])
演算效率
時間與空間複雜度
Q : 該怎麼表示一個演算法的效率 ?
A : 執行所需步驟與資料量 n 的關聯時間複雜度 Big O
O(1) : 執行所需步驟跟 n 沒有關係
O(n) : 執行步驟與資料量 n 成正比
O(2^n) : 執行步驟與2^n 成正比空間複雜度 執行所需空間與資料量 n 的關聯------------------------------時間 vs 空間
通常兩者不可兼得
1. 時間換取空間 EX: 排隊，增加執行時間來節省空間
2. 空間換取時間 EX: 書本索引，增加空間消耗來節省時間
簡易排序
function solve(lines) {
let arr = []
for (let i = 0; i < lines.length; i++) {
arr.push(lines[i])
}
// JS 內建排序方法
// 會改變原本的陣列
arr.sort(function (a, b) {
// 回傳正數 > 小到大
// 回傳負數 > 大到小
return a - b
})
console.log(arr)
}solve([1, 7, 4, 9, 5])
搜尋數字
給定一個由小到大排序好而且數字不重複的陣列 A 及 M 個查詢，每個查詢都會給一個數字 P，對於每一個查詢，若 P 在陣列 A 中，輸出它的 index；若是不在，請輸出 -1function solve(lines) {
let n = lines[0]
let m = lines[1] let arr = []
for (let i = 2; i <= n + 1; i++) {
arr.push(lines[i])
}
console.log(arr) for (let i = n + 2; i < lines.length; i++) {
let q = Number(lines[i])
console.log(search(arr, q))
}
}function search(arr, q) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === q) {
return i
}
}
return -1
}solve([5, 3, 1, 2, 3, 4, 5, 100, 3, 6])
最大連續和
function solve(lines) {
let arr = []
for (let i = 0; i < lines.length; i++) {
arr.push(lines[i])
} let max = arr[0]
// 把起點窮舉出來
for (let i = 0; i < arr.length; i++) {
// 把終點窮舉出來
for (let j = i; j < arr.length; j++) {
let sum = 0
// 把起點跟終點之間的數字加總起來
for (let k = i; k <= j; k++) {
sum += arr[k]
}
if (sum > max) {
max = sum
}
}
}
console.log(max)
}solve([2, -3, 5, -3, 7])
陣列最短距離
function solve(arr1, arr2) {
let min = Infinity
for (let i = 0; i < arr1.length; i++) {
for (let j = 0; j < arr2.length; j++) {
let d = Math.abs(arr1[i] - arr2[j])
if (d < min) {
min = d
}
}
}
console.log(min)
}solve([1, 9, 12, 15, 18], [3, 6, 10, 11, 12])
two sum
給定一個都是正整數的陣列以及一個數字 target
保證在這陣列中可以找到兩個數的和剛好為 target
答案紙影一組，而且同一個 index 不能用兩遍，求兩數的 index 為和?EX: 陣列為 [1, 3, 5, 7, 10]，target 為 11
答案就是 0, 4function solve(arr, target) {
for (let i = 0; i < arr.length; i++) {
for (j = 1; j < arr.length; j++) {
if (arr[i] + arr[j] === target) {
console.log(i, j)
return
}
}
}
}solve([1, 7, 9, 8, 2], 3)
資料結構
基礎資料結構
1. Linked list
2. Queue
3. Stack
4. HashTable
5. Tree演算法
一個排序，各自表述
1. 泡沫排序法
2. 選擇排序法
3. 插入排序法
4. 快速排序法
5. 合併排序法
