摘要:面試中常見算法問題詳解翻譯自從屬于筆者的前端入門與工程實踐。尋找連續數組中的缺失數給定某無序數組,其包含了個連續數字中的個,已知上下邊界,要求以的復雜度找出缺失的數字。
JavaScript Specification 闡述下 JavaScript 中的變量提升JavaScript 面試中常見算法問題詳解 翻譯自 Interview Algorithm Questions in Javascript() {...} 從屬于筆者的 Web 前端入門與工程實踐。下文提到的很多問題從算法角度并不一定要么困難,不過用 JavaScript 內置的 API 來完成還是需要一番考量的。
所謂提升,顧名思義即是 JavaScript 會將所有的聲明提升到當前作用域的頂部。這也就意味著我們可以在某個變量聲明前就使用該變量,不過雖然 JavaScript 會將聲明提升到頂部,但是并不會執行真的初始化過程。
闡述下 use strict; 的作用use strict; 顧名思義也就是 JavaScript 會在所謂嚴格模式下執行,其一個主要的優勢在于能夠強制開發者避免使用未聲明的變量。對于老版本的瀏覽器或者執行引擎則會自動忽略該指令。
// Example of strict mode "use strict"; catchThemAll(); function catchThemAll() { x = 3.14; // Error will be thrown return x * x; }解釋下什么是 Event Bubbling 以及如何避免
Event Bubbling 即指某個事件不僅會觸發當前元素,還會以嵌套順序傳遞到父元素中。直觀而言就是對于某個子元素的點擊事件同樣會被父元素的點擊事件處理器捕獲。避免 Event Bubbling 的方式可以使用event.stopPropagation() 或者 IE 9 以下使用event.cancelBubble。
== 與 === 的區別是什么=== 也就是所謂的嚴格比較,關鍵的區別在于=== 會同時比較類型與值,而不是僅比較值。
// Example of comparators 0 == false; // true 0 === false; // false 2 == "2"; // true 2 === "2"; // false解釋下 null 與 undefined 的區別
JavaScript 中,null 是一個可以被分配的值,設置為 null 的變量意味著其無值。而 undefined 則代表著某個變量雖然聲明了但是尚未進行過任何賦值。
解釋下 Prototypal Inheritance 與 Classical Inheritance 的區別在類繼承中,類是不可變的,不同的語言中對于多繼承的支持也不一樣,有些語言中還支持接口、final、abstract 的概念。而原型繼承則更為靈活,原型本身是可以可變的,并且對象可能繼承自多個原型。
數組 找出整型數組中乘積最大的三個數給定一個包含整數的無序數組,要求找出乘積最大的三個數。
var unsorted_array = [-10, 7, 29, 30, 5, -10, -70]; computeProduct(unsorted_array); // 21000 function 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 array for (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 };尋找連續數組中的缺失數
給定某無序數組,其包含了 n 個連續數字中的 n - 1 個,已知上下邊界,要求以O(n)的復雜度找出缺失的數字。
// 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); //8 function findMissingNumber(array_of_integers, upper_bound, lower_bound) { // Iterate through array to find the sum of the numbers var sum_of_integers = 0; for (var i = 0; i < array_of_integers.length; i++) { sum_of_integers += array_of_integers[i]; } // 以高斯求和公式計算理論上的數組和 // Formula: [(N * (N + 1)) / 2] - [(M * (M - 1)) / 2]; // N is the upper bound and M is the lower bound upper_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) }數組去重
給定某無序數組,要求去除數組中的重復數字并且返回新的無重復數組。
// 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; }數組中元素最大差值計算
給定某無序數組,求取任意兩個元素之間的最大差值,注意,這里要求差值計算中較小的元素下標必須小于較大元素的下標。譬如[7, 8, 4, 9, 9, 15, 3, 1, 10]這個數組的計算值是 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) { // 如果數組僅有一個元素,則直接返回 -1 if (array.length <= 1) return -1; // current_min 指向當前的最小值 var current_min = array[0]; var current_max_difference = 0; // 遍歷整個數組以求取當前最大差值,如果發現某個最大差值,則將新的值覆蓋 current_max_difference // 同時也會追蹤當前數組中的最小值,從而保證 `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 difference if (current_max_difference <= 0) return -1; return current_max_difference; }數組中元素乘積
給定某無序數組,要求返回新數組 output ,其中 output[i] 為原數組中除了下標為 i 的元素之外的元素乘積,要求以 O(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 + 1 for (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; }數組交集
給定兩個數組,要求求出兩個數組的交集,注意,交集中的元素應該是唯一的。
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 added secondArray.forEach(function(element) { if (hashmap[element] === 1) { intersectionArray.push(element); hashmap[element]++; } }); return intersectionArray; // Time complexity O(n), Space complexity O(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); // true function 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 results a = a.split("").sort().join(""); b = b.split("").sort().join(""); return a === b; }會問字符串
判斷某個字符串是否為回文字符串,譬如racecar與race car都是回文字符串:
isPalindrome("racecar"); // true isPalindrome("race Car"); // true function isPalindrome(word) { // Replace all non-letter chars with "" and change to lowercase var lettersOnly = word.toLowerCase().replace(/s/g, ""); // Compare the string with the reversed version of the string return lettersOnly === lettersOnly.split("").reverse().join(""); }棧與隊列 使用兩個棧實現入隊與出隊
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 stack if (stackOutput.length <= 0) { while(stackInput.length > 0) { var elementToOutput = stackInput.pop(); stackOutput.push(elementToOutput); } } return stackOutput.pop(); }判斷大括號是否閉合
創建一個函數來判斷給定的表達式中的大括號是否閉合:
var expression = "{{}}{}{}" var expressionFalse = "{}{{}"; isBalanced(expression); // true isBalanced(expressionFalse); // false isBalanced(""); // true function isBalanced(expression) { var checkString = expression; var stack = []; // If empty, parentheses are technically balanced if (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 undefined if (stack.length > 0) { stack.pop(); } else { return false; } } } // If the array is not empty, it is not balanced if (stack.pop()) return false; return true; }遞歸 二進制轉換
通過某個遞歸函數將輸入的數字轉化為二進制字符串:
decimalToBinary(3); // 11 decimalToBinary(8); // 1000 decimalToBinary(1000); // 1111101000 function 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 digit if (digit % 2) { return decimalToBinary((digit - 1) / 2) + 1; } else { // Recursively return proceeding binary digits return decimalToBinary(digit / 2) + 0; } } else { // Exit condition return ""; } }二分搜索
function recursiveBinarySearch(array, value, leftPosition, rightPosition) { // Value DNE if (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); } }數字 判斷是否為 2 的指數值
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); }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/81594.html
摘要:計算數組的極值微信面試題獲取元素的最終前端掘金一題目用代碼求出頁面上一個元素的最終的,不考慮瀏覽器,不考慮元素情況。 Excuse me?這個前端面試在搞事! - 前端 - 掘金金三銀四搞事季,前端這個近年的熱門領域,搞事氣氛特別強烈,我朋友小偉最近就在瘋狂面試,遇到了許多有趣的面試官,有趣的面試題,我來幫這個搞事 boy 轉述一下。 以下是我一個朋友的故事,真的不是我。 ... ja...
摘要:筆者作為一位,將工作以來用到的各種優秀資料神器及框架整理在此,畢竟好記性不如爛鍵盤,此前端知識點大百科全書前端掘金,,不定期更新技巧前端掘金技巧,偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案,還有一些是在css-tricks看到的。記錄一下,以后會用到。會持續更新… 一、...
摘要:筆者作為一位,將工作以來用到的各種優秀資料神器及框架整理在此,畢竟好記性不如爛鍵盤,此前端知識點大百科全書前端掘金,,不定期更新技巧前端掘金技巧,偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案,還有一些是在css-tricks看到的。記錄一下,以后會用到。會持續更新… 一、...
閱讀 3427·2021-09-26 09:46
閱讀 2782·2021-09-13 10:23
閱讀 3510·2021-09-07 10:24
閱讀 2388·2019-08-29 13:20
閱讀 2919·2019-08-28 17:57
閱讀 3072·2019-08-26 13:27
閱讀 1175·2019-08-26 12:09
閱讀 505·2019-08-26 10:27