parentnode和parentelement【parent node】 收藏 0

大多数文档编辑器的【划线评论】功能，是如何实现的？

嗨, 大家好, 我是徐小夕.

文章首发自趣谈前端公众号

最近一直在迭代多模态文档编辑器flowmix/docx, 也研究学习了很多市面上流行的文档编辑器如腾讯文档, 钉钉文档等, 发现一个非常有价值的功能: 划词评论, 如下:

它可以让文档更有交互性, 也能在协同工作中发挥很大的价值, 刚好这几天研究了一下, 在flowmix/docx 多模态编辑器中实现了这个功能, 接下来就和大家分享一下具体的技术实现.

文档地址: http://flowmix.turntip.cn/docx

后续我会持续分享可视化零代码和多模态文档编辑器中的最新技术干货和产品思考~

本来想划线评论功能画个小半天就实现了， 没想到坑还挺多，对于追求代码质量，代码性能，产品体验的我来说，真的是快要把 javascript 祖师爷扒出来了。

实现划词评论功能之前,我们需要考虑如下几个核心要素:

• 划线评论不能污染文档本身
• 划线评论内容的加载性能
• 划线位置计算和评论列表的位置计算
• 划线评论完整业务数据流设计
• 文档滚动对划线的位置计算的影响

本来想用 canvas 实现的， 做了一个版本，但是考虑到后期的扩展性和灵活性，我还是重新选择了离屏dom + js 来实现。最终效果如下：

实现划词评论, 我们需要充分掌握 window.getSelection() API, 它对于实现富文本编辑器的各种功能来说都非常重要.

下面是我写的一个案例, 介绍了window.getSelection()的用法, 用来获取选中的文本, 然后进行自定义的操作:

当然这个是一个简单的案例, 方便大家更好的理解, 接下来我会分享一个更复杂的案例, 来剖析划词评论的实现原理.

首先实现划词评论需要理清实现的子目标, 接下来我来拆解一下划词评论的关键目标:

• 1.获取当前选中的文本内容和范围;
• 2.检查选中的文本是否已被选中，如果是则不进行画线处理;
• 3.获取选中文本的坐标信息;
• 4.计算选中文本的位置（这里先采用相对于视窗宽度的百分比）
• 5.将新的选中文本信息添加到 rects 状态数组中, 方便渲染划线
• 6.实现制定划线的评论功能

以下是从选中到计算坐标的完整实现逻辑, 大家可以参考一下:

接下来我们需要添加一个事件监听器来捕获 mouseup 事件，这样当用户释放鼠标按钮时，我们就可以处理选中的文本。

接下来我们来渲染高亮文本划线:

当然我们还需要处理当窗口滚动时的划线位置的动态计算, 我写了一个算法来实时更新位置, 大家可以参考一下:

当然还有很多方式可以实现划线评论, 后续我会持续分享和迭代.

之前我们做的 flowmix/docx 文档编辑器版本主要是为企业提供多模态文档解决方案, 帮助企业把多模态文档编辑器轻松集成到内部项目或者知识库产品中. 这里和大家分享一下目前迭代的功能清单:

11 – 12月对文档引擎的一些迭代规划(包含前后端规划):

• 支持文档工作流(基于文档内容自动生成可编辑的工作流)

• 支持高级可视化图表

• 支持AI侧边栏

• 支持一键生成PPT
• 支持多人协同功能

最近会快马加鞭, 做一款类似语雀 & 飞书的文档管理平台, 开放给大家使用. 也会在flowmix视界中同步最新的进展.

当然从体验上来讲, 文档还有很多优化的空间, 这块会持续优化和迭代, 并结合业界最佳体验实践, 将文档搭建能力发挥出最大的价值.

编辑器文档地址: http://flowmix.turntip.cn/docx

如果你有好的想法和建议, 也欢迎随时留言区交流讨论~

WebAPI详细解说【思维导图】

WebApi 思维导图见文章底部

• web: 网页
• API: 接口 一套别人封装的属性和方法
• webAPI: 专门操作网页的方法和属性万物皆对象，在webAPI中把网页中所有元素 <element> 都当成对象来处理

• 文档: document
• 元素: 网页中的标签
• 节点: 网页中所有的内容都叫节点(包括标签、属性、文本、注释)

元素节点就是标签节点

1. nodeType: 1
2. nodeName: 标签名(大写)
3. nodeValue: null

属性包括属性名和属性值

1. nodeType: 2
2. nodeName: 属性名
3. nodeValue: 属性值

1. nodeType: 3
2. nodeName: #text
3. nodeValue: 文本内容

1. nodeType: 8
2. nodeName: #comment
3. nodeValue: 注释内容

• window对象代表浏览器
• window对象是JavaScript中的顶级对象
• 任何全局变量和全局函数声明后 在预解析的过程中都会自动保存为window对象里面的属性和方法
• window的两个特殊属性名不能再次声明!!name: name属性名不管赋值任何值都会转换为字符串 let name = {}; -> [object Object]top
• window的两个方法

在计算机中 事件代表捕捉了用户进行了什么操作 再给对应的事件处理

事件源 事件类型 事件处理函数

用户操作的是什么元素 事件中的this就是事件的事件源(谁触发这个事件那this就是谁)

用户进行了什么操作

• onmouseover 鼠标移入
• onmouseout 鼠标移出
• window.onload 当页面加载完成后执行入口函数 如果想将js代码写在html之前 就可以用这个事件 将js代码写在事件处理函数中
• window.onunload 当页面退出前执行可以保存用户信息 => 用户未保存信息直接退出网页
• onfocus 获得焦点文本框光标闪烁
• onblur 失去焦点
• onkeyup 键盘弹起
• onkeydown 键盘按下
• onscroll 滚动当滚动页面滚动条时触发
• onclick 点击onclick 和 onmousedown 区别onclick 按下弹起才触发onmousedown 按下就会触发

实现拖拽 要考虑元素是否有margin 移动的x和y️减去元素原有的margin 给元素添加鼠标按下事件 在按下事件里面给页面添加鼠标移动事件 给元素注册鼠标弹起事件 => 清除页面鼠标移动事件

• onmousedown 鼠标按下
• onmouseup 鼠标弹起
• onmousemove 鼠标移动

H5拖拽 需要为拖拽的元素添加 draggable = \”true\” 属性 拖拽元素添加

• ondragstart 拖拽开始
• ondrag 拖拽中
• ondragend 拖拽结束拖拽的目标元素添加
• ondropenter 有元素拖进来触发
• ondropleave 有元素拖拽离开触发
• ondropover 主要是为了配合ondrop使用，一定要在ondropover事件里调用e.preventDefault()才能让ondrop触发
• ondrop 有元素拖到我范围内并松手才触发

三参数

ie8 不支持 addEventListener 两参数

元素.on事件 = 处理函数 (添加事件 如果是同名事件，后面的事件处理函数会覆盖前面的) 元素.addEventListener() (添加事件 不会覆盖之前的同名事件)

用什么方式添加的事件就用什么方式移除事件

• on => null

• addEventListener => removeEventListener注意:如果addEventListener添加的事件的事件处理函数是匿名函数不能直接移除事件 只能移除命名事件 (ie8的 attachEvent 一样)

• attachEvent => detachEvent

用户操作后要执行的什么代码

• 本质也是个对象
• 保存了事件触发时的相关信息
• 在事件处理函数中的形参里写参数 eie有兼容问题兼容代码e = e || window.event
• 三大坐标

screen e.screenX 和 e.screenY 获取的是点击的位置相对于屏幕左上角的坐标

page e.pageX,e.pageY 获得的是点击的位置相对于页面（文档）左上角的坐标 有兼容性的问题,IE8不支持，自己计算 pageX = e.clientX + 页面往左滚出去的距离 (scrollLeft) pageY = e.clientY + 页面往上滚出去的距离 (scrollTop)

offset e.offsetX,e.offsetY 获得是是点击的位置相当于事件源的左上角的位置 ie属性 有bug offsetX = e.clientX – 盒子到可视区域的left (el.getBoundingClientRect.left) offsetY = e.clientY – 盒子到可视区域的top (el.getBoundingClientRect.top)

this 和 e.currentTarget 是一樣的 当前调用的是谁的事件 那么this就是谁 e.currentTarget ie8 不支持 => 直接用this

e.target 获取事件源(目标阶段) 正在触发事件的那个元素 ie8不支持 => e.target 兼容代码 var target = e.target || e.srcElement

在事件里可以通过 e.eventPhase 来捕获当前是哪个阶段 捕获 => 1 目标 => 2 冒泡 => 3

捕获 目标 冒泡

一种现象 与冒泡阶段相反 从window开始 依次一级一级往下调用子元素的同名事件，直到找到真正触发事件的事件源 事件捕获默认看不见 想要看到捕获阶段则需要通过 addEventListener来绑定事件，并且第三个参数传true

找到真正触发事件的那个元素 -> 事件源

一种现象 当元素事件触发后 会从事件源开始依次一次一次往上调用父元素的同名事件，直到window 事件冒泡默认存在

好处：给父元素添加事件相当于给子元素添加了事件 -> 事件委托 -> e.target 带来的影响(坏处)：如果子元素和父元素有同名事件 并且业务逻辑相反 则会冲突影响

设置捕获

先捕获 从window开始 依次一级一级调用子元素的同名事件 -> 找到目标(真正触发事件的元素) -> 从目标元素开始 依次一级一级调用父元素的同名事件 直到window

未设置捕获

找到目标(真正触发事件的元素) -> 从目标元素开始 依次一级一级调用父元素的同名事件 直到window

阻止事件冒泡和阻止事件捕获 e.stopPropagation() ie8魔鬼不支持(ie8只有事件冒泡，没有事件捕获) => e.cancelBubble = true

只能存储字符串 查看本地存储 浏览器F12->Application->Local || Session Storage->fille://

可以把数据存储到本地(浏览器) 只要用户不删除 则会一直保存 每个域名都是独立的保存数据 不同域名不能互相访问 长久保存数据可以存储到 localStorage

• 保存数据 localStorage.setItem(key,value)
• 获取数据 localStorage.getItem(key) => 如果没有这个数据 则返回 null
• 删除一个数据 localStorage.removeItem(key)
• 清空所有数据 localStorage.clear()

短暂存储数据 可以多页面传值 相当于localStorage会更安全 浏览器关闭后就不会保存了

• 保存数据 sessionStorage.setItem(key,value)
• 获取数据 sessionStorage.getItem(key) => 如果没有这个数据 则返回 null
• 删除一个数据 sessionStorage.removeItem(key)
• 清空所有数据 sessionStorage.clear()

给元素添加动画定时器 可以将定时器id直接给元素 元素.timeId

每隔一段时间执行一段代码

一段时间后执行一段代码

将a标签的href的路径改为 javascript:void(0) || javascript:void(null) || 简写 javascript:

给a标签添加点击事件 在事件处理函数的最后 return false

阻止事件默认行为 e.preventDefault()

return和事件对象e阻止跳转的区别 return后面的代码不执行 e.preventDefault()不会影响后面代码执行

先把大家恢复成默认，再让自己特殊 tab切换

只能获取行内样式

只能取值 (number) 不能赋值 offsetWidth 和 offsetHeight 获取包括padding和border和width||height

获取盒子的最终宽度

获取盒子的最终高度

获取自身上外边框到定位父级上内边框的距离

获取自身左外边框到定位父级左内边框的距离

scrollWidth 和 scrollHeight 获取的包括了隐藏的部分 只能获取(number)不能修改 scrollLeft 和 scrollTop 可以获取也可以修改 想要滚动条滚动到最右变 直接赋值为 scrollWidth即可

获取盒子内容的总宽度

获取盒子内容的总高度

获取内容上边滚出去的距离

获取内容左边滚出去的距离

scrollTop和scrollLeft有兼容问题 兼容代码

如果元素有滚动条 那么这个元素的可视宽度就是 整个盒子的宽度 – 滚动条的宽度

获取可视区域的宽

获取可视区域的高

获取左边框的宽度

获取上边看的宽度

如果没有这个元素 则返回null 有则返回一个对象

获取 id 只能通过document来获取

document.getElementById(\”id\”)

如果没有这个元素 则返回一个空集合[伪数组] document.getElementsByClassName(\’class\’)

• 有下标索引、有元素、有长度 但是没有数组中的方法

ie8魔鬼有兼容问题 document.getElementsByTagName(\”div\”)

document.getElementsByName(\”name\”)

• 获取的是一个对象 如果匹配到多个元素则返回第一个元素document.querySelector(selectors)
• 获取的是一个伪数组document.querySelectorAll(selectors)

document

document.documentElement

document.head

document.body

• 子节点el.childNodes
• 子元素el.childNodes

区别

el.parentNode可以获取到document el.parentElement不能获取到document 因为document不是一个元素

• 父节点el.parentNode
• 父元素el.parentNode

• 找到上一个兄弟节点(文本、注释、标签)，所有浏览器都支持el.previousSibling
• 找到上一个兄弟元素(只会找到元素)，IE9以下都不支持el.previousElementSibling

• 找到下一个兄弟节点(文本、注释、标签)，所有浏览器都支持el.nextSibling
• 找到下一个兄弟元素(只会找到元素)，IE9以下都不支持el.nextElementSibling

父元素.appendChild(\”子元素\”)

父元素.removeChild(\”子元素\”)

父元素.insertBefore(插入的新元素,要在哪个元素前面插入)

父元素.replaceChild(新的元素,被替换的元素)

既可以操作自带属性，也可以操作自定义属性

• 获取属性el.getAttribute(\”属性名\”)
• 修改属性el.setAttribute(\”属性名\”,\”属性值\”)
• 删除属性el.removeAttribute(\”属性名\”)

在自定义属性前面加 data- 如果自定义属性前面添加了 data- 那么这些自定义属性都会保存到el.dataset \’对象\’ 里面 想要取得属性直接遍历对象即可 取值时 data-会被去掉 并且如果后面还有- 会把后面的-也去掉 并把-后面的首字母大写(驼峰命名法)

• 获得属性el.dataset[\”shengao\”]e.dataset.shengao
• 修改属性el.dataset[\”shengao\”] = \”123cm\”
• 删除属性delete el.dataset[\”shengao\”]

• document.write()

只能在body添加元素，并且会覆盖之前页面中的元素

• document.createElement()

创建一个标签存在内存里面 再通过 父元素.appendChild(“创建出来的元素”) 渲染到页面 appendChild细节 给父元素追加一个元素，添加在最后，如果此元素已经存在，则被移动到最后

• el.innerHtml()

为某元素添加内容，会覆盖原来的内容 += 就只会追加不会覆盖 每次innerHtml赋值(+=)都是重新渲染， 所以有可能会让之前的元素丢失， 还会让之前元素的事件丢失(事件委托可解决) 渲染耗性能，大量资源浪费 先拼接字符串 再循环完了后一次性追加到页面中

• 获取元素.style.样式名
• 修改元素.style.样式名 = 样式值注意

样式名 如果在css 有 \”-\” 的 应使用 驼峰命名法 background-color => backgroundColor

• 获取元素.scr
• 修改元素.scr = \”路径\”

• 获取元素.value
• 修改元素.value = \”值\”

• 获取元素.className
• 添加元素.className += \” class\”注意 用+= 得加空格

el.classList 返回的是一个伪数组 保存的是元素上的所有类名

• 添加一个类el.classList.add(\”class\”)
• 删除一个类el.classList.remove(\”class\”)
• 修改一个类el.classList.replace(\”被替换的类\”,\”要替换的新类\”)
• 切换一个类el.classList.toggle(\”class\”)没有就添加这个类 有就删除这个类
• 判断一个类是否存在el.classList.contains(\”class\”)存在返回true 不存在返回false

• 显示元素.style.displaye = \”block\”
• 隐藏元素.style.displaye = \”none\”如果想要通过一个按钮切换显示隐藏可以声明一个flag 记录显示和隐藏的状态

let flag = this.value == \”隐藏\” ? true : false divBox.style.display = flag ? \”none\” : \”block\” this.value = flag ? \”显示\” : \”隐藏\” // 这里用来下一次 点击再次toggle 所以需要与设置的flag相反设定对应的值

• el.style.disabled = true

加上代表禁用 不加上代表启动 js里面设置它为 true 代表禁用、false 代表启用

• 获取元素.innerText
• 修改元素.innerText = \”值\”

innerHTML没有兼容问题 既可以拿到文本也可以渲染标签

innerText和textContent都是设置标签里面的文本内容 将数据当成字符串输出到页面 不会渲染 innerText在老版火狐里面不支持 textContent在ie9以下都不支持

• value可以获取大部分表单元素的内容(option除外)
• type可以获取表单元素的类型
• disabled禁用属性
• checked复选框选中
• selected下拉框选中

返回的string属性值 \”100px\”

获取鼠标位置相对于自身的x和y (offsetX和offsetY有bug) e.clientX – 盒子到可视区域的left e.clientY – 盒子到可视区域的top

若有感兴趣的小伙伴，需要WebAPI思维导图原图的，关注我，私信回复获取：WebAPI思维导图原图

作者：蓝海00转载链接：https://www.jianshu.com/p/d3b815c8d914

95% 的算法都是基于这 6 种算法思想

写在前面

因为本次文章篇幅较长，所以为了便利大家查看今日最新职位信息，所以将内容上移至顶部，忘各位大大海涵

算法思想是解决问题的核心，万丈高楼起于平地，在算法中也是如此，95% 的算法都是基于这 6 种算法思想，结下了介绍一下这 6 种算法思想，帮助你理解及解决各种算法问题。

1.1 算法策略

递归算法是一种直接或者间接调用自身函数或者方法的算法。

递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。

优缺点：

• 优点：实现简单易上手
• 缺点：递归算法对常用的算法如普通循环等，运行效率较低；并且在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归太深，容易发生栈溢出

1.2 适用场景

递归算法一般用于解决三类问题：

• 数据的定义是按递归定义的。（斐波那契数列）
• 问题解法按递归算法实现。（回溯）
• 数据的结构形式是按递归定义的。（树的遍历，图的搜索）

递归的解题策略：

• 第一步：明确你这个函数的输入输出，先不管函数里面的代码什么，而是要先明白，你这个函数的输入是什么，输出为何什么，功能是什么，要完成什么样的一件事。
• 第二步：寻找递归结束条件，我们需要找出什么时候递归结束，之后直接把结果返回
• 第三步：明确递归关系式，怎么通过各种递归调用来组合解决当前问题

1.3 使用递归算法求解的一些经典问题

• 斐波那契数列
• 汉诺塔问题
• 树的遍历及相关操作

DOM树为例

下面以以 DOM 为例，实现一个 document.getElementById 功能

由于DOM是一棵树，而树的定义本身就是用的递归定义，所以用递归的方法处理树，会非常地简单自然。

第一步：明确你这个函数的输入输出

从 DOM 根节点一层层往下递归，判断当前节点的 id 是否是我们要寻找的 id=\’d-cal\’

输入：DOM 根节点 document ，我们要寻找的 id=\’d-cal\’

输出：返回满足 id=\’sisteran\’ 的子结点

第二步：寻找递归结束条件

从document开始往下找，对所有子结点递归查找他们的子结点，一层一层地往下查找：

• 如果当前结点的 id 符合查找条件，则返回当前结点
• 如果已经到了叶子结点了还没有找到，则返回 null

第三步：明确递归关系式

当前结点的 id 不符合查找条件，递归查找它的每一个子结点

就这样，我们的一个 document.getElementById 功能已经实现了：

最后在控制台验证一下，执行结果如下图所示：

使用递归的优点是代码简单易懂，缺点是效率比不上非递归的实现。Chrome浏览器的查DOM是使用非递归实现。非递归要怎么实现呢？

如下代码：

还是依次遍历所有的 DOM 结点，只是这一次改成一个 while 循环，函数 nextElement 负责找到下一个结点。所以关键在于这个 nextElement 如何实现非递归查找结点功能：

在控制台里面运行这段代码，同样也可以正确地输出结果。不管是非递归还是递归，它们都是深度优先遍历，这个过程如下图所示。

实际上 getElementById 浏览器是用的一个哈希 map 存储的，根据 id 直接映射到 DOM 结点，而 getElementsByClassName 就是用的这样的非递归查找。

参考：我接触过的前端数据结构与算法

2.1 算法策略

在计算机科学中，分治算法是一个很重要的算法，快速排序、归并排序等都是基于分治策略进行实现的，所以，建议理解掌握它。

分治，顾名思义，就是 分而治之 ，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为阿子问题解的合并。

2.2 适用场景

当出现满足以下条件的问题，可以尝试只用分治策略进行求解：

• 原始问题可以分成多个相似的子问题
• 子问题可以很简单的求解
• 原始问题的解是子问题解的合并
• 各个子问题是相互独立的，不包含相同的子问题

分治的解题策略：

• 第一步：分解，将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
• 第二步：解决，解决各个子问题
• 第三步：合并，将各个子问题的解合并为原问题的解

2.3使用分治法求解的一些经典问题

• 二分查找
• 归并排序
• 快速排序
• 汉诺塔问题
• React 时间分片

二分查找

也称折半查找算法，它是一种简单易懂的快速查找算法。例如我随机写0-100之间的一个数字，让你猜我写的是什么？你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。

第一步：分解

每次猜拳都把上一次的结果分出大的一组和小的一组，两组相互独立

• 选择数组中的中间数

第二步：解决子问题

查找数与中间数对比

• 比中间数低，则去中间数左边的子数组中寻找；
• 比中间数高，则去中间数右边的子数组中寻找；
• 相等则返回查找成功

第三步：合并

最后，二分法只能应用于数组有序的情况，如果数组无序，二分查找就不能起作用了

测试成功

3.1 算法策略

贪心算法，故名思义，总是做出当前的最优选择，即期望通过局部的最优选择获得整体的最优选择。

某种意义上说，贪心算法是很贪婪、很目光短浅的，它不从整体考虑，仅仅只关注当前的最大利益，所以说它做出的选择仅仅是某种意义上的局部最优，但是贪心算法在很多问题上还是能够拿到最优解或较优解，所以它的存在还是有意义的。

3.2 适用场景

在日常生活中，我们使用到贪心算法的时候还是挺多的，例如：

从100章面值不等的中，抽出 10 张，怎样才能获得最多的价值？

我们只需要每次都选择剩下的中最大的面值，最后一定拿到的就是最优解，这就是使用的贪心算法，并且最后得到了整体最优解。

但是，我们任然需要明确的是，期望通过局部的最优选择获得整体的最优选择，仅仅是期望而已，也可能最终得到的结果并不一定不能是整体最优解。

例如：求取A到G最短路径：

根据贪心算法总是选择当前最优选择，所以它首先选择的路径是 AB，然后 BE、EG，所得到的路径总长为 1 + 5 + 4 = 10，然而这并不是最短路径，最短路径为 A->C->G : 2 + 2 = 4，所以说，贪心算法得到得并不一定是最优解。

那么一般在什么时候可以尝试选择使用贪心算法喃？

当满足一下条件时，可以使用：

• 原问题复杂度过高
• 求全局最优解的数学模型难以建立或计算量过大
• 没有太大必要一定要求出全局最优解，“比较优”就可以

如果使用贪心算法求最优解，可以按照以下 步骤求解 ：

• 首先，我们需要明确什么是最优解（期望）
• 然后，把问题分成多个步骤，每一步都需要满足：

可行性：每一步都满足问题的约束

局部最优：每一步都做出一个局部最优的选择

• – 不可取消：选择一旦做出，在后面遇到任何情况都不可取消
• 最后，叠加所有步骤的最优解，就是全局最优解

3.3 经典案例：活动选择问题

使用贪心算法求解的经典问题有：

• 最小生成树算法
• 单源最短路径的 Dijkstra 算法
• Huffman 压缩编码
• 背包问题
• 活动选择问题等

其中活动选择问题是最简单的，这里详细介绍这个。

活动选择问题是《算法导论》上的例子，也是一个非常经典的问题。有 n 个活动（a1,a2,…,an）需要使用同一个资源（例如教室），资源在某个时刻只能供一个活动使用。每个活动 ai 都有一个开始时间 si 和结束时间 fi 。一旦被选择后，活动 ai 就占据半开时间区间 [si,fi) 。如果 [si,fi) 和 [sj,fj) 互不重叠，ai 和 aj 两个活动就可以被安排在这一天。

该问题就是要安排这些活动，使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。

共有 7 个活动，它们在 18 个小时内需要占用的时间如上图，如何选择活动，能让这间教室利用率最高喃（能够举行更多的活动）？

贪心算法对这种问题的解决很简单的，它开始时刻开始选择，每次选择开始时间与与已选择活动不冲突的，结束时间又比较靠前的活动，这样会让剩下的时间区间更长。

• 首先 a1 活动的结束时间最早，选择 a1 活动
• a1 结束后，a2 有时间冲突，不可选择，a3、a4 都可选择，但 a4 结束时间最早，选择 a4
• 依次选择时间没有冲突的，又结束时间最早的活动

最终选择活动为 a1，a4，a5，a7。为最优解。

4.1 算法策略

回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。

4.2 适用场景

回溯算法很简单，它就是不断的尝试，直到拿到解。它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解。

4.3 使用回溯算法的经典案例

• 深度优先搜索
• 0-1背包问题
• 正则表达式匹配
• 八皇后
• 数独
• 全排列

等等，深度优先搜索我们在图那一章已经介绍过，这里以正则表达式匹配为例，介绍一下

正则表达式匹配

var string = \”abbc\”

var regex = /ab{1,3}c/

console.log( string.match(regex) )

// [\”abbc\”, index: 0, input: \”abbc\”, groups: undefined]

它的匹配过程：

在第 5 步匹配失败，此时 b{1,3} 已经匹配到了两个 b 正在尝试第三个 b ，结果发现接下来是 c 。此时就需要回溯到上一步， b{1,3} 匹配完毕（匹配到了 bb ），然后再匹配 c ，匹配到了 c 匹配结束。

5.1 算法策略

动态规划也是将复杂问题分解成小问题求解的策略，与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的。

所以，动态规划适用于子问题重叠的情况，即不同的子问题具有公共的子子问题，在这种情况下，分治策略会做出很多不必要的工作，它会反复求解那些公共子子问题，而动态规划会对每个子子问题求解一次，然后保存在表格中，如果遇到一致的问题，从表格中获取既可，所以它无需求解每一个子子问题，避免了大量的不必要操作。

5.2 适用场景

动态规划适用于求解最优解问题，比如，从面额不定的100个硬币中任意选取多个凑成10元，求怎样选取硬币才可以使最后选取的硬币数最少又刚好凑够了10元。这就是一个典型的动态规划问题。它可以分成一个个子问题（每次选取硬币），每个子问题又有公共的子子问题（选取硬币），子问题之间相互关联（已选取的硬币总金额不能超过10元），边界条件就是最终选取的硬币总金额为 10 元。

针对上例，也许你也可以说，我们可以使用回溯算法，不断的去试探，但回溯算法是使用与求解广度的解（满足要求的解），如果是用回溯算法，我们需要尝试去找所有满足条件的解，然后找到最优解，时间复杂度为 O(2^n^) ，这性能是相当差的。大多数适用于动态规划的问题，都可以使用回溯算法，只是使用回溯算法的时间复杂度比较高而已。

最后，总结一下，我们使用动态规划求解问题时，需要遵循以下几个重要步骤：

• 定义子问题
• 实现需要反复执行解决的子子问题部分
• 识别并求解出边界条件

5.3 使用动态规划求解的一些经典问题

• 爬楼梯问题：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
• 背包问题：给出一些资源（有总量及价值），给一个背包（有总容量），往背包里装资源，目标是在背包不超过总容量的情况下，装入更多的价值
• 硬币找零：给出面额不定的一定数量的零钱，以及需要找零的钱数，找出有多少种找零方案
• 图的全源最短路径：一个图中包含 u、v 顶点，找出从顶点 u 到顶点 v 的最短路径
• 最长公共子序列：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变剩下元素的顺序实现）

这里以最长公共子序列为例。

爬楼梯问题

这里以动态规划经典问题爬楼梯问题为例，介绍求解动态规划问题的步骤。

第一步：定义子问题

如果用 dp[n] 表示第 n 级台阶的方案数，并且由题目知：最后一步可能迈 2 个台阶，也可迈 1 个台阶，即第 n 级台阶的方案数等于第 n-1 级台阶的方案数加上第 n-2 级台阶的方案数

第二步：实现需要反复执行解决的子子问题部分

第三步：识别并求解出边界条件

最后一步：把尾码翻译成代码，处理一些边界情况

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

优化空间复杂度：

空间复杂度：O(1)

6.1 算法策略

枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。

6.2 解题思路

• 确定枚举对象、枚举范围和判定条件。
• 逐一列举可能的解，验证每个解是否是问题的解。

7.1 爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意： 给定 n 是一个正整数。

示例 1：

示例 2：

解法：动态规划

动态规划（Dynamic Programming，DP）是一种将复杂问题分解成小问题求解的策略，但与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的。

分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。

我们使用动态规划求解问题时，需要遵循以下几个重要步骤：

• 定义子问题
• 实现需要反复执行解决的子子问题部分
• 识别并求解出边界条件

第一步：定义子问题

如果用 dp[n] 表示第 n 级台阶的方案数，并且由题目知：最后一步可能迈 2 个台阶，也可迈 1 个台阶，即第 n 级台阶的方案数等于第 n-1 级台阶的方案数加上第 n-2 级台阶的方案数

第二步：实现需要反复执行解决的子子问题部分

第三步：识别并求解出边界条件

最后一步：把尾码翻译成代码，处理一些边界情况

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

优化空间复杂度：

空间复杂度：O(1)

7.2 使用最小花费爬楼梯

数组的每个索引作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i] (索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 1:

示例 2:

注意：

• cost 的长度将会在 [2, 1000] 。
• 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999] 。

解法：动态规划

本题注意理解题意：

• 第 i 级台阶是第 i-1 级台阶的阶梯顶部。
• 踏上第 i 级台阶花费 cost[i] ，直接迈一大步跨过而不踏上去则不用花费。
• 楼梯顶部在数组之外，如果数组长度为 len，那么楼顶就在下标为 len

第一步：定义子问题

踏上第 i 级台阶的体力消耗为到达前两个阶梯的最小体力消耗加上本层体力消耗：

• 最后迈 1 步踏上第 i 级台阶：dp[i-1] + cost[i]
• 最后迈 1 步踏上第 i 级台阶：dp[i-2] + cost[i]

第二步：实现需要反复执行解决的子子问题部分

所以踏上第 i 级台阶的最小花费为：

第三步：识别并求解出边界条件

最后一步：把尾码翻译成代码，处理一些边界情况

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

优化：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

更多解答

7.3 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

第一步：定义子问题

动态规划是将整个数组归纳考虑，假设我们已经知道了以第 i-1 个数结尾的连续子数组的最大和 dp[i-1]，显然以第i个数结尾的连续子数组的最大和的可能取值要么为 dp[i-1]+nums[i]，要么就是 nums[i] 单独成一组，也就是 nums[i] ，在这两个数中我们取最大值

第二步：实现需要反复执行解决的子子问题部分

第三步：识别并求解出边界条件

最后一步：把尾码翻译成代码，处理一些边界情况

因为我们在计算 dp[i] 的时候，只关心 dp[i-1] 与 nums[i]，因此不用把整个 dp 数组保存下来，只需设置一个 pre 保存 dp[i-1] 就好了。

代码实现（优化）：

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

7.4 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

示例 2:

解法：动态规划

第一步：定义子问题

动态规划是将整个数组归纳考虑，假设我们已经知道了 i-1 个股票的最大利润为 dp[i-1]，显然 i 个连续股票的最大利润为 dp[i-1] ，要么就是就是 prices[i] – minprice （ minprice 为前 i-1 支股票的最小值 ），在这两个数中我们取最大值

第二步：实现需要反复执行解决的子子问题部分

第三步：识别并求解出边界条件

最后一步：把尾码翻译成代码，处理一些边界情况

因为我们在计算 dp[i] 的时候，只关心 dp[i-1] 与 prices[i]，因此不用把整个 dp 数组保存下来，只需设置一个 max 保存 dp[i-1] 就好了。

代码实现（优化）：

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

7.5 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

示例 2：

提示：

• 输入的字符串长度不会超过 1000 。

解法一：暴力法

复杂度分析：

• 时间复杂度：O(n^3^)
• 空间复杂度：O(1)

解法二：动态规划

一个字符串是回文串，它的首尾字符相同，且剩余子串也是一个回文串。其中，剩余子串是否为回文串，就是规模小一点的子问题，它的结果影响大问题的结果。

我们怎么去描述子问题呢？

显然，一个子串由两端的 i 、j 指针确定，就是描述子问题的变量，子串 s[i…j] （ dp[i][j] ） 是否是回文串，就是子问题。

我们用二维数组记录计算过的子问题的结果，从base case出发，像填表一样递推出每个子问题的解。

注意： i<=j ，只需用半张表，竖向扫描

所以：

即：

否则为 false

代码实现：

代码实现（优化）：

把上图的表格竖向一列看作一维数组，还是竖向扫描，此时仅仅需要将 dp 定义为一维数组即可

复杂度分析：

• 时间复杂度：O(n^2^)
• 空间复杂度：O(n)

更多解答

7.6 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

示例 2：

解法：动态规划

第 1 步：定义状态

dp[i][j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j] 。

第 2 步：思考状态转移方程

对于一个子串而言，如果它是回文串，那么在它的首尾增加一个相同字符，它仍然是个回文串

第 3 步：初始状态：

代码实现：

复杂度分析：

• 时间复杂度：O(n^2^)
• 空间复杂度：O(n^2^)

7.7 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

示例 2：

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

1、DP方程 当前项最小路径和 = 当前项值 + 上项或左项中的最小值 grid[i][j] += Math.min( grid[i – 1][j], grid[i][j – 1] )

2、边界处理 grid的第一行与第一列 分别没有上项与左项 故单独处理计算起项最小路径和 计算第一行：

计算第一列：

3、代码实现

7.8 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

示例 2:

示例 3:

提示：

• 1 <= prices.length <= 3 * 10 ^ 4
• 0 <= prices[i] <= 10 ^ 4

解法一：峰底买入，峰顶卖出

如图，在第二天买入，第三天卖出，第四天买入，第五天卖出获利最高，此处代码不再赘述，可以自己尝试写一下

解法二：贪心算法

贪心算法，故名思义，总是做出当前的最优选择，即期望通过局部的最优选择获得整体的最优选择。

某种意义上说，贪心算法是很贪婪、很目光短浅的，它不从整体考虑，仅仅只关注当前的最大利益，所以说它做出的选择仅仅是某种意义上的局部最优，但是贪心算法在很多问题上还是能够拿到最优解或较优解，所以它的存在还是有意义的。

对应于该题，第一天买入，第二天卖出，…，第 i 天买入，第 i+1 天卖出，如果 i 天买入第 i+1 天卖出有利润则买入，否则不买

第 i-1 天买入第 i 天卖出获利 prices[i+1]-prices[i] ，我们仅仅需要将 prices[i+1]-prices[i] 的所有正值加起来就是可获取的最大利益

代码实现：

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

7.9 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 g~i~ ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 s~j~。如果 s~j~ >= g~i~ ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：

你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。

示例 1:

示例 2:

7.10 分割数组为连续子序列

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。

如果可以完成上述分割，则返回 true ；否则，返回 false 。

示例 1：

示例 2：

示例 3：

提示：

• 输入的数组长度范围为 [1, 10000]

解法：贪心算法

从头开始，我们每次仅仅寻找满足条件的序列（连续子序列长度为3），剔除之后，依次往后遍历：

• 判断当前元素是否能够拼接到前一个满足条件的连续子序列上，可以的话，则拼接
• 如果不可以，则判断以当前元素开始能否构成连续子序列（长度为3），可以的话，则剔除连续子序列
• 否则，返回 false

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

7.11 全排列问题

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

解法：回溯算法

本题是回溯算法的经典应用场景

1. 算法策略

回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。

2. 适用场景

回溯算法很简单，它就是不断的尝试，直到拿到解。它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解。

3. 代码实现

我们可以写一下，数组 [1, 2, 3] 的全排列有：

• 先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列；
• 再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；
• 最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。

即回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

这显然是一个 递归 结构；

• 递归的终止条件是：一个排列中的数字已经选够了 ，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做 depth ，或者命名为 index ，表示当前要确定的是某个全排列中下标为 index 的那个数是多少；
• used（object）：用于把表示一个数是否被选中，如果这个数字(num)被选择这设置为 used[num] = true ，这样在考虑下一个位置的时候，就能够以 O(1)的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想。

4. 复杂度分析

• 时间复杂度：O(n∗n!)，其中 n 为序列的长度这是一个排列组合，每层的排列组合数为：A^m^ ~n~=n!/(n−m)! ，故而所有的排列有 ：A^1^ ~n~ + A^2^ ~n~ + … + A^n-1^ ~n~ = n!/(n−1)! + n!/(n−2)! + … + n! = n! * (1/(n−1)! + 1/(n−2)! + … + 1) <= n! * (1 + 1/2 + 1/4 + … + 1/2^n-1^) < 2 * n!并且每个内部结点循环 n 次，故非叶子结点的时间复杂度为 O(n∗n!)
• 空间复杂度：O(n)

7.12 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

解答：回溯算法（深度优先遍历）

算法策略： 回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。

对应于本题，我们可以每次试探增加 ( 或 ) ，注意：

• 加入 ( 的条件是，当前是否还有 ( 可以选择
• 加入 ) 的时候，受到 ( 的限制，如果已选择的结果里的 ( 小于等于已选择里的 ) 时，此时是不能选择 ) 的，例如如果当前是 () ，继续选择 ) 就是 ()) ，是不合法的

代码实现：

复杂度分析（来源leetcode官方题解）：

本文转载自三分钟学前端

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com