JavaScript面試中容易遇到的算法

素數

Q：你将如何驗證一個素數？

A：一個素數隻能被它自己和1整除。是以，我将運作一個while循環并加1。（看代碼示例，如果你無法了解，那這不是你的菜。先回去學習JavaScript基礎知識然後再回來吧。）

方法1​

function isPrime(n){
 var divisor = 2;
 while (n > divisor){
 if(n % divisor == 0){
  return false; 
 }
 else
  divisor++;
 }
 return true;
}
isPrime(137); // = true
isPrime(237); // = false      

Q：你能做得更好嗎？

A：可以。除數一次增加1個。在3之後我可以增加2.如果一個數可以被任何偶數整除，它将被2整除。

補充：如果你不需要把除數增加到這個數。你可以更早停止。讓我在下面的步驟中解釋一下（如果需要可以多讀幾遍）

第一步，任何數字都不能被大于它的一半的數字整除。例如，13将永遠不能被7,8,9整除……它甚至可以是偶數的一半。例如，16将被8整除，但永遠不會被9,10,11,12 ……

結論：一個數字将永遠不能被一個大于其一半數值的數字整除。是以，我們可以少循環50％。

第二步，現在，如果一個數字不能被3整除。（如果它可被3整除，那麼它就不是質數）。

然後，它不可以被大于其值1/3的任何數整除。例如，35不能被3整除。是以，它永遠不會被大于35/3的數整除，永遠不能被12, 13, 14整除…如果你取一個像36一樣的偶數，它将永遠不能被13, 14, 15整除。

結論：一個數字可以被其數值的三分之一整除。

第三步，例如，你有一個數字127。127不能被2整除，是以你最多應該檢查63.5。其次，127不能被3整除。

是以，您将檢查到127/3大約42。它不能被5整除，除數應該小于127/5大約25，而不是7。那麼，我們該在哪裡停下來？

結論：除數将小于math.sqrt（N）

方法2

如果你不能了解也不用擔心，别管它。如果那你不是一個研究人員就沒關系。

function isPrime(n)
{
 var divisor = 3, 
  limit = Math.sqrt(n);
 //check simple cases
 if (n == 2 || n == 3)
  return true;
 if (n % 2 == 0)
  return false;
 while (divisor <= limit)
 {
 if (n % divisor == 0)
  return false;
 else
  divisor += 2;
 }
 return true;
}
isPrime(137); // = true
isPrime(237); // = false      

素數因子

Q：如何求出一個數的所有素數因子？

A：執行一個while循環。開始除以2，如果不能整除，記錄這個除數，直到完成。​

function primeFactors(n){
 var factors = [], 
  divisor = 2;
 while(n>2){
 if(n % divisor == 0){
  factors.push(divisor); 
  n= n/ divisor;
 }
 else{
  divisor++;
 }  
 }
 return factors;
}
 primeFactors(69); // = [3, 23]      

Q：運作時間複雜度是多少？你能做得更好嗎？

A：O(n)。可以将除數從3開始，累加2。因為，如果一個數被任何偶數整除，它将被2整除。是以，你不需要除以偶數。此外，你不會有一個大于其價值一半的因素。如果你想讓它變得複雜，那就用第一題的補充概念吧。

Fibonacci（斐波那契）

Q：如何獲得第n個斐波納契數字？

A：我建立一個數組并從疊代開始。

斐波那契系列是面向初學者的最受歡迎的面試問題之一。是以，你必須學習這一個。

方法1​

function fibonacci(n){
 var fibo = [0, 1];
 if (n <= 2) return 1;
 for (var i = 2; i <=n; i++ ){
 fibo[i] = fibo[i-1]+fibo[i-2];
 }
 return fibo[n];
} 
fibonacci(12); // = 144      

Q：運作時間複雜度是多少？

A：O(n)；

Q：你能讓它遞歸嗎？

方法2​

function fibonacci(n){
 if(n < =1) {
  return n;
 } else {
  return fibonacci(n-1) + fibonacci (n-2);
 }
}
fibonacci(12); // = 144      

Q：運作時間複雜度是多少？

A：O(2n)；關于時間複雜度的細節

最大公約數

Q: 你會如何找到兩個數字的最大公約數？​

function greatestCommonDivisor(a, b){
 var divisor = 2, 
  greatestDivisor = 1;
 //if u pass a -ve number this will not work. fix it dude!!
 if (a < 2 || b < 2)
  return 1;
 while(a >= divisor && b >= divisor){
 if(a %divisor == 0 && b% divisor ==0){
  greatestDivisor = divisor;  
 }
 divisor++;
 }
 return greatestDivisor;
}
greatestCommonDivisor(14, 21); // 7
greatestCommonDivisor(69, 169); // = 1      

算法範式

很抱歉。我也無法解釋它。因為我自己80％的情況下都不能了解它。我的算法分析教練告訴我這個，又從課堂筆記偷走（我是一個好學生，順便說一句！）​

function greatestCommonDivisor(a, b){
 if(b == 0)
  return a;
 else 
  return greatestCommonDivisor(b, a%b);
}      

注意：用你的大腦來了解它。

去重

Q：你将如何從數組中删除重複的成員？

A：執行一個循環，并儲存一個對象/關聯數組。如果我第一次找到一個元素，我會設定它的值為真（這将告訴我元素添加一次）。如果我在對象中找到這個元素，我不會将它插入到傳回數組中。​

function removeDuplicate(arr){
 var exists ={},
  outArr = [], 
  elm;
 for(var i =0; i<arr.length; i++){
 elm = arr[i];
 if(!exists[elm]){
  outArr.push(elm);
  exists[elm] = true;
 }
 }
 return outArr;
}
removeDuplicate([1,3,3,3,1,5,6,7,8,1]); // = [1, 3, 5, 6, 7, 8]      

合并兩個排序的數組

Q：怎樣合并兩個已排序數組？

A：我将為每個數組保留一個指針（看代碼，并注意這個）。

function mergeSortedArray(a, b){
 var merged = [], 
   aElm = a[0],
   bElm = b[0],
   i = 1,
   j = 1;
 if(a.length ==0)
  return b;
 if(b.length ==0)
  return a;
 /* 
 if aElm or bElm exists we will insert to merged array
 (will go inside while loop)
  to insert: aElm exists and bElm doesn't exists
       or both exists and aElm < bElm
  this is the critical part of the example      
 */
 while(aElm || bElm){
  if((aElm && !bElm) || aElm < bElm){
   merged.push(aElm);
   aElm = a[i++];
  }  
  else {
   merged.push(bElm);
   bElm = b[j++];
  }
 }
 return merged;
}
mergeSortedArray([2,5,6,9], [1,2,3,29]);// = [1, 2, 2, 3, 5, 6, 9, 29]      

不通過臨時變量交換兩個數的值

Q：如何在不使用臨時變量的情況下交換兩個數字？​

function swapNumb(a, b){
 console.log('before swap: ','a: ', a, 'b: ', b);
 b = b -a;
 a = a+ b;
 b = a-b;
 console.log('after swap: ','a: ', a, 'b: ', b); 
}
swapNumb(2, 3);
//  = before swap: a: 2 b: 3
//  = after swap: a: 3 b: 2      

位操作：對不起，我無法向你解釋這一點。Kinjal Dave建議到 logical conjunction了解它。将浪費您30分鐘。

function swapNumb(a, b){
 console.log("a: " + a + " and b: " + b);
 a = a ^ b;
 b = a ^ b;
 a = a ^ b;
 console.log("a: " + a + " and b: " + b);
}
swapNumb(2, 3);
// = a: 2 and b: 3
// = a: 3 and b: 2      

字元串反向

Q：如何在JavaScript中反轉字元串？

A：可以周遊字元串并将字母連接配接到新字元串。

方法1​

function reverse(str){
 var rtnStr = '';
 for(var i = str.length-1; i>=0;i--){
  rtnStr +=str[i];
 }
 return rtnStr;
}
reverse('you are a nice dude');
// = "edud ecin a era uoy"      

Q：你知道在現代浏覽器中串聯效果很好，但在像IE8這樣的舊浏覽器中會變慢。還有什麼不同的方法，可以扭轉一個字元串？

A：當然.我可以使用數組，也可以添加一些檢查。如果字元串是NULL或其他字元串，這将失敗。讓我也做一些類型檢查。使用此數組類似于在某些伺服器端語言中使用字元串緩沖區。

方法2

function reverse(str){
 var rtnStr = [];
 if(!str || typeof str != 'string' || str.length < 2 ) return str;
 for(var i = str.length-1; i>=0;i--){
  rtnStr.push(str[i]);
 }
 return rtnStr.join('');
}      

Q：運作時間複雜度是多少？

A：O(n)；

Q：可以做得更好？

A：我可以周遊索引的一半，它會節省一點點。（這是沒用的，可能不會打動面試官）

方法3​

function reverse(str) {
 str = str.split('');
 var len = str.length,
   halfIndex = Math.floor(len / 2) - 1,
   revStr;
 for (var i = 0; i <= halfIndex; i++) {
  revStr = str[len - i - 1];
  str[len - i - 1] = str[i];
  str[i] = revStr;
 }
 return str.join('');
}      

Q：這有效，但你可以做遞歸的方式嗎？

A：可以。

方法4​

function reverse (str) {
  if (str === "") {
    return "";
  } else {
    return reverse(str.substr(1)) + str.charAt(0);
  }
}      

方法5

Q：你可以在方法中使用任何建構，使它更清潔嗎？

 JavaScript

function reverse(str){
 if(!str || str.length <2) return str;
 return str.split('').reverse().join('');
}      

方法6

Q：你可以做反向函數作為字元串擴充嗎？

A：我需要将這個函數添加到String.prototype，而不是使用str作為參數，我需要使用this

String.prototype.reverse = function (){
 if(!this || this.length <2) return this;
 return this.split('').reverse().join('');
}
'abc'.reverse();
// = 'cba'      

單詞反轉

Q：你如何在句子中颠倒單詞？

A：您必須檢查整個字元串的空白區域。确定是否可能有多個空格。​

//have a tailing white space
//fix this later
//now i m sleepy
function reverseWords(str){
 var rev = [], 
   wordLen = 0;
 for(var i = str.length-1; i>=0; i--){
  if(str[i]==' ' || i==0){
   rev.push(str.substr(i,wordLen+1));
   wordLen = 0;
  }
  else
   wordLen++;
 }
 return rev.join(' ');
}      

内置方法的快速解決方案：​

function reverseWords(str){
 return str.split(' ').reverse();
}      

原位反轉

Q: 如果你有一個字元串如”I am the good boy”， 怎樣變為 “I ma eht doog yob”？注意這些單詞位置不變但是被反轉了。

A: 要做到這一點，我必須做字元串反向和字反轉。

function reverseInPlace(str){
 return str.split(' ').reverse().join(' ').split('').reverse().join('');
}
reverseInPlace('I am the good boy');// = "I ma eht doog yob"      

Q: ok。好的，你能不使用内置反向函數做到嗎？

A: (内心獨白)有沒有搞錯！！​

//sum two methods.
//you can simply split words by ' '
//and for each words, call reverse function
//put reverse in a separate function
//if u cant do this, 
//have a glass of water, and sleep      

第一個非重複字元

Q: 怎麼在字元串中找到第一個非重複字元？

A: 有什麼條件嗎？

A: 比如是否區分大小寫？

面試官可能會說No。

A: 是長字元串還是短字元串？

Q: 這些有什麼關系嗎？

A:例如，如果它是一個非常長的字元串，說一百萬個字元，我想檢查是否有26個英文字元正在重複。我可能會檢查是否所有字元都在每200個字母中重複（例如），而不是循環周遊整個字元串。這将節省計算時間。

Q: 簡單起見， 這個字元串是 “the quick brown fox jumps then quickly blow air”。​

function firstNonRepeatChar(str){
 var len = str.length,
   char, 
   charCount = {};
 for(var i =0; i<len; i++){
  char = str[i];
  if(charCount[char]){
   charCount[char]++;
  }
  else
   charCount[char] = 1;
 }
 for (var j in charCount){
  if (charCount[j]==1)
    return j;
 }
} 
firstNonRepeatChar('the quick brown fox jumps then quickly blow air');// = "f"      

這有一個問題，不能再循環中及時退出。

删除重複的字元

Q: 怎樣删除字元串中的重複字元？

A: 這與第一個非重複字元非常相似。你應該問一些類似的問題。它是區分大小寫的嗎？。

如果面試官說，這是區分大小寫的，那麼你就很輕松了。如果他說不。你可以使用string.toLowercase（）來把字元串。面試官可能不喜歡這個方法。因為傳回字元串不會擁有相同的大小寫。是以​

function removeDuplicateChar(str){
 var len = str.length,
   char, 
   charCount = {}, 
   newStr = [];
 for(var i =0; i<len; i++){
  char = str[i];
  if(charCount[char]){
   charCount[char]++;
  }
  else
   charCount[char] = 1;
 }
 for (var j in charCount){
  if (charCount[j]==1)
    newStr.push(j);
 }
 return newStr.join('');
}
removeDuplicateChar('Learn more javascript dude'); // = "Lnmojvsciptu"      

回文檢查

Q: 如何檢查一個字元串是否是回文？

A: 把字元串反轉，如果反轉前後相等，那麼它就是回文。​

function isPalindrome(str){
 var i, len = str.length;
 for(i =0; i<len/2; i++){
  if (str[i]!== str[len -1 -i])
    return false;
 }
 return true;
}
isPalindrome('madam')
// = true
isPalindrome('toyota')
// = false      

或者​

function checkPalindrom(str) {
  return str == str.split('').reverse().join('');
}      

類似的：在 O(n)時間複雜度内判斷一個字元串是否包含在回文字元串内。你能在O（1）時間解決問題嗎？

找缺失的數字

Q: 在一個1到100的未排序數組中找到缺失的數，你怎麼做？

說明：數組中的數字為1到100。數組中隻有一個數字缺失。數組未排序。找到缺少的數字。

A: 你必須表現得像是在想很多。然後讨論n＝n（n＋1）／2的線性級數之和

function missingNumber(arr){
 var n = arr.length+1, 
   sum = 0,
   expectedSum = n * (n+1)/2;
 for(var i = 0, len = arr.length; i < len; i++){
  sum += arr[i];
 }
 return expectedSum - sum;
}
missingNumber([5, 2, 6, 1, 3]);
// = 4      

注意：這個會傳回任意長度數組中缺失的那個

兩數之和

Q: 在一個未排序的數組中找出是否有任意兩數之和等于給定的數？

A: 簡單！雙重循環。

function sumFinder(arr, sum){
 var len = arr.length;
 for(var i =0; i<len-1; i++){ 
   for(var j = i+1;j<len; j++){
    if (arr[i] + arr[j] == sum)
      return true;
   }
 }
 return false;
}
sumFinder([6,4,3,2,1,7], 9);
// = true
sumFinder([6,4,3,2,1,7], 2);
// = false      

Q: 時間複雜度？

A: O(n2)。

Q: 有更優解？

A: 我想想。我可以用一個對象來存儲目前元素和和值的內插補點。當我拿到一個新元素，如果這個元素的內插補點在對象中存在，那麼我就能判斷出是否存在。​

function sumFinder(arr, sum){
 var differ = {}, 
   len = arr.length,
   substract;
 for(var i =0; i<len; i++){
   substract = sum - arr[i];
   if(differ[substract])
    return true;    
   else
    differ[arr[i]] = true;
 }
 return false;
}
sumFinder([6,4,3,2,1,7], 9);
// = true
sumFinder([6,4,3,2,1,7], 2);
// = false      

最大和

Q: 找到任意兩個元素的最大總和？

A: 這實際上非常簡單直接。找到兩個最大的數字并傳回它們的總和

function topSum(arr){
 var biggest = arr[0], 
   second = arr[1], 
   len = arr.length, 
   i = 2;
 if (len<2) return null;
 if (biggest<second){
  biggest = arr[1];
  second = arr[0];
 } 
 for(; i<len; i++){
  if(arr[i] > biggest){
   second = biggest;
   biggest = arr[i];
  }
  else if (arr[i]>second){
   second = arr[i];
  }
 }
 return biggest + second;
}      

統計零

Q: 統計從1到n的零總數？

A: 如果 n = 100，則0的數目将是11（0,10,20,30,40,50,60,70,80,90,100）。請注意，100有兩個0.這個看起來很簡單，但有點棘手

說明：是以這裡的重點是。如果你有一個1到50的數字，那麼這個數值就是5，就是50除以10.然而，如果這個數值是100，這個數值是11，你将得到100/10 = 10和 10/10 = 1。

那就是你将如何在一個數字中得到更多的零，如（100，200，1000）；

function countZero(n){
 var count = 0;
 while(n>0){
  count += Math.floor(n/10);
  n = n/10;
 }
 return count;
}
countZero(2014);
// = 223      

子字元串

Q: 在字元串中比對子字元串？

A: 在疊代字元串時将使用指針（一個用于字元串，另一個用于子字元串）。然後用另一個變量來儲存初始比對的起始索引。​

function subStringFinder(str, subStr){
 var idx = 0,
   i = 0,
   j = 0,
   len = str.length,
   subLen = subStr.length;
  for(; i<len; i++){
   if(str[i] == subStr[j])
     j++;
   else
     j = 0;
   //check starting point or a match  
   if(j == 0)
    idx = i;
   else if (j == subLen)
    return idx;
 }
 return -1;
}
subStringFinder('abbcdabbbbbck', 'ab')
// = 0
subStringFinder('abbcdabbbbbck', 'bck')
// = 9
//doesn't work for this one.
subStringFinder('abbcdabbbbbck', 'bbbck') 
// = -1      

排列

Q: 如何擷取字元串中的所有排列？

function permutations(str){
  var arr = str.split(''),
    len = arr.length, 
    perms = [],
    rest,
    picked,
    restPerms,
    next;
  if (len == 0)
    return [str];
  for (var i=0; i<len; i++)
  {
    rest = Object.create(arr);
    picked = rest.splice(i, 1);
    restPerms = permutations(rest.join(''));
    for (var j=0, jLen = restPerms.length; j< jLen; j++)
    {
      next = picked.concat(restPerms[j]);
      perms.push(next.join(''));
    }
  }
  return perms;
}