您好,登錄后才能下訂單哦!
素數(shù)
Q:你將如何驗證一個素數(shù)?
A:一個素數(shù)只能被它自己和1整除。所以,我將運行一個while循環(huán)并加1。(看代碼示例,如果你無法理解,那這不是你的菜。先回去學習javaScript基礎(chǔ)知識然后再回來吧。)
方法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:可以。除數(shù)一次增加1個。 在3之后我可以增加2.如果一個數(shù)可以被任何偶數(shù)整除,它將被2整除。
補充:如果你不需要把除數(shù)增加到這個數(shù)。你可以更早停止。讓我在下面的步驟中解釋一下(如果需要可以多讀幾遍)
第一步,任何數(shù)字都不能被大于它的一半的數(shù)字整除。 例如,13將永遠不能被7,8,9整除……它甚至可以是偶數(shù)的一半。 例如,16將被8整除,但永遠不會被9,10,11,12 ……
結(jié)論:一個數(shù)字將永遠不能被一個大于其一半數(shù)值的數(shù)字整除。 所以,我們可以少循環(huán)50%。
第二步,現(xiàn)在,如果一個數(shù)字不能被3整除。(如果它可被3整除,那么它就不是質(zhì)數(shù))。然后,它不可以被大于其值1/3的任何數(shù)整除。例如,35不能被3整除。因此,它永遠不會被大于35/3的數(shù)整除,永遠不能被12, 13, 14整除…如果你取一個像36一樣的偶數(shù),它將永遠不能被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
如果你不能理解也不用擔心,別管它。如果那你不是一個研究人員就沒關(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); // = true isPrime(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:運行時間復(fù)雜度是多少? 你能做得更好嗎?
A:O(n)??梢詫⒊龜?shù)從3開始,累加2。因為,如果一個數(shù)被任何偶數(shù)整除,它將被2整除。因此,你不需要除以偶數(shù)。此外,你不會有一個大于其價值一半的因素。如果你想讓它變得復(fù)雜,那就用第一題的補充概念吧。
Fibonacci(斐波那契)
Q:如何獲得第n個斐波納契數(shù)字?
A: 我創(chuàng)建一個數(shù)組并從迭代開始。
斐波那契系列是面向初學者的最受歡迎的面試問題之一。 所以,你必須學習這一個。
方法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: 運行時間復(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: 運行時間復(fù)雜度是多少?
A: O(2n);關(guān)于時間復(fù)雜度的細節(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); // 7 greatestCommonDivisor(69, 169); // = 1
算法范式
很抱歉。我也無法解釋它。 因為我自己80%的情況下都不能理解它。 我的算法分析教練告訴我這個,又從課堂筆記偷走(我是一個好學生,順便說一句?。?/p>
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理解它。將浪費您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:當然.我可以使用數(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: 運行時間復(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)建,使它更清潔嗎?
function reverse(str){ if(!str || str.length <2) return str; return str.split('').reverse().join(''); }
方法6
Q:你可以做反向函數(shù)作為字符串擴展嗎?
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 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(' '); }
內(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)心獨白)有沒有搞錯??!
//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') // = true isPalindrome('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); // = true sumFinder([6,4,3,2,1,7], 2); // = false
Q: 時間復(fù)雜度?
A: O(n2)。
Q: 有更優(yōu)解?
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: 這實際上非常簡單直接。 找到兩個最大的數(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') // = 0 subStringFinder('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; }
總結(jié)
以上所述是小編給大家介紹的Js面試算法詳解,希望對大家有所幫助,如果大家有任何疑問請給我留言,小編會及時回復(fù)大家的。在此也非常感謝大家對億速云網(wǎng)站的支持!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。