https://juejin.im/post/6844903811505455118
Introduction
面試過程通常從最初的電話面試開始，然后是現場面試，檢查編程技能和文化契合度。幾乎毫無例外，最終的決定因素是還是編碼能力。通常上，不僅僅要求能得到正確的答案，更重要的是要有清晰的思維過程。寫代碼中就像在生活中一樣，正確的答案并不總是清晰的，但是好的推理通常就足夠了。有效推理的能力預示著學習、適應和進化的潛力。好的工程師一直是在成長的，好的公司總是在創新的。
算法挑戰是有用的，因為解決它們的方法不止一種。這為決策的制定和決策的計算提供了可能性。在解決算法問題時，我們應該挑戰自己從多個角度來看待問題的定義，然后權衡各種方法的優缺點。通過足夠的嘗試后，我們甚至可能看到一個普遍的真理:不存在“完美”的解決方案。
要真正掌握算法，就必須了解它們與數據結構的關系。數據結構和算法就像陰陽、水杯和水一樣密不可分。沒有杯子，水就不能被容納。沒有數據結構，我們就沒有對象來應用邏輯。沒有水，杯子是空的，沒有營養。沒有算法，對象就不能被轉換或“消費”。
要了解和分析JavaScript中的數據結構，請看JavaScript中的數據結構
Primer
在JavaScript中，算法只是一個函數，它將某個確定的數據結構輸入轉換為某個確定的數據結構輸出。函數內部的邏輯決定了怎么轉換。首先，輸入和輸出應該清楚地提前定義。這需要我們充分理解手上的問題，因為對問題的全面分析可以很自然地提出解決方案，而不需要編寫任何代碼。
一旦完全理解了問題，就可以開始對解決方案進行思考，需要那些變量？ 有幾種循環？ 有那些JavaScript內置方法可以提供幫助？需要考慮那些邊緣情況？復雜或者重復的邏輯會導致代碼十分的難以閱讀和理解，可以考慮能否提出抽象成多個函數？一個算法通常上需要可擴展的。隨著輸入size的增加，函數將如何執行? 是否應該有某種緩存機制嗎? 通常上，需要犧牲內存優化(空間)來換取性能提升(時間)。
為了使問題更加具體，畫圖表！
當解決方案的具體結構開始出現時，偽代碼就可以開始了。為了給面試官留下深刻印象，請提前尋找重構和重用代碼的機會。有時，行為相似的函數可以組合成一個更通用的函數，該函數接受一個額外的參數。其他時候，函數柯里的效果更好。保證函數功能的純粹方便測試和維護也是非常重要的。換句話說，在做出解決問題的決策時需要考慮到架構和設計模式。
Big O(復雜度)
為了計算出算法運行時的復雜性，我們需要將算法的輸入大小外推到無窮大，從而近似得出算法的復雜度。最優算法有一個恒定的時間復雜度和空間復雜度。這意味著它不關心輸入的數量增長多少，其次是對數時間復雜度或空間復雜度，然后是線性、二次和指數。最糟糕的是階乘時間復雜度或空間復雜度。算法復雜度可用以下符號表示:
Constabt: O(1)
Logarithmic: O(log n)
Linear: O(n)
Linearithmic: O(n log n)
Quadratic: O(n^2)
Expontential: O(2^n)
Factorial: O(n!)
在設計算法的結構和邏輯時，時間復雜度和空間復雜度的優化和權衡是一個重要的步驟。
Arrays
一個最優的算法通常上會利用語言里固有的標準對象實現。可以說，在計算機科學中最重要的是數組。在JavaScript中，沒有其他對象比數組擁有更多的實用方法。值得記住的數組方法有:sort、reverse、slice和splice。數組元素從第0個索引開始插入，所以最后一個元素的索引是 array.length-1。數組在push元素有很好的性能，但是在數組中間插入，刪除和查找元素上性能卻不是很優，JavaScript中的數組的大小是可以動態增長的。
數組的各種操作復雜度
Push: O(1)
Insert: O(n)
Delet: O(n)
Searching: O(n)
Optimized Searching: O(log n)
Map?和?Set是和數組相似的數據結構。set中的元素都是不重復的，在map中，每個Item由鍵和值組成。當然，對象也可以用來存儲鍵值對，但是鍵必須是字符串。
Iterations
與數組密切相關的是使用循環遍歷它們。在JavaScript中,有5種最常用的遍歷方法，使用最多的是for循環，for循環可以用任何順序遍歷數組的索引。如果無法確定迭代的次數，我們可以使用while和do while循環，直到滿足某個條件。對于任何Object, 我們可以使用?for in?和?for of循環遍歷它的keys 和values。為了同時獲取key和value我們可以使用?entries()。我們也可以在任何時候使用break語句終止循環，或者使用continue語句跳出本次循環進入下一次循環。
原生數組提供了如下迭代方法：indexOf,lastIndexOf,includes,fill,join。 另外我們可以提供一個回調函數在如下方法中：findIndex,find,filter,forEach,map,some,every,reduce。
Recursions
在一篇開創性的論文中，Church-Turing論文證明了任何迭代函數都可以用遞歸函數來復制，反之亦然。有時候，遞歸方法更簡潔、更清晰、更優雅。以這個迭代階乘函數為例:
const factorial = number => {
let product = 1
for (let i = 2; i <= number; i++) {
product *= i
}
return product
}
如果使用遞歸，僅僅需要一行代碼
const _factorial = number => {
return number < 2 ? 1 : number * _factorial(number - 1)
}
所有的遞歸函數都有相同的模式。它們由創建一個調用自身的遞歸部分和一個不調用自身的基本部分組成。任何時候一個函數調用它自身都會創建一個新的執行上下文并推入執行棧頂直。這種情況會一直持續到直到滿足了基本情況為止。然后執行棧會一個接一個的將棧頂元素推出。因此，對遞歸的濫用可能導致堆棧溢出的錯誤。
最后，我們一起來思考一些常見算法題！
1. 字符串反轉
一個函數接受一個字符串作為參數，返回反轉后的字符串
describe("String Reversal", () => {
it("Should reverse string", () => {
assert.equal(reverse("Hello World!"), "!dlroW olleH");
})
})
思考
這道題的關鍵點是我們可以使用數組自帶的reverse方法。首先我們使用?split方法將字符串轉為數組，然后使用reverse反轉字符串，最后使用join方法轉為字符串。另外也可以使用數組的reduce方法
給定一個字符串，每個字符需要訪問一次。雖然這種情況發生了很多次，但是時間復雜度會正常化為線性。由于沒有單獨的內部數據結構，空間復雜度是恒定的。
const reverse = string => string.split('').reverse().join('')
const _reverse = string => string.split('').reduce((res,char) => char + res)
2. 回文
回文是一個單詞或短語，它的讀法是前后一致的。寫一個函數來檢查。
describe("Palindrome", () => {
it("Should return true", () => {
assert.equal(isPalindrome("Cigar? Toss it in a can. It is so tragic"), true);
})
it("Should return false", () => {
assert.equal(isPalindrome("sit ad est love"), false);
})
})
思考
函數只需要簡單地判斷輸入的單詞或短語反轉之后是否和原輸入相同，完全可以參考第一題的解決方案。我們可以使用數組的?every?方法檢查第i個字符和第array.length-i個字符是否匹配。但是這個方法會使每個字符檢查2次，這是沒必要的。那么，我們可以使用reduce方法。和第1題一樣，時間復雜度和空間復雜度是相同的。
const isPalindrome = string => {
const validCharacters = "abcdefghijklmnopqrstuvwxyz".split("")
const stringCharacters = string // 過濾掉特殊符號
.toLowerCase()
.split("")
.reduce(
(characters, character) =>
validCharacters.indexOf(character) > -1
? characters.concat(character)
: characters,
[]
);
return stringCharacters.join("") === stringCharacters.reverse().join("")
3. 整數反轉
給定一個整數，反轉數字的順序。
describe("Integer Reversal", () => {
it("Should reverse integer", () => {
assert.equal(reverse(1234), 4321);
assert.equal(reverse(-1200), -21);
})
})
思考
把number類型使用toString方法換成字符串，然后就可以按照字符串反轉的步驟來做。反轉完成之后，使用parseInt方法轉回number類型，然后使用Math.sign加入符號，只需一行代碼便可完成。
由于我們重用了字符串反轉的邏輯，因此該算法在空間和時間上也具有相同的復雜度。
const revserInteger = integer => parseInt(number
.toString()
.split('')
.reverse()
.join('')) * Math.sign(integer)
4. 出現次數最多的字符
給定一個字符串，返回出現次數最多的字符
describe("Max Character", () => {
it("Should return max character", () => {
assert.equal(max("Hello World!"), "l");
})
})
思考
可以創建一個對象，然后遍歷字符串，字符串的每個字符作為對象的key，value是對應該字符出現的次數。然后我們可以遍歷這個對象，找出value最大的key。
雖然我們使用兩個單獨的循環來迭代兩個不同的輸入(字符串和字符映射)，但是時間復雜度仍然是線性的。它可能來自字符串，但最終，字符映射的大小將達到一個極限，因為在任何語言中只有有限數量的字符。空間復雜度是恒定的。
const maxCharacter = (str) => {
const obj = {}
let max = 0
let character = ''
for (let index in str) {
obj[str[index]] = obj[str[index]] + 1 || 1
}
for (let i in obj) {
if (obj[i] > max) {
max = obj[i]
character = i
}
}
return character
}
5.找出string中元音字母出現的個數
給定一個單詞或者短語，統計出元音字母出現的次數
describe("Vowels", () => {
it("Should count vowels", () => {
assert.equal(vowels("hello world"), 3);
})
})
思考
最簡單的解決辦法是利用正則表達式提取所有的元音，然后統計。如果不允許使用正則表達式，我們可以簡單的迭代每個字符并檢查是否屬于元音字母，首先應該把輸入的參數轉為小寫。
這兩種方法都具有線性的時間復雜度和恒定的空間復雜度，因為每個字符都需要檢查，臨時基元可以忽略不計。
const vowels = str => {
const choices = ['a', 'e', 'i', 'o', 'u']
let count = 0
for (let character in str) {
if (choices.includes(str[character])) {
count ++
}
}
return count
}
const vowelsRegs = str => {
const match = str.match(/[aeiou]/gi)
return match ? match.length : 0
}
6.數組分隔
給定數組和大小，將數組項拆分為具有給定大小的數組列表。
describe("Array Chunking", () => {
it("Should implement array chunking", () => {
assert.deepEqual(chunk([1, 2, 3, 4], 2), [[1, 2], [3, 4]]);
assert.deepEqual(chunk([1, 2, 3, 4], 3), [[1, 2, 3], [4]]);
assert.deepEqual(chunk([1, 2, 3, 4], 5), [[1, 2, 3, 4]]);
})
})
一個好的解決方案是使用內置的slice方法。這樣就能生成更干凈的代碼。可通過while循環或for循環來實現，它們按給定大小的步驟遞增。
這些算法都具有線性時間復雜度，因為每個數組項都需要訪問一次。它們還具有線性空間復雜度，因為保留了一個內部的“塊”數組，它與輸入數組成比例地增長。
const chunk = (array, size) => {
const chunks = []
let index = 0
while(index < array.length) {
chunks.push(array.slice(index, index + size))
index += size
}
return chunks
}
7.words反轉
給定一個短語，按照順序反轉每一個單詞
describe("Reverse Words", () => {
it("Should reverse words", () => {
assert.equal(reverseWords("I love JavaScript!"), "I evol !tpircSavaJ");
})
})
思考
可以使用split方法創建單個單詞數組。然后對于每一個單詞，可以復用之前反轉string的邏輯。
因為每一個字符都需要被訪問，而且所需的臨時變量與輸入的短語成比例增長，所以時間復雜度和空間復雜度是線性的。
const reverseWords = string => string
.split(' ')
.map(word => word
.split('')
.reverse()
.join('')
).join(' ')
8.首字母大寫
給定一個短語，每個首字母變為大寫。
describe("Capitalization", () => {
it("Should capitalize phrase", () => {
assert.equal(capitalize("hello world"), "Hello World");
})
})
思考
一種簡潔的方法是將輸入字符串拆分為單詞數組。然后，我們可以循環遍歷這個數組并將第一個字符大寫，然后再將這些單詞重新連接在一起。出于不變的相同原因，我們需要在內存中保存一個包含適當大寫字母的臨時數組。
因為每一個字符都需要被訪問，而且所需的臨時變量與輸入的短語成比例增長，所以時間復雜度和空間復雜度是線性的。
const capitalize = str => {
return str.split(' ').map(word => word[0].toUpperCase() + word.slice(1)).join(' ')
}
9.凱撒密碼
給定一個短語，通過在字母表中上下移動一個給定的整數來替換每個字符。如果有必要，這種轉換應該回到字母表的開頭或結尾。
describe("Caesar Cipher", () => {
it("Should shift to the right", () => {
assert.equal(caesarCipher("I love JavaScript!", 100), "E hkra FwrwOynelp!")
})
it("Should shift to the left", () => {
assert.equal(caesarCipher("I love JavaScript!", -100), "M pszi NezeWgvmtx!");
})
})
思考
首先我們需要一個包含所有字母的數組，這意味著我們需要把給定的字符串轉為小寫，然后遍歷整個字符串，給每個字符增加或減少給定的整數位置，最后判斷大小寫即可。
由于需要訪問輸入字符串中的每個字符，并且需要從中創建一個新的字符串，因此該算法具有線性的時間和空間復雜度。
const caesarCipher = (str, number) => {
const alphabet = "abcdefghijklmnopqrstuvwxyz".split("")
const string = str.toLowerCase()
const remainder = number % 26
let outPut = ''
for (let i = 0; i < string.length; i++) {
const letter = string[i]
if (!alphabet.includes(letter)) {
outPut += letter
} else {
let index = alphabet.indexOf(letter) + remainder
if (index > 25) {
index -= 26
}
if (index < 0) {
index += 26
}
outPut += str[i] === str[i].toUpperCase() ? alphabet[index].toUpperCase() : alphabet[index]
}
}
return outPut
}
10.找出從0開始到給定整數的所有質數
describe("Sieve of Eratosthenes", () => {
it("Should return all prime numbers", () => {
assert.deepEqual(primes(10), [2, 3, 5, 7])
})
})
思考
最簡單的方法是我們循環從0開始到給定整數的每個整數，并創建一個方法檢查它是否是質數。
const isPrime = n => {
if (n > 1 && n <= 3) {
return true
} else {
for(let i = 2;i <= Math.sqrt(n);i++){
if (n % i == 0) {
return false
}
}
return true
}
}
const prime = number => {
const primes = []
for (let i = 2; i < number; i++) {
if (isPrime(i)) {
primes.push(i)
}
}
return primes
}
自己動手實現一個高效的斐波那契隊列(歡迎評論區留下代碼)
describe("Fibonacci", () => {
it("Should implement fibonacci", () => {
assert.equal(fibonacci(1), 1);
assert.equal(fibonacci(2), 1);
assert.equal(fibonacci(3), 2);
assert.equal(fibonacci(6), 8);
assert.equal(fibonacci(10), 55);
})
})最后
看完點個贊，分享一下吧，讓更多的朋友能夠看到。如果你喜歡前端開發博客的分享，就給公號標個星吧，這樣就不會錯過我的文章了。
)
)
)