摘要：中的算法附道面試常見算法題解決方法和思路關(guān)注每日一道面試題詳解面試過程通常從最初的電話面試開始，然后是現(xiàn)場(chǎng)面試，檢查編程技能和文化契合度。值得記住的數(shù)組方法有和。一個(gè)好的解決方案是使用內(nèi)置的方法。

關(guān)注github每日一道面試題詳解

面試過程通常從最初的電話面試開始，然后是現(xiàn)場(chǎng)面試，檢查編程技能和文化契合度。幾乎毫無例外，最終的決定因素是還是編碼能力。通常上，不僅僅要求能得到正確的答案，更重要的是要有清晰的思維過程。寫代碼中就像在生活中一樣，正確的答案并不總是清晰的，但是好的推理通常就足夠了。有效推理的能力預(yù)示著學(xué)習(xí)、適應(yīng)和進(jìn)化的潛力。好的工程師一直是在成長的，好的公司總是在創(chuàng)新的。

算法挑戰(zhàn)是有用的，因?yàn)榻鉀Q它們的方法不止一種。這為決策的制定和決策的計(jì)算提供了可能性。在解決算法問題時(shí)，我們應(yīng)該挑戰(zhàn)自己從多個(gè)角度來看待問題的定義，然后權(quán)衡各種方法的優(yōu)缺點(diǎn)。通過足夠的嘗試后，我們甚至可能看到一個(gè)普遍的真理:不存在“完美”的解決方案。

要真正掌握算法，就必須了解它們與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。數(shù)據(jù)結(jié)構(gòu)和算法就像陰陽、水杯和水一樣密不可分。沒有杯子，水就不能被容納。沒有數(shù)據(jù)結(jié)構(gòu)，我們就沒有對(duì)象來應(yīng)用邏輯。沒有水，杯子是空的，沒有營養(yǎng)。沒有算法，對(duì)象就不能被轉(zhuǎn)換或“消費(fèi)”。

要了解和分析JavaScript中的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)看JavaScript中的數(shù)據(jù)結(jié)構(gòu)

在JavaScript中，算法只是一個(gè)函數(shù)，它將某個(gè)確定的數(shù)據(jù)結(jié)構(gòu)輸入轉(zhuǎn)換為某個(gè)確定的數(shù)據(jù)結(jié)構(gòu)輸出。函數(shù)內(nèi)部的邏輯決定了怎么轉(zhuǎn)換。首先，輸入和輸出應(yīng)該清楚地提前定義。這需要我們充分理解手上的問題，因?yàn)閷?duì)問題的全面分析可以很自然地提出解決方案，而不需要編寫任何代碼。

一旦完全理解了問題，就可以開始對(duì)解決方案進(jìn)行思考，需要那些變量？ 有幾種循環(huán)？ 有那些JavaScript內(nèi)置方法可以提供幫助？需要考慮那些邊緣情況？復(fù)雜或者重復(fù)的邏輯會(huì)導(dǎo)致代碼十分的難以閱讀和理解，可以考慮能否提出抽象成多個(gè)函數(shù)？一個(gè)算法通常上需要可擴(kuò)展的。隨著輸入size的增加，函數(shù)將如何執(zhí)行? 是否應(yīng)該有某種緩存機(jī)制嗎? 通常上，需要犧牲內(nèi)存優(yōu)化(空間)來換取性能提升(時(shí)間)。

當(dāng)解決方案的具體結(jié)構(gòu)開始出現(xiàn)時(shí)，偽代碼就可以開始了。為了給面試官留下深刻印象，請(qǐng)?zhí)崆皩ふ抑貥?gòu)和重用代碼的機(jī)會(huì)。有時(shí)，行為相似的函數(shù)可以組合成一個(gè)更通用的函數(shù)，該函數(shù)接受一個(gè)額外的參數(shù)。其他時(shí)候，函數(shù)柯里的效果更好。保證函數(shù)功能的純粹方便測(cè)試和維護(hù)也是非常重要的。換句話說，在做出解決問題的決策時(shí)需要考慮到架構(gòu)和設(shè)計(jì)模式。

為了計(jì)算出算法運(yùn)行時(shí)的復(fù)雜性，我們需要將算法的輸入大小外推到無窮大，從而近似得出算法的復(fù)雜度。最優(yōu)算法有一個(gè)恒定的時(shí)間復(fù)雜度和空間復(fù)雜度。這意味著它不關(guān)心輸入的數(shù)量增長多少，其次是對(duì)數(shù)時(shí)間復(fù)雜度或空間復(fù)雜度，然后是線性、二次和指數(shù)。最糟糕的是階乘時(shí)間復(fù)雜度或空間復(fù)雜度。算法復(fù)雜度可用以下符號(hà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!)

在設(shè)計(jì)算法的結(jié)構(gòu)和邏輯時(shí)，時(shí)間復(fù)雜度和空間復(fù)雜度的優(yōu)化和權(quán)衡是一個(gè)重要的步驟。

一個(gè)最優(yōu)的算法通常上會(huì)利用語言里固有的標(biāo)準(zhǔn)對(duì)象實(shí)現(xiàn)。可以說，在計(jì)算機(jī)科學(xué)中最重要的是數(shù)組。在JavaScript中，沒有其他對(duì)象比數(shù)組擁有更多的實(shí)用方法。值得記住的數(shù)組方法有:sort、reverse、slice和splice。數(shù)組元素從第0個(gè)索引開始插入，所以最后一個(gè)元素的索引是 array.length-1。數(shù)組在push元素有很好的性能，但是在數(shù)組中間插入，刪除和查找元素上性能卻不是很優(yōu)，JavaScript中的數(shù)組的大小是可以動(dòng)態(tài)增長的。

Push: O(1)

Insert: O(n)

Delet: O(n)

Searching: O(n)

Optimized Searching: O(log n)

Map 和 Set是和數(shù)組相似的數(shù)據(jù)結(jié)構(gòu)。set中的元素都是不重復(fù)的，在map中，每個(gè)Item由鍵和值組成。當(dāng)然，對(duì)象也可以用來存儲(chǔ)鍵值對(duì)，但是鍵必須是字符串。

與數(shù)組密切相關(guān)的是使用循環(huán)遍歷它們。在JavaScript中,有5種最常用的遍歷方法，使用最多的是for循環(huán)，for循環(huán)可以用任何順序遍歷數(shù)組的索引。如果無法確定迭代的次數(shù)，我們可以使用while和do while循環(huán)，直到滿足某個(gè)條件。對(duì)于任何Object, 我們可以使用 for in 和 for of循環(huán)遍歷它的keys 和values。為了同時(shí)獲取key和value我們可以使用 entries()。我們也可以在任何時(shí)候使用break語句終止循環(huán)，或者使用continue語句跳出本次循環(huán)進(jìn)入下一次循環(huán)。

原生數(shù)組提供了如下迭代方法：indexOf,lastIndexOf,includes,fill,join。 另外我們可以提供一個(gè)回調(diào)函數(shù)在如下方法中：findIndex,find,filter,forEach,map,some,every,reduce。

在一篇開創(chuàng)性的論文中，Church-Turing論文證明了任何迭代函數(shù)都可以用遞歸函數(shù)來復(fù)制，反之亦然。有時(shí)候，遞歸方法更簡(jiǎn)潔、更清晰、更優(yōu)雅。以這個(gè)迭代階乘函數(shù)為例:

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)
}

所有的遞歸函數(shù)都有相同的模式。它們由創(chuàng)建一個(gè)調(diào)用自身的遞歸部分和一個(gè)不調(diào)用自身的基本部分組成。任何時(shí)候一個(gè)函數(shù)調(diào)用它自身都會(huì)創(chuàng)建一個(gè)新的執(zhí)行上下文并推入執(zhí)行棧頂直。這種情況會(huì)一直持續(xù)到直到滿足了基本情況為止。然后執(zhí)行棧會(huì)一個(gè)接一個(gè)的將棧頂元素推出。因此，對(duì)遞歸的濫用可能導(dǎo)致堆棧溢出的錯(cuò)誤。

一個(gè)函數(shù)接受一個(gè)字符串作為參數(shù)，返回反轉(zhuǎn)后的字符串

describe("String Reversal", () => {
 it("Should reverse string", () => {
  assert.equal(reverse("Hello World!"), "!dlroW olleH");
 })
})

思考

這道題的關(guān)鍵點(diǎn)是我們可以使用數(shù)組自帶的reverse方法。首先我們使用 split方法將字符串轉(zhuǎn)為數(shù)組，然后使用reverse反轉(zhuǎn)字符串，最后使用join方法轉(zhuǎn)為字符串。另外也可以使用數(shù)組的reduce方法

給定一個(gè)字符串，每個(gè)字符需要訪問一次。雖然這種情況發(fā)生了很多次，但是時(shí)間復(fù)雜度會(huì)正常化為線性。由于沒有多帶帶的內(nèi)部數(shù)據(jù)結(jié)構(gòu)，空間復(fù)雜度是恒定的。

const reverse = string => string.split("").reverse().join("")

const _reverse = string => string.split("").reduce((res,char) => char + res)

回文是一個(gè)單詞或短語，它的讀法是前后一致的。寫一個(gè)函數(shù)來檢查。

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

思考

函數(shù)只需要簡(jiǎn)單地判斷輸入的單詞或短語反轉(zhuǎn)之后是否和原輸入相同，完全可以參考第一題的解決方案。我們可以使用數(shù)組的 every 方法檢查第i個(gè)字符和第array.length-i個(gè)字符是否匹配。但是這個(gè)方法會(huì)使每個(gè)字符檢查2次，這是沒必要的。那么，我們可以使用reduce方法。和第1題一樣，時(shí)間復(fù)雜度和空間復(fù)雜度是相同的。

const isPalindrome = string => {
  const validCharacters = "abcdefghijklmnopqrstuvwxyz".split("")
  const stringCharacters = string // 過濾掉特殊符號(hào)
      .toLowerCase()
      .split("")
      .reduce(
        (characters, character) =>
          validCharacters.indexOf(character) > -1
            ? characters.concat(character)
            : characters,
        []
      );
  return stringCharacters.join("") === stringCharacters.reverse().join("")

給定一個(gè)整數(shù)，反轉(zhuǎn)數(shù)字的順序。

describe("Integer Reversal", () => {
 it("Should reverse integer", () => {
  assert.equal(reverse(1234), 4321);
  assert.equal(reverse(-1200), -21);
 })
})

思考

把number類型使用toString方法換成字符串，然后就可以按照字符串反轉(zhuǎn)的步驟來做。反轉(zhuǎn)完成之后，使用parseInt方法轉(zhuǎn)回number類型，然后使用Math.sign加入符號(hào)，只需一行代碼便可完成。

由于我們重用了字符串反轉(zhuǎn)的邏輯，因此該算法在空間和時(shí)間上也具有相同的復(fù)雜度。

const revserInteger = integer => parseInt(number
      .toString()
      .split("")
      .reverse()
      .join("")) * Math.sign(integer)

給定一個(gè)字符串，返回出現(xiàn)次數(shù)最多的字符

describe("Max Character", () => {
 it("Should return max character", () => {
  assert.equal(max("Hello World!"), "l");
 })
})

思考

可以創(chuàng)建一個(gè)對(duì)象，然后遍歷字符串，字符串的每個(gè)字符作為對(duì)象的key，value是對(duì)應(yīng)該字符出現(xiàn)的次數(shù)。然后我們可以遍歷這個(gè)對(duì)象，找出value最大的key。

雖然我們使用兩個(gè)多帶帶的循環(huán)來迭代兩個(gè)不同的輸入(字符串和字符映射)，但是時(shí)間復(fù)雜度仍然是線性的。它可能來自字符串，但最終，字符映射的大小將達(dá)到一個(gè)極限，因?yàn)樵谌魏握Z言中只有有限數(shù)量的字符。空間復(fù)雜度是恒定的。

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
  }

給定一個(gè)單詞或者短語，統(tǒng)計(jì)出元音字母出現(xiàn)的次數(shù)

describe("Vowels", () => {
 it("Should count vowels", () => {
  assert.equal(vowels("hello world"), 3);
 })
})

思考

最簡(jiǎn)單的解決辦法是利用正則表達(dá)式提取所有的元音，然后統(tǒng)計(jì)。如果不允許使用正則表達(dá)式，我們可以簡(jiǎn)單的迭代每個(gè)字符并檢查是否屬于元音字母，首先應(yīng)該把輸入的參數(shù)轉(zhuǎn)為小寫。

這兩種方法都具有線性的時(shí)間復(fù)雜度和恒定的空間復(fù)雜度，因?yàn)槊總€(gè)字符都需要檢查，臨時(shí)基元可以忽略不計(jì)。

  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
  }

給定數(shù)組和大小，將數(shù)組項(xiàng)拆分為具有給定大小的數(shù)組列表。

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

一個(gè)好的解決方案是使用內(nèi)置的slice方法。這樣就能生成更干凈的代碼。可通過while循環(huán)或for循環(huán)來實(shí)現(xiàn)，它們按給定大小的步驟遞增。

這些算法都具有線性時(shí)間復(fù)雜度，因?yàn)槊總€(gè)數(shù)組項(xiàng)都需要訪問一次。它們還具有線性空間復(fù)雜度，因?yàn)楸Ａ袅艘粋€(gè)內(nèi)部的“塊”數(shù)組，它與輸入數(shù)組成比例地增長。

const chunk = (array, size) => {
  const chunks = []
  let index = 0
   while(index < array.length) {
     chunks.push(array.slice(index, index + size))
     index += size
   }
   return chunks
}

給定一個(gè)短語，按照順序反轉(zhuǎn)每一個(gè)單詞

describe("Reverse Words", () => {
 it("Should reverse words", () => {
  assert.equal(reverseWords("I love JavaScript!"), "I evol !tpircSavaJ");
 })
})

思考

可以使用split方法創(chuàng)建單個(gè)單詞數(shù)組。然后對(duì)于每一個(gè)單詞，可以復(fù)用之前反轉(zhuǎn)string的邏輯。

因?yàn)槊恳粋€(gè)字符都需要被訪問，而且所需的臨時(shí)變量與輸入的短語成比例增長，所以時(shí)間復(fù)雜度和空間復(fù)雜度是線性的。

const reverseWords = string => string
                                  .split(" ")
                                  .map(word => word
                                                .split("")
                                                .reverse()
                                                .join("")
                                      ).join(" ")

給定一個(gè)短語，每個(gè)首字母變?yōu)榇髮憽?/p>

describe("Capitalization", () => {
 it("Should capitalize phrase", () => {
  assert.equal(capitalize("hello world"), "Hello World");
 })
})

思考

一種簡(jiǎn)潔的方法是將輸入字符串拆分為單詞數(shù)組。然后，我們可以循環(huán)遍歷這個(gè)數(shù)組并將第一個(gè)字符大寫，然后再將這些單詞重新連接在一起。出于不變的相同原因，我們需要在內(nèi)存中保存一個(gè)包含適當(dāng)大寫字母的臨時(shí)數(shù)組。

因?yàn)槊恳粋€(gè)字符都需要被訪問，而且所需的臨時(shí)變量與輸入的短語成比例增長，所以時(shí)間復(fù)雜度和空間復(fù)雜度是線性的。

const capitalize = str => {
  return str.split(" ").map(word => word[0].toUpperCase() + word.slice(1)).join(" ")
}

給定一個(gè)短語，通過在字母表中上下移動(dòng)一個(gè)給定的整數(shù)來替換每個(gè)字符。如果有必要，這種轉(zhuǎn)換應(yīng)該回到字母表的開頭或結(jié)尾。

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!");
 })
})

思考

首先我們需要一個(gè)包含所有字母的數(shù)組，這意味著我們需要把給定的字符串轉(zhuǎn)為小寫，然后遍歷整個(gè)字符串，給每個(gè)字符增加或減少給定的整數(shù)位置，最后判斷大小寫即可。

由于需要訪問輸入字符串中的每個(gè)字符，并且需要從中創(chuàng)建一個(gè)新的字符串，因此該算法具有線性的時(shí)間和空間復(fù)雜度。

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
}

describe("Sieve of Eratosthenes", () => {
 it("Should return all prime numbers", () => {
  assert.deepEqual(primes(10), [2, 3, 5, 7])
 })
})

思考

最簡(jiǎn)單的方法是我們循環(huán)從0開始到給定整數(shù)的每個(gè)整數(shù)，并創(chuàng)建一個(gè)方法檢查它是否是質(zhì)數(shù)。

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

查看原文

關(guān)注github每日一道面試題詳解