力扣1-99

1.两数之和（哈希表）

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  // new Map() 遍历数组用声明式
  // map中键是数字,值是index
  // 如果map中有target-x,用get拿到target-x的index,和当前i作为[i,index]return出去
  // 不管怎样本次循环用set设一下当前nums[i],i
  // 循环结束return []
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const x = nums[i];
    if (map.has(target - x)) {
      return [i, map.get(target - x)];
    }
    map.set(x, i);
  }
  return [];
};
// O(n)

2.两数相加(链表)

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

const addTwoNumbers = function (l1, l2) {
  let dummy = new ListNode(0);
  let p = dummy;
  let carry = 0; //该位和，在下一次的进位
  while (l1 || l2) {
    let sum = 0; //该位的和为0，每次循环会刷新

    if (l1) {
      sum += l1.val;
      l1 = l1.next;
    }
    if (l2) {
      sum += l2.val;
      l2 = l2.next;
    }
    sum += carry;
    p.next = new ListNode(sum % 10);
    carry = Math.floor(sum / 10);
    p = p.next;
  }
  // 最后全加完了，发现carry还有，如6+6=12
  // carry必为1
  if (carry === 1) {
    p.next = new ListNode(carry);
  }
  return dummy.next;
};

3.无重复字符的最长子串(滑动窗口)

// 集合l在-1位外循环追逐遍历，第二次删除，内循环往后扩展，l走动，挑战最大值
var lengthOfLongestSubstring = function (s) {
  let l = -1;
  let r = 0;
  let max = 0;
  let set = new Set();
  while (l < r && r < s.length) {
    // 到第二次循环(l!==-1)，重复已经被破坏
    if (l !== -1) {
      set.delete(s[l]);
    }
    //l在任何情况都要自增
    l++;
    // set中有记录过的，破坏
    while (r < s.length && !set.has(s[r])) {
      set.add(s[r++]);
    }
    max = Math.max(max, r - l);
  }
  return max;
};

4.*寻找两个正序数组的中位数(二分)

https://leetcode.cn/problems/median-of-two-sorted-arrays/description/

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

有两个数组A[7,8,9]和B[1,2,3,4,5,6]，两个数组的总长度 len=9 中位数的位置 k=5 比较两个数组第 k/2 项，如果 A[k/2] > B[k/2] 即 B[1],B[2]...B[k/2] 为这两个数组的最小前 k/2 项，则可以直接排除掉，排除掉之后长度和k同步缩小，然后进行下一轮的比较，直到 k=1 的时候，只需要找到两个正序数组第一个元素最小值即可，其中有两个地方需要特殊处理：
1、一个数组为空的情况，直接取另一个数组的第 k 项即可
2、一个数组的长度小于 k/2 的时候，取数组的最后一项

var findMedianSortedArrays = function (nums1, nums2) {
  const len1 = nums1.length;
  const len2 = nums2.length;
  const mid = (len1 + len2 + 1) >> 1;
  const left = getK(nums1, nums2, 0, 0, mid);
  // 判断总长度奇偶
  if ((len1 + len2) % 2) {
    return left;
  } else {
    const right = getK(nums1, nums2, 0, 0, mid + 1);
    return (left + right) / 2;
  }
};

// 取第k小的数
function getK(nums1, nums2, start1, start2, k) {
  const len1 = nums1.length;
  const len2 = nums2.length;
  /* 特例 */
  // nums1 数组的元素排除完
  if (len1 === start1) return nums2[start2 + k - 1];
  if (len2 === start2) return nums1[start1 + k - 1];
  // 排除到只剩两个元素取最小 即剩余元素的最小值
  if (k === 1) return Math.min(nums1[start1], nums2[start2]);

  /* 通常情况 */
  // 取k的一半 同时注意可能会超出数组长度 最多取数组最后一个元素
  const i = start1 + Math.min(len1, k >> 1) - 1;
  const j = start2 + Math.min(len2, k >> 1) - 1;
  // j 前面的所有元素被排除了 同时缩减k的值
  if (nums1[i] > nums2[j]) {
    return getK(nums1, nums2, start1, j + 1, k - (j - start2 + 1));
  } else {
    return getK(nums1, nums2, i + 1, start2, k - (i - start1 + 1));
  }
}

let n = nums1.length + nums2.length;
let nums = nums1.concat(nums2).sort((a, b) => a - b);

let result =
  n % 2 == 0 ? (nums[n / 2] + nums[n / 2 - 1]) / 2 : nums[Math.floor(n / 2)];

return result;

5.最长回文子串(中心开花)

//  特殊s.length<=1 return s
// target = ''
// 设置求回文函数（left,right)
// 循环当left和right不越界且left值等于right值时
// left right向外走动
// 循环结束，挑战最大值，用s.substring(left+1,right).length和target.length
// 比较，更新target为新字符串

// 启动函数，通过一个遍历循环，启动函数（i,i)和（i,i+1)
const longestPalindrome = function (s) {
  if (s.length <= 1) {
    return s;
  }
  let target = "";
  //从哪个字符开始向两边找？
  for (let i = 0; i < s.length; i++) {
    fun(i, i);
    fun(i, i + 1);
  }
  //怎么求回文？
  function fun(left, right) {
    // 这里第一次就会执行，比如ab答案是0
    while (left >= 0 && right <= s.length - 1 && s[left] == s[right]) {
      --left;
      right++;
    }
    //substring:从第一个参数开始，到第二个参数的前一个（包含第一个，不包含第二个）
    // 例： 'asdfg'.substring(1,3)=>'sd'
    if (right - left > target.length) {
      target = s.substring(left + 1, right);
    }
  }
  return target;
};

6.Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

var convert = function (s, numRows) {
  const m = numRows;
  const res = new Array(m).fill().map(() => new Array());
  let current = 0;
  let column = 0;
  while (current < s.length) {
    let i = 0;
    for (; i < m && s[current]; i++) {
      res[i][column] = s[current++];
    }
    i = m - 1;
    while (s[current] && i > 1) {
      res[--i][++column] = s[current++];
    }
    column++;
    //一遍循环读了PAYP
    // 第二遍读了ALIS
  }
  const sres = [];
  // 一行行读取模拟的结果即可
  for (let i = 0; i < res.length; i++) {
    for (let j = 0; j < res[i].length; j++) {
      if (res[i][j]) {
        sres.push(res[i][j]);
      }
    }
  }
  return sres.join("");
};

7.整数反转

var reverse = function (x) {
  let rev = 0;
  while (x !== 0) {
    const digit = x % 10;
    x = ~~(x / 10);
    rev = rev * 10 + digit;
    if (rev < Math.pow(-2, 31) || rev > Math.pow(2, 31) - 1) {
      return 0;
    }
  }
  return rev;
};

8. 字符串转整数

/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function (s) {
  let res = 0,
    // 正负号，默认正号
    negativeSymbol = 1;
  // 把首尾的空格都去掉
  s = s.trim();
  for (let i = 0; i < s.length; i++) {
    // 负数
    if (i == 0 && s[i] == "-") {
      negativeSymbol = -1;
      continue;
      // 正数
    } else if (i == 0 && s[i] == "+") continue;
    // 因为空格会被转成0，所以要排除空格的情况，也就是说在数字范围内就加上
    if (s[i] >= 0 && s[i] <= 9 && s[i] != " ") {
      res = res * 10 + (s[i] - 0);
      // 为什么在这里就判断呢，因为这里如果就溢出的话，就直接跳出，不需要再后面无意义的计算了
      if (res * negativeSymbol <= -2147483648) return -2147483648;
      else if (res * negativeSymbol >= 2147483647) return 2147483647;
    } else break; // 如123fffe
  }
  return res * negativeSymbol;
};

9. 回文数

/**
 * @param {number} x
 * @return {boolean}
 */

//  小于0不是回文数，
// 满足最后一位是0，且是0才是回文数
// 设回文数为0，循环当前数大于回文数。回文数*10+当前数最后位(%10)
// 当前数去掉最后位（Math.floor(x/10))
// 返回x与回文数相等或x与Floor回文数/10相等（x有奇数位）
var isPalindrome = function (x) {
  // // 特殊情况：

  if (x < 0 || (x % 10 === 0 && x !== 0)) return false;
  return (x + "").split("").reverse().join("") === x + "";
  // // 如上所述，当 x < 0 时，x 不是回文数。
  // // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
  // // 则其第一位数字也应该是 0
  // // 只有 0 满足这一属性
  // if (x < 0 || (x % 10 === 0 && x !== 0)) {
  //     return false;
  // }

  let revertedNumber = 0;
  while (x > revertedNumber) {
    revertedNumber = revertedNumber * 10 + (x % 10);
    x = Math.floor(x / 10);
  }

  // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
  // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
  // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
  return x === revertedNumber || x === Math.floor(revertedNumber / 10);
};

10. *正则匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串

const isMatch = (s, p) => {
  if (s == null || p == null) return false;

  const sLen = s.length,
    pLen = p.length;

  const dp = new Array(sLen + 1);
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(pLen + 1).fill(false); // 将项默认为false
  }
  // base case，
  dp[0][0] = true;
  // aaaa和a*必匹配，但是和b*不匹配
  for (let j = 1; j < pLen + 1; j++) {
    if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2];
  }
  // 迭代
  for (let i = 1; i < sLen + 1; i++) {
    for (let j = 1; j < pLen + 1; j++) {
      // a 和 .
      // a 和 a
      if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {
        // 如果上一个匹配则匹配，否则就不匹配
        dp[i][j] = dp[i - 1][j - 1];
      } else if (p[j - 1] == "*") {
        // a 和 a*
        // a 和 .*
        if (s[i - 1] == p[j - 2] || p[j - 2] == ".") {
          //把*看作0试试 （ab->abb*
          //把a*跟a换掉试试
          // (abbbb-> ab*)
          dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
        } else {
          // 把*看作0试试
          dp[i][j] = dp[i][j - 2];
        }
      }
    }
  }
  return dp[sLen][pLen]; // 长sLen的s串 是否匹配 长pLen的p串
};

11.盛最多水的容器

https://leetcode.cn/problems/container-with-most-water/description/

双指针，向中遍历

若向内 移动长板 ，水槽的短板min(h[i],h[j])min(h[i], h[j])min(h[i],h[j])​ 不变或变小，因此下个水槽的面积 一定变小

向内移动长板，面积不变或变大

/**
 * @param {number[]} height
 * @return {number}
 */
Area = function (height) {
  //两根主子间的最大面积
  let max = 0;
  //使用双指针求面积
  for (let i = 0, j = height.length - 1; i < j; ) {
    //求两根柱子之间高度低的哪一个
    let minHeight = height[i] < height[j] ? height[i++] : height[j--];
    //两个柱子之间的宽度
    let leng = j - i + 1;
    //求面积
    let area = leng * minHeight;
    //取最大值
    max = Math.max(max, area);
  }
  return max;
};

12.整数转罗马数字

https://leetcode.cn/problems/integer-to-roman/description/

/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function (num) {
  // 从大到小排列，准备好400 900的特殊情况
  const valueSymbols = [
    [1000, "M"],
    [900, "CM"],
    [500, "D"],
    [400, "CD"],
    [100, "C"],
    [90, "XC"],
    [50, "L"],
    [40, "XL"],
    [10, "X"],
    [9, "IX"],
    [5, "V"],
    [4, "IV"],
    [1, "I"],
  ];
  const res = [];
  for (let [val, roma] of valueSymbols) {
    while (num >= val) {
      num -= val;
      res.push(roma);
    }
  }
  return res.join("");
};

13.罗马数字转整数

https://leetcode.cn/problems/roman-to-integer/description/

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function (s) {
  const symbolValues = new Map();
  // 从小到大排
  symbolValues.set("I", 1);
  symbolValues.set("V", 5);
  symbolValues.set("X", 10);
  symbolValues.set("L", 50);
  symbolValues.set("C", 100);
  symbolValues.set("D", 500);
  symbolValues.set("M", 1000);
  let ans = 0;
  const n = s.length;
  for (let i = 0; i < n; ++i) {
    const value = symbolValues.get(s[i]);
    // 如果遇到IV,则-1+5
    if (i < n - 1 && value < symbolValues.get(s[i + 1])) {
      ans -= value;
    } else {
      ans += value;
    }
  }
  return ans;
};

14.最长公共前缀

/**
 * @param {string[]} strs
 * @return {string}
 */

//  特殊strs.length==0,return ""
// 假设ans为strs[0]
// 从第二个开始遍历strs
// 设j为0
// 当j<ans.length&&j<strs[i].length时
// 如果ans[j]!=strs[i][j] break
// j++
// 跳出循环。ans = ans.substr(0,j)
var longestCommonPrefix = function (strs) {
  if (strs.length == 0) return "";
  let ans = strs[0];
  for (let i = 1; i < strs.length; i++) {
    let j = 0;
    while (j < ans.length) {
      if (ans[j] != strs[i][j]) {
        //第i个单词的第j个字母
        break;
      }
      j++;
    }
    ans = ans.substr(0, j); //ans截取前j个字母
  }
  return ans;
};

15.三数之和(三指针)

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，

同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 特殊nums.len<3
// 将数组升序排列
// 循环遍历
// 1.如果当前值大于0,break
// 2.如果当前位不为0且与上一位值相等,continue去重
// 3.l=i+1三指针第二个,r=len-1三指针第三
// 4.while l<r
// 计算sum
// 41如果sum=0,三值加入res,内部while l<r l值<l+1 l++去重;r同理
// 内循环结束,注意让lr走动
// 42如果sum<0 l++
// 43同理

// 时间复杂度：O(n^2)
// n 为数组长度
var threeSum = function (nums) {
  let ans = [];
  let len = nums.length;
  nums.sort((a, b) => a - b);
  for (let i = 0; i < len - 2; i++) {
    if (nums[i] > 0) break;
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    // 最大情况
    if (nums[i] + nums[len - 2] + nums[len - 1] < 0) continue;
    let l = i + 1;
    let r = len - 1;
    while (l < r) {
      sum = nums[i] + nums[l] + nums[r];
      if (sum === 0) {
        ans.push([nums[i], nums[l], nums[r]]);
        while (l < r && nums[l] === nums[l + 1]) l++;
        while (l < r && nums[r] === nums[r - 1]) r--;
        l++;
        r--;
      }
      if (sum < 0) l++;
      if (sum > 0) r--;
    }
  }
  return ans;
};

16.最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

//  只存在一个解
var threeSumClosest = function (nums, target) {
  let N = nums.length;
  let res = Infinity;
  // 也是升序
  nums.sort((a, b) => a - b);
  for (let i = 0; i < N; i++) {
    let left = i + 1;
    let right = N - 1;
    while (left < right) {
      let sum = nums[i] + nums[left] + nums[right];
      if (sum === target) return sum;
      //每次收缩得到一个相对最接近target的解
      // 类似记录max，反正最后也是输出max
      if (Math.abs(sum - target) < Math.abs(res - target)) {
        res = sum;
      }
      if (sum < target) left++;
      if (sum > target) right--;
    }
  }
  return res;
};

17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  const k = digits.length;
  const map = [
    "",
    "",
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz",
  ];
  if (!k) return [];
  if (k === 1) return map[digits].split("");

  const res = [],
    path = [];
  backtracking(0);
  return res;

  function backtracking(a) {
    if (path.length === k) {
      res.push(path.join(""));
      return;
    }
    for (const v of map[digits[a]]) {
      path.push(v);
      backtracking(a + 1);
      path.pop();
    }
  }
};

18.四数之和

**注意四数之和有 target 而不是像三数之和为 0

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */

// 先升序
//  三层循环，第一层确定第一位~length-4，第二层确定第二位~length-3
// 还是三种剪枝
// 第三层确定left right窗口
var fourSum = function (nums, target) {
  const quadruplets = [];
  if (nums.length < 4) {
    return quadruplets;
  }
  nums.sort((x, y) => x - y);
  const length = nums.length;
  for (let i = 0; i < length - 3; i++) {
    // --- 外层和内层都能剪三次
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
      break;
    }
    if (
      nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] <
      target
    ) {
      continue;
    }
    // ===
    // **   *      *
    // ij固定，left,right动
    for (let j = i + 1; j < length - 2; j++) {
      // ---
      if (j > i + 1 && nums[j] === nums[j - 1]) {
        continue;
      }
      if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
        break;
      }
      if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
        continue;
      }
      //---
      let left = j + 1,
        right = length - 1;
      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum === target) {
          quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);
          while (left < right && nums[left] === nums[left + 1]) {
            left++;
          }
          left++;
          while (left < right && nums[right] === nums[right - 1]) {
            right--;
          }
          right--;
        } else if (sum < target) {
          left++;
        } else {
          right--;
        }
      }
    }
  }
  return quadruplets;
};

19.删除链表的倒数第 N 个结点

var removeNthFromEnd = function (head, n) {
  // ret为虚拟头节点
  // 有虚拟头节点，可以不判断是不是直接删掉第一个节点
  let hair = new ListNode(0, head),
    slow = (fast = hair);
  while (n--) fast = fast.next;
  while (fast.next !== null) {
    fast = fast.next;
    slow = slow.next;
  }
  // 拿到的是被删除的节点的前一个！因此八倒三，要拿5号
  slow.next = slow.next.next;
  return hair.next;
};

20.有效的括号（栈）

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (str) {
  // 对象键名左值右，准备栈，let of遍历，如果是键（左）(map[i]存在)，加入栈，如果不是键是值且
  // 栈顶不是对应键map[stk.pop()]!==i，return false
  // 循环结束,栈空返回true否则false
  let map = {
    "{": "}",
    "(": ")",
    "[": "]",
  };
  let stk = [];
  for (let i of str) {
    // 如果是左括号
    if (map[i]) {
      stk.push(i);
      //如果是右括号，但对不上栈顶
    } else if (map[stk.pop()] !== i) {
      return false;
    }
  }
  return stk.length === 0;
};

21.合并有序链表（递归）

将两个升序链表合并为一个新的 升序 链表并返回。

//  递归函数（l1,l2),如果！l1 returnl2 如果！l2 return l1
// 如果l1值小于l2，l1.next = 递归函数（l1.next,l2) return l1
// else情况对称
var mergeTwoLists = function (l1, l2) {
  if (l1 === null) {
    return l2;
  }
  if (l2 === null) {
    return l1;
  }
  if (l1.val > l2.val) {
    l2.next = mergeTwoLists(l1, l2.next);

    //这种情况，最小的是l2开头，因此返回l2
    return l2;
  } else {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  }
  //通过(l1,l2.next)将问题转为更小的问题
  //return返回符合条件的（偏大的）
  //lx.next赋值能将return的接到链表后面，且lx肯定是前面同一位置较小的一方（因为在if里
};

迭代法(双指针)

const merge = (head1, head2) => {
  let dummy = new ListNode(0);
  let cur = dummy;
  // 新链表，新的值小就先接谁
  while (head1 && head2) {
    if (head1.val < head2.val) {
      cur.next = head1;
      head1 = head1.next;
    } else {
      cur.next = head2;
      head2 = head2.next;
    }
    cur = cur.next;
  }
  // 如果后面还有剩余的就把剩余的接上
  cur.next = head1 == null ? head2 : head1;
  return dummy.next;
};

22.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

var generateParenthesis = function (n) {
  const res = [];
  const track = [];
  function trackCracket(left, right) {
    if (left < 0 || right < 0) return;
    if (left > right) return;
    if (left == 0 && right == 0) {
      res.push(track.join(""));
      return;
    }

    track.push("(");
    trackCracket(left - 1, right);
    track.pop();

    track.push(")");
    trackCracket(left, right - 1);
    track.pop();
  }
  trackCracket(n, n);
  return res;
};

23.合并 K 个升序链表(归并)

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  // 当是空数组的情况下
  if (!lists.length) {
    return null;
  }
  // 合并两个排序链表
  const merge = (head1, head2) => {
    let dummy = new ListNode(0);
    let cur = dummy;
    // 新链表，新的值小就先接谁
    while (head1 && head2) {
      if (head1.val < head2.val) {
        cur.next = head1;
        head1 = head1.next;
      } else {
        cur.next = head2;
        head2 = head2.next;
      }
      cur = cur.next;
    }
    // 如果后面还有剩余的就把剩余的接上
    cur.next = head1 == null ? head2 : head1;
    return dummy.next;
  };
  const mergeLists = (lists, start, end) => {
    // base case  只有一个链接的情况
    if (start + 1 === end) {
      return lists[start];
    }
    // 输入的k个排序链表，可以分成两部分，前k/2个链表和后k/2个链表
    // 如果将这前k/2个链表和后k/2个链表分别合并成两个排序的链表，再将两个排序的链表合并，那么所有链表都合并了
    let mid = start + ((end - start) >> 1);
    let head1 = mergeLists(lists, start, mid);
    let head2 = mergeLists(lists, mid, end);
    return merge(head1, head2);
  };
  // 前闭后开
  return mergeLists(lists, 0, lists.length);
};

24.两两交换链表中的节点

1,2,3,4->2,1,4,3

var swapPairs = function (head) {
  if (head === null || head.next === null) {
    return head;
  }
  const newHead = head.next;
  head.next = swapPairs(newHead.next);
  newHead.next = head;
  return newHead;
};

25.K 个一组翻转链表

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */

// 先实现反转函数（head,tail),return [tail,head]
// prev初始值为4，curr初始值为1
// [1,2,3] 4, 1连上4，prev变为1，curr变为[2,3]

// 主函数（head,k)
// 在head节点的前面加一个hair节点0
// [0,1,2,3,4]
// pre初始值是0,当head存在时，
// 设tail为pre,遍历k次，tail一直next，找到这一group的尾部
// 如果越界了，return hair.next,即哑节点后面的一个，直接结束
// 跳出循环，先用next记录tail.next,
// [head,tail] = myReverse(head,tail)，反转这一group
// 把这一group接到pre的后面,把新tail（let出来的可为新）的后面接上
// next,更新pre为新tail，head为tail.next
// 最终返回hair.next,即哑节点后面的一个

const myReverse = (head, tail) => {
  let prev = null;
  let curr = head;
  // 由于本题tail的下一个不是null，所以终止条件是 prev 已经到头了
  while (prev !== tail) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return [tail, head];
};
const reverseKGroup = function (head, k) {
  const hair = new ListNode(0);
  hair.next = head;
  let originPre = hair;

  while (head) {
    let oneGroupTail = pre;
    // 查看剩余部分长度是否大于等于 k,如果小于，直接return hair.next
    for (let i = 0; i < k; ++i) {
      oneGroupTail = oneGroupTail.next;
      if (!oneGroupTail) {
        // 已经是最后一个group,把最终链表返回出去
        return hair.next;
      }
    }
    //
    const orginNext = oneGroupTail.next;
    [head, oneGroupTail] = myReverse(head, oneGroupTail);
    // 把子链表重新接回原链表
    originPre.next = head;
    oneGroupTail.next = originNext;
    originPre = oneGroupTail;
    head = oneGroupTail.next;
  }
  return hair.next;
};

26.有序数组去重

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。 并返回 nums 中唯一元素的个数

/**
 * @param {number[]} nums
 * @return {number}
 */

//  双指针都从1开始，fast负责扩展，一旦出现不连续，就将当前的fast赋给slow位(去重），slow才进
// 只需要一遍遍历
// 最后要求返回个数,就是slow的值,当然slice()
var removeDuplicates = function (nums) {
  const n = nums.length;
  if (n === 0) {
    return 0;
  }
  let fast = 1,
    slow = 1;
  while (fast < n) {
    if (nums[fast] !== nums[fast - 1]) {
      nums[slow] = nums[fast];
      ++slow;
    }
    ++fast;
  }
  return slow;
};

28.找出字符串中第一个匹配项的下标*

const strStr = (haystack, needle) => {
  // 注意空串和无法匹配的结果不一样
  if (needle === "") return 0;
  const haystackLen = haystack.length;
  const needleLen = needle.length;
  for (let i = 0; i < haystackLen; i++) {
    if (haystack.substring(i, i + needleLen) === needle) return i;
  }
  return -1;
};

29.两数相除 *

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的 商 。

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [-2147483648, 2147483648 − 1] 。本题中，如果商 严格大于 2**31 − 1 ，则返回 2**31 − 1 ；如果商 严格小于 -2**31 ，则返回 -2**31 。

var divide = function (dividend, divisor) {
  if (divisor === 0) return Infinity;
  if (dividend === 0) return 0;
  if (dividend === -2147483648 && divisor === -1) return 2147483647;

  let res = 0;
  let flag = "";
  if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
    flag = "-";
  }
  dividend = Math.abs(dividend);
  divisor = Math.abs(divisor);

  while (dividend >= divisor) {
    let temp = divisor,
      m = 1;
    while (temp <= dividend >> 1) {
      // 位运算模拟乘法，撑到最大。防止溢出
      temp <<= 1;
      m <<= 1;
    }
    dividend -= temp;
    res += m;
  }

  return parseInt(flag + res);
};

31.下一个排列（倒遍历 17831，n-2,n-1）

而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

必须 原地 修改，只允许使用额外常数空间。

function nextPermutation(nums) {
  let i = nums.length - 2; // 向左遍历，i从倒数第二开始是为了nums[i+1]要存在
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    // 从右往左，寻找第一个小于右邻居的数
    i--;
  }
  if (i >= 0) {
    // 这个数在数组中存在，从它身后挑一个数，和它换
    let j = nums.length - 1; // 从最后一项，向左遍历
    while (j >= 0 && nums[j] <= nums[i]) {
      // 寻找第一个大于 nums[i] 的数
      // 17831    18731
      j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]]; // 两数交换，实现变大
  } else {
    // 如果 i = -1，说明是递减排列，如 3 2 1，没有下一排列，直接翻转为最小排列：1 2 3
    // 注意从i+1开始
    let l = i + 1;
    let r = nums.length - 1;
    while (l < r) {
      [nums[l], nums[r]] = [nums[r], nums[l]];
      l++;
      r--;
    }
  }
}

32.最长有效括号（栈，初始-1）

/**
 * @param {string} s
 * @return {number}
 */

const longestValidParentheses = (str) => {
  // 初始有-1
  let stk = [-1];
  let max = 0;
  for (let i in str) {
    // 若为右，则弹出栈顶，如果还有栈顶则计算max
    // 没有栈顶则把右压入作为新栈顶
    if (str[i] === "(") {
      stk.push(i);
    } else if (str[i] === ")") {
      stk.pop();
      if (stk[stk.length - 1]) {
        max = Math.max(max, i - stk[stk.length - 1]);
      } else {
        stk.push(i);
      }
      // 若为左直接压入
    }
  }
  return max;
};

33.搜索旋转排序数组(改造二分)

 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const search = function(nums, target) {
    let start = 0,end = nums.length - 1
    let mid
    while(start <= end){
        mid = Math.floor((end-start)/2) + start
        if(nums[mid] === target){
            return mid
        }
        console.log(nums[mid])
        // 由start<=mid得出
        // s到mid包括部分左升序（严格）,注意是小于等于，只有一个数的情况下，应该在这一个数以左比较，右为空
        if(nums[start]<=nums[mid]){
          //因为是部分左升序，满足这个可以缩小范围，但是不一定收敛成普通二分
            if(target>=nums[start]&&target<nums[mid]){
                end = mid - 1
            }else{
              //不满足，太好了，可以直接收敛成普通二分
                start = mid + 1
            }
        // s到mid为完整左升序加部分右升序，那就去看右部分，因为是完整右升序（严格），容易判断
        }else{
          // 总会有某次循环收敛成正常二分
            if(target>nums[mid]&&target<=nums[end]){
                start = mid + 1
            }else{
                end = mid - 1
            }
        }
    }
    return -1
};

34.在排序数组中查找元素的第一个和最后一个位置（二分）

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

var searchRange = function (nums, target) {
  // 特殊情况
  if (nums.length === 0) return [-1, -1];
  // 左二分尽量往左,(数组，目标)
  // 右二分尽量往右

  // 但是注意右二分可能到左边区间中,一开始是在整个数组找，和左右无关
  // 只是两种限制条件类型的二分，在target找到情况下一个进行r = m - 1
  // 一个进行l = m + 1
  return [leftSearch(nums, target), rightSearch(nums, target)];
};

function leftSearch(nums, target) {
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    let m = Math.floor((l + r) / 2);
    if (nums[m] > target) {
      r = m - 1;
    } else if (nums[m] < target) {
      l = m + 1;
    } else {
      // 如果等于，尽量往左继续找
      // 就算左边没有，下一次l=m+1也会退出循环并找回来
      r = m - 1;
    }
  }
  // l 只会右溢出（在左侧找不到），或者找到第0位，却不是target
  if (l >= nums.length || nums[l] !== target) {
    return -1;
  }
  //等于
  return l;
}

function rightSearch(nums, target) {
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    let m = Math.floor((l + r) / 2);
    if (nums[m] > target) {
      r = m - 1;
    } else if (nums[m] < target) {
      l = m + 1;
    } else {
      l = m + 1;
    }
  }
  // r只会左溢出，或者找到末位但不等于目标
  if (r < 0 || nums[r] !== target) {
    return -1;
  }
  return r;
}

35.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
//  二分,如果<=设置ans为mid
var searchInsert = function (nums, target) {
  const n = nums.length;
  let left = 0,
    right = n - 1,
    ans = n;
  while (left <= right) {
    let mid = ((right - left) >> 1) + left;
    if (target <= nums[mid]) {
      ans = mid;
      // 尽量往左找，能记到target的前一个
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return ans;
};

38.外观数列

var countAndSay = function (n) {
  let str = "1";
  // 第一项为1个1，第二项则为11，第三项则为2个1（21）
  for (let i = 2; i <= n; ++i) {
    const sb = [];
    // 每一项都双指针跑一次
    let start = 0;
    let pos = 0;

    while (pos < str.length) {
      // 内扩展  1211
      while (pos < str.length && str[pos] === str[start]) {
        pos++;
      }
      sb.push("" + (pos - start) + str[start]);
      start = pos;
    }
    str = sb.join("");
  }

  return str;
};

39.组合总和(可以无限选，如果选了小于 0 就不选了，记得有跳过情况)

输入: (candidates = [2, 3, 5]), (target = 8);
输出: [
  [2, 2, 2, 2],
  [2, 3, 3],
  [3, 5],
];

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const ans = [];
    // idx当前遍历到数组哪一位
    const dfs = (target, combine, idx) => {
        if (idx > candidates.length -  1) {
            return;
        }
        if (target === 0) {
            ans.push(combine);
            return;
        }
        // 直接跳过
        dfs(target, combine, idx + 1);
        // 选择当前数,可以反复选择多次，但是一旦target-x>=0就不选了
        if (target - candidates[idx] >= 0) {
            dfs(target - candidates[idx], [...combine, candidates[idx]], idx);
        }
    }

    dfs(target, [], 0);
    return ans;
};

40.组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
const combinationSum2 = (candidates, target) => {
  candidates.sort((a, b) => a - b); // 升序排序,因为排序了可以一路顺着到底
  const res = [];
  const temp = [];
  const dfs = (start, sum) => {
    // start是索引 当前选择范围的第一个
    if (sum > target) {
      // 爆掉了，不用继续选了
      return; // 结束当前递归
    }
    if (sum == target) {
      // 满足条件，加入解集
      res.push([...temp]); // temp是引用，所指向的内存后续还要操作，所以拷贝一份
    }
    for (let i = start; i < candidates.length; i++) {
      // 枚举出当前的选择
      if (i - 1 >= start && candidates[i - 1] == candidates[i]) {
        // 当前选项和左邻选项一样，跳过
        continue;
      }
      temp.push(candidates[i]); // 作出选择
      dfs(i + 1, sum + candidates[i]); // 基于该选择，继续选择，递归
      temp.pop(); // 上面的递归结束，撤销选择，回到选择前的状态，切入另一分支
    }
  };

  dfs(0, 0);
  return res;
};

41.缺失的第一个正数(-1,-1,-1,-1)(1,2,3,4)

/**
 * @param {number[]} nums
 * @return {number}
 */
// 第一次遍历将nums中负数位替换成len+1
var firstMissingPositive = function (nums) {
  const n = nums.length;
  // [3,4,-1,1]
  for (let i = 0; i < n; i++) {
    if (nums[i] <= 0) {
      nums[i] = n + 1;
    }
  }
  console.log(nums);

  // [3,4,5,1]
  // 第二次遍历，将nums中值<=len的位对应的数取反
  // 大于 len不管了
  for (let i = 0; i < n; i++) {
    let num = Math.abs(nums[i]);
    if (num <= n) {
      nums[num - 1] = -Math.abs(nums[num - 1]);
    }
  }
  // [-3,4,-5,-1]
  for (let i = 0; i < n; i++) {
    // 常数级别空间，所以只能数组原地记录

    // 负数位好歹也是有一个大于len的，正好就是缺失的整数
    // 抽屉思想
    if (nums[i] > 0) {
      return i + 1;
    }
  }
  // -1,-1,-1,-1
  // 5,5,5,5
  // 1

  // 1,2,3,4
  // -1,-2,-3,-4
  //5
  return n + 1;
};

42.接雨水(双指针)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

/**
 * @param {number[]} height
 * @return {number}
 */
const trap = function (height) {
  let ans = 0;
  let left = 0,
    right = height.length - 1;
  let leftMax = 0,
    rightMax = 0;
  while (left <= right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);
    //*
    //*234*
    // 每次到这里一次，都能保证是从较低的一边来的
    // 4-》3-》2
    if (height[left] < height[right]) {
      ans += leftMax - height[left];
      ++left;
    } else {
      ans += rightMax - height[right];
      --right;
    }
  }
  return ans;
};

43.字符串相乘

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function (num1, num2) {
  if (num1 === "0" || num2 === "0") return "0";
  let len1 = num1.length,
    len2 = num2.length,
    res = new Array(len1 + len2).fill(0);
  //用11*11举例
  // 结果最多为 m + n 位数
  for (let i = len1 - 1; i >= 0; i--) {
    for (let j = len2 - 1; j >= 0; j--) {
      // 从个位数开始，逐步相乘
      const mul = num1[i] * num2[j];
      // 乘积在结果数组中对应的位置
      const p1 = i + j,
        p2 = i + j + 1;
      // 对结果进行累加，加上结果的第p2位（为上一次进过位的地方
      const sum = mul + res[p2];
      // 结果的第p1位，加上进位的数字
      res[p1] += Math.floor(sum / 10);
      // 结果的第p2位，如果相加后大于10，则变成个位（已经进过位了
      res[p2] = sum % 10;
    }
  }
  if (res[0] === 0) res.shift();
  return res.join("");
};

45.跳跃游戏 II

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

首先不管怎样都能跳到终点

其次刚开始必须走，每一步都计算从这能走的最大步数 直到把开始每次机会都用完

必须要走了，那就按之前最大步数走，count++

同时获得了新拓展的机会，继续每一步都计算能走的最大步数

var jump = function (nums) {
  let end = 0,
    longest = 0,
    count = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    // 注意此处设定为i<length-1
    // 根据题目要求，假定每一个组合都能够跳到最终位置，因此最后一个位置不需要计算在内
    longest = Math.max(longest, nums[i] + i);
    if (end === i) {
      count++;
      end = longest;
    }
  }
  return count;
};

46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  // 递归函数(left,right),如果左长度等于nums长度,进res,return剪枝
  // forEach遍历右,...浅拷贝然后过滤掉i,递归函数(左加i,右)
  // 空右启动
  let len = nums.length;
  let res = [];
  const order = (l, r) => {
    if (l.length === len) {
      res.push(l);
      return;
    }
    r.forEach((i) => {
      // 返回true保留，返回false过滤掉
      let tem = [...r].filter((j) => j !== i);
      order([...l, i], tem);
    });
  };
  order([], nums);
  return res;
};

47.全排列 II *

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  const ans = [];
  const arr = [];
  const vis = new Array(nums.length).fill(false);
  // **************聚拢数字相同的
  nums.sort((x, y) => x - y);

  const backtrack = (idx) => {
    if (idx === nums.length) {
      ans.push([...arr]);
      return;
    }
    // 为什么不必再放？
    // 因为如果上次1没被用过，这次用1相当于重复刷新，类似闭包
    // 如果上次1被用过了，才能真正起到减少1的次数，这样一共
    // 有3个1，也只会用3次

    // 如果在第2个1开始递归，那会重复执行2个1开始的递归

    //向idx位塞入nums每一位，继续递归
    for (let i = 0; i < nums.length; ++i) {
      // 剪枝，idx位塞1已经在第一次塞1递归完了，第二次用到1不用递归啦（！vis[i - 1])，否则重复了很多操作
      if (vis[i] || (i > 0 && nums[i] === nums[i - 1] && !vis[i - 1])) {
        continue;
      }
      arr.push(nums[i]);
      vis[i] = true;
      backtrack(idx + 1);
      vis[i] = false;
      arr.pop();
    }
  };
  backtrack(0);
  return ans;
};

48.旋转图像

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
//12
//34
//56

//135
//246

//531
//642
// 设一个swap函数（矩阵，[x1.y1],[x2,y2])
// 遍历矩阵，交换ij和ji
// 对矩阵中每一行逆序 matrix[i].reverse()
let rotate = function (matrix) {
  function swap(matrix, [x1, y1], [x2, y2]) {
    const tem = matrix[x1][y1];
    matrix[x1][y1] = matrix[x2][y2];
    matrix[x2][y2] = tem;
  }
  const n = matrix.length;
  // 对角线反转
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      swap(matrix, [i, j], [j, i]);
    }
  }
  // 挨个逆序
  for (let i = 0; i < n; i++) {
    matrix[i].reverse();
  }
};

50.Pow(x,n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数

dp

var myPow = function (x, n) {
  if (n == 0) return 1;
  if (n < 0) return 1 / myPow(x, -n);
  //   如果是奇数,手动算一次,即乘x
  if (n % 2) return x * myPow(x, n - 1);
  //   如果不是,继续快速幂
  return myPow(x * x, n / 2);
};

53.最大子数组和（连续子数组的最大和，最大连续和）（dp）

这种连续子数组，之前的状态不符合条件，都应该直接清空成新的 通过挑战最大值记录结果

/**
 * @param {number[]} nums
 * @return {number}
 */
// dp空数组max-10000,遍历数组,dp[i]设为dp[i-1]+nums[i]和num[i]较大一方
// 用dp[i]挑战最大值
// 注意判断dp[i-1]是否存在
function maxSubArray(nums) {
  let dp = [];
  let max = -10000;
  for (let i = 0; i < nums.length; i++) {
    dp[i] = Math.max(nums[i] + (dp[i - 1] ? dp[i - 1] : 0), nums[i]);
    max = Math.max(dp[i], max);
  }
  return max;
}

54.螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
const spiralOrder = function (matrix) {
  if (!matrix.length || !matrix[0].length) {
    return [];
  }

  const rows = matrix.length,
    columns = matrix[0].length;
  const order = [];
  let left = 0,
    right = columns - 1,
    top = 0,
    bottom = rows - 1;
  while (left <= right && top <= bottom) {
    for (let j = left; j <= right; j++) {
      order.push(matrix[top][j]);
    }
    for (let i = top + 1; i <= bottom; i++) {
      order.push(matrix[i][right]);
    }
    //如果只有一行是不能走回头路的，所以要同时满足且情况
    if (left < right && top < bottom) {
      for (let j = right - 1; j > left; j--) {
        order.push(matrix[bottom][j]);
      }
      for (let i = bottom; i > top; i--) {
        order.push(matrix[i][left]);
      }
    }

    // 关键是这里一致的拆分了一个更小的问题
    [left, right, top, bottom] = [left + 1, right - 1, top + 1, bottom - 1];
  }
  return order;
};

55.跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

//  设当前位能往右跳到的最远位置初始为0
// 遍历数组，如果当前位小于最远位置，挑战最远位置i+nums[i]
var canJump = function (nums) {
  let len = nums.length;
  let end = 0;
  for (let i = 0; i < len; i++) {
    if (i <= end) {
      end = Math.max(end, i + nums[i]);
      let jump = i + nums[i];
      if (jump >= len - 1) return true;
    }
  }
  //[0,0,0,1]
  return false;
};

56.合并区间(排序+标记 0+cur 指针)

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */

//  特殊，intervals.length===1 return intervals
// 按照第一个数字大小排序return a[0] - b[0]
// intervals.push(0)标记
// cur = intervals[0]
// 外遍历intervals
// 内循环如果intervals[i]!==0不为标记，且cur[1]>=intervals[i][0]{cur = [cur[0],cur[1]>int[i][1]则为cur[1]否则替换为int[i][1]]，i++
// 这个i++会影响外层循环的i!
// 跳出内循环说明合并完成，res.push(curr) curr= int[i]
var merge = function (ins) {
  if (ins.length === 1) return ins;
  ins.sort(function (arr1, arr2) {
    return arr1[0] - arr2[0];
  });
  const res = [];
  let cur = ins[0];
  ins.push(0); // 退出标志位，因为外循环后面还要做
  for (let i = 0; i < ins.length; i++) {
    // 注意大于等于
    while (ins[i] !== 0 && cur[1] >= ins[i][0]) {
      const temp = [cur[0], cur[1] > ins[i][1] ? cur[1] : ins[i][1]];
      cur = temp;
      i++;
    }
    res.push(cur);
    cur = ins[i];
  }
  return res;
};

61.旋转链表

var rotateRight = function (head, k) {
  if (k === 0 || !head || !head.next) {
    return head;
  }
  let n = 1;
  let cur = head;
  while (cur.next) {
    cur = cur.next;
    n++;
  }
  cur.next = head;
  // 5 - 2%5 = 3
  let add = n - (k % n);
  let newcur = head;
  while (add !== 1) {
    newcur = newcur.next;
    add--;
  }
  //先保留要返回的指针
  const ret = newcur.next;
  newcur.next = null;

  return ret;
};

62.不同路径（dp，上和左的和）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */

//  生成m*n的0填满数组，new Array(m).fill(0).map(()=>new Array(n).fill(0))
// 遍历第一行0~m-1和第一列的0~n-1，设为1
// 双循环遍历,f[i][j] = f[i-1][j] + f[i][j-1]
// 返回f[m-1][n-1]

// 111111
// 123456
// 136000
var uniquePaths = function (m, n) {
  const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
  for (let i = 0; i < m; i++) {
    f[i][0] = 1;
  }
  for (let j = 0; j < n; j++) {
    f[0][j] = 1;
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      f[i][j] = f[i - 1][j] + f[i][j - 1];
    }
  }
  return f[m - 1][n - 1];
};

63.不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */

//  初始点为障碍，和初始化时如果遇到障碍，就停止继续初始化
const uniquePathsWithObstacles = (obstacleGrid) => {
  if (obstacleGrid[0][0] == 1) return 0; // 出发点就被障碍堵住
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
  // dp数组初始化
  const dp = new Array(m).fill().map(() => new Array(n).fill(0));
  // base case
  dp[0][0] = 1; // 终点就是出发点
  for (let i = 1; i < m; i++) {
    // 第一列其余的case
    if (obstacleGrid[i][0] == 1) break;
    dp[i][0] = 1;
  }
  for (let i = 1; i < n; i++) {
    // 第一行其余的case
    if (obstacleGrid[0][i] == 1) break;
    dp[0][i] = 1;
  }
  // 迭代
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      // 落脚点为1，则到这里的方法为0
      dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1]; // 到达(m-1,n-1)的路径数
};

64.最小路径和（dp,min 上和左）

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

/**
 * @param {number[][]} grid
 * @return {number}
 */

//  dp矩阵直接用原地grid就行,因为不回头,
// dp矩阵第一行依次求和
// 第一列一次求和
// 然后双循环从1,1开始遍历,grid[i][j]+=上面的和左边的最小
var minPathSum = function (grid) {
  let row = grid.length,
    col = grid[0].length;

  for (let i = 1; i < row; i++) {
    grid[i][0] += grid[i - 1][0];
  }

  for (let j = 1; j < col; j++) {
    grid[0][j] += grid[0][j - 1];
  }

  for (let i = 1; i < row; i++) {
    for (let j = 1; j < col; j++) {
      grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
    }
  }

  return grid[row - 1][col - 1];
};

67.二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
  let add = 0;
  let sum = [];

  for (let i = a.length - 1, j = b.length - 1; i >= 0 || j >= 0; i--, j--) {
    // 位数不够，默认为 0, 但是全都是0就算完了
    let num1 = +a[i] || 0;
    let num2 = +b[j] || 0;

    // 两数相同异或为0，0与任意数字异或为数字本身
    sum.unshift(num1 ^ num2 ^ add);
    add = num1 + num2 + add > 1 ? 1 : 0;
  }

  if (add === 1) sum.unshift(1);

  return sum.join("");
};

69.x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  if (x < 2) return x;
  let left = 1;
  // >=2
  let right = Math.floor(x / 2);
  while (left <= right) {
    let mid = Math.floor(left + (right - left) / 2);
    if (mid * mid === x) return mid;
    if (mid * mid < x) left = mid + 1;
    else right = mid - 1;
  }
  //** 返回right能保证结果是向下取整的，left则是向上
  return right;
};

70.爬楼梯

/**
 * @param {number} n
 * @return {number}
 */

//  dp[0]和dp[1]都是1
// 从2开始，累加，最后return dp[n]
var climbStairs = function (n) {
  let p = 0;
  let q = 0;
  let m = 1;

  for (let i = 1; i <= n; i++) {
    p = q;
    q = m;
    m = p + q;
  }
  return m;
};

71.简化路径（栈）

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function (path) {
  const names = path.split("/");
  const stack = [];
  for (const name of names) {
    if (name === "..") {
      if (stack.length) {
        stack.pop();
      }
    } else if (name.length && name !== ".") {
      stack.push(name);
    }
  }

  return "/" + stack.join("/");
};

72.编辑距离（dp）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符 删除一个字符 替换一个字符

dp 求最小值的核心在于 Math.min（不同的策略）

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */

//  抛弃第0行和第0列，一律从1开始到word.length
//     word1
//   w000000
//
//

const minDistance = (word1, word2) => {
  let dp = Array.from(Array(word1.length + 1), () =>
    Array(word2.length + 1).fill(0)
  );

  //初始化数组，word1前i个字符最少需要i次操作，比如i次删除变成word2（长度为0
  for (let i = 1; i <= word1.length; i++) {
    dp[i][0] = i;
  }

  //初始化数组，word1最少需要j次操作，比如j次插入变成word2（从0变成长度为j
  for (let j = 1; j <= word2.length; j++) {
    dp[0][j] = j;
  }

  for (let i = 1; i <= word1.length; i++) {
    //循环word1和word2
    for (let j = 1; j <= word2.length; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        //如果word1[i-1] === word2[j-1],说明不用操作。
        // 任何已经存在的字符，即便位置不同，都可以通过以后的操作，对应到正确位置上
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        //dp[i-1][j] + 1：对应删除
        //dp[i][j-1] + 1：对应新增
        //dp[i-1][j-1] + 1：对应替换操作
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1,
          dp[i][j - 1] + 1,
          dp[i - 1][j - 1] + 1
        );
      }
    }
  }

  return dp[word1.length][word2.length];
};

76.最小覆盖子串（滑动窗口）

预处理一个 map needType 计数，只要不为 0，窗口就不满足要求

双重循环 类似 003

var minWindow = function (s, t) {
  let l = 0;
  let r = 0;
  const need = new Map();
  for (let c of t) {
    need.set(c, need.has(c) ? need.get(c) + 1 : 1);
  }

  let needType = need.size;
  let res = "";
  while (r < s.length) {
    let c = s[r];
    if (need.has(c)) {
      need.set(c, need.get(c) - 1);
      if (need.get(c) === 0) needType -= 1;
    }

    while (needType === 0) {
      const newRes = s.substring(l, r + 1);
      // ！res，第一次要算上
      if (!res || newRes.length < res.length) res = newRes;

      const c2 = s[l];
      if (need.has(c2)) {
        need.set(c2, need.get(c2) + 1);
        if (need.get(c2) === 1) needType += 1;
      }
      l += 1;
    }
    r += 1;
  }
  return res;
};

77.组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
  const res = [];
  // 1,2,3,4
  const helper = (x, y, temp) => {
    if (y === k) {
      res.push(temp);
      return;
    }
    for (let i = x; i <= n; i++) {
      helper(i + 1, y + 1, [...temp, i]);
    }
  };
  // k为
  helper(1, 0, []);
  return res;
};

78.子集

// temp,res,
// 递归函数(当前遍历到哪一位)
// 如果长度够，push temp的拷贝
// push当前位,当前位加1,递归
// 弹出当前位,

var subsets = function (nums) {
  const t = [];
  const ans = [];
  const dfs = (cur) => {
    if (cur === nums.length) {
      ans.push(t.slice());
      return;
    }
    t.push(nums[cur]);
    dfs(cur + 1);
    t.pop();
    dfs(cur + 1);
  };
  dfs(0);
  return ans;
};

// var subsets = function(nums) {
//     const ans = [];
//     const n = nums.length;
//     for (let mask = 0; mask < (1 << n); ++mask) {
//         const t = [];
//         for (let i = 0; i < n; ++i) {
// mask的二进制右数第i位是否为1
//             if (mask & (1 << i)) {
//                 t.push(nums[i]);
//             }
//         }
//         ans.push(t);
//     }
//     return ans;
// };

79.单词搜索(dfs)

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

function exist(board, word) {
  if (word.length === 0) return true;
  if (board.length === 0) return false;
  let rowRange = board.length;
  let colRange = board[0].length;
  const backtrack = (i, j, curInx) => {
    // 剪枝：索引越界
    if (i < 0 || j < 0 || i >= rowRange || j >= colRange) return false;
    // 剪枝：当前元素 !== 指定字符
    if (board[i][j] !== word[curInx]) return false;

    // 结果：全部匹配，返回 true
    if (curInx === word.length - 1) return true;

    board[i][j] = null; // 当前字母匹配后，将当前位置置空，避免之后被重复往回找
    // 向上下左右寻找下一个字母
    const res =
      backtrack(i + 1, j, curInx + 1) ||
      backtrack(i - 1, j, curInx + 1) ||
      backtrack(i, j + 1, curInx + 1) ||
      backtrack(i, j - 1, curInx + 1);
    // 回撤, 类似于Pop
    board[i][j] = word[curInx];

    return res;
  };

  for (let i = 0; i < rowRange; i++) {
    for (let j = 0; j < colRange; j++) {
      if (backtrack(i, j, 0)) return true;
    }
  }

  return false;
}

82.删除排序链表中的重复元素 II

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

var deleteDuplicates = function (head) {
  // 2个数字相同则去除2个数字，1个也不保留
  // 0,1,1,1,2,3
  if (!head) return head;
  let dummy = new ListNode(0, head);
  let cur = dummy;
  while (cur.next && cur.next.next) {
    if (cur.next.val == cur.next.next.val) {
      let x = cur.next.next;
      while (x.next && cur.next.val == x.next.val) {
        x = x.next;
      }
      cur.next = x.next;
    } else {
      cur = cur.next;
    }
  }
  return dummy.next;
};

83.删除排序链表中的重复元素

输入：head = [1,1,2] 输出：[1,2]

var deleteDuplicates = function (head) {
  if (!head) {
    return head;
  }

  let cur = head;
  while (cur.next) {
    if (cur.val === cur.next.val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  }
  return head;
};

88.合并两个有序数组（三指针）

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

// nums1上原地修改，三指针m尾n尾总尾,外循环n尾还有，如果m读完(<0)则n全拷continue,否则比较行事，跳出循环m已经在正确位置直接退出

// 原理是提前弄了m+n-1逆向不可能会修改不该修改的
// 而且某一方遍历完了，剩下的一定是给另一方的
const merge = function (nums1, m, nums2, n) {
  let tailm = m - 1;
  let tailn = n - 1;
  let tail = m + n - 1;
  while (tailn >= 0) {
    if (tailm < 0) {
      nums1[tail--] = nums2[tailn--];
      continue;
    }
    nums1[tail--] =
      nums1[tailm] > nums2[tailn] ? nums1[tailm--] : nums2[tailn--];
  }
};

92.反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表

const reverseLinkedList = (head) => {
  let pre = null;
  let cur = head;

  while (cur) {
    const next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
};
var reverseBetween = function (head, left, right) {
  const dummyNode = new ListNode(-1);
  dummyNode.next = head; //虚拟头节点

  let pre = dummyNode;
  for (let i = 0; i < left - 1; i++) {
    //pre遍历到left的前一个节点
    pre = pre.next;
  }

  let rightNode = pre;
  for (let i = 0; i < right - left + 1; i++) {
    //rightNode遍历到right的位置
    rightNode = rightNode.next;
  }

  let leftNode = pre.next; //保存leftNode
  let curr = rightNode.next; //保存rightNode.next

  //切断left到right的子链
  pre.next = null;
  rightNode.next = null;

  //206题的逻辑 反转left到right的子链
  reverseLinkedList(leftNode);

  // 重新连接开头
  pre.next = rightNode;
  leftNode.next = curr;
  return dummyNode.next;
};

93.复原 IP 地址（dfs）

/**
 * @param {string} s
 * @return {string[]}
 */
const restoreIpAddresses = (s) => {
  const res = [];
  // 复原从start开始的子串，start表示当前在字符串的哪一位
  //   subRes里收集了[111],[255],[255],[0]
  const dfs = (subRes, start) => {
    if (subRes.length === 4) {
      // 1.片段满4段
      res.push(subRes.join(".")); // 拼成字符串，加入解集
      return;
    }
    for (let len = 1; len <= 3; len++) {
      // 枚举出选择，三种切割长度; 这里因为如果不满足，下一个肯定也不满足，所以用return就行
      // 不需要continue
      if (start + len - 1 >= s.length) return; // 3.加上要切的长度就越界，不能切这个长度
      if (len != 1 && s[start] === "0") return; // 4.不能切出'0x'、'0xx'

      const str = s.substring(start, start + len); // 5.当前选择切出的片段
      if (+str > 255) return; // 不能超过255

      subRes.push(str); // 作出选择，将片段加入subRes
      dfs(subRes, start + len); // *基于当前选择，继续选择，注意更新指针
      subRes.pop(); //** */ 上面一句的递归分支结束，撤销最后的选择，进入下一轮迭代，考察下一个切割长度,因为会回退，所以只需要维护一个数组就行，不重不漏
    }
  };

  dfs([], 0); // dfs入口
  return res;
};

94.二叉树的中序遍历（双循环，栈）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
//  递归法递归函数（root)，如果！root 剪，递归（root.left) res.push(root.val) 递归(root.right)
// 启动

// 迭代法，特殊!root,外循环（root||stk.length)
// 内循环root，栈入root,root=root.left
// 跳出循环，从stk弹出一个node,res里push结果，root=node.right

const inorderTraversal = function (root) {
  const res = [];
  const stk = [];
  while (root || stk.length) {
    while (root) {
      stk.push(root);
      root = root.left;
    }
    let node = stk.pop();
    res.push(node.val);
    root = node.right;
  }
  return res;
};

98.验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

const isValidBST = (root) => {
  return helper(root, -Infinity, Infinity);
};

const helper = (root, left, right) => {
  //最底层条件
  if (!root) return true;
  // 一般条件
  if (root.val <= left || root.val >= right) return false;

  // 递归化条件
  return (
    // 注意right变成了root.val,表示上界；下界用不上！
    helper(root.left, left, root.val) && helper(root.right, root.val, right)
  );
};