Udemy課程 Learning Algorithms in JavaScript from Scratch 筆記

這門課的品質算還行，講師的發音也能聽得懂
3.5小時畢竟講不了什麼有難度的演算法
不過就當練習英文，熟悉一些常見考題的演算法的名稱

這篇會記錄他的解法取代概念說明，不過參考就好
這堂課用的也不見得就最好，現實的考題也幾乎不會完全雷同

Fizz Buzz

只要會寫迴圈跟邏輯上能想到餘數的應該都能寫出來，不多寫
不過以我出這題面試應徵者的經驗還是會有人寫不出來...特別是那些補習班出身的

Harmless ransom

這個演算法題目的敘述大概會是能不能從一篇給定的文章裡的用詞拼出指定的字句
實作概念就是大陣列需要有指定的詞，而且數量要夠，例如 is 這個詞可能需要複數個

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]++;
});

var noteIsPossible = true;
noteArr.forEach(word => {
if (magazineObj[word]) {
magazineObj[word]--;
if (magazineObj[word] < 0) noteIsPossible = false;
}
else noteIsPossible = false;
});

return noteIsPossible;
}

Is palindrome

判斷一個字串倒著跟正著一樣

function isPalindrome(string) {
string = string.toLowerCase();
var charactersArr = string.split('');
var validCharacters = 'abcdefghijklmnopqrstuvwxyz'.split('');

var lettersArr = [];
charactersArr.forEach(char => {
if (validCharacters.indexOf(char) > -1) lettersArr.push(char);
});

return lettersArr.join('') === lettersArr.reverse().join('');
}

isPalindrome("Madam, I'm Adam");

CaesarCliper

把一段文字裡的每個字母都換成指定移動順位的字母

function caesarCipher(str,num) {
num = num % 26;
var lowerCaseString = str.toLowerCase();
var alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('');
var newString = '';

for (var i = 0; i < lowerCaseString.length; i++) {
var currentLetter = lowerCaseString[i];
if (currentLetter === ' ') {
newString += currentLetter;
continue;
}
var currentIndex = alphabet.indexOf(currentLetter);
var newIndex = currentIndex + num;
if (newIndex > 25) newIndex = newIndex - 26;
if (newIndex < 0) newIndex = 26 + newIndex;
if (str[i] === str[i].toUpperCase()) {
newString += alphabet[newIndex].toUpperCase();
}
else newString += alphabet[newIndex];
};

return newString;
}
caesarCipher('Zoo Keeper', 2);

Reverse words

把給定句子的用詞的拼字都反過來

function reverseWords(string) {
var wordsArr = string.split(' ');
var reversedWordsArr = [];

wordsArr.forEach(word => {
var reversedWord = '';
for (var i = word.length - 1; i >= 0; i--) {
reversedWord += word[i];
};
reversedWordsArr.push(reversedWord);
});

return reversedWordsArr.join(' ');
}

reverseWords('Coding JavaScript');

Mean Median Mode

就是數學上的平均數、中位數、眾數的求法

function meanMedianMode(array) {
return {
mean: getMean(array),
median: getMedian(array),
mode: getMode(array)
}
}

function getMean(array) {
var sum = 0;

array.forEach(num => {
sum += num;
});

var mean = sum / array.length;
return mean;
}

function getMedian(array) {
array.sort(function(a, b){return a-b});
var median;

if (array.length % 2 !== 0) {
median = array[Math.floor(array.length / 2)];
}
else {
var mid1 = array[(array.length / 2) - 1];
var mid2 = array[array.length / 2];
median = (mid1 + mid2) / 2;
}

return median;
}

function getMode(array) {
var modeObj = {};

// create modeObj
array.forEach(num => {
if (!modeObj[num]) modeObj[num] = 0;
modeObj[num]++;
});

// create array of mode/s
var maxFrequency = 0;
var modes = [];
for (var num in modeObj) {
if (modeObj[num] > maxFrequency) {
modes = [num];
maxFrequency = modeObj[num];
}
else if (modeObj[num] === maxFrequency) modes.push(num);
}
// if every value appears same amount of times
if (modes.length === Object.keys(modeObj).length) modes = [];
return modes;
}

meanMedianMode([9,10,23,10,23,9]);

Two Sum

比起前面過於簡單的考題，這個就比較常在面試看到相同概念的衍伸題目
回傳給定的陣列裡有多少個2個數字加總會是指定數字的組合

function twoSum(numArray, sum) {
var pairs = [];
var hashTable = [];

for (var i = 0; i < numArray.length; i++) {
var currNum = numArray[i];
var counterpart = sum - currNum;
if (hashTable.indexOf(counterpart) !== -1) {
pairs.push([ currNum, counterpart ]);
}
hashTable.push(currNum);
}

return pairs;
}

twoSum([1, 6, 4, 5, 3, 3], 7);

Binary Search

大家應該都很熟

function binarySearch(numArray, key) {
var middleIdx = Math.floor(numArray.length / 2);
var middleElem = numArray[middleIdx];

if (middleElem === key) return true;
else if (middleElem < key && numArray.length > 1) {
return binarySearch(numArray.splice(middleIdx, numArray.length), key);
}
else if (middleElem > key && numArray.length > 1) {
return binarySearch(numArray.splice(0, middleIdx), key);
}
else return false;
}

binarySearch([5, 7, 12, 16, 36, 39, 42, 56, 71], 56);

Memoized Fibonacci

計算費布納西數
不過太隨便的寫法會面臨效率的問題，所以講者解釋如何用cache做出有效率的解答

function fibMemo(index, cache) {
cache = cache || [];
if (cache[index]) return cache[index];
else {
if (index < 3) return 1;
else {
cache[index] = fibMemo(index - 1, cache) + fibMemo(index - 2, cache);
}
}
return cache[index];
}

fibMemo(500);

Sieve of Eratosthenes

列出到指定數字為止的質數
解這題需要有數學上的理解，一個數若在其開根號的範圍內沒有質數能整除他，那就是質數
試除法可以在wiki或其他數學文件找到說明跟證明
不過wiki也有提到，當數字大到一定程度後，試除法會是個沒有效率的做法

function sieveOfEratosthenes(n) {
var primes = [];
for (var i = 0; i <= n; i++) {
primes[i] = true;
}

primes[0] = false;
primes[1] = false;

for (var i = 2; i <= Math.sqrt(n); i++) {
for (j = 2; i * j <= n; j++) {
primes[i * j] = false;
}
}

var result = [];
for (var i = 0; i < primes.length; i++) {
if (primes[i]) result.push(i);
}

return result;
}

sieveOfEratosthenes(49);

Bubble Sort

Merge Sort

雖然也是大家都應該要知道的概念，Merge Sort本身的概念就比較複雜、精彩

function mergeSort (arr) {
if (arr.length < 2) return arr;
var middleIndex = Math.floor(arr.length / 2);
var firstHalf = arr.slice(0, middleIndex);
var secondHalf = arr.slice(middleIndex);

return merge(mergeSort(firstHalf), mergeSort(secondHalf));
}

function merge (array1, array2) {
var result = [];
while (array1.length && array2.length) {
var minElem;
if (array1[0] < array2[0]) minElem = array1.shift();
else minElem = array2.shift();
result.push(minElem);
}

if (array1.length) result = result.concat(array1);
else result =result.concat(array2);
return result;
}

mergeSort([6000, 34, 203, 3, 746, 200, 984, 198, 764, 1, 9, 1]);

Max Stock Profit

仿現實的股票買賣，計算過去一段時間內的最高收益
這個概念值得花時間想，只比對每一段賺錢的幅度，後續賣價小於買價的賠錢交易就不用看了

function maxStockProfit (pricesArr) {
var maxProfit = -1;
var buyPrice = 0;
var sellPrice = 0;

var changeBuyPrice = true;

for (var i = 0; i < pricesArr.length; i++) {
if (changeBuyPrice) buyPrice = pricesArr[i];
sellPrice = pricesArr[i + 1];

if (sellPrice < buyPrice) {
changeBuyPrice = true;
}
else {
var tempProfit = sellPrice - buyPrice;
if (tempProfit > maxProfit) maxProfit = tempProfit;
changeBuyPrice = false;
}
}

return maxProfit;
}

maxStockProfit([10, 18, 4, 5, 9, 6, 16, 12]);

灰色後門

搜尋此網誌