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

徐小夕 等级 419 0 0

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

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

参考答案:

/**
 * arr 待排序数组
 * result 计算的结果数组
 */
function rangeArr(arr = [], result = []) {
  arr.forEach(item => {
    let i = /\d*$/.exec(item)[0]
    result[i] ? result[i].push(item) : (result[i] = [item])
  })
  return result.filter(Boolean)
}

网友优质答案:

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

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的所有可能有序对的其中一个成员 。

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

参考答案:

/*
 * @Author: Mr Jiang.Xu
 * @Date: 2019-08-31 00:05:33
 * @Last Modified by:   Mr Jiang.Xu
 * @Last Modified time: 2019-08-31 00:05:33
 */
function cartesian(arr) {
  if (arr.length < 2) return arr[0] || [];
  return [].reduce.call(arr, function (col, set) {
    let res = [];
    col.forEach(c => {
        set.forEach(s => {
          let t = [].concat(Array.isArray(c) ? c : [c]);
          t.push(s);
          res.push(t);
        })
    });
    return res;
  });
}

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

// 创建集合,并实现交集,差集,补集,并集
function MySet() {
  let items = {}
  // 判断值是否存在
  this.has = function(val) {
    return val in items
  }
  // 添加
  this.add = function(val) {
    if(!this.has(val)) {
      items[val] = val
      return true
    }
    return false
  }
  // 移除
  this.remove = function(val) {
    if(this.has(val)) {
      delete items[val]
      return true
    }
    return false
  }
  // 清空
  this.clear = function() {
    items = {}
  }
  // 大小
  this.size = function() {
    return Object.keys(items).length
  }
  // 取值
  this.values = function() {
    return Object.keys(items)
  }
  // 并集
  this.union = function(otherSet) {
    let unionSet = new Set()
    let values = this.values()
    for(let i=0; i < values.length; i++) {
      unionSet.add(values[i])
    }

    values = otherSet.values()
    for(let i=0; i < values.length; i++) {
      unionSet.add(values[i])
    }

    return unionSet
  }
  // 交集
  this.intersection = function(otherSet) {
    let intersectionSet = new Set()
    let values = this.values()
    for(let i=0; i<values.length; i++) {
      if(otherSet.has(values[i])) {
        intersectionSet.add(values[i])
      }
    }
    return intersectionSet
  }
  // 差集
  this.difference = function(otherSet) {
    let differenceSet = new Set()
    let values = this.values()
    for(let i = 0; i < values.length; i++) {
      if(!otherSet.has(values[i])) {
        differenceSet.add(values[i])
      }
    }
    return differenceSet
  }
  // 子集
  this.subset = function(otherSet) {
    if(this.size() > otherSet.size()) {
      return false
    }else {
      let values = this.values()
      for(let i=0; i<values.length; i++) {
        if(!otherSet.has(values[i])) {
          return false
        }
      }
      return true
    }
  }
}

其他优质答案:

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

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算法, 实现每次都返回不同的坐标值, 且坐标值都在圆内.

[参考解法]

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()
    }
  }
}

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

[参考解法]

实现步骤:

  • 用 JavaScript 对象结构表示 DOM 树的结构;然后用该对象构建一个真正的 DOM 树,插到文档中
  • 当状态变更的时候,重新构造一棵新的对象树。然后用新的树和旧的树进行比较,记录两棵树的差异
  • 把第二步所记录的差异应用到步骤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)
        }
    }
}

最后

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

收藏
评论区

相关推荐

一个线上问题的思考:Eureka注册中心集群如何实现客户端请求负载及故障转移?
前言 先抛一个问题给我聪明的读者,如果你们使用微服务SpringCloudNetflix进行业务开发,那么线上注册中心肯定也是用了集群部署,问题来了: 你了解Eureka注册中心集群如何实现客户端请求负载及故障转移吗? 可以先思考一分钟,我希望你能够带着问题来阅读此篇文章,也希望你看完文章后会有所收获! 背景 前段时间线上Sentry平台报警,
关于面试题:[1, 2, 3].map(parseInt)问题的剖析
一、前言 最近有小伙伴在公号中咨询了胡哥这道面试题,窃以为是比较有意思的一道面试题,于此分享给各位小伙伴。先把答案给了各位,和你理解的一样吗?! 1, 2, 3.map(parseInt) // 1, NaN, NaN 如果你答案你都明白,请出门左转:React源码/原理了解一下。 二、剖析 这道面试题,本身并不复杂。不能正确回答问题的小伙
图文并茂讲清楚 JavaScript 内存管理
作为一个 JavaScript 的开发者,大多数情况下你可能不会担心内存管理问题,因为 JavaScript 引擎会帮你处理这些。但是在开发过程中,你或多或少的会遇到一些相关的问题,比如内存泄漏等,只有了解了内存分配的工作机制,你才会知道如何去解决这些问题。 在这篇文章中,我将会向你介绍 内存分配 和 垃圾收集 的机制,以及如何避免一些 常见的内存泄漏 的
初步了解01背包问题(分治篇)
目录 问题描述(问题描述) 输入格式(输入格式) 输出格式(输出格式) 基于0/1背包的迭代算法(基于01背包的动态规划算法) 0/1背包问题的分析(01背包问题的分析) 分治法(分治法) 总结(总结) 问题描述 Coda非常喜欢玩“NewWorld Online”,受到某部动画的影响,他
java传值和传引用问题
这个问题还是很常见的,如果你平常敲代码比较多你可能经常会遇到这个问题。如果你知道java这个机制,你可能还会一直在找代码的问题。java中的值传递和引用传递。比如下面有这俩个方法java private void updataValue(String s){ s "123"; } private void upd
完全背包问题
问题描述 有n种物品和一个容量为c的背包,每种物品都就可以选择任意多个,第i种物品的价值为v\i\,体积为w\i\,求解:在不超过背包容量的情况下,选择放入哪些物品能够使得背包中的价值最大?跟01背包一样,完全背包也是一个很经典的动态规划问题,不同的地方在于01背包问题中,每件物品最多选择一件;而在完全背包问题中,只要背包装得下,每件物品可
JS 手撕-经典面试题
引言首先出这篇文章,一方面是为了记录巩固我所学的知识,明白面试的高频考点。不鼓励大家背题的,初衷是希望总结的一些面试题能帮助你查漏补缺,温故知新。这些题并不是全部,如果你还想看得更多,可以访问,目前已经有552道大厂真题了,涵盖各类前端的真题,欢迎加入我们一起来讨论~函数 call 语法:fn.call(obj,...args) 功
前后端分离的情况下,vue保存cookie时碰到的坑! (axios.defaults.withCredentials = true;)
文章目录 一号坑问题描述当我们的项目是前后端分离的模式时,vue不会自动帮我们保存后端传来的cookie!解决方案我们需要在main中添加axios.defaults.withCredentials true 二号坑问题描述如果你之前处理过跨域方面的问题,应该会记得你曾经在后端请求头添加
你不可不知的JS面试题(第一期)
1、JS中有哪些内置类型?7种。分别是boolean、number、string、object、undefined、null、symbol。 2、NaN是独立的一种类型吗?不是。NaN是number类型。 3、如何判断是哪个类型?Object.prototype.toString.call(),返回为[object Type]。现在我们来验证一下。Objec
你不可不知的JS面试题(第二期)
1、什么是继承?子类可以使用父类的所有功能,并且对功能进行扩展。 新增方法 改用方法 (1)、ES6使用extends子类继承父类的方法。 // 父类     class A         constructor(name)             this.name name;                  getNa
一种极致性能的缓冲队列
本文已收录 https://github.com/lkxiaolou/lkxiaolou 欢迎star。 背景在多线程下的生产者消费者模型中,需求满足如下情况:对生产者生产投递数据的性能要求非常高多个生产者,单个(多个也可以,本文只介绍单个的情况)消费者当消费者跟不上生产者速度时,可容忍少部分数据丢失生产者是单条单条地生产数据举个日志采集的例子,日志在不同的
你不可不知的JS面试题(第三期)
1、什么是闭包?如图所示,闭包就是一个定义在函数内部的函数,其作用是将函数内部和函数外部连接起来。大家知道,作用域的问题,就是在函数内部定义的变量称为局部变量,外部取不到值。下面我们通过代码来更加详细地看一下: function A()        let x  1;        return function B()            c
你不可不知的JS面试题
1、JS中有哪些内置类型?7种。分别是boolean、number、string、object、undefined、null、symbol。 2、NaN是独立的一种类型吗?不是。NaN是number类型。 3、如何判断是哪个类型?Object.prototype.toString.call(),返回为\[object Type\]。 现在我们来验证一下
【Java面试题】全网最全,近5年133个Java面试问题列表汇总,让你轻松拿大厂offer!!!!
133个Java面试问题列表汇总 前言Java 面试随着时间的改变而改变。在过去的日子里,当你知道 String 和 StringBuilder 的区别就能让你直接进第二轮面试但是现在问题变得越来越高级,面试官问的问题也更深入。 在我初入职场的时候,类似于 Vector 与 Array 的区别、HashMap 与 Hashtable 的区别是最流行的问题。
JAVA回调机制(CallBack)之小红是怎样买到房子的??
JAVA回调机制CallBack 序言最近学习java,接触到了回调机制(CallBack)。初识时感觉比较混乱,而且在网上搜索到的相关的讲解,要么一言带过,要么说的比较单纯的像是给CallBack做了一个定义。当然了,我在理解了回调之后,再去看网上的各种讲解,确实没什么问题。但是,对于初学的我来说,缺了一个循序渐进的过程。此处,将我对回调机制的个人理解,按