素數(shù)

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

Q：你能做得更好嗎？

A：可以。除數(shù)一次增加1個。在3之后我可以增加2.如果一個數(shù)可以被任何偶數(shù)整除，它將被2整除。

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

第一步，任何數(shù)字都不能被大于它的一半的數(shù)字整除。例如，13將永遠(yuǎn)不能被7,8,9整除……它甚至可以是偶數(shù)的一半。例如，16將被8整除，但永遠(yuǎn)不會被9,10,11,12 ……
結(jié)論：一個數(shù)字將永遠(yuǎn)不能被一個大于其一半數(shù)值的數(shù)字整除。所以，我們可以少循環(huán)50％。

第二步，現(xiàn)在，如果一個數(shù)字不能被3整除。（如果它可被3整除，那么它就不是質(zhì)數(shù)）。

然后，它不可以被大于其值1/3的任何數(shù)整除。例如，35不能被3整除。因此，它永遠(yuǎn)不會被大于35/3的數(shù)整除，永遠(yuǎn)不能被12, 13, 14整除…如果你取一個像36一樣的偶數(shù)，它將永遠(yuǎn)不能被13, 14, 15整除。

結(jié)論：一個數(shù)字可以被其數(shù)值的三分之一整除。

第三步，例如，你有一個數(shù)字127。127不能被2整除，因此你最多應(yīng)該檢查63.5。其次，127不能被3整除。

因此，您將檢查到127/3大約42。它不能被5整除，除數(shù)應(yīng)該小于127/5大約25，而不是7。那么，我們該在哪里停下來？
結(jié)論：除數(shù)將小于math.sqrt（N）

方法2

如果你不能理解也不用擔(dān)心，別管它。如果那你不是一個研究人員就沒關(guān)系。

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); // = trueisPrime(237); // = false

素數(shù)因子

Q：如何求出一個數(shù)的所有素數(shù)因子？
A：執(zhí)行一個while循環(huán)。開始除以2，如果不能整除，記錄這個除數(shù)，直到完成。

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：運(yùn)行時間復(fù)雜度是多少？你能做得更好嗎？

A：O(n)?？梢詫⒊龜?shù)從3開始，累加2。因為，如果一個數(shù)被任何偶數(shù)整除，它將被2整除。因此，你不需要除以偶數(shù)。此外，你不會有一個大于其價值一半的因素。如果你想讓它變得復(fù)雜，那就用第一題的補(bǔ)充概念吧。

Fibonacci（斐波那契）

Q：如何獲得第n個斐波納契數(shù)字？
A：我創(chuàng)建一個數(shù)組并從迭代開始。

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

方法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：運(yùn)行時間復(fù)雜度是多少？

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：運(yùn)行時間復(fù)雜度是多少？
A：O(2n)；關(guān)于時間復(fù)雜度的細(xì)節(jié)

最大公約數(shù)

Q: 你會如何找到兩個數(shù)字的最大公約數(shù)？

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); // 7greatestCommonDivisor(69, 169); // = 1

算法范式

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

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

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

去重

Q：你將如何從數(shù)組中刪除重復(fù)的成員？
A：執(zhí)行一個循環(huán)，并保存一個對象/關(guān)聯(lián)數(shù)組。如果我第一次找到一個元素，我會設(shè)置它的值為真（這將告訴我元素添加一次）。如果我在對象中找到這個元素，我不會將它插入到返回數(shù)組中。

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]

合并兩個排序的數(shù)組

Q：怎樣合并兩個已排序數(shù)組？
A：我將為每個數(shù)組保留一個指針（看代碼，并注意這個）。

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]

不通過臨時變量交換兩個數(shù)的值

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

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理解它。將浪費(fèi)您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中反轉(zhuǎn)字符串？
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：你知道在現(xiàn)代瀏覽器中串聯(lián)效果很好，但在像IE8這樣的舊瀏覽器中會變慢。還有什么不同的方法，可以扭轉(zhuǎn)一個字符串？

A：當(dāng)然.我可以使用數(shù)組，也可以添加一些檢查。如果字符串是NULL或其他字符串，這將失敗。讓我也做一些類型檢查。使用此數(shù)組類似于在某些服務(wù)器端語言中使用字符串緩沖區(qū)。

方法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：運(yùn)行時間復(fù)雜度是多少？
A：O(n)；
Q：可以做得更好？
A：我可以遍歷索引的一半，它會節(jié)省一點點。（這是沒用的，可能不會打動面試官）

方法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：你可以在方法中使用任何構(gòu)建，使它更清潔嗎？

 JavaScript

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

方法6

Q：你可以做反向函數(shù)作為字符串?dāng)U展嗎？
A：我需要將這個函數(shù)添加到String.prototype，而不是使用str作為參數(shù)，我需要使用this

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

單詞反轉(zhuǎn)

Q：你如何在句子中顛倒單詞？
A：您必須檢查整個字符串的空白區(qū)域。確定是否可能有多個空格。

//have a tailing white space//fix this later//now i m sleepyfunction 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(' ');}

內(nèi)置方法的快速解決方案：

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

原位反轉(zhuǎn)

Q: 如果你有一個字符串如”I am the good boy”， 怎樣變?yōu)?“I ma eht doog yob”？注意這些單詞位置不變但是被反轉(zhuǎn)了。

A: 要做到這一點，我必須做字符串反向和字反轉(zhuǎn)。

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

Q: ok。好的，你能不使用內(nèi)置反向函數(shù)做到嗎？
A: (內(nèi)心獨白)有沒有搞錯?。?/span>

//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

第一個非重復(fù)字符

Q: 怎么在字符串中找到第一個非重復(fù)字符？
A: 有什么條件嗎？
A: 比如是否區(qū)分大小寫？
面試官可能會說No。
A: 是長字符串還是短字符串？
Q: 這些有什么關(guān)系嗎？

A:例如，如果它是一個非常長的字符串，說一百萬個字符，我想檢查是否有26個英文字符正在重復(fù)。我可能會檢查是否所有字符都在每200個字母中重復(fù)（例如），而不是循環(huán)遍歷整個字符串。這將節(jié)省計算時間。
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"

這有一個問題，不能再循環(huán)中及時退出。

刪除重復(fù)的字符

Q: 怎樣刪除字符串中的重復(fù)字符？

A: 這與第一個非重復(fù)字符非常相似。你應(yīng)該問一些類似的問題。它是區(qū)分大小寫的嗎？。

如果面試官說，這是區(qū)分大小寫的，那么你就很輕松了。如果他說不。你可以使用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: 把字符串反轉(zhuǎn)，如果反轉(zhuǎn)前后相等，那么它就是回文。

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')// = trueisPalindrome('toyota')// = false

或者

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

類似的：在 O(n)時間復(fù)雜度內(nèi)判斷一個字符串是否包含在回文字符串內(nèi)。你能在O（1）時間解決問題嗎？

找缺失的數(shù)字

Q: 在一個1到100的未排序數(shù)組中找到缺失的數(shù)，你怎么做？

說明：數(shù)組中的數(shù)字為1到100。數(shù)組中只有一個數(shù)字缺失。數(shù)組未排序。找到缺少的數(shù)字。

A: 你必須表現(xiàn)得像是在想很多。然后討論n＝n（n＋1）／2的線性級數(shù)之和

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

注意：這個會返回任意長度數(shù)組中缺失的那個

兩數(shù)之和

Q: 在一個未排序的數(shù)組中找出是否有任意兩數(shù)之和等于給定的數(shù)？
A: 簡單！雙重循環(huán)。

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);// = truesumFinder([6,4,3,2,1,7], 2);// = false

Q: 時間復(fù)雜度？
A: O(n2)。
Q: 有更優(yōu)解？
A: 我想想。我可以用一個對象來存儲當(dāng)前元素和和值的差值。當(dāng)我拿到一個新元素，如果這個元素的差值在對象中存在，那么我就能判斷出是否存在。

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);// = truesumFinder([6,4,3,2,1,7], 2);// = false

最大和

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

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

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

統(tǒng)計零

Q: 統(tǒng)計從1到n的零總數(shù)？

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

說明：所以這里的重點是。如果你有一個1到50的數(shù)字，那么這個數(shù)值就是5，就是50除以10.然而，如果這個數(shù)值是100，這個數(shù)值是11，你將得到100/10 = 10和 10/10 = 1。

那就是你將如何在一個數(shù)字中得到更多的零，如（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')// = 0subStringFinder('abbcdabbbbbck', 'bck')// = 9//doesn't work for this one.subStringFinder('abbcdabbbbbck', 'bbbck') // = -1

排列

Q: 如何獲取字符串中的所有排列？

A: 根據(jù)您對算法的了解程度，這可能會很困難。

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

學(xué)習(xí)更多技能

請點擊下方公眾號