每日两题 T4

算法

LeetCode T面试题 17.16. 按摩师[1]

描述

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

示例 1：

输入：[1,2,3,1]
输出：4
解释：选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。

实例3

输入：[2,1,4,5,3,1,1,3]
输出：12
解释：选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

分析

该问题是典型的 动态规划 问题，使用两个变量存储时间和，遍历过程中，对比两个变量值大小，始终将大的值赋值给指定的一个变量，最终返回这个变量即为所求。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var massage = function (nums) {
  let a1 = 0, a2 = 0
  for (let i = 0; i < nums.length; i++) {
    let temp = Math.max(a2, a1 + nums[i])
    a1 = a2
    a2 = temp
  }
  return a2
};

JavaScript

介绍下 Set、Map、WeakSet 和 WeakMap ？

Set 和 Map 主要的应用场景在于 数据重组 和 数据储存

Set 是一种叫做集合的数据结构，Map 是一种叫做字典的数据结构

•Set

•成员唯一、无序且不重复•[value, value]，键值与键名是一致的（或者说只有键值，没有键名）•可以遍历，方法有：add、delete、has

•WeakSet

•成员都是对象•成员都是弱引用，可以被垃圾回收机制回收，可以用来保存DOM节点，不容易造成内存泄漏•不能遍历，方法有add、delete、has

•Map

•本质上是键值对的集合，类似集合•可以遍历，方法很多可以跟各种数据格式转换

•WeakMap

•只接受对象作为键名（null除外），不接受其他类型的值作为键名•键名是弱引用，键值可以是任意的，键名所指向的对象可以被垃圾回收，此时键名是无效的•不能遍历，方法有get、set、has、delete

References

[1] 面试题 17.16. 按摩师: https://leetcode-cn.com/problems/the-masseuse-lcci/