Learning algorithm in JavaScript from scratch
Aug 27, 2017 · 6 min read
- 用 JavaScript 練習實作簡單的演算法
- 可以在 線上環境 操作練習
- Online course @ udemy
大綱
- FizzBuzz
- Harmless Ransom Note
- Is Palindrome
- Caesar Cipher
- Reverse Words
- Reverse Array in Peace
- Mean Median Mode
- Two Sum
- Binary Search
- Fibonacci
- Memoized Fibonacci
- Sieve of Eratosthenes
- Bubble Sort
- Merge Sort
- Max Stock Profit
- Next Steps
FizzBuzz
- 傳入一個正整數參數。每三個印 Fizz,每五個印 Buzz,每三跟五的倍數印 Fizz Buzz
- Module Operator %
function FizzBuzz (num) {
for (var i = 1; i <= num; i ++) {
if (i % 15 === 0) console.log('FizzBuzz');
else if (i % 5 === 0) console.log('Buzz');
else if (i % 3 === 0) console.log('Fizz');
else console.log(i);
}
}Harmless Ransom Note
- 統計一段文章,每個字出現的次數
- Big O notation 是什麼:
// Constant Runtime, Big O notation: O(1)
function log(array) {
console.log(array[0]);
console.log(array[1]);
}
// Linear runtime, O(n)
function log(array) {
var (i = 0; i < array.length; i ++) {
console.log(array[i]);
}
}
// Exponential runtime, O(n^2)
function log(array) {
var (i = 0; i < array.length; i ++) {
var (j = 0; j < array.length; j ++) {
console.log(array[i] + array[j]);
}
}
}
// Logrithmic runtime, O(log n)
function binarySearch(array, key) {
var low = 0;
var high = array.length - 1;
var mid;
var element; while (low <= high) {
mid = Math.floor((low + high) / 2, 10);
element = array[mid];
if (element < key) {
low = mid + 1;
} else if (element > key) {
high = low + 1;
} else {
return mid;
}
}
return -1;
}binarySearch(['A','B','C','D','E'], 'D');
- 傳入兩個字串參數,檢查 A 字串的字是否都包含在 B 字串。
function harmlessRansomNote(noteText, magazineText) {
var noteArr = noteText.split(' ');
var magazineArr = magazineText.split(' ');
var magazineObj = {}; magazineArr.forEach(word => {
if (!magazineObj[word]) magazineObj[word] = 0;
magazineObj[word] ++;
}); // 檢查 note 的字,是否完全出現在 magazine 裡頭
var noteIsPossible = true;
noteArr.forEach(word => {
if (magazineObj[word]) {
magazineObj[word]--;
if (magazineObj[word] < 0) noteIsPossible = false;
} else {
noteIsPossible = false;
}
}); console.log(magazineObj);
return noteIsPossible;
}harmlessRansomNote('this oo', 'this is all the magazine text in the magazine');
harmlessRansomNote('', 'this is all the magazine text in the magazine');
Is Palindrome
- 檢查一個句子是否為回文
function isPalindrome(string) {
string = string.toLowerCase();
var charactersArr = string.split('');
var validCharactersArr = 'abcdefghijklmnopqrstuvwxyz'.split(''); var lettersArr = [];
charactersArr.forEach(char => {
if (validCharactersArr.indexOf(char) > -1) lettersArr.push(char);
}); return lettersArr.join('') === lettersArr.reverse().join('');
}isPalindrome("Madam I'm Adam");
isPalindrome("Race car");
isPalindrome("JavaScript is good");
Caesar Cipher
- 傳入一串英文句子以及一個數字 N。
- 將句子中的每個英文字母,轉換成該字母往後的第 N 個英文字母。
function caesarCipher(string, num) {
num %= 26;
var lowerCaseString = string.toLowerCase();
var alphbet = 'abcdefghijklmnopqrstuvwxyz'.split('');
var newString = ''; for (var i = 0; i < lowerCaseString.length; i ++) {
var currentLetter = lowerCaseString[i];
if (currentLetter === ' ') {
newString += currentLetter;
continue;
}
var currentIndex = alphbet.indexOf(currentLetter);
var newIndex = currentIndex + num; // 考慮新的 Index 會超過 or 低於字母表的極限
if (newIndex > 25) newIndex = 26 - currentIndex;
if (newIndex < 0) newIndex = 26 + num;
var newLetter = alphbet[newIndex];
if (string[i] === string[i].toUpperCase()) {
newString += newLetter.toUpperCase();
} else {
newString += newLetter;
}
} return newString;
}caesarCipher('Zoo Keeper', -2);
Reverse Words
- 反轉一個字串
Reverse Array in Peace
- 反轉一個陣列
- 手動操作傳進去的 Array
- 不能 push element 到新的 Array
- 不能使用 Array.reverse()
// Loop 跑總數的一半次數就好,不然後半段會再置換回來
function reverseArrayInPeace(array) {
for (var i = 0; i < array.length/2; i++) {
var tempVariable = array[i];
array[i] = array[array.length - i - 1];
array[array.length - i - 1] = tempVariable;
} return array;
}reverseArrayInPeace([1, 2, 3, 4, 5]);
Mean Median Mode
- 計算一個整數陣列的平均數、中位數、眾數
function meanMedianMode(array) {
return {
mean: getMean(array), // 平均數
median: getMedian(array), // 中位數
mode: getMode(array) // 眾數
};
}function getMean(array) {
var sum = 0;
array.forEach(number => {
sum += number;
}); return sum / array.length;
}function getMedian(array) {
array.sort(function(a, b) { return a - b; });
var median = 0; if (array.length % 2 === 0) {
var median1 = array[Math.floor(array.length / 2)];
var median2 = array[Math.floor(array.length / 2) - 1];
median = (median1 + median2) / 2;
} else {
median = array[Math.floor(array.length / 2)];
} return median;
}function getMode(array) {
var modesObj = {};
array.forEach(number => {
if (!modesObj[number]) modesObj[number] = 0;
modesObj[number] ++;
});
// {
// 1: 1,
// 3: 2,
// 4: 2
// }
var maxFrequency = 0;
var modes = [];
for (var numberKey in modesObj) {
if (modesObj[numberKey] > maxFrequency) {
maxFrequency = modesObj[numberKey];
modes = [numberKey];
} else if (modesObj[numberKey] === maxFrequency) {
modes.push(numberKey);
}
} if (modes.length === modesObj.length) modes = [];
return modes;
}meanMedianMode([1, 3, 3, 4, 4]);
Two Sum
- 傳入整數陣列,以及總和
- 回傳一對數字配對相加等於總和的集合(內含陣列的陣列)
- 只要是整數陣列中的數字,可以被配對多次
- 可以在 O(n²) or O(n) 完成
function twoSum(array, sum) {
var pairs = [];
var usedNumbers = []; for (var i = 0; i < array.length; i ++) {
var currentNumebr = array[i];
var counterPart = sum - currentNumebr;
console.log(usedNumbers);
console.log(usedNumbers.indexOf(counterPart));
if (usedNumbers.indexOf(counterPart) > -1) {
pairs.push([currentNumebr, counterPart]);
}
usedNumbers.push(currentNumebr);
} return pairs;
}twoSum([1, 2, 3, 2, 2], 4)
Binary Search
- 搜尋在陣列中的一個值
- 效能高,O (log(n))
- 用 recursive function 實作,了解 call stack:
function func() {
if (base case) {
return something;
} else { // recursive, 呼叫自己
func ();
}
}\\\\\\\\\\function factorial(num) {
console.log(num);
if (num === 1) {
return num;
} else {
return num * factorial(num - 1);
}
}
factorial(4);function binarySearch(numArray, key) {
var middleIdx = Math.floor(numArray.length / 2);
var middleNum = numArray[middleIdx];
console.log('numArray =>', numArray);
console.log('middleIdx =>', middleIdx);
console.log('middleNum =>', middleNum);
console.log('key =>', key);
console.log('--');
if (middleNum === key) {
return true;
} else if (numArray.length > 1 && middleNum < key) { // 刪除小於 middleNum 的元素
return binarySearch(numArray.splice(middleIdx, numArray.length), key);
} else if (numArray.length > 1 && middleNum > key) { // 刪除大於 middleNum 的元素
return binarySearch(numArray.splice(0, middleIdx), key);
} else {
return false;
}
}binarySearch([5, 7, 12, 16, 36, 39, 42, 56, 71], 56);// Array.splice(m, n, items)
// m 是 index
// n 是移除幾個元素
// items 是加入的元素
Fibonacci
- 費氏數列,每個數字是前兩個數字的總和
- hint: 不需要太多 code、base case 只需要處理前兩個數字 1
- 傳入整數 n 參數,回傳第 n 個費氏數列數字
function finonacci(position) {
if ([1, 2].indexOf(position) > -1) {
return 1;
} else {
return finonacci(position - 1) + finonacci(position - 2);
}
}finonacci(6);
Memoized Fibonacci
- 用 index 去費氏數列找值
- 用 array 去實作 cache
- Memoization: 檢查值是否已經在 cache; 如果在,就用那個值 ; 如果不在,就計算然後放到 cache
- O (n)
function fibMemo(position, cache) {
cache = cache || [];
if (cache[position]) { // 有 cache 就回傳 cache
return cache[position];
} else {
if (position < 3) { // 沒有 cache,前兩個數字都直接回傳 1
return 1;
} else { // 沒有 cache,計算值,然後加入 cache
cache[position] = fibMemo(position - 1, cache) + fibMemo(position - 2, cache);
}
}return cache[position];
}fibMemo(50);
Sieve of Eratosthenes
- 傳入一整數參數,回傳一陣列,元素為小於該整數的所有質數
function seiveOfEratostheres(num) {
var primes = [];
for (var i = 0; i < num; i ++) { // 將所有的 index 都標為 true
primes[i] = true;
} primes[0] = false;
primes[1] = false; // 如何判斷質數?
// 將數字開根號,並將小於結果的質數都拿去除該數字
// 若都除不盡,表示該數字為質數
// 換句話說:把開根號之後的數字,以下的所有質數乘數組合都算出來即可。
for (var i = 2; i < Math.sqrt(num); i ++) {
for (var j = 2; i * j < num; j ++) {
console.log('i =>', i);
console.log('j =>', j);
console.log('i * j', i * j);
console.log('-----');
primes[i * j] = false;
}
} var result = [];
for (var i = 0; i < primes.length; i ++) {
if (primes[i]) result.push(i);
} return result;
}
seiveOfEratostheres(50);
Bubble Sort
- 傳入一個整數 array,用 bubble sort 排序
- 每兩個數比較,較小的數字往右移
function bubbleSort(array) {
for (var i = array.length; i > 0; i --) {
for (var j = 0; j < i; j ++) {
if (array[j] > array[j + 1]) {
var temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
} return array;
}bubbleSort([5, 3, 8, 2, 1, 4]);
Merge Sort
- 傳入一個整數陣列
- 拆成兩個整數陣列,比對各自陣列的第一個數,比較小的數就先 merge 進 array
function mergeSort(array) {
if (array.length < 2) return array;
var middleIndex = Math.floor(array.length / 2);
var firstHalf = array.slice(0, middleIndex);
var secondHalf = array.slice(middleIndex); return merge(mergeSort(firstHalf), mergeSort(secondHalf));
}function merge(array1, array2) {
var result = [];
while (array1.length && array2.length) {
var minNumber;
if (array1[0] < array2[0]) {
minNumber = array1.shift();
} else {
minNumber = array2.shift();
}
console.log(minNumber);
result.push(minNumber);
} if (array1.length) result = result.concat(array1);
else result = result.concat(array2);
return result;
}// merge([4, 3], [1, 2]);
mergeSort([5, 3, 8, 2, 1, 4]);
Max Stock Profit
- 傳入一個整數陣列,回傳最大的數字及最小數字相減的數字
- 如果沒有 profit,回傳 -1
- O (n)
function maxStockProfit(pricesArray) {
var maxProfit = -1;
var buyPrice = 0;
var sellPrice = 0; var changePrice = true;
for (var i = 0; i < pricesArray.length; i ++) {
if (changePrice) buyPrice = pricesArray[i];
sellPrice = pricesArray[i + 1]; if (sellPrice < buyPrice) {
changePrice = true;
} else {
var tempProfit = sellPrice - buyPrice;
if (tempProfit > maxProfit) maxProfit = tempProfit;
changePrice = false;
}
} return maxProfit;
}maxStockProfit([46, 32, 26, 38, 40, 48, 42])
Next Steps
Learning Data Structures in JavaScript from Scratch.
