找回密码
 立即注册

QQ登录

只需一步，快速开始

首页 › 技术交流区 › 前端技术交流 › 查看内容
发新帖

断天涯大虾

社区贡献组

269

主题

272

帖子

1655

积分

社区贡献组

积分
1655

微信认证勋章

最新发帖

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

断天涯大虾
社区贡献组   /  发表于：2017-3-14 09:11  /   查看：5220  /  回复：0
本帖最后由 断天涯大虾 于 2017-3-14 09:18 编辑

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

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

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

  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

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

  3. computeProduct(unsorted_array); // 21000

  5. function sortIntegers(a, b) {
  6.   return a - b;
  7. }

  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;

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

  22.   if (product1 > product2) return product1;

  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;

  6. findMissingNumber(array_of_integers, upper_bound, lower_bound); //8

  8. function findMissingNumber(array_of_integers, upper_bound, lower_bound) {

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

  16.   // 以高斯求和公式计算理论上的数组和
  17.   // Formula: [(N * (N + 1)) / 2] - [(M * (M - 1)) / 2];
  18.   // N is the upper bound and M is the lower bound

  20.   upper_limit_sum = (upper_bound * (upper_bound + 1)) / 2;
  21.   lower_limit_sum = (lower_bound * (lower_bound - 1)) / 2;

  23.   theoretical_sum = upper_limit_sum - lower_limit_sum;

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

  4. Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8]

  6. // ES5 Implementation
  7. var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];

  9. uniqueArray(array); // [1, 2, 3, 5, 9, 8]

  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.

  5. findLargestDifference(array);

  7. function findLargestDifference(array) {

  9.   // 如果数组仅有一个元素，则直接返回 -1

  11.   if (array.length <= 1) return -1;

  13.   // current_min 指向当前的最小值

  15.   var current_min = array[0];
  16.   var current_max_difference = 0;

  18.   // 遍历整个数组以求取当前最大差值，如果发现某个最大差值，则将新的值覆盖 current_max_difference
  19.   // 同时也会追踪当前数组中的最小值，从而保证 `largest value in future` - `smallest value before it`

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

  29.   // If negative or 0, there is no largest difference
  30.   if (current_max_difference <= 0) return -1;

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

  5. productExceptSelf(firstArray); // [8, 8, 4, 16]
  6. productExceptSelf(secondArray); // [0, 0, 0, 0]
  7. productExceptSelf(thirdArray); // [12, 12, 8, -12]

  9. function productExceptSelf(numArray) {
  10.   var product = 1;
  11.   var size = numArray.length;
  12.   var output = [];

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

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

  31.   return output;
  32. }
复制代码

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

数组交集
给定两个数组，要求求出两个数组的交集，注意，交集中的元素应该是唯一的。
  1. var firstArray = [2, 2, 4, 1];
  2. var secondArray = [1, 2, 0, 2];

  4. intersection(firstArray, secondArray); // [2, 1]

  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.

  11.   var hashmap = {};
  12.   var intersectionArray = [];

  14.   firstArray.forEach(function(element) {
  15.     hashmap[element] = 1;
  16.   });

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

  26.   return intersectionArray;

  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!";

  3. // Output becomes !ediuG tpircsavaJ siht ot emocleW
  4. var reverseEntireSentence = reverseBySeparator(string, "");

  6. // Output becomes emocleW ot siht tpircsavaJ !ediuG
  7. var reverseEachWord = reverseBySeparator(reverseEntireSentence, " ");

  9. function reverseBySeparator(string, separator) {
  10.   return string.split(separator).reverse().join(separator);
  11. }
复制代码

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

乱序同字母字符串
给定两个字符串，判断是否颠倒字母而成的字符串，譬如Mary与Army就是同字母而顺序颠倒：
  1. var firstWord = "Mary";
  2. var secondWord = "Army";

  4. isAnagram(firstWord, secondWord); // true

  6. function isAnagram(first, second) {
  7.   // For case insensitivity, change both words to lowercase.
  8.   var a = first.toLowerCase();
  9.   var b = second.toLowerCase();

  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("");

  15.   return a === b;
  16. }
复制代码

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

会问字符串
判断某个字符串是否为回文字符串，譬如racecar与race car都是回文字符串：
  1. isPalindrome("racecar"); // true
  2. isPalindrome("race Car"); // true

  4. function isPalindrome(word) {
  5.   // Replace all non-letter chars with "" and change to lowercase
  6.   var lettersOnly = word.toLowerCase().replace(/\s/g, "");

  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

  4. // For enqueue, just push the item into the first stack
  5. function enqueue(stackInput, item) {
  6.   return stackInput.push(item);
  7. }

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

  20.   return stackOutput.pop();
  21. }
复制代码

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


判断大括号是否闭合
创建一个函数来判断给定的表达式中的大括号是否闭合：
  1. var expression = "{{}}{}{}"
  2. var expressionFalse = "{}{{}";

  4. isBalanced(expression); // true
  5. isBalanced(expressionFalse); // false
  6. isBalanced(""); // true

  8. function isBalanced(expression) {
  9.   var checkString = expression;
  10.   var stack = [];

  12.   // If empty, parentheses are technically balanced
  13.   if (checkString.length <= 0) return true;

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

  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

  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;

  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

  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)

  18.   return number & (number - 1) === 0;
  19. }

  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
   
关于葡萄城：全球最大的控件提供商，世界领先的企业应用定制工具、企业报表和商业智能解决方案提供商，为超过75%的全球财富500强企业提供服务。

0 个回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
产品与服务
活字格低代码平台
Wyn 商业智能软件
SpreadJS纯前端表格控件
技术服务体系
技术博客
低代码技术
客户与案例
典型客户
成功案例
用户访谈
合作与生态
合作伙伴网络
葡萄城市场
葡萄城与国产化
活字格用友客开工具
品牌活动
葡萄城公开课
品牌战略发布会
赋能开发者高峰论坛
企业级低代码发展研讨会
企业级低代码应用大赛
表格技术研讨会
了解葡萄城
葡萄城简介
愿景使命
研发与创新
荣誉奖项
加入我们
联系方式
联系我们
400-657-6008

葡萄城社区二维码

关注“葡萄城社区”

赋能开发者

西安葡萄城软件有限公司
专业的软件开发技术和低代码平台提供商

陕ICP备2020018819号  |   陕公网安备：61019002000258  |   隐私政策  |   网站地图  

邮箱： info.xa@grapecity.com  |  © 2024 葡萄城软件，保留所有权利

Archiver| 手机版| 小黑屋|

返回顶部