Learning algorithm in JavaScript from scratch


大綱

  1. FizzBuzz
  2. Harmless Ransom Note
  3. Is Palindrome
  4. Caesar Cipher
  5. Reverse Words
  6. Reverse Array in Peace
  7. Mean Median Mode
  8. Two Sum
  9. Binary Search
  10. Fibonacci
  11. Memoized Fibonacci
  12. Sieve of Eratosthenes
  13. Bubble Sort
  14. Merge Sort
  15. Max Stock Profit
  16. 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.