1、【两数之和】twoSum 得到两个数的之后等于 target

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解题方式一、双重循环

const twoSum = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
}

注意：时间复杂度为：O(n^2)

解题方式二、Map 取差值（将值和下标对应）

const twoSum = (nums, target) => {
  const map = {}
  for (let i = 0; i < nums.length; i++) {
    const value = nums[i]
    const diff = target - value // 计算差值
    if (typeof map[diff] !== 'undefined') {
      return [map[diff], i]
    } else {
      map[value] = i
    }
  }
}

注意：时间复杂度为：O(n)

2、【全排列】

给定一个字符串，输出该字符串所有排列的可能。如输入“abc”，输出“abc,acb,bca,bac,cab,cba”。

思路：定义一个数组存放全排列的情况并返回。判断输入的字符串是否为单个字符串的情况。是，返回其本身。不是，则遍历字符串中的每一个元素，并将字符串中除了该元素的其他元素

function fullPermutation(str) {
  var result = [] // 存放全排列的情况
  if (str.length > 1) {
    for (var i = 0; i < str.length; i++) {
      var left = str[i] // 当前元素
      // 除当前元素以外的其他组合
      var rest = str.slice(0, i) + str.slice(i + 1, str.length) // ab ac bc
      var preResult = fullPermutation(rest) // 递归调用，上一次递归返回的全排列
      // 结合在一起
      for (var j = 0; j < preResult.length; j++) {
        var temp = left + preResult[j]
        result.push(temp)
      }
    }
  } else if (str.length === 1) {
    // 单个字符串的情况
    result.push(str)
  }
  return result
}

3、【二分查找】

二分搜索法，也称折半搜索，是一种在 有序数组 中查找特定元素的搜索算法。

实现步骤：
1. 首先从数组中间开始查找对比，若相等则找到，直接返回中间元素的索引
2. 若查找值小于中间值，则在小于中间值的那一部分执行步骤 1 的操作
3. 若查找值大于中间值，则在大于中间值的那一部分执行步骤 1 的操作
4. 否则，返回结果为查不到，返回-1

解题方式一、非递归方式，采用 while 方式，判断是否符合要求

function binary_search (arr, key) {
    var low = 0, high = arr.length - 1 // 定义最大值，最小值
    while (low <= high) {
        var mid = Math.floor((low + high) / 2) // 得到中间数的索引
        if (key === arr[mid]) { // 刚好等于
            return mid
        } else if (key > arr[mid]) { // 说明在右边
            low = mid - 1
        } else if (key < arr][mid]) { // 说明在左边
            high = mid + 1
        } else {
            return -1
        }
    }
}

解题方式二、递归方式，采用 if 方式，依次递归，找到相应的值

function binary_search(arr, key) {
  return search(arr, key, 0, arr.length - 1)
  /**
   * @param {*} arr 已排好的数组
   * @param {*} key 想要查找的值
   * @param {*} low 第一个值的索引
   * @param {*} high 最后一个值的索引
   * @returns
   */
  function search(arr, key, low, high) {
    if (low > high) {
      return -1
    }
    var mid = Math.floor((low + high) / 2)
    if (key === arr[mid]) {
      // 刚好找到
      return mid
    } else if (key > arr[mid]) {
      // 说明在右边
      return search(arr, key, mid + 1, high)
    } else if (key < arr[mid]) {
      // 说明在左边
      return search(arr, key, low, high - 1)
    }
  }
}

4、【LRU 算法】

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。实现 LRUCache 类：
1. LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
3. void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间

题目要求的 1 和 2 相对简单，主要是条件 3，当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值。容量和条件 1 相呼应，关键是怎么理解最久未使用呢?

读和写都是在使用数据
假设不管是读还是写，我们都把对应的 key 值放到数组的 末尾，那么是不是意味着数组的 头部 就是 最久未使用 的了呢？

解题方式一、数组 & 对象 方式实现

var LRUCache = function(capacity) {
  this.keys = [] // 用数组记录读和写的顺序
  this.cache = {} // 用对象保存 key value 的值
  this.capacity = capacity // 容量
}
LRUCache.prototype.get = function(key) {
  if (this.cache[key]) {
    // 如果存在
    remove(this.keys, key) // 先删除原来的位置
    this.keys.push(key) // 再将其移动到最后一个，保持最新访问
    return this.cache[key] // 返回值
  }
}
LRUCache.prototype.put = function(key, value) {
  if (this.cache[key]) {
    // 如果存在
    this.cache[key] = value // 存在的时候先更新值
    remove(this.keys, key) // 再删除原来的位置
    this.keys.push(key) // 最后再将其移动到最后一个，保持最新访问
  } else {
    // 之前不存在
    this.keys.push(key) // 直接加入
    this.cache[key] = value
    // 容量如果超过最大值，则删除最近最久未使用（也就是数组第一个）
    if (this.keys.length > this.capacity) {
      removeCache(this.cache, this.keys, this.keys[0])
    }
  }
}
// 移除数组中的key
function remove(arr, key) {
  // 当数组存在
  if (arr.length) {
    const index = arr.indexOf(key)
    // 要删除的key存在数组中
    if (index > -1) {
      return arr.splice(index, 1)
    }
  }
}
// 移除缓存中的key
function removeCache(cache, keys, key) {
  cache[key] = null // 删除缓存中的记录
  remove(keys, key) // 删除数组中的记录
}

解题方式二、使用 Map 方式实现

var LRUCache = function(capacity) {
  this.cache = new Map()
  this.capacity = capacity
}
LRUCache.prototype.get = function(key) {
  // 如果存在
  if (this.cache.has(key)) {
    // 获取值
    var value = this.cache.get(key)
    // 更新位置
    this.cache.delete(key) // 删除之前的
    this.cache.set(key, value) // 再重新添加
    return value // 返回值
  }
}
LRUCache.prototype.put = function(key, value) {
  if (this.cache.has(key)) {
    // 如果存在，先删除后插入
    this.cache.delete(key)
  } else {
    // 如果不存在，插入数据先判断，size是否符合capacity, 如果size大于capacity，需要把最开始插入的数据删除
    // keys方法可以得到一个可遍历对象，执行next(), 拿到一个形如{ value: 'xxx', done: false } 的对象
    if (this.cache.size >= this.capacity) {
      this.cache.delete(this.cache.keys().next().value)
    }
  }
  this.cache.set(key, value)
}

var lru = new LRUCache(3)
lru.put(1, '11')
lru.put(2, '22')
lru.put(3, '33')
lru.put(4, '44')
console.log(lru.get(1))

# 1、【两数之和】twoSum 得到两个数的之后等于 target

# 2、 【全排列】

# 3、 【二分查找】

# 4、 【LRU 算法】

1、【两数之和】twoSum 得到两个数的之后等于 target

2、【全排列】

3、【二分查找】

4、【LRU 算法】