您当前的位置：首页 > 计算机 > 编程开发 > 数据结构与算法

面试之递归、斐波那契数列、快速排序、二分查找

时间：12-14来源：作者：点击数：5

算法，这个题目有点大。

其实算法是一个很宽的概念，我们写的所有程序都可称之为算法，因为算法就是一个处理问题的逻辑，将问题进行归类，抽象出一个统一范式，然后为这个范式取个名字，比如：快速排序。

所以这里我们就来看下前端有哪些常用的算法。

递归

递归算法

英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

递归的两个要素：

调用自身
能跳出循环

阶乘

n! = n*(n-1)...21
6! = 6 * 5 * 4 * 3 * 2 *1

规律：n 的阶乘就是从 n 开始依次递减值的积

    functionfactorial(number){
      if(number==1) {
        return number;
      } else{
        return number * factorial(number - 1);
      }
    }

斐波那契数列

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 求第 n 个数是多少

第一个数: 1
第二个数: 1
第三个数: 1+1
第三个数: 2+1+1
第四个数: 3+2+1+1
第五个数: 4+3+2+1+1
...

规律：后一项是前两项的和

    functionfibonacci(number) {
      if (number <=2) {
        return1;
      }
      return fibonacci(number-1) + fibonacci(number -2)
    }

排序算法

冒泡排序算法

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

比较流程

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

升顺排列

6 2 7 9 5

第一次冒泡: 2 6 7 9 5
第二次冒泡: 2 5 7 9 6
...

    // 升序比较functionbubbleSort(arr) {
      var nArr =arr.slice();
      var temp;
      if (nArr.length>0) {
         for (var i =0; i <nArr.length; i++){
            for (var l = i; l < (nArr.length-1); l++){
                if (nArr[i] > nArr[l+1]) {            
                  temp = nArr[i];
                  nArr[i] = nArr[l+1];
                  nArr[l+1] = temp;
                }
            }
         }
      }
    
      return nArr;
    }

快速排序算法

快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。

排序说明

第一步: 基准值选取。基准值可以任意选取
第二步: 进行分区操作。按照顺序将每个元素与基准进行比较，想成两个子集（大于基准值，小于基准值）
第三步，递归操作。对两个子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止

    functionqSort(arr) {
      if (arr.length==0) {
          return [];
      }
      var left = [];
      var right = [];
      var pivot = arr[0];
      for (var i =1; i <arr.length; i++) { // 注意这里的起始值，因为有一个作为 flag 了
          if (arr[i] < pivot) {
              left.push(arr[i]);
          } else {
              right.push(arr[i]);
          }
      }
      return qSort(left).concat(pivot, qSort(right));
    }

检索算法

二分查找算法

也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

查找说明

将数组的第一个位置设置为下边界（0）

将数组最后一个元素所在的位置设置为上边界（数组的长度减1）。

若下边界等于或小于上边界，则做如下操作。

将中点设置为（上边界加上下边界）除以2

如果中点的元素小于查询的值，则将下边界设置为中点元素所在下标加1

如果中点的元素大于查询的值，则将上边界设置为中点元素所在下标减1

否则中点元素即为要查找的数据，可以进行返回。

注意这里的数组必须是有序的

function binSearch(arr, data) {
  var upperBound =arr.length-1;
  var lowerBound =0;
  while (lowerBound <= upperBound) {
      var mid =Math.floor((upperBound + lowerBound) /2);
      if (arr[mid] < data) {
          lowerBound = mid +1;
      }
      elseif(arr[mid] > data) {
          upperBound = mid -1;
      } else {
          return mid;
      }
  }
  return-1;
}

二叉树算法

二叉树

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的特性

每个结点最多有两颗子树，结点的度最大为2
左子树和右子树是有顺序的，次序不能颠倒
即使某结点只有一个子树，也要区分左右子树。

二叉树遍历

这里采用递归 - 先序遍历一个树形结构

varpreOrder=function (node) {
  if (node) {
    console.log(node.value);
    preOrder(node.left);
    preOrder(node.right);
  }
}

JavaScript 经典面试题

一：记忆化斐波那契函数（Memoization）

题目：斐波那契数列指的是类似于以下的数列：

1, 1, 2, 3, 5, 8, 13, ....

也就是，第 n 个数由数列的前两个相加而来：f(n) = f(n - 1) + f(n -2)

请你完成 fibonacci 函数，接受 n 作为参数，可以获取数列中第 n 个数，例如：

fibonacci(1) // => 1
fibonacci(2) // => 1
fibonacci(3) // => 2

测试程序会从按顺序依次获取斐波那契数列中的数，请注意程序不要超时，也不要添加额外的全局变量。

本题来源：《JavaScript 语言精髓》

答案：

const fibonacci = ((memo = [0, 1]) => {
  const fib = (n) => {
    let result = memo[n]
    if (typeof result !== "number") {
      result = fib(n - 1) + fib(n - 2)
      memo[n] = result
    }
    return result
  }
  return fib
})()

二：解析字串

题目：完成一个 extractStr 函数，可以把一个字符串中所有的 : 到 . 的子串解析出来并且存放到一个数组当中，例如：

extractStr('My name is:Jerry. My age is:12.') // => ['Jerry', '12']

注意，: 和 . 之间不包含 : 和 .。也即是说，如果 ::abc..，则返回 ['abc']。

本题来源：《JavaScript Cookbook》

答案：

const extractStr = (str) => {
  const ret = str.match(/:([^:\.])*?\./g) || []
  return ret.map((subStr) => subStr.replace(/[:\.]/g, '')) 
}

三： safeGet

题目：有时候我们需要访问一个对象较深的层次，但是如果这个对象某个属性不存在的话就会报错，例如：

var data = { a: { b: { c: 'ScriptOJ' } } }
data.a.b.c // => scriptoj
data.a.b.c.d // => 报错，代码停止执行
console.log('ScriptOJ') // => 不会被执行

请你完成一个 safeGet 函数，可以安全的获取无限多层次的数据，一旦数据不存在不会报错，会返回 undefined，例如：

var data = { a: { b: { c: 'ScriptOJ' } } }
safeGet(data, 'a.b.c') // => scriptoj
safeGet(data, 'a.b.c.d') // => 返回 undefined
safeGet(data, 'a.b.c.d.e.f.g') // => 返回 undefined
console.log('ScriptOJ') // => 打印 ScriptOJ

答案：

const safeGet = (o, path) => {
  try {
    return path.split('.').reduce((o, k) => o[k], o)
  } catch (e) {
    returnvoid666
  }
}

四：判断两个矩形是否重叠

题目：用一个对象的数据来表示一个矩形的位置和大小：

{
  x: 100,
  y: 100,
  width: 150,
  height: 250
}

它表示一个宽为 150 高为 250 的矩形在页面上的 (100, 100) 的位置。

请你完成一个函数 isOverlap 可以接受两个矩形作为参数，判断这两个矩形在页面上是否重叠。例如：

const rect1 = { x: 100, y: 100, width: 100, height: 100 }
const rect2 = { x: 150, y: 150, width: 100, height: 100 }
isOverlap(rect1, rect2) // => true

答案：

// 原理：http://www.geeksforgeeks.org/find-two-rectangles-overlap/
const isOverlap = (rect1, rect2) => {
  const l1 = { x: rect1.x, y: rect1.y }
  const r1 = { x: rect1.x + rect1.width, y: rect1.y + rect1.height }
  const l2 = { x: rect2.x, y: rect2.y }
  const r2 = { x: rect2.x + rect2.width, y: rect2.y + rect2.height }
  if (
    l1.x > r2.x ||
    l2.x > r1.x ||
    l1.y > r2.y ||
    l2.y > r1.y
  ) returnfalsereturntrue
}

五： spacify

题目：请你给字符串都添加上原型方法 spacify，可以让一个字符串的每个字母都多出一个空格的间隔：

"ScriptOJ".spacify() // => "S c r i p t O J"

本题来源：http://blog.sourcing.io/interview-questions

答案：

String.prototype.spacify = function () {
  returnthis.split('').join(' ')
}

六：按下标插入

题目：现在有一个数组存放字符串数据：

['item1', 'item2', 'item3', 'item4', 'item5']

有另外一个数组存放一组对象：

[
  { content: 'section1', index: 0 },
  { content: 'section2', index: 2 }
]

它每个对象表示的是会往原来的数组的 index 坐标插入 content 数据（index 不会重复）：

01234
 item1  itme2  item3  item4  item5
^             ^ 
|             |

section1 section2

最后结果是：['section1', 'item1', 'item2', 'section2', 'item3', 'item4', 'item5']

请你完成 injectSections 函数，可以达到上述的功能：

injectSections(
  ['item1', 'item2', 'item3', 'item4', 'item5'],
  [
    { content: 'section1', index: 0 },
    { content: 'section2', index: 2 }
  ]
) // => ['section1', 'item1', 'item2', 'section2', 'item3', 'item4', 'item5']

答案：

const injectSections = (items, sections) => {
  /* 需要插入坐标对应数据存放到 map 里面 */
  const sectionsMap = newMap(sections.map(({ index, content }) => [index, content]))
  /* 新建一个数组，然后往里面 push 原来数组的数据 */
  return items.reduce((ret, item, index) => {
    /* push 的时候先检查 map 里面有没有，有的话先 push map 里面的数据 */
    if (sectionsMap.has(index)) ret.push(sectionsMap.get(index))
    /* 再 push 原来的数据 */
    ret.push(item)
    return ret
  }, [])
}

七：数组拍平（二）

题目：编写一个 JavaScript generator 函数，接受一个仅包含数字的多维数组，返回一个迭代器，可以遍历得到它拍平以后的结果。例如：

const numbers = flatten2([1, [[2], 3, 4], 5])
numbers.next().value // => 1
numbers.next().value // => 2
numbers.next().value // => 3
numbers.next().value // => 4
numbers.next().value // => 5

答案：

function *flatten2(arr) {
  for (let i = 0; i < arr.length; i++) {
    const item = arr[i]
    /* yield* 的使用可以大大简化程序编写 */
    Array.isArray(item) ? yield* flatten2(item) : yield item;
  }
}

/* 用 flatten2 来完成 flatten 也是很方便的 */
// const flatten = (arr) => [...flatten2(arr)]

八：判断两个 Set 是否相同

题目：完成 isSameSet 函数，它接受了两个 Set 对象作为参数，请你返回 true/false 来表明这两个 set 的内容是否完全一致，例如：

const a = {}
const b = 1const c = 'ScriptOJ'const set1 = newSet([a, b, c])
const set2 = newSet([a, c, b])

isSameSet(set1, set2) // => true

答案：

/* 这道题不能简单地使用 sort，使用 sort 并不靠谱。因为 Set 里面的内容可能有很多种类
 * 字符串、对象、数字，不同类型之间是不可对比的，所以排序结果并不会一致
 *
 * 最好的方式是按照数学上集合相等的定义：
 * A = B 当且仅当 A 是 B 的子集并且 B 是 A 的子集。
 *
 * 这种判断方式还可以用在 对象、map 等其他数据类型的判断当中。
 */const isSameSet = (s1, s2) => {
  /* 获取一个集合所有的值，判断另外一个集合是否全部包含该这些值 */const isSame = (a, b) => {
    const values = [...a]
    for (let val of values) {
      /* 及时跳出循环，可以降低算法复杂度 */if (!b.has(val)) returnfalse
    }
    returntrue
  }
  /* a 包含 b，b 包含 a，那么两个集合相同 */return isSame(s1, s2) && isSame(s2, s1)
}

/* By 陈小俊 */
// const isSameSet = (set1, set2) =>
//   [...set1].every((o) => set2.has(o)) &&
//   [...set2].every((o) => set1.has(o))

九：数组去重

题目：编写一个函数 unique(arr)，返回一个去除数组内重复的元素的数组。例如：

unique([0, 1, 2, 2, 3, 3, 4]) // => [0, 1, 2, 3, 4]
unique([0, 1, '1', '1', 2]) // => [0, 1, '1', 2]

答案：

const unique = (arr) => [...new Set(arr)]

十：字体高亮函数

题目：请你完成 highlight 函数，可以把模版字符串中的插入内容替换掉，并且插入文档以后显示红色。例如：

const yourName = 'ScriptOJ'
const myName = 'Jerry'
document.body.innerHTML = highlight`Hello, ${yourName}. I am ${myName}.`

上面例子的页面显示如下：

0_1498033735172_upload-2abd65b1-1e98-46ba-b46f-df4188a036a5

请你完成 highlight 函数的编写。

答案：

css:

.highlight {
  color: red;
}

js:

// 考察的是 Tagged template literals 的使用
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Template_literalsconst
highlight = (strings, ...args) => {
  return strings.reduce((str, cur, i) => {
    return`${str}${cur}${args[i] ? `<span class="highlight">${args[i]}</span>` : '' }`
  }, '')
}