跳到主要内容

力扣 100-199

101.对称二叉树​

//里面设递归函数(l,r)
// 如果l无r有,l有r无 return false
// 如果l值不等于r值 return false
// 如果左右都无,返回true

// outside=递归函数(l.left,r.right)
// inside=递归函数(l.right,r.left)
// 返回inside&&outside

// 外层返回启动函数(root.left,root.right)
var isSymmetric = function (root) {
  var compare = function (left, right) {
    if ((left && !right) || (!left && right)) {
      return false;
    } else if (!left && !right) {
      return true;
    } else if (left.val != right.val) {
      return false;
    }
    //剩下的情况便是两侧有值并且相等，那么就进行下一步递归

    return compare(left.left, right.right) && compare(left.right, right.left);
  };

  return compare(root.left, root.right);
};

102.二叉树的层序遍历​

// 特殊!root
// q里存root
// 循环q.length
// 当前层level数组
// 记录q.length(上一层容量)
// for每次shift一个q元素,当前层加入val (如果用pop则先加right再加left)
// 如果元素有left,q里push元素
// 右边同理
// 跳出循环把当前层加入ans

var levelOrder = function (root) {
  let ans = [];
  if (!root) {
    return ans;
  }
  let q = [root];
  while (q.length !== 0) {
    //   双层循环，不断加level
    let level = [];
    // 必须记录q长度，因为长度不固定
    let cur = q.length;
    for (let i = 0; i < cur; i++) {
      //   把节点给拿出来直接.val不要用下标
      // 从队列首
      let tem = q.shift();
      level.push(tem.val);
      //   if判断有没有tem
      if (tem.left) q.push(tem.left);
      if (tem.right) q.push(tem.right);
    }
    ans.push(level);
  }
  return ans;
};

103.二叉树的锯齿形层序遍历​

const zigzagLevelOrder = function (root) {
  if (!root) {
    return [];
  }
  let q = [root];
  let n = true;
  let ans = [];
  while (q.length) {
    let thisLevel = [];
    let thisLevelsize = q.length;
    for (let i = 0; i < thisLevelsize; i++) {
      let forNode = q.shift();
      // 以下为升级
      if (n) {
        thisLevel.push(forNode.val);
      } else {
        // 逆序，把当前的q-node加在thisLevel最左边
        thisLevel.unshift(forNode.val);
      }
      // 以上为升级
      // 往q中加入下一层，还是跟层序遍历题一样从左往右加
      if (forNode.left) {
        q.push(forNode.left);
      }
      if (forNode.right) {
        q.push(forNode.right);
      }
    }
    ans.push(thisLevel);
    n = !n;
  }
  return ans;
};

104.二叉树的最大深度​

const maxDepth = function (root) {
  let ans = 0;
  if (!root) return 0;
  ans = Math.max(maxDepth(root.left), ans);
  ans = Math.max(maxDepth(root.right), ans);
  return ans + 1;
};

105.从前序与中序遍历序列构造二叉树​

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

//  TreeNode题目已给，用treeNode创建节点
// 递归函数buildTree(先序数组preoreder,中序数组inorder)
// *如果先序数组有长度
// 从先序数组shift()第一个值,用TreeNode new出head
// 用head.val加indexOf找出中序数组中的index位
// head.left = 递归函数(先序遍历从0到index的截取slice,中序遍历从0到index的截取)
// head.right = 递归函数(先序遍历从index开始的截取,中序遍历从index+1开始的截取) 因为先序遍历shift了,中序遍历没shift
// return head
// *否则 return null

const buildTree = function (preorder, inorder) {
  if (!preorder.length) return null;
  let head = new TreeNode(preorder.shift());
  // 1
  let index = inorder.indexOf(head.val);
  // [ 0，1 )
  head.left = buildTree(preorder.slice(0, index), inorder.slice(0, index));
  // [1,   [2,
  // preorder.slice(index) 右子树的前序遍历
  // inorder.slice(index+1) 右子树的中序遍历，因为前序遍历被shift了，去掉首位3，变成
  //9|20,15,7 index所以为1
  //但是中序遍历没shift 为 9|3|15，20，7，所以去除右子树的中序遍历index要加1（相当于去掉父节点3）
  head.right = buildTree(preorder.slice(index), inorder.slice(index + 1));
  // 这⾥要注意，preorder前⾯shift⼀次⻓度⽐inorder⼩1
  return head;
};

106.从中序与后序遍历序列构造二叉树​

/**
 * 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 {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
const buildTree = function (inorder, postorder) {
  let post_idx = postorder.length - 1;
  const valMapIndexofInorder = new Map();
  inorder.forEach((val, idx) => {
    // 用val做key,idx做val
    valMapIndexofInorder.set(val, idx);
  });

  const helper = (l, r) => {
    if (l > r) {
      return null;
    }
    const root_val = postorder[post_idx];
    const index = valMapIndexofInorder.get(root_val);
    post_idx--;
    const root = new TreeNode(root_val);
    root.right = helper(index + 1, r);
    root.left = helper(l, index - 1);
    return root;
  };

  return helper(0, inorder.length - 1);
};

110.平衡二叉树（-114514）​

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

var isBalanced = function (root) {
  //   递归主函数
  return walk(root) !== -114514;
};

const walk = function (node) {
  if (!node) return 0;
  // 拿到左边最大长度
  const left = walk(node.left);
  const right = walk(node.right);
  // 已经不平衡 ｜｜ 将要不平衡
  if (left === -114514 || right === -114514 || Math.abs(left - right) > 1) {
    return -114514;
  }
  return Math.max(left, right) + 1;
};

108.将有序数组转换为二叉搜索树(升序列表从中间 slice)​

var sortedArrayToBST = function (nums) {
  if (!nums.length) {
    return null;
  }

  // 二叉搜索树的中序遍历，就是升序列表
  // 以升序数组的中间元素作为根节点 root
  const mid = Math.floor(nums.length / 2);
  const root = new TreeNode(nums[mid]);

  root.left = sortedArrayToBST(nums.slice(0, mid));
  root.right = sortedArrayToBST(nums.slice(mid + 1));

  return root;
};

110.平衡二叉树​

var isBalanced = function (root) {
  //   递归主函数
  return walk(root) !== -999;
};

const walk = function (node) {
  if (!node) return 0;
  // 拿到左边最大长度
  const left = walk(node.left);
  const right = walk(node.right);
  if (left === -999 || right === -999 || Math.abs(left - right) > 1) {
    return -999;
  }
  return Math.max(left, right) + 1;
};

111.二叉树的最小深度​

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
  if (root == null) {
    return 0;
  }
  // 不像最大深度,最小深度必须分开判断,防止一条链表的情况,
  // 只有两边都没有子树才是叶子节点
  if (root.left == null && root.right == null) {
    return 1;
  }
  let ans = Number.MAX_SAFE_INTEGER;
  if (root.left != null) {
    ans = Math.min(minDepth(root.left), ans);
  }
  if (root.right != null) {
    ans = Math.min(minDepth(root.right), ans);
  }
  return ans + 1;
};

112.路径总和​

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum

var hasPathSum = function (root, targetSum) {
  let flag = false;
  if (!root) return false;

  const dfs = (curr, sum) => {
    if (sum === targetSum && !curr.left && !curr.right) {
      flag = true;
      return;
    }
    if (curr.left && !flag) dfs(curr.left, sum + curr.left.val);
    if (curr.right && !flag) dfs(curr.right, sum + curr.right.val);
  };
  dfs(root, root.val);
  return flag;
};

113.路径总和 II(dfs,pushpop)​

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

//  比路径总和多一个参数path,每次push path,递归下一层,再pop
// 而且比路径总和增加一个细节,
// 函数执行一开始push当前值,最后pop当前值
var pathSum = function (root, targetSum) {
  if (root == null) return [];

  const res = [];

  function getPath(node, sum, path) {
    path.push(node.val);
    if (node.left == null && node.right == null && sum == targetSum) {
      res.push(path.slice());
    }
    if (node.left) {
      // 先push再pop,注意这里path不包含左值，下一次递归才会加入path
      getPath(node.left, sum + node.left.val, path);
    }

    if (node.right) {
      getPath(node.right, sum + node.right.val, path);
    }
    path.pop();
  }

  getPath(root, root.val, []);
  return res;
};

114.二叉树转链表（前序遍历进数组，然后一个个拼）​

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
  const list = [];
  preorderTraversal(root, list);
  const size = list.length;
  for (let i = 1; i < size; i++) {
    const prev = list[i - 1],
      curr = list[i];
    prev.left = null;
    prev.right = curr;
  }
};

const preorderTraversal = (root, list) => {
  if (root != null) {
    list.push(root);
    preorderTraversal(root.left, list);
    preorderTraversal(root.right, list);
  }
};

115.不同的子序列​

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

输入：s = "rabbbit", t = "rabbit" 输出：3 解释： 有 3 种可以从 s 中得到 "rabbit" 的方案。

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function (s, t) {
  const m = s.length,
    n = t.length;
  if (m < n) {
    return 0;
  }
  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  //   r a t
  // r 2 2 2 1
  // a 0 2 2 1
  // b 0 0 2 1
  // b 0 0 2 1
  // t 0 0 2 1
  // t 0 0 1 1
  //   0 0 0 1

  // 右多一列下多一排，右列初始化为1
  // 如果相等，则下右和，如果不等，则下，dp[0][0]

  for (let i = 0; i <= m; i++) {
    dp[i][n] = 1;
  }
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      if (s[i] == t[j]) {
        // 和下右有关
        dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
      } else {
        // 和下有关
        dp[i][j] = dp[i + 1][j];
      }
    }
  }
  return dp[0][0];
};

118.杨辉三角​

在「杨辉三角」中，每个数是它左上方和右上方的数的和，如果左上方没有数，则用右上方

外围永远是 1

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  const ret = [];

  for (let i = 0; i < numRows; i++) {
    const row = new Array(i + 1).fill(1);
    // 第一次遍历 1 2* 1，只循环过中间一位
    // 1 3* 3* 1，只循环过中间两位
    for (let j = 1; j < row.length - 1; j++) {
      row[j] = ret[i - 1][j - 1] + ret[i - 1][j];
    }
    ret.push(row);
  }
  // [[1],[1,1],[1,2,1]....]
  return ret;
};

119.杨辉三角 II​

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

var getRow = function (rowIndex) {
  const row = new Array(rowIndex + 1).fill(0);
  // 第五行 14641
  row[0] = 1;
  for (let i = 1; i <= rowIndex; ++i) {
    // 1 0 0 0 0 0
    // 1 1 0 0 0 0
    // 1 2 1 0 0 0
    // 1 3 3 1 0 0
    // 1 4 6 4 1 0
    for (let j = i; j > 0; --j) {
      row[j] += row[j - 1];
    }
  }
  return row;
};

121.买卖股票的最佳时机（maxProfit 和 min）​

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

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

//  min=100001 profit = 0
// 遍历数组，挑战价格减去最小值的最大（profit)
// 再挑战最小值和当前的最小
var maxProfit = function (prices) {
  let _min = 100001;
  let profit = 0;
  let len = prices.length;
  for (let i = 0; i < len; i++) {
    profit = Math.max(profit, prices[i] - _min);
    _min = Math.min(prices[i], _min);
  }
  return profit;
};

122.买卖股票的最佳时机 II​

找到每一处的提升量

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let ans = 0;
  let n = prices.length;
  for (let i = 1; i < n; ++i) {
    ans += Math.max(0, prices[i] - prices[i - 1]);
  }
  return ans;
};

124.二叉树中的最大路径和(dfs)​

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和

/**
 * @param {TreeNode} root
 * @return {number}
 */
const maxPathSum = (root) => {
  let maxSum = Number.MIN_SAFE_INTEGER; // 最大路径和

  const dfs = (root) => {
    if (root == null) {
      // 遍历到null节点，收益0
      return 0;
    }
    const left = dfs(root.left); // 左子树提供的最大路径和
    const right = dfs(root.right); // 右子树提供的最大路径和

    // 如果在这里终止
    const innerMaxSum = left + root.val + right; // 当前子树内部的最大路径和
    maxSum = Math.max(maxSum, innerMaxSum); // 挑战最大纪录

    // 不在这里终止，继续往上提供（只能取一边）
    const outputMaxSum = root.val + Math.max(0, left, right); // 当前子树对外提供的最大和

    // 如果对外提供的路径和为负，直接返回0。啥都不要了
    return outputMaxSum < 0 ? 0 : outputMaxSum;
  };

  dfs(root); // 递归的入口

  return maxSum;
};

125.验证回文串(reverse)​

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
  s = s
    .replace(/[^a-zA-Z0-9]/g, "")
    .replace(/\s/g, "")
    .toLowerCase();
  let t = s.split("").reverse().join("");
  return s == t;
};

128.最长连续序列（哈希表）​

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

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

输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  let nums_set = new Set();
  // 全加入哈希表
  for (let num of nums) {
    nums_set.add(num);
  }
  let longestStreak = 0;
  for (let num of nums_set) {
    // 如果是序列起始数，非起数忽略
    if (!nums_set.has(num - 1)) {
      let curNum = num;
      let curStreak = 1;
      // 哈希表查找时间复杂度O（1）
      while (nums_set.has(curNum + 1)) {
        // 从curNum开始和从1开始
        curNum++;
        curStreak++;
      }
      longestStreak = Math.max(curStreak, longestStreak);
    }
  }
  return longestStreak;
};

129.求根节点到叶节点数字之和​

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。

const sumNumbers = function (root) {
  return helper(root, 0);
};
const helper = function (root, presum) {
  if (!root) return 0;
  // 和递归结果无关的事
  let sum = presum * 10 + root.val;
  // 递归终止时刻，一定在递归下次执行前
  if (!root.left && !root.right) return sum;
  // 利用递归结果做的事，最终利用完返回
  return helper(root.left, sum) + helper(root.right, sum);
};

136.只出现一次的数字（位运算）​

除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

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

// yihuo运算
var singleNumber = function (nums) {
  let ans = 0;
  for (const num of nums) {
    ans ^= num;
  }
  return ans;
};

139.单词拆分(dp 缓存，n2 往前)​

const wordBreak = (s, wordDict) => {
  const n = s.length;
  const set = new Set(wordDict);
  // dp初始化，除了第一个，全为false
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;
  // true,false,true, apple
  // 从1到n遍历s
  for (let i = 1; i <= n; i++) {
    // 当遍历到i时，再从0到i遍历
    for (let j = 0; j < i; j++) {
      // 当前i所处的子串是否是否可以，取决于分割点j
      // 对于分割点j，若[0,j]满足，且剩下的在wordDict中出现过，则当前[0,i]子串就满足
      if (dp[j] && set.has(s.slice(j, i))) {
        dp[i] = true;
        // 若当前[0,i]子串满足，就不用继续遍历当前子串的分割点了
        // 跳过，判断下一轮子串[0,i+1]
        break;
      }
    }
  }

  return dp[n];
};

141.环形链表​

如果链表中存在环 ，则返回 true 。 否则，返回 false

const hasCycle = (head) => {
  if (!head || !head.next) return false;
  let slow = head.next;
  let fast = head.next.next;
  while (fast && fast.next) {
    if (slow === fast) return true;
    slow = slow.next;
    fast = fast.next.next;
  }
  return false;
};
// 因为fast一开始就超过slow，所以想要再相遇肯定有环。
// 而且由于有环的链表，fast会一直在环内跑，等着slow;slow也会一直在环内跑
// 所以迟早会相遇。不相遇必然是无环，fast走到null

// 时间复杂度O(N) 空间负责度O(1)

142.环形链表 II(简便法 Set)​

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

var detectCycle = function (head) {
  const visited = new Set();
  while (head !== null) {
    if (visited.has(head)) {
      return head;
    }
    visited.add(head);
    head = head.next;
  }
  return null;
};

数学法​

let detectCycle = function (head) {
  if (!head || !head.next) return null;
  // 快慢指针
  let fast = head,
    slow = head;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) break;
  }
  if (fast != slow) return null; // 无环
  // 此时快慢指针相遇, 头节点到入口节点的距离=相遇节点到入口节点的距离 + n*环形周长
  let index1 = head,
    index2 = fast;
  while (index1 != index2) {
    index1 = index1.next;
    index2 = index2.next;
  }
  return index1;
};
//fast和slow会在环上相遇且，从起点到环位置的距离等于相遇点到环位置的距离加n-1圈
//所以index1和index2相遇的位置就是环位置

// a  b
//    c      fast: a+2b+c head:0  a+2b+c = 2* (a+b) -> c=a
//           head: a  fast: 2a + 2b + c = a + 2(b+c) = a + 2n,因此相遇点就是环位置

143.重排链表(快慢指针找中间+链表反转+双指针)​

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
var reorderList = function (head) {
  if (head.next === null) return head;
  let p1 = head,
    halfNode = head,
    fullNode = head;
  // 奇数和偶数情况下均能找到中间节点
  while (fullNode.next && fullNode.next.next) {
    //找到中间结点
    halfNode = halfNode.next;
    fullNode = fullNode.next.next;
  }
  //将后半部分链表反转，注意后半部分从halfnode.next开始
  let pre = null;
  let cur = halfNode.next;
  //!一定要断链
  halfNode.next = null;
  while (cur) {
    let next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }

  part2 = pre;
  //将前半部分和后半部分链表用双指针逐个链接
  while (part2.next && part1) {
    let nextNode1 = part1.next;
    part1.next = part2;
    let nextNode2 = part2.next;
    part2.next = nextNode1;
    part1 = nextNode1;
    part2 = nextNode2;
  }
  return head;
};

144.二叉树前序遍历（队列但是一次只取一个）​

var preorderTraversal = function (root, res = []) {
  if (!root) return res;
  res.push(root.val);
  preorderTraversal(root.left, res);
  preorderTraversal(root.right, res);
  return res;
};
var preorderTraversal = function (root) {
  let res = [];
  if (!root) return [];
  let q = [root];
  while (q.length) {
    let node = q.shift();
    res.push(node.val);
    if (node.left) {
      q.push(node.left);
    }
    if (node.right) {
      q.push(node.right);
    }
  }
  return res;
};

145.二叉树的后序遍历​

板子

var postorderTraversal = function (root) {
  if (!root) return [];
  let stk = [root];
  let res = [];
  while (stk.length) {
    let node = stk.pop();
    res.push(node.val);
    // 先放入左节点
    if (node.left) {
      stk.push(node.left);
    }
    if (node.right) {
      stk.push(node.right);
    }
  }
  // 倒序
  return res.reverse();
};

146.LRU 缓存​

// 构造函数this.map = new Map() this.maxSize = 参数
// 构造函数原型get（key) 如果map没有key,return - 1
// val = map.get(key)
// this.map.delete(key)
// this.map.set(key,val) return val

// put（key,value) 如果map有key,删除key
// 如果map的size已经等于maxSize
// const it = this.map.keys()
// 删除第一个key,this.map.delete(it.next().value)
// 不管等不等于，都this.map.set(key,value)

const LRUCache = function (capacity) {
  this.hashMap = new Map();
  this.maxSize = capacity;
};

// map 有序
LRUCache.prototype.get = function (key) {
  if (!this.hashMap.has(key)) return -1;
  const val = this.hashMap.get(key);
  // 这里删除重建是为了更新最久使用次数最少数据，多次被使用的数据只会被记录一次
  // 先按最久排，再按最少排
  this.hashMap.delete(key);
  this.hashMap.set(key, val);
  return val;
};

LRUCache.prototype.put = function (key, value) {
  if (this.hashMap.has(key)) {
    this.hashMap.delete(key);
  } else if (this.hashMap.size === this.maxSize) {
    // keys返回一个可迭代的对象，里面含有hashMap的所有key，可以通过.next()访问第一个
    // 第一个即为最久的使用次数最少的数据，因为大小有限被删掉
    const it = this.hashMap.keys();
    // it是一个迭代器
    this.hashMap.delete(it.next().value);
  }
  this.hashMap.set(key, value);
};

148.排序链表(归并)​

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
//1和2排序好，然后12和34排序好，然后1234和5678排序好
var merge = function (l1, l2) {
  if (l1 === null) {
    return l2;
  }
  if (l2 === null) {
    return l1;
  }
  if (l1.val > l2.val) {
    l2.next = merge(l1, l2.next);

    //这种情况，最小的是l2开头，因此返回l2
    return l2;
  } else {
    l1.next = merge(l1.next, l2);
    return l1;
  }
};

const toSortList = (head, tail) => {
  if (head === null) {
    //极端情况
    return head;
  }
  if (head.next === tail) {
    //分割到只剩一个节点
    head.next = null;
    return head;
  }
  let slow = head,
    fast = head;
  // 第一次是fast!==null
  while (fast !== tail) {
    //得到中间节点
    slow = slow.next;
    fast = fast.next;
    if (fast !== tail) {
      fast = fast.next;
    }
  }
  const mid = slow;
  // 左闭右开，不包含mid
  return merge(toSortList(head, mid), toSortList(mid, tail)); //分割区间 递归合并
};

var sortList = function (head) {
  //最后一个看作null
  return toSortList(head, null);
};

151.反转字符串中的单词​

输入：s = "the sky is blue" 输出："blue is sky the"

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

//  左右指针，循环左指针为空走动，循环右指针为空走动,(或者str.trim()也行)
// 循环left<=len - 1,如果左指针为空且当前有word,队列里unshiftword,word清空
// 否则如果左指针不为空，word+charAt
// 无论怎样left走动
// 由于最后一个word没加进去，所以一开始在字符串末尾加一空,返回queue.join(" ")
var reverseWords = function (str) {
  str = str.trim() + " ";
  let left = 0;
  let word = "";
  let queue = [];
  let len = str.length;
  while (left <= len - 1) {
    if (str.charAt(left) === " ") {
      // 在队首加入
      if (word) {
        queue.unshift(word);
      }
      word = "";
    } else {
      word += str.charAt(left);
    }
    left++;
  }
  return queue.join(" ");
};

152.乘积最大子数组(贪心所有情况)​

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组 （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

var maxProduct = (nums) => {
  let res = nums[0];
  let prevMin = nums[0];
  let prevMax = nums[0];
  let temp1 = 0,
    temp2 = 0;
  for (let i = 1; i < nums.length; i++) {
    temp1 = prevMin * nums[i];
    temp2 = prevMax * nums[i];
    // nums[i]作为保底
    prevMin = Math.min(temp1, temp2, nums[i]);
    prevMax = Math.max(temp1, temp2, nums[i]);
    res = Math.max(prevMax, res);
  }
  return res;
};

155.最小栈​

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。 void push(int val) 将元素 val 推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。

// 构造函数创建this.stack数组，和this.min
// prototype上push方法，挑战this.min再push
// pop方法，先pop, this.min=Math.min(...this.stack)
// top，返回栈顶元素

var MinStack = function () {
  this.stack = [];
  this.min = Infinity;
};

MinStack.prototype.push = function (val) {
  this.min = Math.min(this.min, val);
  this.stack.push(val);
};

MinStack.prototype.pop = function () {
  let num = this.stack.pop();
  this.min = Math.min(...this.stack);
  return num;
};

MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function () {
  return this.min;
};

160.相交链表（双指针）​

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

var getIntersectionNode = function (headA, headB) {
  // A,B 链表头指针同时开始移动，让某一方遍历完整个链表，指针移动到另一个链表的首部重新开始移动

  if (!headA || !headB) {
    return null;
  }
  let pA = headA,
    pB = headB;
  // 循环都为null时一定能结束
  while (pA !== pB) {
    pA = pA === null ? headB : pA.next;
    pB = pB === null ? headA : pB.next;
  }
  return pA;
};

165.比较版本号​

利用 api

var compareVersion = function (version1, version2) {
  version1 = version1.split(".");
  version2 = version2.split(".");
  let n = Math.max(version1.length, version2.length);
  for (let i = 0; i < n; i++) {
    let code1 = version1[i] === undefined ? 0 : parseInt(version1[i]);
    let code2 = version2[i] === undefined ? 0 : parseInt(version2[i]);
    if (code1 > code2) {
      return 1;
    } else if (code1 < code2) {
      return -1;
    }
  }
  return 0;
};
/**
 * @param {string} version1
 * @param {string} version2
 * @return {number}
 */

const compareVersion = function (v1, v2) {
  // 双指针，外循环至少有一个没走完，里面两个for循环x<v1len&&v1[x]!==".",sum*10+当前位
  // for循环结束注意让xy走动
  // 双循环结束，已经可以比较sumxy返回1或-1
  // 外循环结束,版本号相等返回0
  let x = 0,
    y = 0;
  let v1l = v1.length,
    v2l = v2.length;
  while (x < v1l || y < v2l) {
    let sumx = 0;
    let sumy = 0;
    for (; x < v1l && v1[x] !== "."; x++) {
      sumx = sumx * 10 + v1[x];
    }
    x++;
    for (; y < v2l && v2[y] !== "."; y++) {
      sumy = sumy * 10 + v2[y];
    }
    y++;
    if (sumx > sumy) {
      return 1;
    }
    if (sumx < sumy) {
      return -1;
    }
  }
  return 0;
};

167.两数之和 II (双指针)​

使用常量级别空间 numbers 按 非递减顺序 排列 输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

const twoSum = function (nums, target) {
  let low = 0;
  high = nums.length - 1;
  while (low < high) {
    let sum = nums[low] + nums[high];
    if (sum < target) {
      low++;
    } else if (sum > target) {
      high--;
    } else {
      return [low + 1, high + 1];
    }
  }
};

169.多数元素（出现次数超过一半的数）​

/**
 * @param {number[]} nums
 * @return {number}
 */
const majorityElement = (nums) => {
  let count = 1;
  // 将第一个数赋予 majority
  let majority = nums[0];

  for (let i = 1; i < nums.length; i++) {
    if (count === 0) {
      majority = nums[i];
    }

    if (nums[i] === majority) {
      count++;
    } else {
      count--;
    }
  }

  return majority;
};

179.最大数（尽量把 999888 堆到前面）​

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

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

/**
 * @param {number[]} nums
 * @return {string}
 */
//  根据string开头的第一个字符排序，也就是ASCII码
// 尽量把999888堆到前面
var largestNumber = function (nums) {
  nums.sort((a, b) => {
    var stra = b.toString() + a.toString(),
      strb = a.toString() + b.toString();
    // console.log(stra," ",strb)
    if (stra > strb) {
      return 1;
    } else {
      return -1;
    }
  });
  if (nums[0] == 0) return "0";
  return nums.join("");
};

189. 轮转数组​

三次轮转

输入: (nums = [1, 2, 3, 4, 5, 6, 7]), (k = 3);
输出: [5, 6, 7, 1, 2, 3, 4];

const reverse = (nums, start, end) => {
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start += 1;
    end -= 1;
  }
};

var rotate = function (nums, k) {
  k %= nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
};

198. 打家劫舍​

如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

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

//  特殊len=0,return 0
// dp len+1
// dp[0] 为0 dp[1]为nums[0]
// 从2开始遍历到len
// dp[i]挑战上次和上上次加这次的最大值
var rob = function (nums) {
  const len = nums.length;
  if (len == 0) return 0;
  const dp = new Array(len + 1);
  dp[0] = 0;
  dp[1] = nums[0];
  for (let i = 2; i <= len; i++) {
    // 有一次反悔上次选择的机会足够了
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
  }
  return dp[len];
};

199.二叉树的右视图​

var rightSideView = function (root) {
  if (!root) return [];
  let q = [root];
  let res = [];
  while (q.length !== 0) {
    let cur = q.length;
    let firstTime = true;
    for (let i = 0; i < cur; i++) {
      let node = q.shift();
      if (firstTime) {
        res.push(node.val);
        firstTime = false;
      }
      // 层析遍历但是每层从右往左排,取出的第一个即是右视图看到的,且每一层只取一次,用firstTime标记
      if (node.right) q.push(node.right);
      if (node.left) q.push(node.left);
    }
  }
  return res;
};