背景介绍

基于PM2.5的健康路径规划项目，需要轨迹记录和轨迹展示功能。帮助用户记录出行轨迹，并提供分析PM2.5的吸入剂量。

主要涉及功能如下

• 实时采集用户轨迹并可视化在主页面地图中，点击开始按钮，采集开始，点击结束按钮采集结束，采集过程中支持暂停/继续
• 轨迹展示功能，点击轨迹在地图中生成轨迹图

亮点

• 定期推送功能
• 轨迹展示的灵活统计功能

设计思路

轨迹采集

两种策略：一种是暂存起来，定量推动到服务器。另外基于websocket实时推送

第一种策略实时性差，但是如果只是推送到服务器，不需要共享到其他用户，实时性不重要。前端可视化也不依赖于服务器的数据。第二种策略的实时性强，但是要保持持久连接较耗时。因此选择第一种。但是本文会给出两者的实现方法。

定量推送

主逻辑

• 定量推送数据：当 localStorage 中的数据量达到设定的阈值就推送到服务器。

• 因为网络异常推送失败或其他原因，localStorage 数据不断增加，导致容量接近上限时，上限是容量的2/3，将数据转移到 IndexedDB，继续保持数据采集。

• 顺序问题：当恢复网络时，必须优先推送 IndexedDB 中的数据，随后再推送 localStorage 中的数据，确保数据按时间顺序上传。

• 检测网络状态：navigator.onLine用于判断当前网络状态是否在线。online 和 offline 事件：分别在网络恢复和网络断开时触发。online 事件触发后立即尝试发送缓存数据，确保及时上传未发送的数据。

• 为保证上传顺序使用任务队列和互斥锁，避免上传任务的冲突。

采用互斥锁

在上传过程中引入一种互斥锁的机制，确保在上传过程中不会重复访问同一份数据。这样在上传过程中，即使有新的数据加入到 localStorage，也不会与当前正在上传的数据发生冲突。避免了多个上传任务可能同时进行，导致并发冲突，比如数据重复上传、数据上传顺序错乱等问题

如何实现：在 JavaScript 的单线程环境中，虽然没有直接的互斥锁机制，但我们可以通过标志位（flag）的方式实现互斥锁的效果。

在我们的实现中，isUploading 就相当于一个互斥锁，它用来标记当前是否有上传任务正在进行：

1
2

let isUploading = false; // 标志是否正在上传数据
锁定（加锁）：当开始执行上传任务时，我们将 isUploading 设为 true，这就相当于上了锁，表示系统正在上传数据。

1
2

isUploading = true; // 加锁，表示系统正在执行上传任务
解锁：上传任务完成后，记得将 isUploading 设为 false，解锁表示上传任务完成，允许下一次上传开始。

1
2
3

isUploading = false; // 解锁，表示上传任务完成
在上传任务的开始处，我们通过判断 isUploading 来决定是否执行上传任务。如果 isUploading 为 true，则跳过当前任务，以避免多个上传任务同时进行：

1

if (isUploading) return; // 如果已加锁（正在上传），直接返回，不执行新的上传任务

实现

• 1. 数据采集与存储
  • 使用 navigator.geolocation 进行轨迹点的实时采集。每次采集到一个点后，立即将其存入 localStorage 中。
  • 在 localStorage 达到容量的 2/3 时，将数据转移到 IndexedDB 中以防止 localStorage 的存储容量不足。
  • 轨迹点数据的采集频率不依赖于网络状态，数据始终保持持续采集。
• 2. 任务队列与上传机制
  • 使用任务队列来管理数据上传过程，确保即使有多个任务并发执行时，上传操作不会发生冲突。
  • 每次采集到的数据会在 localStorage 中暂存。当数据量达到一定的阈值（如 500 个点），或者网络恢复时，系统会尝试将数据上传到服务器。
  • 如果当前已有正在执行的上传任务，则新的上传任务会被添加到任务队列中，等待前一个任务完成后依次执行。这样可以避免同时多个上传任务导致的冲突。
• 3. 网络状态检测与数据传输
  • 系统实时监控网络状态，当网络断开时，数据会继续存储到 localStorage 或 IndexedDB 中，而不会尝试上传。
  • 当网络恢复时，会优先处理任务队列中的上传任务，将缓存中的数据（优先从 IndexedDB，然后是 localStorage）上传至服务器。
• 4. 上传过程与冲突管理
  • 通过任务队列机制来防止并发上传冲突：当一个上传任务正在进行时，新的上传任务不会立即执行，而是加入队列等待当前任务完成。
  • 在上传成功后，系统会清理已上传的数据（从 localStorage 或 IndexedDB 中删除），并继续处理下一个上传任务，直到所有缓存的数据都上传完成。
• 5. 数据传输与顺序维护
  • 当网络恢复时，系统首先检查 IndexedDB 中的数据。由于 IndexedDB 保存的是 localStorage 中超过容量的数据，因此 IndexedDB 中的数据应优先上传。
  • 在 IndexedDB 的数据上传完成后，系统会继续处理 localStorage 中的数据，保证传输顺序的正确性。

实时推送

主逻辑

• 获取到一个点数据就备份到localStorage中，然后推送到服务端，同送成功将备份删除。

• 遇到websocket断开的的情况，将数据保存如localStorage，链接回复，将localStorage的数据推送到服务端，推送成功就删除localStorage中的数据。

推送顺序问题

点的顺序对轨迹来说是重要的，因此需要确保数据库中存储的点的数据是正确的，每一个点数据有时间戳，可以在后端进行排序。也可以在前端控制推送顺序，使用双队列。从复杂度上说前端复杂度较小，因此选择前端处理的方式。

实现

• 1. 数据采集与存储
  • 使用 navigator.geolocation 进行轨迹点的实时采集，每次采集到一个点后，立即将其存入实时队列，并将该数据缓存到 localStorage 中。
  • 实时队列用于存储采集到的新数据，实时发送给服务端；localStorage 则作为本地缓存，防止断网或其他异常情况下数据丢失。
• 2. WebSocket 连接与重连机制
  • WebSocket 建立后，若连接成功，会开始发送实时数据，并检查是否有缓存的轨迹数据（localStorage 中）。
  • 若WebSocket 连接断开，会进入重连模式，在重连成功后立即尝试将缓存中的数据发送到服务器。
• 3. 双队列管理
     实时队列：存储正在采集的数据，WebSocket 连接正常时，直接发送数据给服务端。
  • 缓存队列（localStorage）：当 WebSocket 连接断开时，实时队列中的数据存储到 localStorage 中；当连接恢复时，发送缓存队列的数据。
• 4. 数据传输与顺序维护
  • 当网络恢复时，先将 localStorage 中的数据传输到服务端，随后再发送实时队列中的新数据，确保传输顺序不乱。
• 5. localStorage 清空与缓存清理
  • 在 WebSocket 连接恢复后，成功发送缓存队列的数据后，立即从localStorage 中删除已成功推送的数据。
  • 避免重复发送数据，确保只发送最新数据。

历史轨迹展示

可以根据年、月、周、日来统计和显示轨迹，对后端传来的数据进行处理统计，统计原则根据用户的设置决定，生成用于渲染的数据。点击每一条数据在地图上生成轨迹。

自适应调整页面-rem和vh/vw

简介使用rem适应不同终端的变化，调整页面元素的大小。
使用动态计算vh的目的是，因为移动端的地址栏的出现与消失会影响也页面视窗的高度即vh。因此需要动态计算。

核心问题是移动浏览器（Chrome 和 Safari）有一个“有用”的功能，地址栏有时可见，有时隐藏，从而改变视口的可见大小。这些浏览器并没有随着视口高度的变化而将高度调整100vh为屏幕的可见部分，而是将100vh地址栏设置为隐藏地址的浏览器高度。结果是，当地址栏可见时，屏幕的底部将被切断，从而违背了100vh最初的目的。

rem

rem 的值是根据根元素 html 字体大小的来计算的，即1rem = html font-szie，
如果 html 元素没有指定字体大小，那么浏览器默认的字体大小是 16px ，所以 1rem = 16px
如果 html 元素指定 font-size: 1px ，那么 1rem = 1px
同理 html 元素指定 font-size: 3px ，那么 1rem = 3px
同理 html 元素指定 font-size: 1000000px ，那么 1rem = 1000000px
同理 html 元素指定 font-size: 0.000001px ，那么 1rem = 0.000001px

rem和em的区别

em 是以父元素的字体大小来计算; rem 顾名思义,就是 root 的 em， 所以它是以html的字体大小来计算

不同屏幕自适应

不同用户的设备屏幕宽度不同，若每个用户对应的 html 元素 font-size 值相同的话，用户看到的显示效果也是不同的。

可以用 JavaScript 来根据用户的屏幕宽度，动态更改 html 元素上的 font-size 值，从而使实际显示的内容比例始终保持不变，不同用户看到的效果也会保持一致。

比如，设计稿的宽度为 400px ，里面显示了一个宽度为 40px 的盒子。某用户以 800px 宽度的设备来访问，看到的盒子宽度应该为 80px。那么此时在 html 元素的 font-size 值设置为 2px ，然后盒子的宽度采用 rem 单位，设置为 40rem ，那么就能显示出 80px 的盒子了。保持用户看到的和设计稿中的效果比例一致。

所以，html元素的font-size计算公式为：

1
2

// 用户设备宽度 / 设计稿标准宽度
document.documentElement.style.fontSize = document.documentElement.clientWidth / 375 + 'px'

vh

vh 和 vw 都是相对于视窗的宽高度，“视窗”所指为浏览器内部的可视区域大小，即window.innerWidth/window.innerHeight大小，不包含任务栏标题栏以及底部工具栏的浏览器区域大小。可以简单理解为屏幕百分比，1vh = 屏幕的1%

移动端 100vh 显示 bug

vh 在移动端的Chrome 和 Safari上会显示溢出 ，如下图

当地址栏处于视图中时，元素底部被裁剪（右），但我们想要的是元素能完整的占据一屏（左）。
造成这种现象的原因就在于移动端浏览器对于 vh 单位的计算，是不包含地址栏的，也就是说 100vh 的高度会使带有地址栏的视图溢出。

解决方法

使用 window.innerHeight 获取当前视窗的的高度，将高度按 100 份等分，得到视窗的单位高度, 然后通过 js 设置成一个 css 的变量 --vh。

1

document.documentElement.style.setProperty('--vh', `${vh}px`)

css中使用

1
2
3
4
5

//表示100vh
height: calc(var(--vh, 1vh) * 100);

//100vh - 60rem
height: calc(var(--vh, 1vh) * 100 - 60rem);

代码

1
2
3
4
5
6
7
8
9
10
11

function resetVhAndPx() {
  let vh = window.innerHeight * 0.01
  document.documentElement.style.setProperty('--vh', `${vh}px`)
  document.documentElement.style.fontSize = document.documentElement.clientWidth / 375 + 'px'
}

onMounted(() => {
  resetVhAndPx()
  // 监听resize事件 视图大小发生变化就重新计算1vh的值
  window.addEventListener('resize',resetVhAndPx)
})

实现原理

无限滑动的原理和虚拟滚动的原理差不多，要保持 SlideList 里面永远只有 N 个 SlideItem，就要在滑动时不断的删除和增加 SlideItem。
滑动时调整 SlideList 的偏移量 translateY 的值，以及列表里那几个 SlideItem 的 top 值，就可以了

为什么要调整 SlideList 的偏移量 translateY 的值同时还要调整 SlideItem 的 top 值呢？
因为 translateY 只是将整个列表移动，如果我们列表里面的元素是固定的，不会变多和减少，那么没关系，只调整　translateY 值就可以了，上滑了几页就减几页的高度，下滑同理

但是如果整个列表向前移动了一页，同时前面的 SlideItem 也少了一个，，那么最终效果就是移动了两页…因为 塌陷 了一页
这显然不是我们想要的，所以我们还需要同时调整 SlideItem 的 top 值，加上前面少的 SlideItem 的高度，这样才能显示出正常的内容

是什么

• 针对问题：
  在同一个请求中，要上传大量的数据，导致整个过程会比较漫长，且失败后需要重头开始上传。

• 解决思路：
  将这个请求拆分成多个请求，每个请求的时间就会缩短，且如果某个请求失败，只需要重新发送这一次请求即可，无需从头开始，这样是否可以解决大文件上传的问题呢？

• 要求

  • 支持拆分上传文件请求
  • 支持断点续传
  • 支持显示上传进度和暂定进度

• 技术

  • webWorker:
    是一种在后台线程中运行脚本的技术，允许开发者在不阻塞用户界面的情况下执行复杂和耗时的任务。Web Worker 提供了一个独立的执行环境，与主线程（UI 线程）隔离开来，避免了长时间运行的脚本导致的页面卡顿。

逻辑

• 1、将上传的文件切片，并对每个切片标上记号，是哪个文件的切片是切片的那一部分（用hash实现标记）
• 2、后端把成功的标记记录下来，上传每个文件时，都判断一下标记是否存在，如果存在不上传，如果存在就上传。
• 3、后端对上传完整的文件切片进行拼接。

细节

webworker 处理对文件的切片

webWorker的特点

• 独立线程：Web Worker 在独立的线程中运行，与主线程并行执行。
• 无阻塞：由于在独立线程中运行，Web Worker 不会阻塞主线程的执行。
• 通信机制：主线程和 Worker 线程之间通过消息传递（postMessage 和 onmessage）进行通信。
• 受限环境：Worker 线程不能访问 DOM，也不能调用一些特定的 Web API，如 alert 和 localStorage。

基本用法

• 监听消息事件

  1 2 3 4 5 6

  self.addEventListener('message', async e => { console.log(e) const { file, chunkSize } = e.data const fileChunkList = await createFileChunk(file, chunkSize) await calculateChunksHash(fileChunkList) })

• 监听错误事件

  1 2 3 4 5

  self.addEventListener('error', function (e) { console.log("%cWorker 线程 error 监听事件: ", 'color: red', e) // worker 线程关闭 self.close() })

切片实现

• 1、文件切片

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  //第一个参数是file，第二个是切片大小 function createFileChunk(file, chunkSize) { // new Promise 的基本用法：来创建一个新的 Promise 对象,该函数有两个参数：resolve 和 reject。 //resolve 用于在异步操作成功时返回结果，reject 用于在异步操作失败时返回错误。 return new Promise(resolve => { let fileChunkList = [] let cur = 0 while (cur < file.size) { fileChunkList.push({ chunkFile: file.slice(cur, cur + chunkSize) }) cur += chunkSize } resolve(fileChunkList) }) }

切片标记

• 每个切片有自己的MD5哈希值，所有切片的哈希值保存在SparkMD5.ArrayBuffer 实例spark中，在切片完成后，spark值传递给fileHash，webWork将fileHash和fileChunkList文件切片传给了主线程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// 记载并计算文件切片的 md5
async function calculateChunksHash(fileChunkList = []) {
  // 创建一个 SparkMD5.ArrayBuffer 实例，用于计算 MD5 哈希值。
  const spark = new SparkMD5.ArrayBuffer()

  // 计算切片进度
  let percentage = 0

  try {
    const fileHash = await loadNext()
    self.postMessage({ percentage: 100, fileHash, fileChunkList })
    self.close()
  } catch (err) {
    self.postMessage({ name: 'error', data: err })
    self.close()
  }

  // 递归函数，处理文件的切片
  async function loadNext(index = 0) {
    // 所有的切片都已处理完毕
    if (index >= fileChunkList.length) {
      // 返回这个文件的MD5哈希值
      return spark.end()
    }
    return new Promise((resolve, reject) => {
      const reader = new FileReader()
      reader.readAsArrayBuffer(fileChunkList[index].chunkFile)
      reader.onload = (e) => {
        spark.append(e.target.result)
        percentage += 100 / fileChunkList.length
        self.postMessage({
          percentage
        })
        resolve(loadNext(index + 1))
      }
      reader.onerror = (err) => reject(err)
    })
  }
}

主线程任务

• 该方法能依次上传多个文件。
• 切片大小设置为5MB
• 多个文件输入处理逻辑：
  • 如果输入框有change事件，判断是否有文件传入，如果有将每个文件进行切片处理，并上传
  • 对每个文件绑定响应式对象，对象包括文件名、文件大小、文件状态、所有需要上传的切片、文件hash、最大报错次数、上传进度等属性。
  • 根据文件的状态来确定，当前文件需要进行的流程。
  • 需要切片上传的文件，交给webworker切片，并将结果返回。作为参数传给开始上传函数
  • 多个文件并行上传
• 开始上传文件的逻辑：
  • 需要参数，file，inTaskArrItem（初始化的一个对象，包含单个文件的属性）， fileChunkList（单个文件的切片）
  • 判断文件是否已经存在于服务器，如果存在直接return，如果不存在执行上传的逻辑
  • 将每个切片的信息写入inTaskArrItem的allChunList（所有需要上传的切片）中
  • 对allChunkList进行过滤，过滤掉已经上传成功的切片（判断是否上传成功，由checkfile函数完成）
  • 如果没有需要上传的切片，但是前面判断服务器中没有此文件，说明需要合并，再次执行文件合并函数
• 每一个文件的处理逻辑
  • 如果没有需要上传的切片或者状态为正在被上传，不做处理
  • 找出需要上传的文件，并将入待处理文件的列表中。根据列表长度计算每个文件的并发请求数量。（chrome浏览器同域名同一时间请求的最大并发数限制为 6，如果有三个文件需要上传，那么每个文件上传只能同时并发2个请求）
  • 从需要上传的切片尾部拿2个切片，放入请求数组中。并将其从allChunkList中删除
  • 开始上传切片
• 切片上传逻辑
  • 首先判断文件状态，如果文件状态为暂停或终端就什么都不错
  • 每个切片由三次机会，如果三次都失败，则文件上传失败

图片懒加载

简介

• 图片懒加载是一种前端性能优化技术，它通过延迟非关键资源（如图片）的加载时机，直到这些资源即将被用户看到内或者经过一定的延迟后，才开始加载，从而减少初次页面加载的时间和数据使用量，提高用户体验。
• 本文总结的图片懒加载技术依赖vue，并将其封装为一个插件
• 支持组件可见或即将可见时懒加载
• 支持加载真实组件前展示骨架组件，提高用户体验

涉及的属性

非响应式

1.timeout:

• 类型：Number
• 作用：指定延迟加载的时间（以毫秒为单位）。如果设置了这个属性，组件将在指定时间后初始化。

2、tagName:

• 类型：String
• 默认值：’div’
• 作用：指定包裹内容的 HTML 标签名称。默认是 div，可以根据需要更改为其他标签。

3、viewport:

• 类型：HTMLElement 或 Object
• 默认值：null
• 作用：指定视口元素，用于 IntersectionObserver。如果没有指定，默认是 null，表示使用浏览器的视口。

4、threshold:

• 类型：String
• 默认值：’0px’
• 作用：指定触发懒加载的阈值。可以设置为像素值或百分比，例如 ‘100px’ 或 ‘50%’。

5、direction:

• 类型：String
• 默认值：’vertical’
• 作用：指定滚动方向。可以是 ‘vertical’（垂直方向）或 ‘horizontal’（水平方向）。

6、maxWaitingTime:

• 类型：Number
• 默认值：50
• 作用：指定最大等待时间（以毫秒为单位），用于 requestAnimationFrame 回调，防止主线程卡顿。

这些属性允许用户在使用 VueLazyComponent 时进行灵活配置，以满足不同的需求。

响应式

1、isInit:

• 类型：Boolean
• 默认值：false
• 作用：表示组件是否已经初始化。当组件完成初始化时，这个值会被设置为 true。

2、timer:

• 类型：null 或 Number
• 默认值：null
• 作用：用于存储定时器的引用。如果设置了 timeout 属性，组件会在指定时间后初始化，这个定时器用于实现这个功能。

3、io:

• 类型：null 或 IntersectionObserver
• 默认值：null
• 作用：用于存储 IntersectionObserver 的实例。IntersectionObserver 用于检测组件是否进入视口，以便延迟加载内容。

4、loading:

• 类型：Boolean
• 默认值：false
• 作用：表示组件是否正在加载内容。当组件开始加载内容时，这个值会被设置为 true。

这些数据属性用于管理组件的状态和行为。通过响应式的数据属性，Vue.js 可以在数据变化时自动更新视图，从而实现动态和交互式的用户界面。

功能详解

懒加载内容

• IntersectionObserver是浏览器内置API，用于异步观察一个目标元素与其祖先元素或顶级文档视口（viewport）交叉状态的变化。它可以用于实现懒加载、无限滚动、广告曝光监测等功能。

• IntersectionObserver 构造函数用于创建一个新的 IntersectionObserver 实例。它接受两个参数：

  • 回调函数（callback）：当目标元素的可见性发生变化时，这个回调函数会被调用。
  • 选项对象（options）：用于配置 IntersectionObserver 的行为。
    可选参数，用于配置 IntersectionObserver 的行为。包含以下属性：
    • root：指定用作视口的元素，必须是目标元素的祖先元素。默认是浏览器的视口。
    • rootMargin：用于扩展或缩小 root 元素的边界，类似于 CSS 的 margin 属性。可以使用像素值或百分比。
    • threshold：一个数值或数值数组，表示目标元素的可见比例达到这些值时，回调函数会被触发。

骨架展示

模板中的条件渲染：

• 使用 v-if 和 v-else-if 指令根据 isInit 状态渲染实际内容或骨架屏。
• isInit 为 false 时显示骨架屏，为 true 时显示实际内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

<template>
  <transition-group :tag="tagName" name="lazy-component" style="position: relative;"
    @before-enter="(el) => $emit('before-enter', el)"
    @before-leave="(el) => $emit('before-leave', el)"
    @after-enter="(el) => $emit('after-enter', el)"
    @after-leave="(el) => $emit('after-leave', el)"
  >
    <div v-if="isInit" key="component">
      <slot :loading="loading"></slot>
    </div>
    <div v-else-if="$slots.skeleton" key="skeleton">
      <slot name="skeleton"></slot>
    </div>
    <div v-else key="loading">
    </div>
  </transition-group>
</template>

过渡动画

transition-group：

• 使用 transition-group 包裹内容，实现内容切换时的过渡动画。
• 通过 @before-enter、@before-leave、@after-enter 和 @after-leave 事件触发父组件的相应事件。

事件通知

在组件生命周期的不同阶段触发事件，通知父组件。

逻辑

• 首先搞清楚，这里的懒加载是指以显示骨架内容代替真实数据，，等到有需要的时候再加载真实数据。

• 在视口加载和超过设定时长自动加载，两者通过timeout属性决定，timeout为true使用延时加载，否则使用视口加载模式

• 初始化是指加载真实数据的组件，即将loading指改为true。

• 在挂载时，如果timeout值为加假，说明要使用视口交叉来懒加载图片。需要初始化视口交叉监视API：IntersectionObserver

• 在创建阶段，如果指定timeout则无论可见与否都是在timeout之后初始化

• 销毁：在组件销毁前取消观察

• 然后这里还定义了一些自定义函数，供插件使用者监听组件的状况。

双指针系列

合并两个有序数组

解决思路

逆向双指针，从后往前比较两个数组的元素大小。大的填入应在的位置，然后指针前移，小的不作操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 逆向双指针的方法
var merge = function(nums1, m, nums2, n) {
  let p1 = m-1,p2 = n-1,p = m+n-1  //三个指针，第一个用来遍历数组1中的每个值。
  //第二个用来遍历数组2中的每一个值，第三个用来存数据，从数组1的最后一个位置开始。
  while(p1>=0 && p2>=0){ // 双指针，从两个数组的最后一个数开始，倒着比较值的大小。
    if (nums2[p2]>=nums1[p1]){
      nums1[p] = nums2[p2]
      p2--
    }
    else{
      nums1[p] = nums1[p1]
      p1--
    }
    p--
  }
  while(p2>=0){//如果数组2中还有剩余的元素，全部放在数组1的前面
    nums1[p] = nums2[p2]
    p2--
    p--
  }
};

最长无重复子串

解题思路

滑动窗口

• 1、使用left和right两个指针，分别表示滑动窗口的左右边界，初始时都指向字符串的开头。
• 2、使用一个哈希表（或者数组）来记录字符是否出现过以及字符出现的位置。
• 3、不断移动右指针 right，每次移动时判断当前字符是否出现过：
  • 如果当前字符已经出现过，并且在当前窗口内（即其位置大于等于 left），则更新 left 指针的位置为该字符上次出现的位置的下一个位置。
  • 如果当前字符没有出现过，或者虽然出现过但不在当前窗口内，则更新最长子字符串的长度。
• 不断更新最长子字符串的长度，并返回结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var lengthOfLongestSubstring = function(s) {
  let l=0,r=0,max=0
  let map = new Map()
  while(r<s.length){
    //判断map的记录中，这个字符的值是否在滑动窗口内
    if (map.has(s[r]) && map.get(s[r]) >= l) {
      //如果在窗口内l指针指向当前记录值的后一位
      l = map.get(s[r])+1
    }
    //如果map中没有当前字符得记录或者有记录但是不在滑动窗口范围内
    map.set(s[r], r)
    max = Math.max(max, r - l + 1)
    r++
  }
  return max
}

判断子序列

解题思路

• 初始化指针i，j分别指向字符串是，和t的起始位置；其中s是子串，t是较长的字符串
• 遍历比较s[i]和t[j]的情况
  • 如果s[i]==t[j]，那么指向子串的指针+1，即i++；且j++
  • 如果不想等j++
• 判断子序列：如果 i 移动到了 s 的末尾，则说明 s 是 t 的子序列，返回 true；否则返回 false。

代码

1
2
3
4
5
6
7
8
9
10
11

var isSubsequence = function(s, t) {
  let i=0,j=0
  //处理两个字符串都是空字符串的情况
  if (s==t) return true
  while (j<t.length){
    if (s[i]===t[j]) i++
    j++
  }
  if (i==s.length) return true
  else return false
};

两数之和

解题思路

使用字典,判断目标值减去当前值的结果是否，存在于字典中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13

var twoSum = function(nums, target) {
  let map = new Map()
  // 判断target-当前元素的结果是否存在于map中，如果存在返回下标
  for (let i=0;i<nums.length;i++){
    if (map.has(target-nums[i])){
      return [map.get(target-nums[i]),i]
    }
    //如果不存在，设置当前元素为键，当前元素下表为值
    else{
      map.set(nums[i],i)
    }
  }
}

三数之和

解决思路回溯算法：

1、回溯的三部曲，参数确定，确定终止条件，单层递归逻辑。提升效率要剪枝
2、双指针法：对数组进行排序，先确定第一个数字，然后使用双指针分别总数组的第一个和第最后一个开始，判断当前总和，综合大，右边指针前移，否者左边指针后移。

去重逻辑：第一个数字的去重，和后面两个数字的去重。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

var threeSum = function (nums) {
  let res = []
  nums = nums.sort((a,b)=>a-b) //首先要进行排序
  for (let i = 0; i < nums.length-2; i++) {  //减2是因为求得是三个元素的和。
    if (i > 0 && nums[i] == nums[i - 1]) continue //a去重
    let left = i + 1,right = nums.length - 1 //指定双指针
    while (left < right) {
      let sum = nums[i]+nums[left]+nums[right]
      if (sum>0) right--
      if (sum<0) left++
      if(sum===0){
        res.push([nums[i],nums[left],nums[right]])
        //后两个数去重逻辑，如果指针指向下一个元素与当前相同，跳过该元素
        while(left<right && nums[left] === nums[left+1]) left++
        while(left<right && nums[right] === nums[right-1]) right--
        left++     //忘记调整这两个了
        right--
      }
    }
  }
  return res
}

反转链表

自定义链表

解题代码

1
2
3
4
5
6
7
8
9
10
11
12

var reverseList = function(head) {
  let prev = null
  let cur = head
  while(cur){
    // 这一步我忘记了，没有把next的值保存下来，直接给cur.next赋值了
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev //最后一个cur是null，他前面一个才是第一个有值的节点
};

排序算法

快速排序

其核心思想是分治，选择一个基准元素，将比基准小的元素放在左边，比基准大的元素放在右边。然后地柜对左右两个部分，分别进行快速排序。

快速排序复杂度
平均时间复杂度（Onlogn）、最坏情况O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function quickSort(arr) {
  //终止条件
  if (arr.length <= 1) return arr
  //找基准,选择最后一个元素作为基准
  let std = arr.length - 1
  //用来存储左右两个数组
  let leftArr = [],
    rightArr = []
  for (let i = 0; i < std && i != std; i++) {
    if (arr[i] <= arr[std]) leftArr.push(arr[i])
    else rightArr.push(arr[i])
  }
  //分别处理左右两个子数组
  return [...quickSort(leftArr), arr[std], ...quickSort(rightArr)]
}
console.log(quickSort([5, 2, 9, 1, 7, 6,3,80,34]))

选择排序

选择最大的数，放在数组的最右边，然后再选择第二大的数，放在数组的右边第二的位置，以此类推。

选择排序复杂度
平均时间复杂度（Onlogn）、最坏情况O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function selectSort(arr){
  const n = arr.length-1
  // 从后往前排好arr的顺序，所以遍历从后往前
  for (let i=n;i>0;i--){
    let maxIndex = i
    // 将没排好序的过一遍
    for (let j=0;j<=i;j++){
      if (arr[j]>arr[maxIndex]) maxIndex = j
    }
    if (maxIndex != i){
      [arr[maxIndex],arr[i]] = [arr[i],arr[maxIndex]]
    }
  }
  return arr
}

冒泡排序

冒泡排序通过重复遍历要排序的列表，每次比较相邻的两个元素。如果顺序不正确，就交换它们的位置。这个过程会重复直到整个列表有序。

每一轮遍历会将一个最大的元素“冒泡”到末尾。

复杂度：时间复杂度：O(n²)

1
2
3
4
5
6
7
8
9
10

function populeSort(arr){
  let len = arr.length-1
  for(let i=0;i<len;i++){
    // 每一轮遍历都会将一个最大的元素“冒泡”到末尾，所以下一轮遍历就不用再遍历最后一个元素
    for(let j=0;j<len-1;j++){
      if(arr[j]>arr[j+1]) [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
    }
  }
  return arr
}

插入排序

插入排序将数组划分为已排序和未排序部分，从未排序部分取出元素，并将其插入到已排序部分的适当位置。这个过程会反复执行，直到所有元素都被插入到正确的位置。

复杂度：时间复杂度：O(n²) 最好情况（数组本身有序）：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function insertSort(arr){
  //有序无序两部分，从无序的数据中一次拿数据，插入到有序部分
  let len = arr.length
  // 第一个元素是有序部分，从第二个数据开始拿数据
  for(let i=1;i<len;i++){
    let curr = arr[i]
    let j=i-1
    //从有序数据的后面开始往前遍历，直到找到合适插入的位置
    while(j>=0 && curr<arr[j]){
      // 给将来要插入元素的地方腾位置
      arr[j+1] = arr[j]
      j--
    }
    arr[j+1] = curr
  }
  return arr
}

归并排序

归并排序是另一种分治算法，它将数组递归地拆分为两个子数组，直到每个子数组只有一个元素。然后将这些子数组有序地合并，直到所有元素合并成一个有序数组。

归并排序是一种稳定排序，而且它的最坏情况复杂度和平均复杂度都是 O(n log n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function mergeSort(arr){
  //终止条件，就是arr长度
  if (arr.length<=1) return arr
  //首先将数组分为二部分
  let mid = Math.floor(arr.length/2)
  let leftArr = arr.slice(0,mid)
  let rightArr = arr.slice(mid)
  return merge(mergeSort(leftArr),mergeSort(rightArr))
}

function merge(left,right){
  let result =[]
  let i=0,j=0
  while(i<left.length && j<right.length){
    if (left[i]<right[j]){
      result.push(left[i])
      i++
    }
    else{
      result.push(right[j])
      j++
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j))
}

堆排序

堆排序利用了堆这种数据结构。堆是一种特殊的完全二叉树，分为大顶堆和小顶堆。堆排序的核心思想是：首先将数组构造成一个最大堆，然后依次将堆顶元素（最大值）与最后一个元素交换，再将剩下的元素重新调整为堆，直到排序完成。

复杂度：时间复杂度：O(n log n)

二叉树系列

层序遍历

前序遍历

递归法

1
2
3
4
5
6
7
8
9
10
11

var preorderTraversal = function (root) {
  const res = []
  const preorder = (rt)=>{
    if (!rt) return
    res.push(rt.val)
    preorder(rt.left)
    preorder(rt.right)
  }
  preorder(root)
  return res
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13

var preorderTraversal = function (root) {
  let res = []
  if (!root) return res   // 应对空二叉树
  let queue = [root]
  while(queue.length){
    //每次从队列里去一个节点，把该节点的值添加到result，
    let cur = queue.pop()
    res.push(cur.val) //该节点的右孩子和左孩子依次加入节点，
    if (cur.right) queue.push(cur.right) //等到下一轮，就会分别依次遍历左孩子和有孩子了
    if (cur.left) queue.push(cur.left)
  }
return res
}

后序遍历

递归法

1
2
3
4
5
6
7
8
9
10
11

var postorderTraversal = function (root) {
  let res = []
  const postorder = (rt) => {
    if (!rt) return    //不要忘了这个条件
    postorder(rt.left)
    postorder(rt.right)
    res.push(rt.val)
  }
  postorder(root)
  return res
}

迭代法

1

中序遍历

递归法

1
2
3
4
5
6
7
8
9
10
11

var inorderTraversal = function (root) {
  let res =[]
  const inorder = (rt)=>{
    if (!rt) return
    rt.left && inorder(rt.left)
    res.push(rt.val)
    rt.right && inorder(rt.right)
  }
  inorder(root)
  return res
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

var inorderTraversal = function (root) {
  // 入栈:左->右
  // 出栈:左 中 右
  let res = []
  const stack = []
  if (root) stack.push(root)
  while (stack.length) {
    const node = stack.pop()
    if (!node) {
      res.push(stack.pop().val)
      continue
    }
    if (node.right) stack.push(node.right) // 右
    stack.push(node) // 中
    stack.push(null)
    if (node.left) stack.push(node.left) // 左
  }
  return res
}

promise

是什么

Promise 是用于处理异步操作的对象。它有三种状态：pending（进行中）、fulfilled（已成功）和 rejected（已失败）。我们可以手写一个简化版的 Promise，实现其基本功能。

实现思路：
Promise 构造函数接收一个执行器函数，该函数有两个参数 resolve 和 reject，用于改变 Promise 的状态。
then 方法用于注册回调函数，在 Promise的状态改变后执行。
使用状态机来管理 pending、fulfilled 和 rejected 状态。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

class MyPromise {hexp
  constructor(executor) {
    this.state = 'pending';   // 初始状态
    this.value = undefined;    // 成功的值
    this.reason = undefined;   // 失败的原因
    this.onFulfilledCallbacks = []; // 存储成功回调
    this.onRejectedCallbacks = [];  // 存储失败回调

    // resolve 函数
    const resolve = (value) => {
      if (this.state === 'pending') {
        this.state = 'fulfilled';   // 状态转为 fulfilled
        this.value = value;         // 传递成功的值
        this.onFulfilledCallbacks.forEach(fn => fn(this.value)); // 执行成功回调
      }
    };

    // reject 函数
    const reject = (reason) => {
      if (this.state === 'pending') {
        this.state = 'rejected';   // 状态转为 rejected
        this.reason = reason;      // 传递失败的原因
        this.onRejectedCallbacks.forEach(fn => fn(this.reason)); // 执行失败回调
      }
    };

    // 执行 executor，并捕获异常
    try {
      executor(resolve, reject);
    } catch (error) {
      reject(error);
    }
  }

  // then 方法
  then(onFulfilled, onRejected) {
    // 如果 `onFulfilled` 不是函数，默认返回 value
    onFulfilled = typeof onFulfilled === 'function' ? onFulfilled : value => value;
    // 如果 `onRejected` 不是函数，默认抛出 reason
    onRejected = typeof onRejected === 'function' ? onRejected : reason => { throw reason };

    if (this.state === 'fulfilled') {
      onFulfilled(this.value);
    }

    if (this.state === 'rejected') {
      onRejected(this.reason);
    }

    if (this.state === 'pending') {
      this.onFulfilledCallbacks.push(onFulfilled);
      this.onRejectedCallbacks.push(onRejected);
    }
  }
}

// 测试 MyPromise
const promise = new MyPromise((resolve, reject) => {
  setTimeout(() => {
    resolve('Success!');
  }, 1000);
});

promise.then(
  value => console.log('Fulfilled:', value),
  reason => console.log('Rejected:', reason)
);

promise.all

是什么

Promise.all() 是一个用于并行处理多个 Promise 的方法，它接受一个包含多个 Promise 的可迭代对象，并返回一个新的 Promise。只有当所有 Promise 都成功时，这个新的 Promise 才会 resolve；如果其中任何一个 Promise 失败，Promise.all() 就会 reject，并返回第一个失败的 Promise 的原因。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// promise.all
function promiseAll(promises){
  return new Promise((resolve,reject)=>{
    if(!Array.isArray(promises)) return reject(new TypeError('参数类型应该为数组'))
    if (promises.length==0) return resolve([])
    let resultArr = []
    let completedPromises = 0
    promises.forEach((promise,index)=>{
      Promise.resolve(promise)
      .then(result=>{
        resultArr[index] = result
        completedPromises ++
        if (completedPromises==promises.length) resolve(resultArr)
      })
      .catch(error=> reject(error))
    })
  })
}
// 示例
const p1 = Promise.resolve(3)
const p2 = new Promise((resolve) => setTimeout(resolve, 1000, 'foo'))
const p3 = Promise.resolve(42)

promiseAll([p1, p2, p3])
  .then((results) => console.log(results)) // 输出 [3, "foo", 42]
  .catch((err) => console.log(err))

promise.race

是什么

Promise.race() 方法会返回一个新的 Promise，一旦传入的 Promise 中有一个完成（无论是 resolved 还是 rejected），就会立即以那个 Promise 的结果（resolved 或 rejected）进行决议。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

function promiseRace(promises) {
  return new Promise((resolve, reject) => {
    if (!Array.isArray(promises)) {
      return reject(new TypeError('Argument must be an array'));
    }

    // 如果传入的数组为空，Promise 将永远不会 resolve 或 reject
    if (promises.length === 0) {
      return;  // 不返回任何内容，Promise 将保持 pending 状态
    }

    // 遍历每个 Promise
    promises.forEach(promise => {
      // 使用 Promise.resolve 将所有项处理为 Promise
      Promise.resolve(promise)
        .then(resolve)   // 一旦某个 Promise resolve，立即 resolve 结果
        .catch(reject);  // 一旦某个 Promise reject，立即 reject 错误
    });
  });
}

// 示例
const p1 = new Promise((resolve) => setTimeout(resolve, 500, "First"));
const p2 = new Promise((resolve) => setTimeout(resolve, 100, "Second"));
const p3 = new Promise((resolve, reject) => setTimeout(reject, 200, "Error"));

promiseRace([p1, p2, p3])
  .then(result => console.log(result))  // 输出 "Second" 因为 p2 最先完成
  .catch(err => console.log(err));

web缓存

是什么

• web缓存有两部分：浏览器缓存和http缓存

  • 浏览器缓存比如:localStorage、sessionStorage、cookies等。用于缓存一些必要数据，用户信息、需要携带到后端的参数、一些列表数据。

  • 存储大小有限制localStorage、sessionStorage有5M，cookies大概4kb

• http缓存

  官方介绍:Web 缓存是可以自动保存常见文档副本的 HTTP 设备。当 Web 请求抵达缓存时， 如果本地有“已缓存的”副本，就可以从本地存储设备而不是原始服务器中提取这 个文档。

• 客户端发起请求http请求，服务器需要处理http的请求，并且http去传输数据，需要带宽，带宽是要钱买的啊。而我们缓存，就是为了让服务器不去处理这个请求，客户端也可以拿到数据。

• 一般缓存静态资源html，css，img，动态资源实时性强不适合缓存

解决的问题与优缺点

• 减少不必要的网络传输，节省带宽。
• 更快加载页面
• 减少服务器负担，避免服务器过载

实际场景：

其实日常的开发中，我们最最最最关心的，还是”更快的加载页面”;尤其是对于react/vue等SPA（单页面）应用来说，首屏加载是老生常谈的问题。这个时候，缓存就显得非常重要。不需要往后端请求，直接在缓存中读取。速度上，会有显著的提升。是一种提升网站性能与用户体验的有效策略。

知识扩展

• 单页Web应用（single page web application，SPA），整个应用在初次加载时加载一个包含必要资源的HTML页面，之后所有的页面内容变化都是通过JavaScript动态更新DOM来实现，不需要重新加载整个页面。
• 多页面应用，每次用户导航到新的页面时，都需要从服务器加载一个新的HTML页面。

强缓存和协商缓存

强缓存

从强制缓存的角度触发，如果浏览器判断请求的目标资源有效命中强缓存，如果命中，则可以直接从内存中读取目标资源，无需与服务器做任何通讯。

Cache-control的使用方法页很简单，只要在资源的响应头上写上需要缓存多久就好了，单位是秒。比如
在响应头中Cache-Control:’max-age=10’

Cache-Control:max-age=N，N就是需要缓存的秒数。从第一次请求资源的时候开始，往后N秒内，资源若再次请求，则直接从磁盘（或内存中读取），不与服务器做任何交互。

• Cache-control有max-age、s-maxage、no-cache、no-store、private、public这六个属性。
  • max-age决定客户端资源被缓存多久。
  • s-maxage决定代理服务器缓存的时长。
  • no-cache表示是强制进行协商缓存。
  • no-store是表示禁止任何缓存策略。
  • public表示资源即可以被浏览器缓存也可以被代理服务器缓存。
  • private表示资源只能被浏览器缓存。

    注意，no-cache和no-store是一组互斥属性，这两个属性不能同时出现在Cache-Control中。
    注意，public和private也是一组互斥属性。他们两个不能同时出现在响应头的cache-control字段中。
    注意，max-age和s-maxage并不互斥。他们可以一起使用。

协商缓存

• 基于last-modified的协商缓存
  基于last-modified的协商缓存实现方式是:
  1、首先需要在服务器端读出文件修改时间，
  2、将读出来的修改时间赋给响应头的last-modified字段。
  3、最后设置Cache-control:no-cache

注意圈出来的三行。
第一行，读出修改时间。
第二行，给该资源响应头的last-modified字段赋值修改时间
第三行，给该资源响应头的Cache-Control字段值设置为:no-cache.(上文有介绍，Cache-control:no-cache的意思是跳过强缓存校验，直接进行协商缓存。)
还没完。到这里还无法实现协商缓存
当客户端读取到last-modified的时候，会在下次的请求标头中携带一个字段:If-Modified-Since。

那么之后每次对该资源的请求，都会带上If-Modified-Since这个字段，而务端就需要拿到这个时间并再次读取该资源的修改时间，让他们两个做一个比对来决定是读取缓存还是返回新的资源。

使用以上方式的协商缓存已经存在两个非常明显的漏洞。这两个漏洞都是基于文件是通过比较修改时间来判断是否更改而产生的。

1.因为是更具文件修改时间来判断的，所以，在文件内容本身不修改的情况下，依然有可能更新文件修改时间（比如修改文件名再改回来），这样，就有可能文件内容明明没有修改，但是缓存依然失效了。

2.当文件在极短时间内完成修改的时候（比如几百毫秒）。因为文件修改时间记录的最小单位是秒，所以，如果文件在几百毫秒内完成修改的话，文件修改时间不会改变，这样，即使文件内容修改了，依然不会 返回新的文件。

为了解决上述的这两个问题。从http1.1开始新增了一个头信息，ETag(Entity 实体标签)

基础ETag的协商缓存
不用太担心，如果你已经理解了上面比较时间戳形式的协商缓存的话，ETag对你来说不会有难度。

ETag就是将原先协商缓存的比较时间戳的形式修改成了比较文件指纹。

文件指纹:根据文件内容计算出的唯一哈希值。文件内容一旦改变则指纹改变。

1.第一次请求某资源的时候，服务端读取文件并计算出文件指纹，将文件指纹放在响应头的etag字段中跟资源一起返回给客户端。

2.第二次请求某资源的时候，客户端自动从缓存中读取出上一次服务端返回的ETag也就是文件指纹。并赋给请求头的if-None-Match字段，让上一次的文件指纹跟随请求一起回到服务端。

3.服务端拿到请求头中的is-None-Match字段值（也就是上一次的文件指纹），并再次读取目标资源并生成文件指纹，两个指纹做对比。如果两个文件指纹完全吻合，说明文件没有被改变，则直接返回304状态码和一个空的响应体并return。如果两个文件指纹不吻合，则说明文件被更改，那么将新的文件指纹重新存储到响应头的ETag中并返回给客户端

单调栈

何时用单调栈

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。如果暴力破解复杂度为O(n^2)。

那么单调栈的原理是什么呢？为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢？

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。

更直白来说，就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。

单调栈怎们用

• 栈中元素存什么
  存元素下标

• 单调栈里元素是递增呢？ 还是递减呢？

  • 首先是递增和递减的判断是指，从栈口到栈底
  • 递增：求左边或者右边第一个比他大的元素
  • 递减：求左边或者右边第一个比他晓得元素

• 单调栈的作用
  存放遍历过的元素

• 主要判断条件
  当前遍历元素T[i]与T[st.pop()]的关系

  • 1、T[i] > T[st.pop()] i-st.pop() i进栈
  • 2、T[i] == T[st.pop()] i-st.pop() i进栈
  • 3、T[i] < T[st.pop()] i进栈

题目

每日温度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

var dailyTemperatures = function(temperatures) {
  let n = temperatures.length
  let stack = [0]
  let res = Array(n).fill(0)
  for(let i=1;i<n;i++){
    let top = stack[stack.length-1]
    //小于和等于的情况，直接压入栈
    if (temperatures[i] === temperatures[top]){
      stack.push(i)
    }
    else if(temperatures[i] < temperatures[top]){
      stack.push(i)
    }
    //当前元素大于栈顶元素的情况，要计算距离，
    //删掉栈顶元素知道所有小于当前元素的栈顶元素被删完，压入当前元素
    else{
      while (stack.length && temperatures[i] > temperatures[stack[stack.length-1]]) {
        top = stack.pop()
        res[top] = i-top
      }
      stack.push(i)
    }
  }
  return res
};

下一个更大元素 I

思路
用到hash,将nums1存在map中，键位nums1中的元素，值为nums1中元素的索引

使用单调栈解决问题，遍历数组nums2，根据条件进行不同处理

• 1、当前元素小于或等于栈顶元素，当前元素压入栈
• 2、当前元素大于栈顶元素，查看栈顶元素是否出现在nums1中，如果在，那么及已经找到的他右边的较大元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

var nextGreaterElement = function (nums1, nums2) {
  const m = nums1.length
  const n = nums2.length
  let stack = [nums2[0]]
  let res = Array(m).fill(-1)
  let map = new Map()
  for (let i = 0; i < m; i++) {
    map.set(nums1[i],i)
  }
  for (let j = 1; j < n; j++) {
    let top = stack[stack.length-1]
    if (nums2[j]<top || nums2===top) stack.push(nums2[j])
    else{
        // console.log(res)
        while(stack.length && nums2[j]>stack[stack.length-1]){
          top = stack.pop()
          if (map.has(top)){
            res[map.get(top)] = nums2[j]

          }
        }
        stack.push(nums2[j])
      }
  }
  return res
}

下一个更大元素

思路
数组循环了，思路是把数组复制一份拼接在原数组后面，但是这占用了空间，所以思路是遍历两次数组就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

var nextGreaterElements = function(nums) {
  let n = nums.length
  let res = Array(n).fill(-1)
  let stack = [0]
  for(let i=1;i<n*2;i++){
    let j = i
    if (i>=n)  j = i - n
    while (stack.length && nums[j] > nums[stack[stack.length - 1]]) {
      let top = stack.pop()
      res[top] = nums[j]
    }
    stack.push(j)
  }
  return res
};

接雨水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

var trap = function(height) {
  let n = height.length
  let res = 0
  let stack = [0]
  for(let i=1;i<n;i++){
    while(stack.length && height[i]>height[stack[stack.length-1]]){
        let top = stack.pop()
        if (stack.length === 0) break
        let topl = stack[stack.length-1]
        res += (Math.min(height[i],height[topl])-height[top]) * (i-topl-1)
    }
    stack.push(i)
  }
  return res
};

柱状图中最大的矩形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var largestRectangleArea = function(heights) {
  heights = [0,...heights,0]
  let n = heights.length
  let maxArea = 0
  let stack =[0]
  for (let i=1;i<n;i++){
    while(heights[i]<heights[stack[stack.length-1]]){
      let top = stack.pop()
      let topl = stack[stack.length-1]
      let w = i-topl-1
      maxArea = Math.max(maxArea,w*heights[top])
    }
    stack.push(i)
  }
  return maxArea
};

LCR 130. 衣橱整理

思路

首先需要理解题意，我刚开始理解为在一个矩阵中找到所有符合digit(i)+digit(j)<=cnt的个数。如下图我以为是找出蓝色格子数量。

实际并不是，只要找到从(0,0)触发，能通过向下或向右走一格能到达的符合digit(i)+digit(j)<=cnt的格子的个数。也就是说要找的是从（0，0）出发通过右移或下移一格能到达的蓝色格子的个数。

题解和网友说要用到深度优先遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function wardrobeFinishing(m, n, cnt) {
  const digitSum = (num) => {
    let sum = 0
    while (num) {
      sum += num % 10
      num = Math.floor(num / 10)
    }
    return sum
  }

  const visited = Array.from({ length: m }, () => Array(n).fill(false))
  let count = 0

  const dfs = (i, j) => {
    if ( i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || digitSum(i) + digitSum(j) > cnt)
      return
    visited[i][j] = true
    count++
    dfs(i + 1, j) // 向下移动
    dfs(i, j + 1) // 向右移动
  }

  dfs(0, 0) // 从(0, 0)开始搜索
  return count
}