请选择 进入手机版 | 继续访问电脑版
 找回密码
 立即注册

QQ登录

只需要一步,快速开始

搜索
开启左侧

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

马上注册,分享更多源码,享用更多功能,让你轻松玩转云大陆。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
JavaScript 面试中常见算法问题详解 翻译自 Interview Algorithm Questions in Javascript 从属于笔者的 Web 前端入门与工程实践。下文提到的很多问题从算法角度并不一定多么困难,不过用 JavaScript 内置的 API 来完成还是需要一番考量的。


JavaScript Specification
阐述下 JavaScript 中的变量提升
所谓提升,顾名思义即是 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 comparators0 == false; // true0 === false; // false 2 == '2'; // true2 === '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 8var 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; }  // 以高斯求和公式计算理论上的数组和 // 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 Implementationvar array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8]; Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8]  // ES5 Implementationvar 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])) { hashmap[array] = 1; unique.push(array); } } 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  current_min && (array - current_min > current_max_difference)) { current_max_difference = array - current_min; } else if (array = 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 &#x27;&#x27;; }}


二分搜索
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); // trueisPowerOfTwo(64); // trueisPowerOfTwo(1); // trueisPowerOfTwo(0); // falseisPowerOfTwo(-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);}
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

  • 0 关注
  • 0 粉丝
  • 7 帖子
广告招商