这些经典的前端基础算法题, 你会做几道?

之前因为工作原因接触了很多有意思的算法知识,为了巩固大家的算法基础和编程能力,笔者总结了8道算法题, 供大家学习参考. 接下来我们来看看题目.

1. 有一个数组arr = [a1, a2, a3, b1, b2, b3, c1, c2, c3...], 通过算法将数组进行拆分, 转化为如下格式的数组a1, b1, c1], [a2, b2, c2], [a3, b3, c3]并实现通用公式.

参考答案:

1/**
2 * arr 待排序数组
3 * result 计算的结果数组
4 */
5function rangeArr(arr = [], result = []) {
6  arr.forEach(item => {
7    let i = /\d*$/.exec(item)[0]
8    result[i] ? result[i].push(item) : (result[i] = [item])
9  })
10  return result.filter(Boolean)
11}

网友优质答案:

2. 假设集合A={a, b}，集合B={0, 1, 2}，则两个集合的笛卡尔积为{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}。求当A={a, b, ..., n}, B={0, 1, 2, ..., n}时的笛卡尔积.

笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尓积，又称直积，表示为X × Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。

参考答案:

1/*
2 * @Author: Mr Jiang.Xu
3 * @Date: 2019-08-31 00:05:33
4 * @Last Modified by:   Mr Jiang.Xu
5 * @Last Modified time: 2019-08-31 00:05:33
6 */
7function cartesian(arr) {
8  if (arr.length < 2) return arr[0] || [];
9  return [].reduce.call(arr, function (col, set) {
10    let res = [];
11    col.forEach(c => {
12        set.forEach(s => {
13          let t = [].concat(Array.isArray(c) ? c : [c]);
14          t.push(s);
15          res.push(t);
16        })
17    });
18    return res;
19  });
20}

3. 原生js实现一个Set数据类型, 并实现集合的差集, 并集, 补集, 交集

1// 创建集合,并实现交集,差集,补集,并集
2function MySet() {
3  let items = {}
4  // 判断值是否存在
5  this.has = function(val) {
6    return val in items
7  }
8  // 添加
9  this.add = function(val) {
10    if(!this.has(val)) {
11      items[val] = val
12      return true
13    }
14    return false
15  }
16  // 移除
17  this.remove = function(val) {
18    if(this.has(val)) {
19      delete items[val]
20      return true
21    }
22    return false
23  }
24  // 清空
25  this.clear = function() {
26    items = {}
27  }
28  // 大小
29  this.size = function() {
30    return Object.keys(items).length
31  }
32  // 取值
33  this.values = function() {
34    return Object.keys(items)
35  }
36  // 并集
37  this.union = function(otherSet) {
38    let unionSet = new Set()
39    let values = this.values()
40    for(let i=0; i < values.length; i++) {
41      unionSet.add(values[i])
42    }
43
44    values = otherSet.values()
45    for(let i=0; i < values.length; i++) {
46      unionSet.add(values[i])
47    }
48
49    return unionSet
50  }
51  // 交集
52  this.intersection = function(otherSet) {
53    let intersectionSet = new Set()
54    let values = this.values()
55    for(let i=0; i<values.length; i++) {
56      if(otherSet.has(values[i])) {
57        intersectionSet.add(values[i])
58      }
59    }
60    return intersectionSet
61  }
62  // 差集
63  this.difference = function(otherSet) {
64    let differenceSet = new Set()
65    let values = this.values()
66    for(let i = 0; i < values.length; i++) {
67      if(!otherSet.has(values[i])) {
68        differenceSet.add(values[i])
69      }
70    }
71    return differenceSet
72  }
73  // 子集
74  this.subset = function(otherSet) {
75    if(this.size() > otherSet.size()) {
76      return false
77    }else {
78      let values = this.values()
79      for(let i=0; i<values.length; i++) {
80        if(!otherSet.has(values[i])) {
81          return false
82        }
83      }
84      return true
85    }
86  }
87}

其他优质答案:

4. 给定一个任意嵌套结构的对象如下，使用你熟悉的算法，将对象的属性按照层级输出到一个数组中.如下：

参考答案: 更多优质答案：

5.找出数字数组中出现多次的数字，比如[1,2,2,3,4,5,4] => [2,4]

其他优质答案: 对这个问题的进一步扩展，比如说我不仅要求重复的数字，我还要计算出出现次数最多的数字呢？笔者写了一个方法，供大家参考：

6. 输入一个正数N, 输出所有和为N的连续正数序列. 例如输入15, 结果: [[1, 2, 3, 4, 5], [4, 5, 6], [7, 8]].

[优质解法]

7. 已知圆的半径为1, 用javascript算法, 实现每次都返回不同的坐标值, 且坐标值都在圆内.

[参考解法]

1function generateRandomPos() {
2  // 缓存已存在坐标
3  const cache = {}
4  // 圆形边界
5  const boundRect = [-1, 1]
6  // 生成在-1到1的随机值
7  const random = () => boundRect[+(Math.random() > 0.5)] * Math.random()
8  return generate()
9  function generate() {
10    // 生成x,y坐标
11    let x = random(),
12        y = random()
13    // 根据勾股定理,xy的平方和应小于等于1(圆形坐标关系),并且之前没有生成同样的坐标
14    if(Math.pow(x, 2) + Math.pow(y, 2) <= 1 && !cache[`${x}${y}`]) {
15      return cache[`${x}${y}`] = [x, y]
16    }else {
17      return generate()
18    }
19  }
20}

8. 用原生javasctript实现一个虚拟dom及其基本渲染api.

[参考解法]

实现步骤:

用 JavaScript 对象结构表示 DOM 树的结构；然后用该对象构建一个真正的 DOM 树，插到文档中
当状态变更的时候，重新构造一棵新的对象树。然后用新的树和旧的树进行比较，记录两棵树的差异
把第二步所记录的差异应用到步骤1所构建的真正的DOM树上，视图更新

Virtual DOM 本质就是在 JS 和 DOM 之间做了一个缓存, 实现代码如下:

1// 定义虚拟元素
2function Element (tagName, props, children) {
3  this.tagName = tagName
4  this.props = props
5  this.children = children
6}
7// 渲染方法
8Element.prototype.render = function () {
9  let el = document.createElement(this.tagName) // 根据tagName构建
10  let props = this.props
11
12  for (let propName in props) { // 设置节点的DOM属性
13    let propValue = props[propName]
14    el.setAttribute(propName, propValue)
15  }
16
17  let children = this.children || []
18
19  children.forEach(function (child) {
20    let childEl = (child instanceof Element)
21      ? child.render() // 如果子节点也是虚拟DOM，递归构建DOM节点
22      : document.createTextNode(child) // 如果字符串，只构建文本节点
23    el.appendChild(childEl)
24  })
25  return el
26}
27
28// 更新逻辑
29Element.prototype.updateElement = function (root, newEl, oldEl, index = 0) {
30    if (!oldEl){
31        root.appendChild(newEl.render());
32    } else if (!newEl) {
33        root.removeChild(root.childNodes[index]);
34    } else if ((typeof newEl !== typeof oldEl) ||
35           (typeof newEl === 'string' && newEl !== oldEl) ||
36           (newEl.type !== oldEl.type)) {
37        if (typeof newEl === 'string') {
38            root.childNodes[index].textContent = newEl;
39        } else {
40            root.replaceChild(newEl.render(), root.childNodes[index]);
41        }
42    } else if (newEl.tagName) {
43        let newLen = newEl.children.length;
44        let oldLen = oldEl.children.length;
45        for (let i = 0; i < newLen || i < oldLen; i++) {
46            this.updateElement(root.childNodes[index], newEl.children[i], oldEl.children[i], i)
47        }
48    }
49}

最后

如果想了解更多H5游戏, webpack，node，gulp，css3，javascript，nodeJS，canvas数据可视化等前端知识和实战，欢迎在公众号《趣谈前端》加入我们一起学习讨论，共同探索前端的边界。

这些经典的前端基础算法题, 你会做几道?

最后

评论区

相关推荐