澳门新葡萄京网站 > 新葡萄京Web前端 > JavaScript 面试中常见算法问题详解

JavaScript 面试中常见算法问题详解
2019-12-17 15:26

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

2017/02/20 · JavaScript · 1 评论 · 算法

原文出处: 王下邀月熊_Chevalier   

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

因为绝大多数的浏览器都和它兼容,你可以在这些浏览器中使用它。JavaScript被接受的相当快,因为它是如此的简单,而且使用范围相当广泛。许多程序员过去常常认为JavaScript是一门“玩具语言”,但是,AJAX进入市场后表现出了完全相反的一面,它让JavaScript展现出了完全不同的能力和功能。 由于这个发明的出现,程序员现在已经可以创建带有桌面应用程序效果的Web应用程序了,这是很有益处的,因为数据可以更快地改变。这是一些迷你技巧,它们可以帮助初学者更好地使用JavaScript。JavaScript的使用范围相当广泛,而且还有这么多的风格,所以它可以有很多的技巧。另外,虽然它很多的编程方法,但是我只挑选了10个技巧,我认为这些技巧对初学者理解JavaScript来说是很好的的起点。 1,在一个数组的最后添加一个元素 这个技巧可以让你使用Length属性在一个数组的最后添加一个元素,因为Length属性比数组的最后一个元素的下标多1。这个方法和“push”方法是相同的。例如: 复制代码 代码如下: var myArray = []; myArray[myArray.length] = 'New Element'; 2,调整一个数组的长度 Length属性不是只读的,所以你可以设置Length属性的值。而且,你可以使用它增大或缩小数组的长度。例如: 复制代码 代码如下: var myArray = [1,2,3]; myArray.length // 3 myArray.length = 2; //Delete the last element myArray.length = 20 // add 18 elements to the array; the elements have the undefined value. 3,使用“!!”把任意数据类型转换成Boolean 这个技术可以让你使用“!!”把任意数据类型(比如string, number或integer)转换成Boolean。例如: 复制代码 代码如下: var myString = '23255'; typeof myString; //String myString = !!myString; typeof myString //Boolean 4,把Number转换成String 这个技巧可以让你在number的结尾添加一个空的string来把number转换成string,例如: 复制代码 代码如下: var mynumber = 234; typeof mynumber; //Number mynumber += ''; typeof mynumber; //String 5,了解一个函数需要多少个变量 这是一个伟大的技巧,可以让你准确地知道一个函数需要多少个变量。例如: 复制代码 代码如下: function add_nums{ return num1 + num2; } add_nums.length // 2 is the amount of parameters expected by the function add_nums 6,使用“arguments”对象来了解一个函数接收到了多少个参数 这个技术可以让你使用“arguments”对象来了解一个函数接收到了多少个参数。例如: 复制代码 代码如下: function add_nums(){ return arguments.length; } add_nums(23,11,32,56,89,89,89,44,6); //this return the number 9 当你需要检查参数个数的有效性的时候,或者当你需要创建一个不确定参数个数的函数的时候,这个技巧是很有用的。 复制代码 代码如下: function sum_three_nums{ if throw new Error('received ' + arguments.length + ' parameters and should work with 3'); } sum_three_nums; //Return the error message function sum_num(){ var total = 0; for(var i=0;i复制代码 代码如下: function insertData(name,lastName,phone,address){ code here; } 重构以后的代码是这样的: 复制代码 代码如下: function insertData{ var name = parameters.name; var lastName = parameters.lastName; var phone = parameters.phone; var address = parameters.address; } 当你要使用默认值的时候,它也是十分有用的。例如: 复制代码 代码如下: function insertData{ var name = parameters.name; var lastName = parameters.lastName; var phone = parameters.phone; var address = parameters.address; var status = parameters.status || 'single' //If status is not defined as a property //in the object the variable status take single as value } 现在,要使用这个函数十分的简单;我们可以用两种方式来发送数据: 复制代码 代码如下: //Example 1 insertData({name:'Mike', lastName:'Rogers', phone:'555-555-5555',address:'the address', status:'married'}); //Example 2 var myData = { name:'Mike', lastName:'Rogers', phone:'555-555-5555', address:'the address', status:'married' }; insertData; 8,函数就是数据 函数就是像strings或numbers那样的数据,我们可以把它们当成函数参数来传递它们,这可以创建十分令人惊讶而又“威风凛凛”的Web应用程序。这个方法是非常有用的,几乎所有的主流框架都使用了这个方法。例如: 复制代码 代码如下: function byId{ Document.getElementById.['on'+event] = f; //f is the function that we pass as parameter } byId('myBtn','click',function(){alert; Another example of functions as data: //Example 1 function msg; } //Example 2 var msg = function;} 这些函数几乎是完全相同的。唯一的区别是使用它们的方式。例如:第一个函数,在你声明它以前,你就可以使用它了;但是第二个函数只有声明以后才能使用: //Example 1 msg; //This will work function msg; } //Example 2 msg; //Does not work because JavaScript cannot find the function msg because is used before is been declared. var msg = function} 9,扩展本地对象 虽然一些JavaScript的领袖不推荐这个技术,但是它已经被一些框架使用了。它可以让你针对JavaScript API来创建一些辅助性的方法。 复制代码 代码如下: //We create the method prototype for our arrays //It only sums numeric elements Array.prototype.sum = function(){ var len = this.length; total = 0; for{ if(typeof this[i]!= 'number') continue; total += this[i]; } return total; } var myArray = [1,2,3,'hola']; myArray.sum(); Array.prototype.max = function(){ return Math.max.apply; } 10,Boolean 注意它们之间的区别,因为这会节省你调试脚本的时间。 复制代码 代码如下: '' == '0' // false 0 == '' // true 0 == '0' // true false == 'false' // false false == '0' // true false == undefined // false false == null // false null == undefined // true true == 1 // true '' == null // false false == '' // true 如果你在其他地方看过这些脚本,那么这些技巧可以帮助你融会贯通。这些技巧甚至还不及JavaScript所有功能的冰山一角,但是这是一个开始!请不要客气,留下你的评论,问题,额外的技巧或疑虑吧,但是请记住,这是一篇针对初学者的文章!!我希望能收到一些开发者同行的来信!Enjoy!

JavaScript Specification

阐述下 JavaScript 中的变量提升

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

阐述下 use strict; 的作用

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

JavaScript

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

1
2
3
4
5
6
7
8
// 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

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

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

JavaScript

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

1
2
3
4
5
6
// 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 的概念。而原型继承则更为灵活,原型本身是可以可变的,并且对象可能继承自多个原型。

数组

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

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

JavaScript

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 };

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)的复杂度找出缺失的数字。

JavaScript

// 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) }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 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)
}

数组去重

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

JavaScript

// 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; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 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。

JavaScript

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; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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) 复杂度实现:

JavaScript

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; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
}
上一篇:常见的算法 下一篇:没有了