他大爷的，刷了就忘！！！

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。 但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 思路：循环数组的时候，用和target减去当前循环的数算出另一个数，找出数组里是否存在这另一个数

var twoSum = function(nums, target) {
    // 第一种用数组方法查找另一个数
    for(let i = 0; i < nums.length; i++) {
        let other = target - nums[i];
        let index = nums.lastIndexOf(other);
        // 注意考虑查找到当前循环数的情况，导致一样
        if(index!=-1 && index != i) {
            return [i,index]
        }
    }
    // 第二种方法用 Map 存储已经循环过的数，在 Map 里查找是否存在另一个数
    // 这种情况不用考虑下标一样的情况，因为是在已经循环过的数里面查找另一个数
    // let map = new Map();
    // for(let i = 0; i < nums.length; i++){
    //     let other = target - nums[i];
    //     if(map.has(other)){
    //         return [map.get(other),i]
    //     }else {
    //         map.set(nums[i],i)
    //     }
    // }
};

2.合并升序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：迭代法：新建一个链表，比较两个链表的头部节点大小，小的加到新链表上。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let list = new ListNode();
    // 记一下新链表的头指针
    let pre = list;
    while(l1!=null && l2!=null){
        if(l1.val <= l2.val){
            list.next = l1;
            l1 = l1.next;
        }else {
            list.next = l2;
            l2 = l2.next;
        }
        list = list.next;
    }
    // 肯定有一个没有循环完
    list.next = (l1 == null) ? l2 : l1;
    return pre.next;
};

3.最大数（中）

题目：给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

• 中等难度

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

输入：nums = [10,2]
输出："210"
输入：nums = [3,30,34,5,9]
输出："9534330"
输入：nums = [1]
输出："1"
输入：nums = [10]
输出："10"

思路：高位数字越大，就越往数组前面排，利用字符串之间相减的规则（字符串相减是一位一位地比较，比如"9">"43"），再用上数组的sort()方法来排序。

//代码
var largestNumber = function(nums) {
  const res = nums.sort((a, b) =>  (b + '' + a) - (a + '' + b)).join(''); // sort 排序后再 join 成字符串

  return res.startsWith('0') ? '0' : res; // 万一数组里面都是0，就返回一个0
};

4.最长子串（中）

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

输入: s = ""
输出: 0

思路：建立一个数组，从这个字符串里面一个一个地取出字符加到数组里面，同时判断数组里面是否有相同的字符，如果有相同的字符就把前一个相同的字符前面的所有字符都截取掉。同时计算数组的长度。

//代码
var lengthOfLongestSubstring = function(s) {
    let arr = [];
    let max = 0;
    // str 用来存储最长子串
    let str = '';
    for(let item of s){
        let index = arr.indexOf(item);
        if(index != -1){
            arr.splice(0,index + 1);
        }
        arr.push(item);
        if(max<arr.length){
            max = arr.length;
            str = arr.join();
        }
    }
    return max;
};

5.LRU

LRU算法的特点：

• 认为最近被访问过的数据将来被访问的概率越大
• 空间满了之后，优先删除长时间未被访问的数据

Map 数据结构的特点：

• 新添加的元素会被插入到map的末尾
• Map.secretKey.keys().next().value 用来找到第一个元素，因为整个栈倒序查看

//  一个Map对象在迭代时会根据对象中元素的插入顺序来进行
// 新添加的元素会被插入到map的末尾，整个栈倒序查看
class LRUCache {
  constructor(capacity) {
    this.secretKey = new Map();
    this.capacity = capacity;
  }
  get(key) {
    if (this.secretKey.has(key)) {
      let tempValue = this.secretKey.get(key);
      this.secretKey.delete(key);
      this.secretKey.set(key, tempValue);
      return tempValue;
    } else return -1;
  }
  put(key, value) {
    // key存在，仅修改值
    if (this.secretKey.has(key)) {
      this.secretKey.delete(key);
      this.secretKey.set(key, value);
    }
    // key不存在，cache未满
    else if (this.secretKey.size < this.capacity) {
      this.secretKey.set(key, value);
    }
    // 添加新key，删除旧key
    else {
      this.secretKey.set(key, value);
      // 删除map的第一个元素，即为最长未使用的
      this.secretKey.delete(this.secretKey.keys().next().value);
    }
  }
}
// let cache = new LRUCache(2);
// cache.put(1, 1);
// cache.put(2, 2);
// console.log("cache.get(1)", cache.get(1))// 返回  1
// cache.put(3, 3);// 该操作会使得密钥 2 作废
// console.log("cache.get(2)", cache.get(2))// 返回 -1 (未找到)
// cache.put(4, 4);// 该操作会使得密钥 1 作废
// console.log("cache.get(1)", cache.get(1))// 返回 -1 (未找到)
// console.log("cache.get(3)", cache.get(3))// 返回  3
// console.log("cache.get(4)", cache.get(4))// 返回  4

6.存在重复元素

题目：给定一个整数数组，判断是否存在重复元素。如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

输入: [1,2,3,1]
输出: true

示例 2:

输入: [1,2,3,4]
输出: false

思路：入门题，用 map 判断就行了

const containsDuplicate = function(nums) {
    let map = new Map();
    for(let i of nums){
        if(map.has(i)){
            return true;
        }else{
            map.set(i, 1);
        }
    }
    return false;
};

7.给你一个“A2B3”这样的字符串，输出“AABBB”

用正则来做是最简单的，可惜不会

function test(str) {
    let i = 0;
    let num = ''; 
    let res = '';
    let word = '';
    for(;i < str.length;i++){
        if('0123456789'.includes(str[i])){
            num = num + str[i];
        }else {
            if(word != ''){
                res = res + ''.padStart(parseInt(num), word);word = str[i];num = '';
            }else {
                word = word + str[i];
            }
        }
    };
    // 最后还有一次转换
    res = res + ''.padStart(parseInt(num), word);console.log(word, num);
    return res;
};

8.青蛙跳台阶

题目描述：一次跳一级或者二级，到 n 级台阶共有几种方法。

思路：规律和斐波那契数列是一样的，都是一个值是它前两个值的和。

// 全局变量，表示递归的深度
let depth = 0; 
function climbStairs(n) {
    // 防止爆栈
    ++depth;
    if (depth > 1000) {
        throw new Error('小心爆栈');
    }

    if (n < 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    return climbStairs(n - 2) + climbStairs(n - 1);
}

/** 
 * 
 * @param {*} n 
 */
function climbStairs(n) {
    if (n < 1) {
        return 0;
    }
    // base case
    if (n === 1) {
        return 1;
    }
    if (n === 2) {
        return 2;
    }

    // 因为状态转移只和上一次迭代和上上次迭代的结果有关，所以只用两个变量存储，不需要用数组，减少了空间
    let pre = 1;
    let cur = 2;

    for (let i = 3; i <= n; i++) {
        let sum = pre + cur;
        pre = cur;
        cur = sum;
    }

    return cur;
}

9.大数相加

传进去两个字符串大整数，计算结果；题目不让用 BigInt 来算

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
    let length = num1.length > num2.length ? num1.length : num2.length;
    // 根据长度补 0
    num1 = num1.padStart(length, '0');
    num2 = num2.padStart(length, '0');
    let res = '';
    let temp = 0;
    for(let i = length - 1; i >= 0; i --) {
        let a = Number(num1[i]);
        let b = Number(num2[i]);
        // 按照数学加法一位一位地加，注意进 1
        res = ((a + b + temp) % 10).toString() + res;
        temp = (a + b + temp) >= 10 ? 1 : 0;
        
    };
    if(temp) {
        res = temp.toString() + res;
    }
    return res;
};

10.字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

// 用一个对象{}来记数，出现过一次就+1，
// 遍历完毕，再次遍历字符串，看它们在之前记录的对象里的值，是否是1，是就返回下标，不是返回-1。
var firstUniqChar = function(s) {
  const map = {};
  for(let v of s) map[v] = (map[v] || 0) + 1;
  for(let i = 0; i < s.length; i++) if(map[s[i]] === 1) return i;
  return -1;
};

11.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

// 声明计数器，一个对象 const obj = {}
// 遍历s字符串，如果遍历到字符串的'a'字母，去看obj[a]是否存在
// 不存在说明第一次遍历到'a'字母，那么初始化obj[a] = 1
// 如果存在则obj[a] += 1
// t字符串同理，它每次减1
// 遍历完s字符串后，遍历obj对象，看它的每一对key：value，是否value都是0

var isAnagram = function(s, t) {

  const sLen = s.length;
  const tLen = t.length;
  if(sLen !== tLen ) {
      return false;
  }
  const obj = {};
  for(let i = 0 ; i < sLen ; i++){
      const currentS = s[i];
      const currentT = t[i];
      obj[currentS] ? obj[currentS]++ : obj[currentS] = 1;
      obj[currentT] ? obj[currentT]-- : obj[currentT] = -1;
  }
  return Object.values(obj).every(v=>v===0);
};

12.只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4


const countMap = {};
数组.forEach((item)=> { countMap[item] ? countMap[item] += 1 : countMap[item] = 1 } )
最后再遍历一次countMap，然后看谁的次数是`1`，就解决了

// 另一种解法
异或运算符(^)，这个运算符的功能

任何数和自己做异或运算，结果为 0，即 a⊕a=0。
任何数和 0 做异或运算，结果还是自己，即 a⊕0=a。
异或运算中，满足交换律和结合律，也就是a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

所以出现两次的字母异或运算得0，跟出现一次的字母异或运算得到自己

var singleNumber = function(nums) {
  let init = nums[0];
  for(let i = 1; i < nums.length; i++){
      init ^=  nums[i];
  }
  return init;
};

13.广度优先算法，深度优先算法

// 实现一个广度优先搜索算法（非递归）
    function bfs(tree, name) {
      let res = [];
      if (tree) {
        let queue = [];
        //利用队列特性先进先出
        queue.unshift(tree);
        while (queue.length !== 0) {
          let item = queue.shift();
          res.push(item);
          if (item.children) {
            for (let i = 0; i < item.children.length; i++) {
                queue.push(item.children[i]);
            }
          }
        }
      }
      console.log('bfs',res);

      return res.find((i) => i.name === name);
    }

// 实现一个深度优先搜索算法（非递归）
    function dfs(tree, name) {
      // 请在这里实现
      let res = [];
      if (tree) {
        let stack = [];
        //利用栈特性先进后出
        stack.push(tree);
        while (stack.length !== 0) {
          let item = stack.pop();
          res.push(item);
          if (item.children) {
            for (let i = item.children.length - 1; i >= 0; i--) {
              stack.push(item.children[i]);
            }
          }
        }
      }
      console.log('dfs',res);

      return res.find((i) => i.name === name);
    }

 // 实现一个深度优先搜索算法（递归）
    function dfs(tree, name) {
      let res = [];
      function deepTraversal(tree) {
        if (tree) {
          res.push(tree);
          if (tree.children) {
            for (let i = 0; i < tree.children.length; i++) {
              deepTraversal(tree.children[i]);
            }
          }
        }
      }
      deepTraversal(tree);
      console.log('dfs',res);
      return res.find((i) => i.name === name);
    }

14.买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

输入： [7,1,5,3,6,4]
输出： 5
解释： 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

输入： prices = [7,6,4,3,1]
输出： 0
解释： 在这种情况下, 没有交易完成, 所以最大利润为 0。

var maxProfit = function(prices) {
    const len = prices.length
    // 初始化最低价格为第一天价格
    let min = prices[0],
    // 初始化最大利润为0
    res = 0;
    // 遍历每天价格
    for(let i = 1;i<len;i++){
        // 当天价格小于最低价格，更新最低价格
        if(min>prices[i]) min = prices[i]
        // 试着更新最大利润
        else res = Math.max(res,prices[i]-min)
    }
    return res;
};

数组转 tree

输入

let arr = [
    {id: 1, name: '部门1', pid: 0},
    {id: 2, name: '部门2', pid: 1},
    {id: 3, name: '部门3', pid: 1},
    {id: 4, name: '部门4', pid: 3},
    {id: 5, name: '部门5', pid: 4},
]

输出

[
    {
        "id": 1,
        "name": "部门1",
        "pid": 0,
        "children": [
            {
                "id": 2,
                "name": "部门2",
                "pid": 1,
                "children": []
            },
            {
                "id": 3,
                "name": "部门3",
                "pid": 1,
                "children": [
                    // 结果 ,,,
                ]
            }
        ]
    }
]

function tree(arr, id = 1) { 
  const o = {}; 
  arr.forEach(item => { 
    const pItem = o[item.pid] || (o[item.pid] = { children: [] }); 
    o[item.id] = { ...item, children: o[item.id] && o[item.id].children || [], }; 
    pItem.children.push(o[item.id]); 
  }) 
  return o[id]; 
}

// 另一种
function arrayToTree(items) {
  const result = [];   // 存放结果集
  const itemMap = {};  // 
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;

    if (!itemMap[id]) {
      itemMap[id] = {
        children: [],
      }
    }

    itemMap[id] = {
      ...item,
      children: itemMap[id]['children']
    }

    const treeItem =  itemMap[id];

    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }

  }
  return result;
}