JavaScript 面试中常见算法问题详解

JavaScript 中的变量提升

所谓提升，顾名思义即是 JavaScript 会将所有的声明提升到当前作用域的顶部。这也就意味着我们可以在某个变量声明前就使用该变量，不过虽然 JavaScript 会将声明提升到顶部，但是并不会执行真的初始化过程。、

-----------------------------------------------------------------------------------------------------------------------------

use strict; 的作用

顾名思义也就是 JavaScript 会在所谓严格模式下执行，其一个主要的优势在于能够强制开发者避免使用未声明的变量。对于老版本的浏览器或者执行引擎则会自动忽略该指令。

1. // Example of strict mode
   
2. "use strict";
   
3. 
   
4. catchThemAll();
   
5. function catchThemAll() {
   
6.   x = 3.14; // Error will be thrown
   
7.   return x * x;
   
8. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

Event Bubbling 以及如何避免

Event Bubbling 即指某个事件不仅会触发当前元素，还会以嵌套顺序传递到父元素中。直观而言就是对于某个子元素的点击事件同样会被父元素的点击事件处理器捕获。避免 Event Bubbling 的方式可以使用event.stopPropagation() 或者 IE 9 以下使用event.cancelBubble。

-----------------------------------------------------------------------------------------------------------------------------

== 与 === 的区别是什么

=== 也就是所谓的严格比较，关键的区别在于===会同时比较类型与值，而不是仅比较值。

1. // Example of comparators
   
2. 0 == false; // true
   
3. 0 === false; // false
   
4. 
   
5. 2 == '2'; // true
   
6. 2 === '2'; // false

复制代码

-----------------------------------------------------------------------------------------------------------------------------

null 与 undefined 的区别

JavaScript 中，null 是一个可以被分配的值，设置为 null 的变量意味着其无值。而 undefined 则代表着某个变量虽然声明了但是尚未进行过任何赋值。

-----------------------------------------------------------------------------------------------------------------------------

解释下 Prototypal Inheritance 与 Classical Inheritance 的区别

在类继承中，类是不可变的，不同的语言中对于多继承的支持也不一样，有些语言中还支持接口、final、abstract 的概念。而原型继承则更为灵活，原型本身是可以可变的，并且对象可能继承自多个原型。

-----------------------------------------------------------------------------------------------------------------------------

数组找出整型数组中乘积最大的三个数

给定一个包含整数的无序数组，要求找出乘积最大的三个数。

1. var unsorted_array = [-10, 7, 29, 30, 5, -10, -70];
   
2. 
   
3. computeProduct(unsorted_array); // 21000
   
4. 
   
5. function sortIntegers(a, b) {
   
6.   return a - b;
   
7. }
   
8. 
   
9. // greatest product is either (min1 * min2 * max1 || max1 * max2 * max3)
   
10. function computeProduct(unsorted) {
    
11.   var sorted_array = unsorted.sort(sortIntegers),
    
12.     product1 = 1,
    
13.     product2 = 1,
    
14.     array_n_element = sorted_array.length - 1;
    
15. 
    
16.   // Get the product of three largest integers in sorted array
    
17.   for (var x = array_n_element; x > array_n_element - 3; x--) {
    
18.       product1 = product1 * sorted_array[x];
    
19.   }
    
20.   product2 = sorted_array[0] * sorted_array[1] * sorted_array[array_n_element];
    
21. 
    
22.   if (product1 > product2) return product1;
    
23. 
    
24.   return product2
    
25. };

复制代码

-----------------------------------------------------------------------------------------------------------------------------

寻找连续数组中的缺失数

给定某无序数组，其包含了 n 个连续数字中的 n – 1 个，已知上下边界，要求以O(n)的复杂度找出缺失的数字。

1. // The output of the function should be 8
   
2. var array_of_integers = [2, 5, 1, 4, 9, 6, 3, 7];
   
3. var upper_bound = 9;
   
4. var lower_bound = 1;
   
5. 
   
6. findMissingNumber(array_of_integers, upper_bound, lower_bound); //8
   
7. 
   
8. function findMissingNumber(array_of_integers, upper_bound, lower_bound) {
   
9. 
   
10.   // Iterate through array to find the sum of the numbers
    
11.   var sum_of_integers = 0;
    
12.   for (var i = 0; i < array_of_integers.length; i++) {
    
13.     sum_of_integers += array_of_integers[i];
    
14.   }
    
15. 
    
16.   // 以高斯求和公式计算理论上的数组和
    
17.   // Formula: [(N * (N + 1)) / 2] - [(M * (M - 1)) / 2];
    
18.   // N is the upper bound and M is the lower bound
    
19. 
    
20.   upper_limit_sum = (upper_bound * (upper_bound + 1)) / 2;
    
21.   lower_limit_sum = (lower_bound * (lower_bound - 1)) / 2;
    
22. 
    
23.   theoretical_sum = upper_limit_sum - lower_limit_sum;
    
24. 
    
25.   //
    
26.   return (theoretical_sum - sum_of_integers)
    
27. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

数组去重

给定某无序数组，要求去除数组中的重复数字并且返回新的无重复数组。

1. // ES6 Implementation
   
2. var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
   
3. 
   
4. Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8]
   
5. 
   
6. // ES5 Implementation
   
7. var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
   
8. 
   
9. uniqueArray(array); // [1, 2, 3, 5, 9, 8]
   
10. 
    
11. function uniqueArray(array) {
    
12.   var hashmap = {};
    
13.   var unique = [];
    
14.   for(var i = 0; i < array.length; i++) {
    
15.     // If key returns null (unique), it is evaluated as false.
    
16.     if(!hashmap.hasOwnProperty([array[i]])) {
    
17.       hashmap[array[i]] = 1;
    
18.       unique.push(array[i]);
    
19.     }
    
20.   }
    
21.   return unique;
    
22. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

数组中元素最大差值计算

给定某无序数组，求取任意两个元素之间的最大差值，注意，这里要求差值计算中较小的元素下标必须小于较大元素的下标。譬如[7, 8, 4, 9, 9, 15, 3, 1, 10]这个数组的计算值是 11( 15 – 4 ) 而不是 14(15 – 1)，因为 15 的下标小于 1。

1. var array = [7, 8, 4, 9, 9, 15, 3, 1, 10];
   
2. // [7, 8, 4, 9, 9, 15, 3, 1, 10] would return `11` based on the difference between `4` and `15`
   
3. // Notice: It is not `14` from the difference between `15` and `1` because 15 comes before 1.
   
4. 
   
5. findLargestDifference(array);
   
6. 
   
7. function findLargestDifference(array) {
   
8. 
   
9.   // 如果数组仅有一个元素，则直接返回 -1
   
10. 
    
11.   if (array.length <= 1) return -1;
    
12. 
    
13.   // current_min 指向当前的最小值
    
14. 
    
15.   var current_min = array[0];
    
16.   var current_max_difference = 0;
    
17. 
    
18.   // 遍历整个数组以求取当前最大差值，如果发现某个最大差值，则将新的值覆盖 current_max_difference
    
19.   // 同时也会追踪当前数组中的最小值，从而保证 `largest value in future` - `smallest value before it`
    
20. 
    
21.   for (var i = 1; i < array.length; i++) {
    
22.     if (array[i] > current_min && (array[i] - current_min > current_max_difference)) {
    
23.       current_max_difference = array[i] - current_min;
    
24.     } else if (array[i] <= current_min) {
    
25.       current_min = array[i];
    
26.     }
    
27.   }
    
28. 
    
29.   // If negative or 0, there is no largest difference
    
30.   if (current_max_difference <= 0) return -1;
    
31. 
    
32.   return current_max_difference;
    
33. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

数组中元素乘积

给定某无序数组，要求返回新数组 output ，其中 output为原数组中除了下标为 i 的元素之外的元素乘积，要求以 O(n) 复杂度实现：

1. var firstArray = [2, 2, 4, 1];
   
2. var secondArray = [0, 0, 0, 2];
   
3. var thirdArray = [-2, -2, -3, 2];
   
4. 
   
5. productExceptSelf(firstArray); // [8, 8, 4, 16]
   
6. productExceptSelf(secondArray); // [0, 0, 0, 0]
   
7. productExceptSelf(thirdArray); // [12, 12, 8, -12]
   
8. 
   
9. function productExceptSelf(numArray) {
   
10.   var product = 1;
    
11.   var size = numArray.length;
    
12.   var output = [];
    
13. 
    
14.   // From first array: [1, 2, 4, 16]
    
15.   // The last number in this case is already in the right spot (allows for us)
    
16.   // to just multiply by 1 in the next step.
    
17.   // This step essentially gets the product to the left of the index at index + 1
    
18.   for (var x = 0; x < size; x++) {
    
19.       output.push(product);
    
20.       product = product * numArray[x];
    
21.   }
    
22. 
    
23.   // From the back, we multiply the current output element (which represents the product
    
24.   // on the left of the index, and multiplies it by the product on the right of the element)
    
25.   var product = 1;
    
26.   for (var i = size - 1; i > -1; i--) {
    
27.       output[i] = output[i] * product;
    
28.       product = product * numArray[i];
    
29.   }
    
30. 
    
31.   return output;
    
32. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

数组交集

给定两个数组，要求求出两个数组的交集，注意，交集中的元素应该是唯一的。

1. var firstArray = [2, 2, 4, 1];
   
2. var secondArray = [1, 2, 0, 2];
   
3. 
   
4. intersection(firstArray, secondArray); // [2, 1]
   
5. 
   
6. function intersection(firstArray, secondArray) {
   
7.   // The logic here is to create a hashmap with the elements of the firstArray as the keys.
   
8.   // After that, you can use the hashmap's O(1) look up time to check if the element exists in the hash
   
9.   // If it does exist, add that element to the new array.
   
10. 
    
11.   var hashmap = {};
    
12.   var intersectionArray = [];
    
13. 
    
14.   firstArray.forEach(function(element) {
    
15.     hashmap[element] = 1;
    
16.   });
    
17. 
    
18.   // Since we only want to push unique elements in our case... we can implement a counter to keep track of what we already added
    
19.   secondArray.forEach(function(element) {
    
20.     if (hashmap[element] === 1) {
    
21.       intersectionArray.push(element);
    
22.       hashmap[element]++;
    
23.     }
    
24.   });
    
25. 
    
26.   return intersectionArray;
    
27. 
    
28.   // Time complexity O(n), Space complexity O(n)
    
29. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

字符串颠倒字符串

给定某个字符串，要求将其中单词倒转之后然后输出，譬如”Welcome to this Javascript Guide!” 应该输出为 “emocleW ot siht tpircsavaJ !ediuG”。

1. var string = "Welcome to this Javascript Guide!";
   
2. 
   
3. // Output becomes !ediuG tpircsavaJ siht ot emocleW
   
4. var reverseEntireSentence = reverseBySeparator(string, "");
   
5. 
   
6. // Output becomes emocleW ot siht tpircsavaJ !ediuG
   
7. var reverseEachWord = reverseBySeparator(reverseEntireSentence, " ");
   
8. 
   
9. function reverseBySeparator(string, separator) {
   
10.   return string.split(separator).reverse().join(separator);
    
11. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

乱序同字母字符串

给定两个字符串，判断是否颠倒字母而成的字符串，譬如Mary与Army就是同字母而顺序颠倒：

1. var firstWord = "Mary";
   
2. var secondWord = "Army";
   
3. 
   
4. isAnagram(firstWord, secondWord); // true
   
5. 
   
6. function isAnagram(first, second) {
   
7.   // For case insensitivity, change both words to lowercase.
   
8.   var a = first.toLowerCase();
   
9.   var b = second.toLowerCase();
   
10. 
    
11.   // Sort the strings, and join the resulting array to a string. Compare the results
    
12.   a = a.split("").sort().join("");
    
13.   b = b.split("").sort().join("");
    
14. 
    
15.   return a === b;
    
16. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

会问字符串

判断某个字符串是否为回文字符串，譬如racecar与race car都是回文字符串：

1. isPalindrome("racecar"); // true
   
2. isPalindrome("race Car"); // true
   
3. 
   
4. function isPalindrome(word) {
   
5.   // Replace all non-letter chars with "" and change to lowercase
   
6.   var lettersOnly = word.toLowerCase().replace(/\s/g, "");
   
7. 
   
8.   // Compare the string with the reversed version of the string
   
9.   return lettersOnly === lettersOnly.split("").reverse().join("");
   
10. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

栈与队列使用两个栈实现入队与出队

1. var inputStack = []; // First stack
   
2. var outputStack = []; // Second stack
   
3. 
   
4. // For enqueue, just push the item into the first stack
   
5. function enqueue(stackInput, item) {
   
6.   return stackInput.push(item);
   
7. }
   
8. 
   
9. function dequeue(stackInput, stackOutput) {
   
10.   // Reverse the stack such that the first element of the output stack is the
    
11.   // last element of the input stack. After that, pop the top of the output to
    
12.   // get the first element that was ever pushed into the input stack
    
13.   if (stackOutput.length <= 0) {
    
14.     while(stackInput.length > 0) {
    
15.       var elementToOutput = stackInput.pop();
    
16.       stackOutput.push(elementToOutput);
    
17.     }
    
18.   }
    
19. 
    
20.   return stackOutput.pop();
    
21. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------


判断大括号是否闭合

创建一个函数来判断给定的表达式中的大括号是否闭合：

1. var expression = "{{}}{}{}"
   
2. var expressionFalse = "{}{{}";
   
3. 
   
4. isBalanced(expression); // true
   
5. isBalanced(expressionFalse); // false
   
6. isBalanced(""); // true
   
7. 
   
8. function isBalanced(expression) {
   
9.   var checkString = expression;
   
10.   var stack = [];
    
11. 
    
12.   // If empty, parentheses are technically balanced
    
13.   if (checkString.length <= 0) return true;
    
14. 
    
15.   for (var i = 0; i < checkString.length; i++) {
    
16.     if(checkString[i] === '{') {
    
17.       stack.push(checkString[i]);
    
18.     } else if (checkString[i] === '}') {
    
19.       // Pop on an empty array is undefined
    
20.       if (stack.length > 0) {
    
21.         stack.pop();
    
22.       } else {
    
23.         return false;
    
24.       }
    
25.     }
    
26.   }
    
27. 
    
28.   // If the array is not empty, it is not balanced
    
29.   if (stack.pop()) return false;
    
30.   return true;
    
31. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

递归二进制转换

通过某个递归函数将输入的数字转化为二进制字符串：

1. decimalToBinary(3); // 11
   
2. decimalToBinary(8); // 1000
   
3. decimalToBinary(1000); // 1111101000
   
4. 
   
5. function decimalToBinary(digit) {
   
6.   if(digit >= 1) {
   
7.     // If digit is not divisible by 2 then recursively return proceeding
   
8.     // binary of the digit minus 1, 1 is added for the leftover 1 digit
   
9.     if (digit % 2) {
   
10.       return decimalToBinary((digit - 1) / 2) + 1;
    
11.     } else {
    
12.       // Recursively return proceeding binary digits
    
13.       return decimalToBinary(digit / 2) + 0;
    
14.     }
    
15.   } else {
    
16.     // Exit condition
    
17.     return '';
    
18.   }
    
19. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

二分搜索

1. function recursiveBinarySearch(array, value, leftPosition, rightPosition) {
   
2.   // Value DNE
   
3.   if (leftPosition > rightPosition) return -1;
   
4. 
   
5.   var middlePivot = Math.floor((leftPosition + rightPosition) / 2);
   
6.   if (array[middlePivot] === value) {
   
7.     return middlePivot;
   
8.   } else if (array[middlePivot] > value) {
   
9.     return recursiveBinarySearch(array, value, leftPosition, middlePivot - 1);
   
10.   } else {
    
11.     return recursiveBinarySearch(array, value, middlePivot + 1, rightPosition);
    
12.   }
    
13. }

复制代码

-----------------------------------------------------------------------------------------------------------------------------

数字判断是否为 2 的指数值

1. isPowerOfTwo(4); // true
   
2. isPowerOfTwo(64); // true
   
3. isPowerOfTwo(1); // true
   
4. isPowerOfTwo(0); // false
   
5. isPowerOfTwo(-1); // false
   
6. 
   
7. // For the non-zero case:
   
8. function isPowerOfTwo(number) {
   
9.   // `&` uses the bitwise n.
   
10.   // In the case of number = 4; the expression would be identical to:
    
11.   // `return (4 & 3 === 0)`
    
12.   // In bitwise, 4 is 100, and 3 is 011. Using &, if two values at the same
    
13.   // spot is 1, then result is 1, else 0. In this case, it would return 000,
    
14.   // and thus, 4 satisfies are expression.
    
15.   // In turn, if the expression is `return (5 & 4 === 0)`, it would be false
    
16.   // since it returns 101 & 100 = 100 (NOT === 0)
    
17. 
    
18.   return number & (number - 1) === 0;
    
19. }
    
20. 
    
21. // For zero-case:
    
22. function isPowerOfTwoZeroCase(number) {
    
23.   return (number !== 0) && ((number & (number - 1)) === 0);
    
24. }

复制代码

原文链接：http://www.codeceo.com/article/javascript-interviews-common-algorithm-issues.html