掌握

常见的JavaScript面试算法
您需要的前端面试算法(上)
前端笔试&面试爬坑系列—-算法
前端面试必备-40道LeetCode经典面试算法题

二叉树
排序
数据结构

一、常见的JavaScript面试算法

1、斐波那契数列

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……..

这个数列从第3项开始，每一项都等于前两项之和。
斐波那契数列的定义者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci）

  1. // Base
  2. function Fibonacci1(n) {
  3.     if (n === 1) {
  4.         return 1
  5.     }
  6.     if (n === 2) {
  7.         return 1
  8.     }
  9.     if (n > 2) {
  10.         return Fibonacci1(n - 1) + Fibonacci1(n - 2)
  11.     }
  12. }
  14. // More
  15. function Fibonacci2(n) {
  16.     if (n === 1 || n === 2) {
  17.         return 1
  18.     } else {
  19.         var pre = 1
  20.         var next = 1
  21.         var target
  22.         for (var i = 3; i <= n; i++) {
  23.             target = pre + next
  24.             pre = next
  25.             next = target
  26.         }
  27.         return target
  28.     }
  29. }
  31. var start = new Date().getTime()
  32. console.log(Fibonacci1(30))       // 832040
  33. var end = new Date().getTime()
  34. console.log(end - start)         // 43
  36. start = new Date().getTime()
  37. console.log(Fibonacci2(30))      // 832040
  38. end = new Date().getTime()
  39. console.log(end - start)         // 0

上述写了实现斐波那契数列的两种方法，第一种方法用了递归；第二种方法用了循环赋值；通过上述实践，可以看出第二种方式的时间空间复杂度很小很小。所以，在此推荐用第二种方法实现斐波那契数列

2、字符串反转


  1. var strChar = 'wangsuoling'
  3. // Base
  4. function strReserve1 (str) {
  5.   if (typeof str !== 'string') {
  6.     return false
  7.   } else {
  8.     var result = ''
  9.     // 字符串通过索引取值，IE7及其以前的版本不支持
  10.     for (var i = str.length - 1; i >= 0 ; i--) {
  11.       result += str[i]
  12.     }
  13.     return result
  14.   }
  15. }
  17. // More
  18. function strReserve2 (str) {
  19.   if (typeof str !== 'string') {
  20.       return false
  21.   } else {
  22.       let strNew = str.split('').reverse().join('')
  23.       return strNew
  24.   }
  25. }
  27. var start = new Date().getTime()
  28. console.log(strReserve1(strChar))       // 'gnilousgnaw'
  29. var end = new Date().getTime()
  30. console.log(end - start)         // 0
  32. start = new Date().getTime()
  33. console.log(strReserve2(strChar))      // 'gnilousgnaw'
  34. end = new Date().getTime()
  35. console.log(end - start)         // 0

上述写了实现字符串反转的两种方法，通过上述实践，可以看出第二种方式的时间空间复杂度很小很小。所以，在此推荐用第二种方法实现字符串反转

3、判断字符串是否是回文

  1. var str1 = 'abeffeba'
  2. var str2 = 'abcdcba'
  3. var str3 = 'abcd1234'
  5. // Base
  6. function huiWen1 (str) {
  7.     for (let i = 0; i < str.length; i++) {
  8.         if (str[i] === str[str.length - 1 - i]) {
  9.             return true
  10.         } else {
  11.             return false
  12.         }
  13.     }
  14. }
  16. // Middle--利用栈 后进先出的特性
  17. function huiWen2 (str) {
  18.     var stackNewArr = [], len, mid, next, top
  19.     len = str.length
  20.     mid = Math.floor(len / 2 - 1)
  21.     top = 0
  22.     for (var i = 0; i <= mid; i++) {
  23.         stackNewArr[++top] = str[i]
  24.     }
  25.     if (len % 2 === 0) {
  26.         next = mid + 1
  27.     } else {
  28.         next = mid + 2
  29.     }
  30.     for (var j = next; j <= len-1; j++) {
  31.         if (str[j] !== stackNewArr[top]) {
  32.         break
  33.         }
  34.         top--
  35.     }
  37.     if (top === 0) {
  38.         return true
  39.     } else {
  40.         return false
  41.     }
  42. }
  44. // More
  45. function huiWen3 (str) {
  46.     let strNew = str.split('').reverse().join('')
  47.     if (strNew === str) {
  48.         return true
  49.     } else {
  50.         return false
  51.     }
  52. }
  54. var start = new Date().getTime()
  55. console.log(huiWen1(str2))       // true
  56. var end = new Date().getTime()
  57. console.log(end - start)         // 0
  59. start = new Date().getTime()
  60. console.log(huiWen2(str2))      // true
  61. end = new Date().getTime()
  62. console.log(end - start)         // 0
  64. start = new Date().getTime()
  65. console.log(huiWen3(str2))      // 'gnilousgnaw'
  66. end = new Date().getTime()
  67. console.log(end - start)         // 0

4、数组去重

  1. // 思路：设置一个临时数组temp，然后遍历要去重的数组arr，如果arr中的元素能够在temp中找到，则跳过此元素，否则将此元素存入temp，最后返回temp
  2. // Base
  3. function unique(arr){
  4.     var temp = [];
  5.     var len = arr.length;
  6.     for(var i = 0; i < len; i++){
  7.         if(temp.indexOf(arr[i]) === -1) temp.push(arr[i]);
  8.     }    
  9.     return temp;
  10. }
  11. // 思路：遍历要去重的数组arr, 循环判断当前元素的索引和从数组尾部查询的索引是否一致，不一致的情况，说明有重复项，则根据尾部的索引删除
  12. function unique(arr){
  13.     for(var i=0;i<arr.length;i++){
  14.     var lastIndex = arr.lastIndexOf(arr[i]
  15.     while(arr.indexOf(arr[i]) != lastIndex){
  16.       arr.splice(lastIndex,1)
  17.     }
  18.     }
  19.     return arr
  20. }

二、您需要的前端面试算法(上)

1、数组遍历

2、字符串替换

3、链表逆序打印

4、重建二叉树

5、栈与队列的互相实现

6、旋转数组的最小数字

7、斐波那契数列

8、位运算

9、数值的整数次方

10、删除链表节点

11、调整数组顺序

12、链表中导数第k个结点

13、反转链表

14、合并两个排序的链表

15、二叉树的包含

16、二叉树的镜像

17、顺时针打印矩阵

三、前端笔试&面试爬坑系列—-算法

1、排序

练习：

前端面试必备-40道LeetCode经典面试算法题

了解：

贪心算法

分治算法

动态规划