JavaScript 面試中常見算法問題詳解，翻譯自?https://github.com/kennymkchan/interview-questions-in-javascript。下文提到的很多問題從算法角度并不一定要么困難，不過用 JavaScript 內(nèi)置的 API 來完成還是需要一番考量的。

　JavaScript Specification

　　闡述下 JavaScript 中的變量提升

　　所謂提升，顧名思義即是 JavaScript 會將所有的聲明提升到當前作用域的頂部。這也就意味著我們可以在某個變量聲明前就使用該變量，不過雖然 JavaScript 會將聲明提升到頂部，但是并不會執(zhí)行真的初始化過程。

　　闡述下 use strict; 的作用

　　use strict; 顧名思義也就是 JavaScript 會在所謂嚴格模式下執(zhí)行，其一個主要的優(yōu)勢在于能夠強制開發(fā)者避免使用未聲明的變量。對于老版本的瀏覽器或者執(zhí)行引擎則會自動忽略該指令。

// Example of strict mode "use strict";catchThemAll(); function catchThemAll() {x = 3.14; // Error will be thrownreturn x * x; }

　　解釋下什么是 Event Bubbling 以及如何避免

　　Event Bubbling 即指某個事件不僅會觸發(fā)當前元素，還會以嵌套順序傳遞到父元素中。直觀而言就是對于某個子元素的點擊事件同樣會被父元素的點擊事件處理器捕獲。避免 Event Bubbling 的方式可以使用event.stopPropagation() 或者 IE 9 以下使用event.cancelBubble。

　　== 與 === 的區(qū)別是什么

　　=== 也就是所謂的嚴格比較，關(guān)鍵的區(qū)別在于=== 會同時比較類型與值，而不是僅比較值。

// Example of comparators 0 == false; // true 0 === false; // false2 == '2'; // true 2 === '2'; // false

　　解釋下 null 與 undefined 的區(qū)別

　　JavaScript 中，null 是一個可以被分配的值，設(shè)置為 null 的變量意味著其無值。而 undefined 則代表著某個變量雖然聲明了但是尚未進行過任何賦值。

　　解釋下 Prototypal Inheritance 與 Classical Inheritance 的區(qū)別

　　在類繼承中，類是不可變的，不同的語言中對于多繼承的支持也不一樣，有些語言中還支持接口、final、abstract 的概念。而原型繼承則更為靈活，原型本身是可以可變的，并且對象可能繼承自多個原型。

　數(shù)組

　　找出整型數(shù)組中乘積最大的三個數(shù)

　　給定一個包含整數(shù)的無序數(shù)組，要求找出乘積最大的三個數(shù)。

var unsorted_array = [-10, 7, 29, 30, 5, -10, -70];computeProduct(unsorted_array); // 21000function sortIntegers(a, b) {return a - b; }// greatest product is either (min1 * min2 * max1 || max1 * max2 * max3) function computeProduct(unsorted) {var sorted_array = unsorted.sort(sortIntegers),product1 = 1,product2 = 1,array_n_element = sorted_array.length - 1;// Get the product of three largest integers in sorted arrayfor (var x = array_n_element; x > array_n_element - 3; x--) {product1 = product1 * sorted_array[x];}product2 = sorted_array[0] * sorted_array[1] * sorted_array[array_n_element];if (product1 > product2) return product1;return product2 };

　　尋找連續(xù)數(shù)組中的缺失數(shù)

　　給定某無序數(shù)組，其包含了 n 個連續(xù)數(shù)字中的 n - 1 個，已知上下邊界，要求以O(shè)(n)的復雜度找出缺失的數(shù)字。

// The output of the function should be 8 var array_of_integers = [2, 5, 1, 4, 9, 6, 3, 7]; var upper_bound = 9; var lower_bound = 1;findMissingNumber(array_of_integers, upper_bound, lower_bound); //8function findMissingNumber(array_of_integers, upper_bound, lower_bound) {// Iterate through array to find the sum of the numbersvar sum_of_integers = 0;for (var i = 0; i < array_of_integers.length; i++) {sum_of_integers += array_of_integers[i];}// 以高斯求和公式計算理論上的數(shù)組和// Formula: [(N * (N + 1)) / 2] - [(M * (M - 1)) / 2];// N is the upper bound and M is the lower boundupper_limit_sum = (upper_bound * (upper_bound + 1)) / 2;lower_limit_sum = (lower_bound * (lower_bound - 1)) / 2;theoretical_sum = upper_limit_sum - lower_limit_sum;//return (theoretical_sum - sum_of_integers) }

　　數(shù)組去重

　　給定某無序數(shù)組，要求去除數(shù)組中的重復數(shù)字并且返回新的無重復數(shù)組。

// ES6 Implementation var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8]; Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8]// ES5 Implementation var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8]; uniqueArray(array); // [1, 2, 3, 5, 9, 8] function uniqueArray(array) {var hashmap = {};var unique = [];for(var i = 0; i < array.length; i++) {// If key returns null (unique), it is evaluated as false.if(!hashmap.hasOwnProperty([array[i]])) {hashmap[array[i]] = 1;unique.push(array[i]);}}return unique; }

　　數(shù)組中元素最大差值計算

　　給定某無序數(shù)組，求取任意兩個元素之間的最大差值，注意，這里要求差值計算中較小的元素下標必須小于較大元素的下標。譬如[7, 8, 4, 9, 9, 15, 3, 1, 10]這個數(shù)組的計算值是 11( 15 - 4 ) 而不是 14(15 - 1)，因為 15 的下標小于 1。

var array = [7, 8, 4, 9, 9, 15, 3, 1, 10]; // [7, 8, 4, 9, 9, 15, 3, 1, 10] would return `11` based on the difference between `4` and `15` // Notice: It is not `14` from the difference between `15` and `1` because 15 comes before 1.findLargestDifference(array); function findLargestDifference(array) {// 如果數(shù)組僅有一個元素，則直接返回 -1if (array.length <= 1) return -1;// current_min 指向當前的最小值var current_min = array[0];var current_max_difference = 0;// 遍歷整個數(shù)組以求取當前最大差值，如果發(fā)現(xiàn)某個最大差值，則將新的值覆蓋 current_max_difference// 同時也會追蹤當前數(shù)組中的最小值，從而保證 `largest value in future` - `smallest value before it`for (var i = 1; i < array.length; i++) {if (array[i] > current_min && (array[i] - current_min > current_max_difference)) {current_max_difference = array[i] - current_min;} else if (array[i] <= current_min) {current_min = array[i];}}// If negative or 0, there is no largest differenceif (current_max_difference <= 0) return -1;return current_max_difference; }

　　數(shù)組中元素乘積

　　給定某無序數(shù)組，要求返回新數(shù)組 output ，其中 output[i] 為原數(shù)組中除了下標為 i 的元素之外的元素乘積，要求以 O(n) 復雜度實現(xiàn)：

var firstArray = [2, 2, 4, 1]; var secondArray = [0, 0, 0, 2]; var thirdArray = [-2, -2, -3, 2];productExceptSelf(firstArray); // [8, 8, 4, 16] productExceptSelf(secondArray); // [0, 0, 0, 0] productExceptSelf(thirdArray); // [12, 12, 8, -12]function productExceptSelf(numArray) {var product = 1;var size = numArray.length;var output = [];// From first array: [1, 2, 4, 16]// The last number in this case is already in the right spot (allows for us)// to just multiply by 1 in the next step.// This step essentially gets the product to the left of the index at index + 1for (var x = 0; x < size; x++) {output.push(product);product = product * numArray[x];}// From the back, we multiply the current output element (which represents the product// on the left of the index, and multiplies it by the product on the right of the element)var product = 1;for (var i = size - 1; i > -1; i--) {output[i] = output[i] * product;product = product * numArray[i];}return output; }

　　數(shù)組交集

　　給定兩個數(shù)組，要求求出兩個數(shù)組的交集，注意，交集中的元素應該是唯一的。

var firstArray = [2, 2, 4, 1]; var secondArray = [1, 2, 0, 2];intersection(firstArray, secondArray); // [2, 1]function intersection(firstArray, secondArray) {// The logic here is to create a hashmap with the elements of the firstArray as the keys.// After that, you can use the hashmap's O(1) look up time to check if the element exists in the hash// If it does exist, add that element to the new array.var hashmap = {};var intersectionArray = [];firstArray.forEach(function(element) {hashmap[element] = 1;});// Since we only want to push unique elements in our case... we can implement a counter to keep track of what we already addedsecondArray.forEach(function(element) {if (hashmap[element] === 1) {intersectionArray.push(element);hashmap[element]++;}});return intersectionArray;// Time complexity O(n), Space complexity O(n) }

　字符串

　　顛倒字符串

　　給定某個字符串，要求將其中單詞倒轉(zhuǎn)之后然后輸出，譬如"Welcome to this Javascript Guide!" 應該輸出為 "emocleW ot siht tpircsavaJ !ediuG"。

var string = "Welcome to this Javascript Guide!";// Output becomes !ediuG tpircsavaJ siht ot emocleW var reverseEntireSentence = reverseBySeparator(string, "");// Output becomes emocleW ot siht tpircsavaJ !ediuG var reverseEachWord = reverseBySeparator(reverseEntireSentence, " ");function reverseBySeparator(string, separator) {return string.split(separator).reverse().join(separator); }

　　亂序同字母字符串

　　給定兩個字符串，判斷是否顛倒字母而成的字符串，譬如Mary與Army就是同字母而順序顛倒：

var firstWord = "Mary"; var secondWord = "Army";isAnagram(firstWord, secondWord); // truefunction isAnagram(first, second) {// For case insensitivity, change both words to lowercase.var a = first.toLowerCase();var b = second.toLowerCase();// Sort the strings, and join the resulting array to a string. Compare the resultsa = a.split("").sort().join("");b = b.split("").sort().join("");return a === b; }

　　會問字符串

　　判斷某個字符串是否為回文字符串，譬如racecar與race car都是回文字符串：

isPalindrome("racecar"); // true isPalindrome("race Car"); // truefunction isPalindrome(word) {// Replace all non-letter chars with "" and change to lowercasevar lettersOnly = word.toLowerCase().replace(/\s/g, "");// Compare the string with the reversed version of the stringreturn lettersOnly === lettersOnly.split("").reverse().join(""); }

　棧與隊列

　　使用兩個棧實現(xiàn)入隊與出隊

var inputStack = []; // First stack var outputStack = []; // Second stack// For enqueue, just push the item into the first stack function enqueue(stackInput, item) {return stackInput.push(item); }function dequeue(stackInput, stackOutput) {// Reverse the stack such that the first element of the output stack is the// last element of the input stack. After that, pop the top of the output to// get the first element that was ever pushed into the input stackif (stackOutput.length <= 0) {while(stackInput.length > 0) {var elementToOutput = stackInput.pop();stackOutput.push(elementToOutput);}}return stackOutput.pop(); }

　　判斷大括號是否閉合

　　創(chuàng)建一個函數(shù)來判斷給定的表達式中的大括號是否閉合：

var expression = "{{}}{}{}" var expressionFalse = "{}{{}";isBalanced(expression); // true isBalanced(expressionFalse); // false isBalanced(""); // truefunction isBalanced(expression) {var checkString = expression;var stack = [];// If empty, parentheses are technically balancedif (checkString.length <= 0) return true;for (var i = 0; i < checkString.length; i++) {if(checkString[i] === '{') {stack.push(checkString[i]);} else if (checkString[i] === '}') {// Pop on an empty array is undefinedif (stack.length > 0) {stack.pop();} else {return false;}}}// If the array is not empty, it is not balancedif (stack.pop()) return false;return true; }

　遞歸

　　二進制轉(zhuǎn)換

　　通過某個遞歸函數(shù)將輸入的數(shù)字轉(zhuǎn)化為二進制字符串：

decimalToBinary(3); // 11 decimalToBinary(8); // 1000 decimalToBinary(1000); // 1111101000function decimalToBinary(digit) {if(digit >= 1) {// If digit is not divisible by 2 then recursively return proceeding// binary of the digit minus 1, 1 is added for the leftover 1 digitif (digit % 2) {return decimalToBinary((digit - 1) / 2) + 1;} else {// Recursively return proceeding binary digitsreturn decimalToBinary(digit / 2) + 0;}} else {// Exit conditionreturn '';} }

　　二分搜索

function recursiveBinarySearch(array, value, leftPosition, rightPosition) {// Value DNEif (leftPosition > rightPosition) return -1;var middlePivot = Math.floor((leftPosition + rightPosition) / 2);if (array[middlePivot] === value) {return middlePivot;} else if (array[middlePivot] > value) {return recursiveBinarySearch(array, value, leftPosition, middlePivot - 1);} else {return recursiveBinarySearch(array, value, middlePivot + 1, rightPosition);} }

　數(shù)字

　　判斷是否為 2 的指數(shù)值

isPowerOfTwo(4); // true isPowerOfTwo(64); // true isPowerOfTwo(1); // true isPowerOfTwo(0); // false isPowerOfTwo(-1); // false// For the non-zero case: function isPowerOfTwo(number) {// `&` uses the bitwise n.// In the case of number = 4; the expression would be identical to:// `return (4 & 3 === 0)`// In bitwise, 4 is 100, and 3 is 011. Using &, if two values at the same// spot is 1, then result is 1, else 0. In this case, it would return 000,// and thus, 4 satisfies are expression.// In turn, if the expression is `return (5 & 4 === 0)`, it would be false// since it returns 101 & 100 = 100 (NOT === 0)return number & (number - 1) === 0; }// For zero-case: function isPowerOfTwoZeroCase(number) {return (number !== 0) && ((number & (number - 1)) === 0); }

轉(zhuǎn)載于:https://www.cnblogs.com/woodyliang/p/6438222.html

總結(jié)

以上是生活随笔為你收集整理的JavaScript 面试中常见算法问题详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。