JS刷力扣 【持续跟新】

1.两数之和【哈希表+数组】

前置知识：

1. 哈希表：根据键（Key）而直接访问在内存存储位置的数据结构
2. map

//常用的几个set()、get()、has()搞明白
//1.set(key,value)
//2.get(key)  返回value
//3.has(key)  只能判断是否包含某个key，不能判断value
const map1 = new Map();
map1.set('bar', 'foo');

console.log(map1.get('bar'));   //foo
console.log(map1.get('foo'));   //undefined
console.log(map1.has('bar'));   //true
console.log(map1.has('foo'));   //false

思路：

1. 创建一个map
2. for循环遍历nums数组
3. 用target减nums[i]
   计算哪个数能跟当前的数字相加得到target
4. 检查map里有没有这个数
   有则返回结果
   没有则把num[i]当做key，i当做value放入map中
   （这里主要是因为使用map.has()进行判断的时候判断的是key是否存在，所以把num[i]当作key放入才能判断有没有这个元素，其次get()返回的是value，这样反着存，得到的就是num[i]的下标）

var twoSum = function(nums, target) {
   
    const map = new Map()
    for(let i = 0; i < nums.length; i++){
   
        let complement = target - nums[i]
        if(map.has(complement)){
   
            return [map.get(complement),i]
        }else{
   
            map.set(nums[i],i)
        }
    }
    return []
};
//[0,1]

2.两数相加【链表+递归】

前置知识：
1. 链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
2. 链表的入口节点称为链表的头结点也就是head。

leetcode里 new Listnode()就是定义一个空节点的链表
定义一个节点值为空的链表let dummy = new ListNode()节点值为空也相当于是定义了一个空链表
定义一个节点值非空的链表xx = new ListNode(val)
a. 取链表的当前值xx.val
b. 取之后的值：当前值之后的那个值赋值给当前的值xx = xx.next

思路：

1. 定义一个变量carry用来存储进位；定义一个sum变量
2. 两链表相加要生成一个新的链表，新的链表的头部创建一个dummy节点用来占位（两个节点相加会生成一个新的节点，新的节点需要一个头部然后剩下的节点就可以一个个串在后面）
3. 让最初的curr节点指向dummy节点；没相加生成一个新的节点curr往前进一位
4. 判断两个链表相加得到的是个位数还是两位数；大于10则对sum取余sum%10得到个位数，然后将sum除10并向下取整Math.floor(sum/10)后的值赋给carry（这一步每次都要进行）
5. 两个链表的下一次相加要再加上carry，然后将carry置为0
6. 这一系列操作完成后还需要最后再检查一次carry，如果值为0则不用操作，如果值不为0要在新链表最后再加一个节点值为1
   有则返回结果
   没有则把num[i]当做key，i当做value放入map中
   （这里主要是因为使用map.has()进行判断的时候判断的是key是否存在，所以把num[i]当作key放入才能判断有没有这个元素，其次get()返回的是value，这样反着存，得到的就是num[i]的下标）

/**
 * 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 addTwoNumbers = function(l1, l2) {
   
    // 生成一个新的链表节点 头部之前指向dummy dummy用来占位
    let dummy = new ListNode()
    // 创建一个用来遍历链表的变量 cur
    let cur = dummy
    // 生成一个用来存放进位的变量
    let carry = 0
    // 判断 输入的两个链表都非空
    while(l1 !== null || l2 !== null){
   
        let sum = 0  // 用来统计两个链表的和
        // 判断两个链表都非空 非空则用sum加上
        if(l1 !== null){
   
            sum += l1.val
            l1 = l1.next
        }
        if(l2 !== null){
   
            sum += l2.val
            l2 = l2.next
        }
        sum += carry
        // 首先除10取余 让cur的下一个节点值为全部相加后的个位数
        // 然后除10并向下取整 carry存放有没有进位
        // 最后让cur指向下一个节点
        cur.next = new ListNode(sum % 10)
        carry = Math.floor(sum/10)
        cur = cur.next
        // console.log(dummy.next)    //[7] [7,0] [7,0,8]
    }
    if(carry > 0){
   
        cur.next = new ListNode(carry)
    }
    return dummy.next
    // console.log(dummy.next)   [7,0,8]
};

3.无重复字符的最长子串【滑动窗口+哈希表】

前置知识

1. Set()构造函数
   Set对象是值的集合，集合中的元素只会出现一次。
   const set = new Set()
   1. set.add(value) 在该集合中插入一个具有指定值的新元素
   2. set.has(value) 返回一个布尔值来知识对应的值是否存在于该集合中
   3. set.size 返回集合中元素的个数（注意size后面是没有括号的）
2. String构造函数和String函数
   1. JS中我们一般通过字面量的方式创建String
      var str = "abc"
      当操作字符串时会转换为字符串对象
      var str = new String('abc')
   2. 字符串是一个类似数组的对象，有length属性，可以通过数值键0,1取值；
      str[i] 与 str.charAt(i)本质上没有区别，str.charAt(i)相对更标准
   3. String()构造函数的方法
      1. charAt(index):返回索引处的字符串
      2. indexOf(index):在字符串中搜索指定子字符串，并返回其第一次出现的位置索引。
      3. split():方法接受一个模式，通过搜索模式将字符串分割成一个有序的子串列表，将这些子串放入一个数组，并返回该数组。
      4. concat(str1,str2,...):将字符串参数连接到调用的字符串，并返回一个新的字符串
      5. toString()<=>valueOf(): 返回该字符串的值
      6. trim(): 从字符串的两端移除空白字符，并返回一个新的字符串，而不会修改原始字符串。
      7. toUpperCase(): 将该字符串转换为大写形式
      8. toLowerCase(): 将该字符串转换为小写形式
      9. length:
      10. substring(indexStart, indexEnd)： 返回该字符串从起始索引到结束索引（不包括）的部分，如果未提供结束索引，则返回到字符串末尾的部分。

const str1 = 'Hello';
const str2 = 'World';
const str3 = 'W,o,r,l,d';
const str4 = 'Worldyoyoyo';
console.log(str1.charAt(1))  //"e"
console.log(str2.charAt(2))  //"r"

console.log(str1.indexOf("l"))  // 2

console.log(str2.split(""))  // ["W", "o", "r", "l", "d"]
console.log(str3.split(",")) // ["W", "o", "r", "l", "d"]

console.log(str2.substring(2,6)) // "rldy"

console.log(str1.concat(' ', str2, " 123")); // "Hello World 123"
console.log(str2.concat(', ', str1)); // "World, Hello"
console.log(str2.length); // 5

const greeting = '   Hello world!   ';
console.log(greeting); // "   Hello world!   "
console.log(greeting.trim()); //  "Hello world!"

解题思路
1. 借助滑动窗口
2. 创建一个Set()，主要用它来存放已经检索过的部分 并且判断是不是有已经出现过
3. 两个指针：第一个指向字符串的开头-j；第二个随着for循环遍历字符串-i
4. 如果set里没有s[i]，表明到目前为止没有重复的字符，把s[i]添加到set里，然后更新最大不重复字符的数量
5. 如果set里有s[i]，则从set里开始删除s[j]，并且递增j，再检查set里是否有s[i]，如此反复直到set里没有s[i]为止
6. 重复步骤4和5，直到遍历完整个字符串

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
   
    let set = new Set()
    let i =0, j = 0, maxlength = 0
    if(s == null){
   
        return
    }
    for(i; i < s.length; i++){
   
        if(!set.has(s[i])){
   
            set.add(s[i])
            maxlength = Math.max(maxlength,set.size)
        }else{
   
            while(set.has(s[i])){
   
                set.delete(s[j])
                j++
            }
            set.add(s[i])
        }
    }
    return maxlength
};

5.最长回文子串【双指针+动态规划】

前置知识

1. 回文：就是一个字符串从前往后读和从后往前读，内容都是一样的

思路

1. 如果字符串长度小于2，直接返回原字符串
2. 定义两个变量，一个start存储当前找到的最大回文字符串的长度（终止位置就是start+maxLength）
3. 创建一个helper function，判断左边和右边是否越界，同时最左边的字符串是否等于最右边的字符串。如果以上3个条件都满足，则判断是否需要更新回文字符串最大长度及最大字符串的起始位置。然后将left–，right++，继续判断，直到不满足三个条件之一
4. 遍历字符串，每个位置调用helper function两遍，第一遍（字符串有中心）检查i-1，i+1；第二遍（字符串没有中心）检查i，i+1
   从一个字符串中找出最长的回文子字符串，采用中心扩散的思想，这种适用于有中心的回文字符串 babad；还有一种没有中心的回文字符串 cabbad。所以对于每个字符串都要检查两遍

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
   
    if(s.length < 2){
   
        return s
    }
    let start = 0
    let maxLength = 1 //这里不等于0是因为单一个字符也是一个回文子字符串
    function expandAroundCenter(left,right){