之前因为工作原因接触了很多有意思的算法知识,为了巩固大家的算法基础和编程能力,笔者将开展为期2个月的算法学习打卡, 每周3-5次算法训练, 并附有算法题的答案, 供大家学习参考. 接下来我们复盘第三周的算法打卡内容.

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

[优质解法]

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

[参考解法]

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

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

[参考解法]

    3.1 实现步骤:

  1. 用 JavaScript 对象结构表示 DOM 树的结构;然后用该对象构建一个真正的 DOM 树,插到文档中

  2. 当状态变更的时候,重新构造一棵新的对象树。然后用新的树和旧的树进行比较,记录两棵树的差异

  3. 把第二步所记录的差异应用到步骤1所构建的真正的DOM树上,视图更新

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

// 定义虚拟元素
function Element (tagName, props, children) {
  this.tagName = tagName
  this.props = props
  this.children = children
}
// 渲染方法
Element.prototype.render = function () {
  let el = document.createElement(this.tagName) // 根据tagName构建
  let props = this.props


  for (let propName in props) { // 设置节点的DOM属性
    let propValue = props[propName]
    el.setAttribute(propName, propValue)
  }


  let children = this.children || []


  children.forEach(function (child) {
    let childEl = (child instanceof Element)
      ? child.render() // 如果子节点也是虚拟DOM,递归构建DOM节点
      : document.createTextNode(child) // 如果字符串,只构建文本节点
    el.appendChild(childEl)
  })
  return el
}
// 更新逻辑
Element.prototype.updateElement = function (root, newEl, oldEl, index = 0) {
    if (!oldEl){
        root.appendChild(newEl.render());
    } else if (!newEl) {
        root.removeChild(root.childNodes[index]);
    } else if ((typeof newEl !== typeof oldEl) ||
           (typeof newEl === 'string' && newEl !== oldEl) ||
           (newEl.type !== oldEl.type)) {
        if (typeof newEl === 'string') {
            root.childNodes[index].textContent = newEl;
        } else {
            root.replaceChild(newEl.render(), root.childNodes[index]);
        }
    } else if (newEl.tagName) {
        let newLen = newEl.children.length;
        let oldLen = oldEl.children.length;
        for (let i = 0; i < newLen || i < oldLen; i++) {
            this.updateElement(root.childNodes[index], newEl.children[i], oldEl.children[i], i)
        }
    }
}

参考文献

Virtual DOM    https://medium.com/@deathmood/write-your-virtual-dom-2-props-events-a957608f5c76

最后

接下笔者将会继续带着大家每周进行算法学习打卡, 并持续推出以实战为主大前端知识技能探索和实践. 赶紧一起学习吧~

往期打卡回顾

javascript算法学习打卡(第二周)

javascript算法学习打卡(第一周)

javascript经典算法之最小硬币找零问题

前端进阶第8-9周打卡题目汇总

初中级前端面试题目汇总和答案解析

前端进阶第7周打卡题目汇总

前端进阶第6周打卡题目汇总

前端进阶第5周打卡题目汇总

前端进阶第4周打卡题目汇总

前端进阶第3周打卡题目汇总