前言

前端也是要刷算法的呀= =
选自 leetcode hot 100 和剑指 offer

1.两数之和【哈希表】

给定一个整数数组nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于O(n2) 的算法吗？

这道题对前端来说考察的应该是用 map 方法来操作数据的问题。
回顾一下 map 的三个方法
map.get(key)用于返回 key 对应的 value 值
map.set(key,value)设置 key 和 value 值
map.has(key)返回 key 是否存在
那么这道题的思路就是先遍历数组判断 target 和数字的差值是否在 map 里面，如果是则返回 key 和当前 i，否则存入 map

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

其实不用到 map 这个 api 也是可以做的，并且用时还快一点

var twoSum = function (nums, target) {
  let map = {};
  for (let i = 0; i < nums.length; i++) {
    let less = target - nums[i];
    if (map[less] !== undefined) {
      return [map[less], i];
    } else {
      map[nums[i]] = i;
    }
  }
};

2.两数相加【链表】【链表合并】

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

这个就很类似于链表的合并，但是这个相较于合并特殊的一点在于它不能设置 val 为 0 而是要设置 next 为一个新的节点。

var addTwoNumbers = function (l1, l2) {
  let dummy = new ListNode();
  let cur = dummy;
  let newAdd = 0;
  while (l1 || l2) {
    let count = 0;
    //对l1 l2的加法逻辑单独放一块 避免有一方提前结束
    if (l1) {
      count += l1.val;
      l1 = l1.next;
    }
    if (l2) {
      count += l2.val;
      l2 = l2.next;
    }
    count += newAdd;
    //这里下个节点要用listnode新建，不能直接赋当前的val为count%10
    cur.next = new ListNode(count % 10);
    //向下取整进位数
    newAdd = Math.floor(count / 10);
    cur = cur.next;
  }
  //如果已经结束了且最后的进位还大于0 那么要再新建一个节点放这个数
  if (newAdd > 0) {
    cur.next = new ListNode(newAdd);
  }
  return dummy.next;
};

3.无重复字符的最长字串【API】

思路就是用 include 方法循环判断是否存在这个字符如果存在就删去，如果不存在就 push
然后判断 maxlength

var lengthOfLongestSubstring = function (s) {
  let arr = [];
  let max = 0;
  for (let str of s) {
    while (arr.includes(str)) {
      arr.shift();
    }
    arr.push(str);
    if (arr.length > max) {
      max = arr.length;
    }
  }
  return max;
};

4.寻找两个正序数组的中位数【API】

思路就是合并数组然后 sort 排序，然后判断奇偶来写。

var findMedianSortedArrays = function (nums1, nums2) {
  let arr = [...nums1, ...nums2];
  arr.sort((a, b) => {
    return a - b;
  });
  let len = arr.length;
  if (len % 2 !== 0) {
    return parseFloat(arr[(len - 1) / 2]);
  } else {
    return parseFloat((arr[len / 2] + arr[len / 2 - 1]) / 2);
  }
};

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

思路就是快慢指针，快指针先走 n 步，然后快慢一起遍历就能找到要删除节点的前驱节点和后继节点。
注意细节问题

var removeNthFromEnd = function (head, n) {
  let dummy = new ListNode();
  dummy.next = head;
  let fast = dummy;
  let slow = dummy;
  while (n--) {
    fast = fast.next;
  }
  //  这里判断不能写fast 要写fast.next 如果写了前者，那么到最后一个节点他还会前进
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  //注意这里不能直接写fast 如果只存在一个节点那么快慢指针同步 最后还是会返回fast节点的值
  //  slow.next = fast;
  slow.next = slow.next.next;
  return dummy.next;
};

20.有效的括号【栈】

思路利用栈先定义括号的数据结构，然后进站的是右括号如果和出栈的对应那么最后栈空

var isValid = function (s) {
  let stack = [];
  let leftToRight = {
    "(": ")",
    "[": "]",
    "{": "}",
  };
  for (let i = 0; i < s.length; i++) {
    let ch = s[i];
    if (ch === "{" || ch === "[" || ch === "(") {
      stack.push(leftToRight[ch]);
    } else {
      if (stack.pop() !== ch) {
        return false;
      }
    }
  }
  return !stack.length;
};

21.合并两个有序链表【链表】【链表合并】

思路
对链表进行穿针
穿针的步骤是把cur的下一位标志为当前最小val，然后让这个链表进位，最后cur进位
结束后多余出来的部分直接合并

var mergeTwoLists = function (list1, list2) {
  let head = new ListNode();
  let cur = head;
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      cur.next = list1;
      list1 = list1.next;
    } else {
      cur.next = list2;
      list2 = list2.next;
    }
    cur = cur.next;
  }
  //注意这里是cur.next 因为是合并剩下的部分 而不是取代当前
  cur.next = list1 ? list1 : list2;
  return head.next;
};

11. 盛最多水的容器【双指针】

看到涉及前后的问题使用双指针指向头尾

高度是相对小的指针的值宽度是下标的差值
指针移动的条件是相对小的那边移动

var maxArea = function (height) {
  let left = 0;
  let right = height.length - 1;
  let max = 0;
  while (right !== left) {
    let square = Math.min(height[left], height[right]) * (right - left);
    if (square > max) {
      max = square;
    }
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return max;
};

15.三数之和【双指针】

思路就是双指针头指针和尾指针

先对数组进行排序
遍历数组，还有个 next 指针为i+1
头指针 next 指针尾指针用while来判断，终止条件是 next 等于尾指针

若它们代表的元素相加若等于 0，将三个指针代表的元素入数组，并将 next 指针指向下一位，如果下一位和上一位的数字相同则跳过 next 继续指向下一位
如果小于 0 next 指针++
如果大于 0 尾指针—
特别注意如果前一项等于后一项那么直接跳过当前项
代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  nums.sort((a, b) => a - b);
  let len = nums.length;
  let res = [];
  for (let i = 0; i < len; i++) {
    if (nums[i] === nums[i - 1]) continue;
    let next = i + 1;
    let last = len - 1;
    while (next < last) {
      const sum = nums[i] + nums[next] + nums[last];
      if (sum === 0) {
        res.push([nums[i], nums[next], nums[last]]);
        next++;
        while (nums[next] === nums[next - 1]) {
          next++;
        }
      } else if (sum < 0) {
        next++;
      } else {
        last--;
      }
    }
  }
  return res;
};

16.最接近的三数之和【双指针】

思路和三数之和类似多了个比较最接近其实就是绝对值最小
代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
  nums.sort((a, b) => a - b);
  let len = nums.length;
  let min = Infinity;
  let res;

  for (let i = 0; i < len; i++) {
    let next = i + 1;
    let last = len - 1;
    while (next < last) {
      const sum = nums[i] + nums[next] + nums[last];
      const diff = Math.abs(sum - target);
      if (diff < min) {
        min = diff;
        res = sum;
      }
      if (sum < target) {
        next++;
      } else {
        last--;
      }
    }
  }
  return res;
};

18.四数之和【双指针】

思路和三数差不多但是多了层循环
代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  nums.sort((a, b) => a - b);
  let len = nums.length;
  let res = [];
  for (let i = 0; i < len; i++) {
    if (i > 0 && nums[i] === nums[i - 1] && i < len) continue;
    let first = i + 1;
    while (first < len - 2) {
      if (first > i + 1 && nums[first] === nums[first - 1] && first < len - 2)
        continue;
      let next = first + 1;
      let last = len - 1;
      while (next < last) {
        let sum = nums[i] + nums[first] + nums[next] + nums[last];
        if (sum === target) {
          res.push([nums[i], nums[first], nums[next], nums[last]]);
          next++;
          while (nums[next] === nums[next - 1]) {
            next++;
          }
        } else if (sum < target) {
          next++;
        } else {
          last--;
        }
      }
      first++;
      while (nums[first] === nums[first - 1]) {
        first++;
      }
    }
  }
  return res;
};

53.最大子数组和【动态规划】

动态规划但是是从前往后
正负收益如果是相减是负收益那么不要这个取当前项
优化：不使用 dp 数组来维护这些变量直接用一个 sum 变量来代替

var maxSubArray = function (nums) {
  //初始化maxSum
  let maxSum = nums[0];
  //初始化sum
  let sum = nums[0];
  for (let i = 1; i < nums.length; i++) {
    //比较收益 两者差值和当前值谁更大 取更大的
    sum = Math.max(sum + nums[i], nums[i]);
    //比较最大收益 取最大收益
    maxSum = Math.max(sum, maxSum);
  }
  return maxSum;
};

0 的地方是表示没有变化

70.爬楼梯【动态规划】

动态规划状态方程是f[n]= f[n-1]+f[n-2]

var climbStairs = function (n) {
  let f = [];
  f[1] = 1;
  f[2] = 2;
  for (let i = 3; i <= n; i++) {
    f[i] = f[i - 1] + f[i - 2];
  }
  return f[n];
};

94.二叉树的中序遍历【二叉树】【中序遍历】

注意在函数里面递归你的二叉树

var inorderTraversal = function (root) {
  const arr = [];
  const res = (n) => {
    if (!n) return;
    res(root.left);
    arr.push(root.val);
    res(root.right);
  };
  res(root);
  return arr;
};

101.对称二叉树【二叉树】【递归】

左右节点都存在
左右节点相等
左节点的左等于右节点的右
左节点的右等于右键点的左
即为镜像

var isSymmetric = function (root) {
  if (!root) return true;

  const jud = (l, r) => {
    //已经是叶子节点了 返回真
    if (!l && !r) return true;
    if (
      l &&
      r &&
      l.val === r.val &&
      jud(l.left, r.right) &&
      jud(l.right, r.left)
    ) {
      return true;
    } else {
      return false;
    }
  };
  return jud(root.left, root.right);
};

104. 二叉树的最大深度【二叉树】【深度优先】

最大深度用深度优先遍历
然后注意判断的时机
代码

var maxDepth = function (root) {
  if (!root) return 0;
  let max = 0;
  const dfs = (n, l) => {
    if (!n) return;
    //只在叶子节点的时候开始判断
    if (!n.left && !n.right) {
      max = Math.max(max, l);
    }
    dfs(n.left, l + 1);
    dfs(n.right, l + 1);
  };
  dfs(root, 1);
  return max;
};

121. 买卖股票的最佳时机【动态规划】

先提出一个概念收益这里的话是前后元素的差值
这里涉及到一个问题其实有时候不需要知道买进卖出的价格我们只需要知道在这个过程中，收益的幅度，也就是收益为负的时候，刷新这个收益为 0，收益为正的时候，和最大收益比较并考虑是否刷新最大收益。
代码

var maxProfit = function (prices) {
  let max = 0;
  let last = 0;
  for (let i = 0; i < prices.length - 1; i++) {
    last = Math.max(0, last + prices[i + 1] - prices[i]);
    max = Math.max(max, last);
  }
  return max;
};

136. 只出现一次的数字【位运算】

利用异或的性质

0 异或任何数都返回那个数字
两个数字异或相同 0 不同 1
代码

var singleNumber = function (nums) {
  let res = 0;
  nums.forEach((item) => {
    res = res ^ item;
  });
  return res;
};

226. 翻转二叉树【二叉树】

代码

var invertTree = function (root) {
  if (!root) {
    return root;
  }
  let left = invertTree(root.left);
  let right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
};

141. 环形链表【链表】【快慢指针】【环形链表】

快慢指针如果是环形快指针走两步慢指针走一步最后肯定会相遇

var hasCycle = function (head) {
  let slow = head;
  let fast = head;
  while (slow && fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
};

155. 最小栈【栈】

两个栈一个用于存放最小的数据集合一个用于普通存放

var MinStack = function () {
  this.stack1 = [];
  this.stack2 = [];
};

/**
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
  this.stack1.push(val);
  if (!this.stack2) {
    this.stack2.push(val);
  } else {
    if (val <= this.stack2[this.stack2.length - 1]) {
      this.stack2.push(val);
    } else {
      this.stack2.unshift(val);
    }
  }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  if (this.stack1.pop() === this.stack2[this.stack2.length - 1]) {
    this.stack2.pop();
  }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
  return this.stack1[this.stack1.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
  return this.stack2[this.stack2.length - 1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

160. 相交链表【链表】

连接 headA 和 headB 使得它们总路程相同
那么可以看此时总路程相同速度相同如果有相交的点那么最后肯定会到达该点
假设公共路径是 c 第一条公共路径之前是 a 第二条是 b
那么第一条路径就是 a+c+b+c
第二条就是 b+c+a+c
当第一条走过 a+c+b 的时候第二条也走过了 b+c+a 此时下一步的 c 就是交点或者终点

var getIntersectionNode = function(headA, headB) {
	let p1 = headA;
	let p2 = headB;
	while(p1!===p2){
		p1 = p1 ? p1.next : headB;
		p2 = p2 ? p2.next : headA;
	}
	return p1;
}

448. 找到所有数组中消失的数字【API】

思路 set 去重之后找到利用 set 的 has 特性如果不存在该数字就把数组原地的nums[count]修改为 i ，最后分割数组即可。

var findDisappearedNumbers = function (nums) {
  let set = new Set(nums);
  let count = 0;
  for (let i = 1; i <= nums.length; i++) {
    if (!set.has(i)) {
      nums[count] = i;
      count++;
    }
  }
  return nums.splice(0, count);
};

169. 多数元素【API】

code

var majorityElement = function (nums) {
  nums.sort((a, b) => {
    return a - b;
  });
  return nums[parseInt(nums.length / 2)];
};

283. 移动零【】

code

var moveZeroes = function (nums) {
  let n = nums.length;
  let k = 0;
  for (let i = 0; i < n; i++) {
    if (nums[i] != 0) {
      nums[k++] = nums[i];
    }
  }
  while (k < n) {
    nums[k++] = 0;
  }
};

617. 合并二叉树【二叉树】【合并】

code

var mergeTrees = function (root1, root2) {
  if (!root1 && !root2) return null;
  const jud = (n1, n2) => {
    if (!n1) return n2;
    if (!n2) return n1;
    n1.val += n2.val;
    n1.left = jud(n1.left, n2.left);
    n1.right = jud(n1.right, n2.right);
    return n1;
  };
  return jud(root1, root2);
};

543. 二叉树的直径【二叉树】

代码

var diameterOfBinaryTree = function (root) {
  let max = 0;
  const deep = (n1) => {
    if (!n1) return 0;
    let left = deep(n1.left);
    let right = deep(n1.right);
    max = Math.max(left + right, max);
    return Math.max(left, right) + 1;
  };
  deep(root);
  return max;
};

461. 汉明距离【API】

code

var hammingDistance = function (x, y) {
  return (x ^ y)
    .toString(2)
    .split("")
    .filter((s) => s === "1").length;
};

338. 比特位计数【API】

code

var countBits = function (n) {
  let arr = [];
  for (let i = 0; i <= n; i++) {
    arr.push(i.toString(2).replace(/0/g, "").length);
  }
  return arr;
};

剑指 Offer 10- I. 斐波那契数列【动态规划】

经典动态规划注意栈溢出。

var fib = function (n) {
  let f = [];
  f[0] = 0;
  f[1] = 1;
  for (let i = 2; i <= n; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % 1000000007;
  }
  return f[n];
};

剑指 Offer 10- II. 青蛙跳台阶问题【动态规划】

code

var numWays = function (n) {
  if (n <= 1) return 1;
  let f = [];
  f[1] = 1;
  f[2] = 2;
  for (let i = 3; i <= n; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % 1000000007;
  }
  return f[n];
};

剑指 Offer 11. 旋转数组的最小数字【API】

代码

1
2
3

var minArray = function (numbers) {
  return Math.min(...numbers);
};

剑指 Offer 15. 二进制中 1 的个数【API】

code

var hammingWeight = function (n) {
  return n
    .toString(2)
    .split("")
    .filter((s) => s === "1").length;
};

剑指 Offer 17. 打印从 1 到最大的 n 位数【】

code

var printNumbers = function (n) {
  // n = Math.pow(10,n);
  let count = 1;
  while (n > 0) {
    count *= 10;
    n--;
  }
  let arr = [];
  for (let i = 1; i < count; i++) {
    arr.push(i);
  }
  return arr;
};

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面【双指针】

双指针左指针维护奇数数组右指针维护偶数数组

var exchange = function (nums) {
  let left = 0;
  let right = nums.length;
  while (left < right) {
    if (nums[left] % 2 === 1) {
      left++;
    } else {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      right--;
    }
  }
  return nums;
};

剑指 Offer 27. 二叉树的镜像【二叉树】

反转二叉树

var mirrorTree = function (root) {
  if (!root) return root;
  let left = mirrorTree(root.left);
  let right = mirrorTree(root.right);
  root.left = right;
  root.right = left;
  return root;
};

剑指 Offer 28. 对称的二叉树【二叉树】

对称二叉树

var isSymmetric = function (root) {
  if (!root) return true;
  const jud = (l, r) => {
    if (!l && !r) return true;
    if (
      l &&
      r &&
      l.val === r.val &&
      jud(l.left, r.right) &&
      jud(l.right, r.left)
    ) {
      return true;
    } else {
      return false;
    }
  };
  return jud(root.left, root.right);
};

剑指 Offer 40. 最小的 k 个数【API】

代码

1
2
3

var getLeastNumbers = function (arr, k) {
  return arr.sort((a, b) => a - b).slice(0, k);
};

剑指 Offer 42. 连续子数组的最大和【动态规划】

收益和当前值比较取最大得到新收益
新收益和总收益比较刷新总收益
注意初始化的时候总收益和收益都是第一个元素避免只有一个元素的时候

var maxSubArray = function (nums) {
  let bonus = nums[0];
  let max = nums[0];
  for (let i = 0; i < nums.length; i++) {
    bonus = Math.max(bonus + nums[i], nums[i]);
    max = Math.max(bonus, max);
  }
  return max;
};

剑指 Offer 50. 第一个只出现一次的字符【API】

巧用 indexOf 的第二个属性
从 xx 位置开始查找
所以如果查了第一次发现第一次后面还有该数就说明重复

var firstUniqChar = function (s) {
  for (let i = 0; i < s.length; i++) {
    let a = s.indexOf(s[i]);
    let b = s.indexOf(s[i], a + 1);
    if (b === -1) {
      return s[i];
    }
  }
  return " ";
};

剑指 Offer 39. 数组中出现次数超过一半的数字【API】

中位数

1
2
3

var majorityElement = function (nums) {
  return nums.sort((a, b) => a - b).splice(nums.length / 2, 1)[0];
};

剑指 Offer 53 - I. 在排序数组中查找数字 I 【API】

code

var search = function (nums, target) {
  return nums.filter((item) => {
    return item === target;
  }).length;
};

剑指 Offer 53 - II. 0 ～ n-1 中缺失的数字【API】

code

var missingNumber = function (nums) {
  let len = nums.length;
  let vsum = ((0 + len) * (len + 1)) / 2;
  let rsum = nums.reduce((pre, cur) => {
    return (cur += pre);
  });
  return vsum - rsum;
};

剑指 Offer 57. 和为 s 的两个数字【双指针】

code 双指针

var twoSum = function (nums, target) {
  let len = nums.length;
  let i = 0;
  let j = len - 1;
  while (i < j) {
    let sum = nums[i] + nums[j];
    if (sum > target) {
      j--;
    } else if (sum < target) {
      i++;
    } else {
      return [nums[i], nums[j]];
    }
  }
};

剑指 Offer 58 - I. 翻转单词顺序【API】

注意条件
code

var reverseWords = function (s) {
  return s
    .trim("")
    .split(" ")
    .filter((item) => {
      return item !== "";
    })
    .reverse()
    .join(" ");
};

剑指 Offer 57 - II. 和为 s 的连续正数序列【双指针】

双指针滑动窗口
初始化左右指针数值为 1，和为 0
循环条件左指针小于目标值一半(比如说目标值 15 一半就是 7.5 左最大只能到 7)
当和小于目标值的时候需要扩大右边界此时和+=右指针右指针++
当和大于目标值需要扩大左边界此时和-=左指针左指针++
当和等于目标值循环嵌入值

var findContinuousSequence = function (target) {
  let list = [];
  let left = 1;
  let right = 1;
  let sum = 0;
  while (left < target / 2) {
    if (sum < target) {
      sum += right;
      right++;
    } else if (sum > target) {
      sum -= left;
      left++;
    } else {
      let arr = [];
      //此时的right已经进位
      for (let i = left; i < right; i++) {
        arr.push(i);
      }
      list.push(arr);
      sum -= left;
      left++;
    }
  }
  return list;
};

剑指 Offer 58 - II. 左旋转字符串【API】

code

1
2
3

var reverseLeftWords = function (s, n) {
  return s.substring(n).concat(s.substring(0, n));
};

剑指 Offer 61. 扑克牌中的顺子

code

var isStraight = function (nums) {
  let nozero = nums.filter((item) => item !== 0);
  let set = new Set(nozero);
  if (set.size !== nozero.length) {
    return false;
  } else {
    if (Math.max(...nozero) - Math.min(...nozero) < 5) {
      return true;
    } else {
      return false;
    }
  }
};

剑指 Offer 62. 圆圈中最后剩下的数字【约瑟夫环】

约瑟夫环
code

var lastRemaining = function(n, m) {
    let curIndex = 0;
    for(ler i=2;i<=n;i++){
        curIndex = (curIndex+m)%i;
    }
    return curIndex
};

剑指 Offer 65. 不用加减乘除做加法【位运算】

先异或计算进位，再位与进位
推导过程 eg 0001+0011=0100

0001^0011 = 0010 //2
0001&0011 = 0001
0001<<1 = 0010 //2
//2+2=4
0010^0010 = 0000 //0
0010&0010 = 0010
0010<<1 = 0100 //4
//0+4=4 条件是b==0截至

所以代码是

var add = function (a, b) {
  while (b !== 0) {
    var c = a ^ b;
    b = (a & b) << 1;
    a = c;
  }
  return a;
};

剑指 Offer 29. 顺时针打印矩阵【API】【矩阵】

定义一个数组 res 为空
四个方向，一次循环右下左上
第一步右 res 直接 concat 目标数组 shift 的内容
第二步下循环遍历目标数组删除目标数组中每一个数组的最后一位并加入 res
注意此时要判断数组是否还存在。
第三步左取出目标数组最后一行 pop 后反转加入 res 此时 res 需要 concat
注意此时要判断数组是否还存在。
第四步上剩余的最后一层到第一层
注意此时要判断数组是否还存在。

var spiralOrder = function (matrix) {
  let res = [];
  while (matrix.length) {
    //右
    res.concat(matrix.shift());
    //下
    for (let i = 0; i < matrix.length; i++) {
      matrix[i].length && res.push(matrix[i].pop());
    }
    //左
    matrix.length && (res = res.concat(matrix.pop().reverse()));
    //上
    for (let i = matrix.length - 1; i > 0; i--) {
      matrix[i].length && res.push(matrix[i].shift());
    }
  }
  return res;
};

剑指 Offer 32 - II. 从上到下打印二叉树 II 【二叉树】

bfs + map 记录

var levelOrder = function (root) {
  let map = {};
  let count = 0;
  const jud = (n, count) => {
    if (!n) return;
    if (!map[count]) {
      map[count] = [n.val];
    } else {
      map[count].push(n.val);
    }
    count++;
    jud(n.left, count);
    jud(n.right, count);
  };
  jud(root, count);
  return [...Object.values(map)];
};

剑指 Offer 55 - I. 二叉树的深度【二叉树】【bfs】

code bfs

var maxDepth = function (root) {
  let max = 0;
  const deep = (n, l) => {
    if (!n) return;
    max = Math.max(l, max);
    deep(n.left, l + 1);
    deep(n.right, l + 1);
  };
  deep(root, 1);
  return max;
};

剑指 Offer 54. 二叉搜索树的第 k 大节点【二叉树】【二叉搜索树】

中序遍历的结果是升序数组反过来就是降序找 k 个就行

var kthLargest = function (root, k) {
  let res;
  const midOrder = (root) => {
    if (!root) return;
    midOrder(root.right);
    k--;
    if (!k) return (res = root.val);
    midOrder(root.left);
  };
  midOrder(root);
  return res;
};

剑指 Offer 55 - II. 平衡二叉树【二叉树】【平衡二叉树】

后序遍历，自下而上，如果遇到了不符合的情况直接剪枝返回-1

var isBalanced = function (root) {
  const post = (n) => {
    if (!n) return 0;
    let left = post(n.left);
    let right = post(n.right);
    if (right < 0 || left < 0) return -1;
    return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1;
  };
  return post(root) != -1;
};

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先【二叉树】【二叉搜索树】【最近公共祖先】

二叉搜索树的概念：
左子树的值恒小于根节点的值
右子树的值恒大于根节点的值
因此对于二叉搜索树的最近公共祖先有三种情况

如果左小于根右大于根则返回根节点
如果左右小于根那么第一个符合值相等条件的就是公共祖先
如果左右大于根那么第一个符合值相等条件的就是公共祖先
注意传入的是节点不是节点值

var lowestCommonAncestor = function (root, p, q) {
  while (root) {
    if (p.val < root.val && q.val < root.val) {
      root = root.left;
    } else if (p.val > root.val && q.val > root.val) {
      root = root.right;
    } else {
      break;
    }
  }
  return root;
};

剑指 Offer 68 - II. 二叉树的最近公共祖先【二叉树】【最近公共祖先】

isLeft 代表左树中有 q 或 p isRight 代表右树中有 q 或 p
isNode 表示此节点为 q 或 p
当左中右其中两个为真那么此节点就是公共祖先

var lowestCommonAncestor = function (root, p, q) {
  let res = root;
  const dfs = (n) => {
    if (!n) return;
    let isLeft = dfs(n.left);
    let isRight = dfs(n.right);
    let isNode = n === p || n === q;
    if ((isLeft && isRight) || (isLeft && isNode) || (isRight && isNode))
      res = n;
    return isLeft || isRight || isNode;
  };
  dfs(root);
  return res;
};

中等题

31. 下一个排列【排列组合】

遍历空出最后两个位置
前后一对，定义 a 为 nums[i]
如果靠后 a 的那个数字小于 a
那么查看此时靠后 a 的数字是否是最后一个如果是直接交换它和 a
如果不是则定义 k 等于 i+1 找到比 a 大的第一个数字因为后面的数字都是降序排列所以用一个 while 就能搞定 (while(a<nums[k+1]){k++})
然后交换 k 和 a
再将 a 后面的数字做升序排列

如果 i 已经是 0 了
那么 nums 反转

var nextPermutation = function (nums) {
  let len = nums.length - 1;
  for (let i = len - 1; i >= 0; i--) {
    let a = nums[i];
    if (a < nums[i + 1]) {
      if (i + 1 === len) {
        [nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
        break;
      }
      let k = i + 1;
      while (a < nums[k + 1]) {
        k++;
      }
      nums[i] = nums[k];
      nums[k] = a;
      let left = i + 1;
      let right = len;
      while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
      }

      break;
    } else if (i === 0) {
      nums.reverse();
    }
  }
};

153. 寻找旋转排序数组中的最小值【双指针】

注意 mid 可以写成left+((right-left)>>1)
如果 left 值等于 right 值说明升序直接返回 nums0
乱序的情况下：
如果 mid 大于 left，right 就来到左边界
如果 mid 小于 left，left 就来到右边界
如果 mid》mid+1 说明 mid+1 是最小值
如果 mid《mid-1 说明 mid 是最小值

var findMin = function (nums) {
  if (!nums.length) return null;
  if (nums.length === 1) return nums[0];
  let left = 0;
  let right = nums.length - 1;
  //升序
  if (nums[left] < nums[right]) {
    return nums[0];
  }
  while (left <= right) {
    let mid = left + ((right - left) >> 1);
    if (nums[mid] > nums[left]) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
    if (nums[mid] > nums[mid + 1]) {
      return nums[mid + 1];
    }
    if (nums[mid] < nums[mid - 1]) {
      return nums[mid];
    }
  }
  return null;
};

33. 搜索旋转排序数组【双指针】

边界条件是 mid===target
如果 left《=mid
且 target》left 小于 mid 说明在左侧 right=mid-1 否则在右侧 left=mid+1
如果 left》mid
且 target》mid 小于 right 说明在右侧 left =mid+1 否则在左侧 right=mid-1

var search = function (nums, target) {
  if (!nums.length) return -1;
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    let mid = left + ((right - left) >> 1);
    if (nums[mid] === target) return mid;
    if (nums[mid] >= nums[left]) {
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
};

81. 搜索旋转排序数组 II 【双指针】

去重思路
如果 numsleft===numsmid 则++left continue

var search = function (nums, target) {
  if (!nums.length) return false;
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    let mid = left + ((right - left) >> 1);
    if (nums[mid] === target) return true;
    if (nums[mid] === nums[left]) {
      ++left;
      continue;
    }
    if (nums[mid] > nums[left]) {
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return false;
};

34. 在排序数组中查找元素的第一个和最后一个位置【双指针】

找到之后判断前面和后面的数

var searchRange = function (nums, target) {
  if (!nums.length) return [-1, -1];
  let left = 0;
  let right = nums.length - 1;
  let mid;
  while (left <= right) {
    mid = left + ((right - left) >> 1);
    if (nums[mid] === target) {
      break;
    }
    if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  if (left > right) {
    return [-1, -1];
  }
  let i = mid,
    j = mid;
  while (nums[i] === nums[i - 1]) i--;
  while (nums[j] === nums[j + 1]) j++;
  return [i, j];
};

39. 组合总和【排列组合】

回溯

var combinationSum = function (nums, target) {
  let res = [];
  const dfs = (idx, path, t) => {
    if (t <= 0) {
      if (t === 0) {
        res.push([...path]);
      }
      return;
    }
    for (let i = idx; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i, path, t - nums[i]);
      path.pop();
    }
  };
  dfs(0, [], target);
  return res;
};

46. 全排列【排列组合】【回溯】

回溯带 used 注意使用方法是new Array(nums.length).fill(false)

var permute = function (nums) {
  let res = [];
  let used = new Array(nums.length).fill(false);
  const dfs = (path) => {
    if (path.length === nums.length) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      path.push(nums[i]);
      used[i] = true;
      dfs(path);
      path.pop();
      used[i] = false;
    }
  };
  dfs([]);
  return res;
};

48. 旋转图像【矩阵】

先对角线交换然后反转。

var rotate = function (matrix) {
  let len = matrix.length;
  for (let i = 0; i < len; i++) {
    for (let j = i; j < len; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  return matrix.map((item) => item.reverse());
};

92. 反转链表 II 【链表】【反转链表】

截取反转再补上注意环

var reverseBetween = function (head, left, right) {
  const reverse = (head) => {
    let cur = head;
    let pre = null;
    while (cur) {
      [cur.next, pre, cur] = [pre, cur, cur.next];
    }121. 买卖股票的最佳时机
    return pre;
  };
  let dummy = new ListNode(-1);
  dummy.next = head;
  let pre = dummy;
  for (let i = 0; i < left - 1; i++) {
    pre = pre.next;
  }
  //12345
  let rightNode = pre;
  for (let i = 0; i < right - left + 1; i++) {
    rightNode = rightNode.next;
  }
  //45
  let leftNode = pre.next; //2345
  let curr = rightNode.next; //5
  pre.next = null; //1 234
  rightNode.next = null; //4 5
  reverse(leftNode); //432
  pre.next = rightNode;
  leftNode.next = curr;
  return dummy.next;
};

165. 比较版本号【API】

var compareVersion = function (version1, version2) {
  let arr1 = version1.split(".");
  let arr2 = version2.split(".");
  for (let i = 0; i < Math.max(arr1.length, arr2.length); i++) {
    if (!arr2[i]) arr2[i] = 0;
    if (!arr1[i]) arr1[i] = 0;
    if (Number(arr1[i]) === Number(arr2[i])) {
      continue;
    } else if (Number(arr1[i]) < Number(arr2[i])) {
      return -1;
    } else if (Number(arr1[i]) > Number(arr2[i])) {
      return 1;
    }
  }
  return 0;
};

647. 回文子串【回文】

我们要知道一个串是否是回文子串
从 i 开头 j 结尾开始
此时 charAt 的 i 和 j 相等就得判断 i+1 和 j-1 是否是相等
或者说当 j-i 小于等于 2 的时候这个时候足够小就可以认为它是回文子串。
所以得出 dp 的条件是dp[i][j] = (j-i<=2)||dp[i+1][j-1]
但是我们要计算dp[i+1][j-1]直接从上到下是不行的，必须 i 从下到上，因此代码为

var countSubstrings = function (s) {
  let len = s.length;
  let dp = new Array(len);
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len).fill(false);
  }
  let count = 0;
  for (let i = len - 1; i >= 0; i--) {
    for (let j = i; j < len; j++) {
      if (s.charAt(i) !== s.charAt(j)) continue;
      dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
      if (dp[i][j]) count++;
    }
  }
  return count;
};

最长回文子串【回文】

回文子串的做法加判断
res 初始化为 s0
如果 dp 为真且j-i+1>res.length的情况下
返回res = s.slice(i,j+1)

var longestPalindrome = function (s) {
  let len = s.length;
  let dp = new Array(len);
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len).fill(false);
  }
  let res = s[0];
  for (let i = len - 1; i >= 0; i--) {
    for (let j = i; j < len; j++) {
      if (s.charAt(i) !== s.charAt(j)) continue;
      dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
      if (dp[i][j] && j - i + 1 > res.length) {
        res = s.slice(i, j + 1);
      }
    }
  }
  return res;
};

22. 括号生成【DFS】

dfs 传入 l，r 和 str 初始的时候 l 和 r 都是 n str 是空串
前两者用于判断左右括号是否害存在
如果左大于 0 l-1 空串加入左括号
如果左小于右那么右括号才能进组 r-1 加入右括号
结束的条件是当空串的长度为 2n 的时候

var generateParenthesis = function (n) {
  let res = []; //空数组放结果
  let len = n * 2; //最大长度
  const dfs = (l, r, str) => {
    if (str.length === len) {
      res.push(str);
      return;
    }
    if (l > 0) {
      dfs(l - 1, r, str + "(");
    }
    if (l < r) {
      dfs(l, r - 1, str + ")");
    }
  };
  dfs(n, n, "");
  return res;
};

55. 跳跃游戏【贪心】【动态规划】

贪心，不必比较每次跳多少，而是是否超过 cover 的距离，如果大于 cover 刷新，如果 cover 已经超出长度则返回 true
跳跃的距离是nums[i]+i

var canJump = function (nums) {
  if (nums.length === 1) return true;
  let cover = nums[0];
  for (let i = 0; i <= cover; i++) {
    cover = Math.max(cover, nums[i] + i);
    if (cover > nums.length - 1) return true;
  }
  return false;
};

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

如果中序遍历的长度不存在或者中序遍历的过程没有值直接返回 null
从前序遍历找到根节点（第一个或者 shift）
此时在中序中找到这个节点，然后新建树
根据中序遍历分类出左子树和右子树
之后左子树加入这个节点之前，右子树在该节点之后
注意新建节点：new TreeNode(xxx)

var buildTree = function (preorder, inorder) {
  const res = (inorder) => {
    if (!inorder || !inorder.length) return null;
    let top = preorder.shift();
    let p = inorder.indexOf(top);
    let tree = new TreeNode(top);
    tree.left = res(inorder.slice(0, p));
    tree.right = res(inorder.slice(p + 1));
    return tree;
  };
  return res(inorder);
};

98. 验证二叉搜索树【二叉树】【二叉搜索树】

如果中序遍历的时候左子树值小于根节点右子树值大于根节点即可。

var isValidBST = function (root, min = -Infinity, max = Infinity) {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return (
    isValidBST(root.left, min, root.val) &&
    isValidBST(root.right, root.val, max)
  );
};

49. 字母异位词分组【哈希表】

哈希表
如何判断abc和bca相等关键在于"bca".split("").sort().toString() //a,b,c
用 map 维护 key 为上述字符串，value 为结果数组的结果集
最后返回[...map.values()]即可

var groupAnagrams = function (str) {
  let map = new Map();
  for (const item of str) {
    let s1 = item.split("").sort().toString();
    let res = map.get(s1) || [];
    res.push(item);
    map.set(s1, res);
  }
  return [...map.values()];
};

56. 合并区间【区间】

先对数组进行排序注意这里是 sort 每个数组的第一位避免出现[1,4],[0,4]这样的比较正确应该是比较[0,4],[1,4]
然后取数组的第一个作为基准 temp 之后遍历数组如果 temp[1]比数组当前项 item 的[0]要大则有交集，
再取两者的右边界最大值为 temp[1]
如果没有交集则 temp 入 res temp 和 item 交换
最后一个也要入 res

思路是对数组的第一个元素进行排序，排序之后的数组取出第一个数组为基准，如果基准数组的末尾元素大于等于下一个比较元素的头元素，说明产生了交集，然后开始合并，合并的第一个元素默认是基准数组的第一位(因为已经排序)，第二个元素就是基准数组和下一个比较数组的末尾元素更大的部分。不产生交集，就将基准数组入栈，下一个比较数组作为基准。最后还要再入栈一次，因为先前入栈的都是基准数组。

var merge = function (intervals) {
  let res = [];
  intervals = intervals.sort((a, b) => a[0] - b[0]);
  let temp = intervals[0];
  for (let i = 1; i < intervals.length; i++) {
    let item = intervals[i];
    if (temp[1] >= item[0]) {
      temp[1] = Math.max(temp[1], item[1]);
    } else {
      res.push(temp);
      temp = item;
    }
  }
  res.push(temp);//最后还要入数组，因为前面没判断第一个数组是否存在。
  return res;
};

62. 不同路径【路径】【动态规划】

用一维数组维护数组

1
2
3

1 1 1
1 2 3
1 3 6 //6是最后答案 那么6是怎么计算出来的呢？

如下：

1 1 1
//step2
1 1+1=2 2+1=3
//step3
1 2+1=3 3+3=6
//6

code

let dp = new Array(m);
dp.fill(1); // 直接从1开始
for (let i = 1; i < n; i++) {
  for (let j = 1; j < m; j++) {
    dp[j] += dp[j - 1];
  }
}
return dp[m - 1];

78. 子集【回溯】

回溯
传递空数组 path，长度 l，开始位置 start。
遍历数组传递初始长度是 i，开始位置是 0 注意 i 要小于等于原数组长度（比如说 123 才能取到 123 否则只有 12 1 这种情况）
当数组长度等于长度的时候 push 到 res 数组里面然后返回（截至条件）
从 start 开始遍历数组传递 concat 当前 numi 项，长度，和 i+1 作为下次的条件

var subsets = function (nums) {
  let res = [];
  const backtrack = (path, l, start) => {
    if (path.length === l) {
      res.push(path);
      return;
    }
    for (let i = start; i < nums.length; i++) {
      backtrack(path.concat(nums[i]), l, i + 1);
    }
  };
  for (let i = 0; i <= nums.length; i++) {
    backtrack([], i, 0);
  }
  return res;
};

79. 单词搜索【DFS】

定二维数组 used 初始化 false
双重循环 dfs
dfs 第一步判断越界情况
第二步标记存在或者不等于该单词 false
定义 res 传入 dfs 四个方向
成功回调改变 used 状态

var exist = function (board, word) {
  let r = board.length;
  let c = board[0].length;
  const used = new Array(r);
  for (let i = 0; i < r; i++) {
    used[i] = new Array(c).fill(false);
  }
  const dfs = (row, col, i) => {
    if (i === word.length) {
      return true;
    }
    if (row < 0 || col < 0 || row === r || col === c) return false;
    if (used[row][col] || board[row][col] !== word[i]) return false;
    used[row][col] = true;
    const res =
      dfs(row + 1, col, i + 1) ||
      dfs(row - 1, col, i + 1) ||
      dfs(row, col + 1, i + 1) ||
      dfs(row, col - 1, i + 1);
    if (res) return true;
    used[row][col] = false;
    return false;
  };
  for (let i = 0; i < r; i++) {
    for (let j = 0; j < c; j++) {
      if (dfs(i, j, 0)) {
        return true;
      }
    }
  }
  return false;
};

75. 颜色分类【双指针】

左右指针

var sortColors = function (nums) {
  let left = 0,
    right = nums.length - 1;
  let cur = 0;
  const swap = (i, j) => {
    [nums[i], nums[j]] = [nums[j], nums[i]];
  };
  while (cur <= right) {
    while (cur >= left && cur <= right && nums[cur] !== 1) {
      if (nums[cur] === 0) swap(cur, left++);
      else if (nums[cur] === 2) swap(cur, right--);
    }
    cur++;
  }
  return nums;
};

64. 最小路径和【路径】

一维数组维护
例子

1 3 1
1 5 1
4 2 1
那么路径表则是
1 4 5
2 7 6
6 8 7//->7

其实是一个一维数组的作用 upset = [0]
状态方程是：Math.min(left,top)+grid[i][j]
注意边界问题

var minPathSum = function (grid) {
  let ret = 0;
  let upset = [0];
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      let top = isNaN(upset[j]) ? Infinity : upset[j];
      let left = isNaN(upset[j - 1]) ? top : upset[j - 1];
      ret = Math.min(top, left) + grid[i][j];
      upset[j] = ret;
    }
  }
  return ret;
};

96. 不同的二叉搜索树【二叉树】【二叉搜索树】

code

var numTrees = function (n) {
  //初始化dp数组，dp[0]也就是一边没有节点（拎起的是第一个或最后一个节点），没有节点的组合应该只有一种
  let dp = [1, 1, 2];
  if (n <= 2) return dp[n];
  //从3个节点开始遍历到n个节点
  for (let i = 3; i <= n; i++) {
    dp[i] = 0;
    //计算出中间节点
    let mid = Math.floor(i / 2);
    //j表示拎起第j个节点
    // 总共i个节点
    // i - j 表示拎起的节点的右边节点的数量
    //  左边节点数量为 i - 1 - (i - j) = j - 1
    for (let j = 1; j <= mid; j++) {
      dp[i] += 2 * dp[i - j] * dp[j - 1];
    }
    //节点数为奇数时要对中间节点特殊处理
    if (i % 2 !== 0) {
      dp[i] += dp[i - (mid + 1)] * dp[i - (mid + 1)];
    }
  }
  return dp[n];
};

114. 二叉树展开为链表【二叉树】

code

var flatten = function (root) {
  if (!root) return;
  // 拍平左右子树为链表
  flatten(root.left);
  flatten(root.right);
  // 保存左右子树
  let left = root.left;
  let right = root.right;
  // 去掉左子树 将右子树变成左子树
  root.left = null;
  root.right = left;
  // 拿到现在的树 将右子树插入
  let p = root;
  while (p.right != null) {
    p = p.right;
  }
  p.right = right;
};

128. 最长连续序列【哈希表】

哈希表建立 set 遇到有 value1-1 就跳过否则就 while 判断是否有 value+1 有就删除避免重复
code

var longestConsecutive = function (nums) {
  let max = 0;
  nums = new Set(nums);
  for (let item of nums) {
    if (nums.has(item - 1)) continue;
    let count = 1; //本身也算
    while (nums.has(item + 1)) {
      nums.delete(item + 1);
      item++;
      count++;
    }
    max = Math.max(max, count);
  }
  return max;
};

142. 环形链表 II 【链表】【环形链表】

先找到 slow 和 fast 交点然后 pre 开始出发和 slow 香蕉则是起点。

var detectCycle = function (head) {
  if (!head || !head.next) return null;
  let slow = head;
  let fast = head;
  let pre = head;
  while (slow && fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      while (pre !== slow) {
        slow = slow.next;
        pre = pre.next;
      }
      return pre;
    }
  }
  return null;
};

148. 排序链表【链表】

code

var sortList = function (head) {
  if (!head) return new ListNode().next;
  const res = [head.val];
  let node = head.next;
  let node2 = head;
  let node3 = node2;
  while (node) {
    res.push(node.val);
    node = node.next;
  }
  res.sort((a, b) => a - b);
  for (let j = 0; j < res.length; j++) {
    node2.val = res[j];
    node2 = node2.next;
  }
  return node3;
};

152. 乘积最大子数组【】

定义 max，curMax 和 curMin 初始化为 nums0
从 1 开始遍历，curmax，curmin 都乘上 numsi
比较 curmax，curmin，numsi 三者最大值和最小值分别赋给 curmax，curmin
如果 max 小于 curmax 交换
返回 max

var maxProduct = function (nums) {
  if (!nums.length) return null;
  let [max, curMax, curMin] = [nums[0], nums[0], nums[0]];
  for (let i = 1; i < nums.length; i++) {
    [curMax, curMin] = [curMax * nums[i], curMin * nums[i]];
    [curMax, curMin] = [
      Math.max(curMax, curMin, nums[i]),
      Math.min(curMax, curMin, nums[i]),
    ];
    if (max < curMax) max = curMax;
  }
  return max;
};

287. 寻找重复数【哈希表】

哈希表

var findDuplicate = function (nums) {
  let set = new Set();
  for (let item of nums) {
    if (set.has(item)) return item;
    set.add(item);
  }
  return -1;
};

剑指 Offer 07. 重建二叉树【二叉树】

根节点是前序的第一个为 top
在中序中 indexof 该节点 p
新建树 tree 根是 top
用 dfs 不断将节点插入 treeleft 和 right 方法是 slice

var buildTree = function (preorder, inorder) {
  const dfs = (inorder) => {
    if (!inorder || !inorder.length) return null;
    let top = preorder.shift();
    let tree = new TreeNode(top);
    let p = inorder.indexOf(top);
    tree.left = dfs(inorder.slice(0, p));
    tree.right = dfs(inorder.slice(p + 1));
    return tree;
  };
  return dfs(inorder);
};

剑指 Offer 04. 二维数组中的查找【二分排序】【API】

方法 1 拍平然后 include

1
2
3

var findNumberIn2DArray = function (matrix, target) {
  return matrix.flat(2).includes(target);
};

方法 2 对每项进行二分

var findNumberIn2DArray = function (matrix, target) {
  for (const item of matrix) {
    let left = 0,
      right = item.length - 1;
    while (left <= right) {
      const mid = left + ((right - left) >> 1);
      if (item[mid] === target) {
        return true;
      } else if (item[mid] > target) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
  }
  return false;
};

剑指 Offer 13. 机器人的运动范围【DFS】

初始化二维数组，未遍历的为 0
设置 dfs 传入 ij，判断越界，已经遍历则直接 return
否则打上标记判断分割的数之和是否小于等于 k
如果是则 count++，往下和往右 dfs

var movingCount = function (m, n, k) {
  const arr = new Array(m).fill().map((_) => new Array(n).fill(0));
  let count = 0;
  const run = (i, j) => {
    if (i >= m || j >= n) return;
    if (arr[i][j]) return;
    arr[i][j] = 1;
    if (bitCount(i) + bitCount(j) <= k) {
      count++;
      run(i + 1, j);
      run(i, j + 1);
    }
  };
  const bitCount = (n) => {
    let res = 0;
    while (n) {
      res += n % 10;
      n = Math.floor(n / 10);
    }
    return res;
  };
  run(0, 0);
  return count;
};

208. 实现 Trie (前缀树) 【前缀树】

code

var Trie = function () {
  this.trie = new Set();
};

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
  this.trie.add(word);
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  if (this.trie.has(word)) {
    return true;
  } else {
    return false;
  }
};

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
  for (let item of this.trie) {
    if (item.startsWith(prefix)) {
      return true;
    }
  }
  return false;
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

406. 根据身高重建队列【其他】

先用 sort 排序第一个数字从大到小，如果相同比较第二个数字按小到大
eg

1
2
3

[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
=>
[ [ 7, 0 ], [ 7, 1 ], [ 6, 1 ], [ 5, 0 ], [ 5, 2 ], [ 4, 4 ] ]

然后用 splice 在 item1 前面添加 item 进行排序
code

var reconstructQueue = function (people) {
  let res = [];
  people.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]));
  console.log(people);
  people.forEach((item) => {
    res.splice(item[1], 0, item);
    console.log(res);
  });
  return res;
};
console.log(
  reconstructQueue([
    [7, 0],
    [4, 4],
    [7, 1],
    [5, 0],
    [6, 1],
    [5, 2],
  ])
)[([7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4])][[7, 0]][([7, 0], [7, 1])][
  ([7, 0], [6, 1], [7, 1])
][([5, 0], [7, 0], [6, 1], [7, 1])][([5, 0], [7, 0], [5, 2], [6, 1], [7, 1])][
  ([5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1])
][([5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1])];

238. 除自身以外数组的乘积【其他】

pre  1 2 3 4
res  1 1 2 6
prod 1 2 6 24
=>
res  24 12 8 6
prod 24 24 12 4

code

var productExceptSelf = function (nums) {
  let res = [];
  let prod = 1;
  for (let i = 0; i < nums.length; i++) {
    res[i] = prod;
    prod *= nums[i];
  }
  prod = 1;
  for (let i = nums.length - 1; i >= 0; i--) {
    res *= prod;
    prod *= nums[i];
  }
  return res;
};

538. 把二叉搜索树转换为累加树【二叉搜索树】【二叉树】

BST 中序遍历为升序列，逆向中序遍历为降序列。
使用一个 sum 变量记录累加和，从大到小（树从右到左）遍历一遍，每次加上结点本身的值即可。

var convertBST = function (root) {
  let sum = 0;
  const inOrderR = (n) => {
    if (!n) return;
    inOrderR(n.right);
    sum += n.val;
    n.val = sum;
    inOrderR(n.left);
  };
  inOrderR(root);
  return root;
};

236. 二叉树的最近公共祖先【二叉树】【最近公共祖先】

新建根 broot dfs 初始化 count
count 增加的条件是当当前值等于 p 或 q 的时候
如果 broot 还不存在
如果此时左子树还有递归左子树找相同 count+=dfs 左
如果 broot 还不在就是说左边没有或者只有一个那么 count+=dfs 右
如果 broot 还不在且 count 找到两个节点那么回源 root 就是他的公共祖先

var lowestCommonAncestor = function (root, p, q) {
  let broot = null;
  const dfs = (n) => {
    if (!n) return;
    let count = 0;
    if (n.val === p.val || n.val === q.val) {
      count++;
    }
    if (!broot) {
      if (n.left) {
        count += dfs(n.left);
      }
      if (!broot && n.right) {
        count += dfs(n.right);
      }
      if (!broot && count === 2) {
        broot = n;
      }
      return count;
    }
  };
  dfs(root);
  return broot;
};

739. 每日温度【单调栈】

单调栈
先看看一个单调栈的做法

// 单调递增栈的实现
let arr = [3, 4, 2, 6, 4, 5, 2, 3];
let res = [];

for (let i = 0; i < arr.length; i++) {
  while (res.length && res[res.length - 1] < arr[i]) {
    res.pop();
  }
  res.push(arr[i]);
  console.log(res);
}
// 6 5 3

过程是

1	[3][4][(4, 2)][6][(6, 4)][(6, 5)][(6, 5, 2)][(6, 5, 3)];

所以本题弹出的时候取到 index 然后res[index] = i-index
注意栈放的是下标

var dailyTemperatures = function (nums) {
  let stack = [];
  let len = nums.length;
  let res = new Array(len).fill(0);
  for (let i = 0; i < len; i++) {
    while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
      let index = stack.pop();
      res[index] = i - index;
    }
    stack.push(i);
  }
  return res;
};

279. 完全平方数【BFS】

bfs

注意 bfs 的技巧是第一次 for 因为后续要带入新的 length，所以不能写i<xxx.length而是要写len=xxx.length;i<len

var numSquares = function (n) {
  let queue = [n];
  let level = 0;
  let visitMap = {};
  while (queue.length) {
    level++;
    for (let i = 0, len = queue.length; i < len; i++) {
      let cur = queue.shift();
      let maxNum = Math.floor(Math.sqrt(cur));
      for (let j = 1; j <= maxNum; j++) {
        let res = cur - j * j;
        if (res === 0) return level;
        if (!visitMap[res]) {
          visitMap[res] = true;
          queue.push(res);
        }
      }
    }
  }
};

347. 前 K 个高频元素【哈希表】

设置 map 对每个元素出现的次数进行维护
然后使用解构和 sort 分类出最大次数的
最后利用 slice+map 返回前 k 高频

var topKFrequent = function (nums, k) {
  let map = new Map();
  nums.forEach((n) => {
    map.set(n, map.has(n) ? map.get(n) + 1 : 1);
  });
  let resArr = [...map].sort((a, b) => b[1] - a[1]);
  return resArr.slice(0, k).map((n) => n[0]);
};

二叉树专栏

99. 恢复二叉树【二叉树】

本来一看，这不就是 BST 的合法性判断然后交换节点吗
于是就写出了这样的代码

const isValidBST = (n,max,min){
    if(!n)return;
    if(!max&&n.val>max.val){
        [max.val,n.val] = [n.val,,max.val];
    }
    if(!min&&n.val<min.val){
        [min.val,n.val] = [n.val,min.val];
    }
    isValidBST(n.left,n,min);
    isValidBST(n.right,max,n);
}

这样大概过了 3/4 的用例吧，因为这样做前提的条件是交换的节点在根和左或者根和右，假如需要交换的节点是左右就不行了，比如 321,根据上面的方法转换出来的是 123 很明显就不对了。

所以换个思路，既然是 BST，那么 BST 的特性中，可以使用到的还有中序遍历。那么我们只要找到冲突的两个节点，并交换，就能解决问题了

那么出发点就到了怎么找到冲突的节点，我们知道，我们判断整个值是否升序在中序之中，可以用一个数组存取，最后按正常的思维捕获。也可以在遍历的过程中，获取上一次的值，来操作

比如 321 这个顺序，我们一看就知道 3 和 1 是冲突的，交换 3 和 1 即可。

那么我们就可以设置一个 prev 变量为空，如果第一次遍历的时候，prev 没有值，就把 3 给 prev

let prev;
if (!prev) {
  prev = n;
}

如果 prev 已经有值了，就拿当前的值和 prev 比较，如果当前值小于 prev，说明这个顺序是降序的，而我们中序是升序的，很明显不符合，此时这个 prev 就是冲突节点，将它放到我们的 first 变量中记录下来。这个 n 就是第二个冲突的节点

else{
    if(n.val<prev.val){
        first = prev;
        second = n;
    }
    prev = n;
}

这里需要注意一点，我们的第一个冲突节点是不能刷新的，第二个冲突节点是可以刷新的。所以我们在创建第一个节点的时候要加一层判断

if (n.val < prev.val) {
  if (!first) {
    first = prev;
  }
  second = n;
}
prev = n;

这样继续遍历，就能找到冲突节点 3 和冲突节点 1，交换就可。

总结：关键在于利用中序遍历的特性，去和上一次的值比较，存入第一个冲突节点，刷新第二个冲突节点

完整 code

var recoverTree = function (root) {
  let first, second, prev;
  const inorder = (n) => {
    if (!n) return null;
    inorder(n.left);
    if (!prev) {
      prev = n;
    } else {
      if (n.val < prev.val) {
        if (!first) {
          first = prev;
        }
        second = n;
      }
      prev = n;
    }
    inorder(n.right);
  };
  inorder(root);
  [first.val, second.val] = [second.val, first.val];
  return root;
};

100. 相同的树【二叉树】

一开始左这个题，emm 不就很简单吗
直接前序遍历开写，然后就发现了一点小问题

比如说[1,null,2]和[1,2]不是相同的树这件事

然后就改代码咯，不要去想一个节点空另外一个节点不是空的情况

如果两个节点都是空说明这两个节点相同，

如果两个节点都不为空，且值相同，且遍历左右子树的结果是 true 就返回真否则假

var isSameTree = function (p, q) {
  if (!p && !q) return true;
  if (
    p &&
    q &&
    p.val === q.val &&
    isSameTree(p.left, q.left) &&
    isSameTree(p.right, q.right)
  ) {
    return true;
  } else {
    return false;
  }
};

当然这题还可以用别的方法，其实就是判断对象是否相等

1	return JSON.stringify(p) === JSON.stringify(q);

108. 将有序数组转为二叉搜索树【二叉树】【二叉搜索树】

这题是关于 BST 的构造的一个题，因为数组是排序好的，所以中间的点就是根节点，然后递归构造即可。注意边界是 nums 为空的时候

var sortedArrayToBST = function (nums) {
  if (nums.length === 0) return null;
  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;
};

109. 有序链表转二叉搜索树【二叉树】

链表转数组，之后做法同上

var sortedListToBST = function (head) {
  if (!head) return null;
  const bstArr = [];
  let cur = head;
  while (cur) {
    bstArr.push(cur.val);
    cur = cur.next;
  }
  const dfs = (nums) => {
    if (nums.length === 0) return null;
    const mid = Math.floor(nums.length / 2);
    const root = new TreeNode(nums[mid]);
    root.left = dfs(nums.slice(0, mid));
    root.right = dfs(nums.slice(mid + 1));
    return root;
  };
  return dfs(bstArr);
};

111. 二叉树最小深度【二叉树】

求最小深度用 bfs，bfs 的核心思路是队列，可以想象成一个面，从一个点开始发散。

var minDepth = function (root) {
  if (!root) return 0;
  const q = [[root, 1]];
  while (q.length) {
    // 解构出q
    const [n, deep] = q.shift();
    if (!n.left && !n.right) {
      return deep;
    }
    if (n.left) q.push([n.left, deep + 1]);
    if (n.right) q.push([n.right, deep + 1]);
  }
};

112. 路径总和【二叉树】

总和使用 dfs 的方法,记得这里最好采用累加判断的方法

var hasPathSum = function (root, targetSum) {
  if (!root) return false;
  let res = false;
  const dfs = (n, sum) => {
    if (!n.left && !n.right && sum === targetSum) {
      res = true;
    }
    if (n.left) dfs(n.left, sum + n.left.val);
    if (n.right) dfs(n.right, sum + n.right.val);
  };
  dfs(root, root.val);
  return res;
};

113. 路径总和 II 【二叉树】

这道题由于要记录路径，要使用外部的 path 来记录路径，也就是要用到 dfs+回溯。

var pathSum = function (root, targetSum) {
  if (!root) return [];
  const res = [];
  const path = [root.val];
  const dfs = (n, sum) => {
    if (!n.left && !n.right && sum === targetSum) {
      res.push([...path]);
    }
    if (n.left) {
      path.push(n.left.val);
      dfs(n.left, sum + n.left.val);
    }
    if (n.right) {
      path.push(n.right.val);
      dfs(n.right, sum + n.right.val);
    }
    path.pop();
  };
  dfs(root, root.val);
  return res;
};

117. 填充每个节点的下一个右侧节点指针 II 【二叉树】

这题给的是一颗二叉树不是完美二叉树所以不能像之前一样简单的递归了，现在使用 bfs 做层序遍历，所以其实这题的关键就在于 null 指针怎么填充，我们知道在每一层空的时候去插入 null，就是这个队列是空的时候，也就是 for 循环中它的 i+1 大于 len 的时候

// 题目返回的是树,所以不需要数组存取
var connect = function (root) {
  if (!root) return null;
  const q = [root];
  while (q.length) {
    let len = q.length;
    for (let i = 0; i < len; i++) {
      const n = q.shift();
      if (i + 1 > len) {
        n.next = null;
      } else {
        n.next = q[0];
      }
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
  }
  return root;
};

107. 二叉树的层序遍历 II 【二叉树】

这道题就是层序遍历翻转

var levelOrderBottom = function (root) {
  if (!root) return [];
  const res = [];
  const q = [root];
  while (q.length) {
    const temp = [];
    const len = q.length;
    for (let i = 0; i < len; i++) {
      const n = q.shift();
      temp.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(temp);
  }
  return res.reverse();
};

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

加判断

var zigzagLevelOrder = function (root) {
  if (!root) return [];
  const res = [];
  const q = [root];
  let isTran = false;
  while (q.length) {
    const temp = [];
    const len = q.length;
    for (let i = 0; i < len; i++) {
      const n = q.shift();
      temp.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    if (isTran) {
      res.push(temp.reverse());
    } else {
      res.push(temp);
    }
    isTran = !isTran;
  }
  return res;
};

144. 二叉树的前序遍历【二叉树】

code

var preorderTraversal = function (root) {
  if (!root) return [];
  const preorder = (n) => {
    if (!n) return;
    res.push(n.val);
    preorder(n.left);
    preorder(n.right);
  };
  const res = [];
  preorder(root);
  return res;
};

145. 二叉树的后序遍历【二叉树】

code

var postorderTraversal = function (root) {
  if (!root) return [];
  const postorder = (n) => {
    if (!n) return;
    postorder(n.left);
    postorder(n.right);
    res.push(n.val);
  };
  const res = [];
  postorder(root);
  return res;
};

129. 求根节点到叶节点数字之和【二叉树】

遍历加回溯，遍历一遍树记录节点，到叶子节点就开始解析累加，然后回溯,这里提供两种方法，一种是数组一种是字符串

var sumNumbers = function (root) {
  if (!root) return null;
  let res = 0;
  const traverse = (n, path) => {
    if (!n) return;
    path += n.val;
    if (!n.left && !n.right) {
      res += parseInt(path.toString());
    }
    traverse(n.left, path);
    traverse(n.right, path);
    path -= n.val;
  };
  traverse(root, "");
  return res;
};

数组

var sumNumbers = function (root) {
  if (!root) return null;
  let res = 0;
  const traverse = (n, path) => {
    if (!n) return;
    path.push(n.val);
    if (!n.left && !n.right) {
      res += parseInt(path.join("").toString());
    }
    traverse(n.left, path);
    traverse(n.right, path);
    path.pop();
  };
  traverse(root, []);
  return res;
};

199. 二叉树的右视图【二叉树】

基本思路 bfs 层序遍历类似于那个填充右侧节点，相同的算法，在 i+1 大于等于 len 的节点添加即可

var rightSideView = function (root) {
  if (!root) return [];
  const q = [root];
  const res = [];
  while (q.length) {
    const n = q.shift();
    let len = q.length;
    for (let i = 0; i < len; i++) {
      if (i + 1 >= len) {
        res.push(n.val);
      }
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
  }
  return res;
};

二叉树的所有路径【二叉树】

常规 dfs 题目也可以采用数组的方式，最后在转为字符串即可

var binaryTreePaths = function (root) {
  if (!root) return [];
  const res = [];
  const dfs = (n, path) => {
    if (!n.left && !n.right) {
      res.push([...path].join(""));
    }
    if (n.left) {
      path.push("->" + n.left.val);
      dfs(n.left, path);
    }
    if (n.right) {
      path.push("->" + n.right.val);
      dfs(n.right, path);
    }
    path.pop();
  };
  dfs(root, [root.val]);
  return res;
};

331. 验证二叉树的前序序列化【二叉树】

code 反向 dfs

var isValidSerialization = function (preorder) {
  const nodearr = preorder.split(",");
  if (!nodearr.length) return false;
  let i = 0;
  const dfs = () => {
    if (i > nodearr.length) return;
    if (nodearr[i] === "#") return;
    i++;
    dfs();
    i++;
    dfs();
  };
  dfs();
  return i == nodearr.length - 1;
};

404. 左叶子之和【二叉树】

左叶子n.left&&!n.left.left&&!n.left.right
code

var sumOfLeftLeaves = function (root) {
  if (!root) return 0;
  let res = 0;
  const dfs = (n) => {
    if (!n) return;
    if (n.left && !n.left.left && !n.left.right) {
      res += n.left.val;
    }
    dfs(n.left);
    dfs(n.right);
  };
  dfs(root);
  return res;
};

429. N 叉树的层序遍历【二叉树】

回顾一下二叉树的层序遍历模板

var levelOrder = function (root) {
  if (!root) return null;
  const q = [root];
  const res = [];
  while (q.length) {
    const temp = [];
    let len = q.length;
    for (let i = 0; i < len; i++) {
      // 提取出每一项,然后放入temp中
      const n = q.shift();
      temp.push(n.val);
      // 再去处理左右
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    // 每次循环结束就保存到res
    res.push(temp);
  }
  return res;
};

我们可以观察到类似的步骤在处理左右的时候，我们现在拥有一颗多叉树，它是不分左右的，它的孩子是个数组，我们只需要处理数组即可。

1
2
3

for (let j = 0; j < n.children.length; j++) {
  q.push(n.children);
}

所以代码就是

var levelOrder = function (root) {
  if (!root) return [];
  const q = [root];
  const res = [];
  while (q.length) {
    const temp = [];
    let len = q.length;
    for (let i = 0; i < len; i++) {
      const n = q.shift();
      temp.push(n.val);
      for (let j = 0; j < n.children.length; j++) {
        q.push(n.children[j]);
      }
    }
    res.push(temp);
  }
  return res;
};

437. 路径总和 III 【二叉树】

用前序遍历加回溯的性质去做这个题，先拿到的

var pathSum = function (root, targetSum) {
  let res = [];
  const dfs = (n, path, sum) => {
    if (!n) return;
    sum += n.val;
    for (let item of path) {
      if (sum - item === targetSum) {
        res++;
        return;
      }
    }
    path.push(n.val);
    dfs(n.left, path, sum);
    dfs(n.right, path, sum);
    sum -= n.val;
    path.pop();
  };
  dfs(root, [], 0);
  return res;
};

88. 合并两个有序数组【二叉树】

双指针逆序
code

var merge = function (nums1, m, nums2, n) {
  let i = m - 1;
  let j = n - 1;
  let end = m + n - 1;
  while (j >= 0) {
    nums1[end--] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
  }
};

前言

1.两数之和 【哈希表】

2.两数相加 【链表】【链表合并】

3.无重复字符的最长字串 【API】

4.寻找两个正序数组的中位数 【API】

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

20.有效的括号 【栈】

21.合并两个有序链表 【链表】【链表合并】

11. 盛最多水的容器 【双指针】

15.三数之和 【双指针】

16.最接近的三数之和 【双指针】

18.四数之和 【双指针】

53.最大子数组和 【动态规划】

70.爬楼梯 【动态规划】

94.二叉树的中序遍历 【二叉树】【中序遍历】

101.对称二叉树 【二叉树】【递归】

104. 二叉树的最大深度 【二叉树】【深度优先】

121. 买卖股票的最佳时机 【动态规划】

136. 只出现一次的数字 【位运算】

226. 翻转二叉树 【二叉树】

141. 环形链表 【链表】【快慢指针】【环形链表】

155. 最小栈 【栈】

160. 相交链表 【链表】

448. 找到所有数组中消失的数字 【API】

169. 多数元素 【API】

283. 移动零 【】

617. 合并二叉树 【二叉树】【合并】

543. 二叉树的直径 【二叉树】

461. 汉明距离 【API】

338. 比特位计数 【API】

剑指 Offer 10- I. 斐波那契数列 【动态规划】

剑指 Offer 10- II. 青蛙跳台阶问题 【动态规划】

剑指 Offer 11. 旋转数组的最小数字 【API】

剑指 Offer 15. 二进制中 1 的个数 【API】

剑指 Offer 17. 打印从 1 到最大的 n 位数 【】

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 【双指针】

剑指 Offer 27. 二叉树的镜像 【二叉树】

剑指 Offer 28. 对称的二叉树 【二叉树】

剑指 Offer 40. 最小的 k 个数 【API】

剑指 Offer 42. 连续子数组的最大和 【动态规划】

剑指 Offer 50. 第一个只出现一次的字符 【API】

剑指 Offer 39. 数组中出现次数超过一半的数字 【API】

剑指 Offer 53 - I. 在排序数组中查找数字 I 【API】

剑指 Offer 53 - II. 0 ～ n-1 中缺失的数字 【API】

剑指 Offer 57. 和为 s 的两个数字 【双指针】

剑指 Offer 58 - I. 翻转单词顺序 【API】

剑指 Offer 57 - II. 和为 s 的连续正数序列 【双指针】

剑指 Offer 58 - II. 左旋转字符串 【API】

剑指 Offer 61. 扑克牌中的顺子

剑指 Offer 62. 圆圈中最后剩下的数字 【约瑟夫环】

剑指 Offer 65. 不用加减乘除做加法 【位运算】

剑指 Offer 29. 顺时针打印矩阵 【API】【矩阵】

剑指 Offer 32 - II. 从上到下打印二叉树 II 【二叉树】

剑指 Offer 55 - I. 二叉树的深度 【二叉树】【bfs】

剑指 Offer 54. 二叉搜索树的第 k 大节点 【二叉树】【二叉搜索树】

剑指 Offer 55 - II. 平衡二叉树 【二叉树】【平衡二叉树】

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 【二叉树】【二叉搜索树】【最近公共祖先】

剑指 Offer 68 - II. 二叉树的最近公共祖先 【二叉树】【最近公共祖先】

中等题

31. 下一个排列 【排列组合】

153. 寻找旋转排序数组中的最小值 【双指针】

33. 搜索旋转排序数组 【双指针】

81. 搜索旋转排序数组 II 【双指针】

34. 在排序数组中查找元素的第一个和最后一个位置 【双指针】

39. 组合总和 【排列组合】

46. 全排列 【排列组合】【回溯】

48. 旋转图像 【矩阵】

92. 反转链表 II 【链表】【反转链表】

165. 比较版本号 【API】

647. 回文子串 【回文】

最长回文子串 【回文】

22. 括号生成 【DFS】

55. 跳跃游戏 【贪心】【动态规划】

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

98. 验证二叉搜索树 【二叉树】【二叉搜索树】

49. 字母异位词分组 【哈希表】

56. 合并区间 【区间】

62. 不同路径 【路径】【动态规划】

78. 子集 【回溯】

79. 单词搜索 【DFS】

1.两数之和【哈希表】

2.两数相加【链表】【链表合并】

3.无重复字符的最长字串【API】

4.寻找两个正序数组的中位数【API】

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

20.有效的括号【栈】

21.合并两个有序链表【链表】【链表合并】

11. 盛最多水的容器【双指针】

15.三数之和【双指针】

16.最接近的三数之和【双指针】

18.四数之和【双指针】

53.最大子数组和【动态规划】

70.爬楼梯【动态规划】

94.二叉树的中序遍历【二叉树】【中序遍历】

101.对称二叉树【二叉树】【递归】

104. 二叉树的最大深度【二叉树】【深度优先】

121. 买卖股票的最佳时机【动态规划】

136. 只出现一次的数字【位运算】

226. 翻转二叉树【二叉树】

141. 环形链表【链表】【快慢指针】【环形链表】

155. 最小栈【栈】

160. 相交链表【链表】

448. 找到所有数组中消失的数字【API】

169. 多数元素【API】

283. 移动零【】

617. 合并二叉树【二叉树】【合并】

543. 二叉树的直径【二叉树】

461. 汉明距离【API】

338. 比特位计数【API】

剑指 Offer 10- I. 斐波那契数列【动态规划】

剑指 Offer 10- II. 青蛙跳台阶问题【动态规划】

剑指 Offer 11. 旋转数组的最小数字【API】

剑指 Offer 15. 二进制中 1 的个数【API】

剑指 Offer 17. 打印从 1 到最大的 n 位数【】

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面【双指针】

剑指 Offer 27. 二叉树的镜像【二叉树】

剑指 Offer 28. 对称的二叉树【二叉树】

剑指 Offer 40. 最小的 k 个数【API】

剑指 Offer 42. 连续子数组的最大和【动态规划】

剑指 Offer 50. 第一个只出现一次的字符【API】

剑指 Offer 39. 数组中出现次数超过一半的数字【API】

剑指 Offer 53 - II. 0 ～ n-1 中缺失的数字【API】

剑指 Offer 57. 和为 s 的两个数字【双指针】

剑指 Offer 58 - I. 翻转单词顺序【API】

剑指 Offer 57 - II. 和为 s 的连续正数序列【双指针】

剑指 Offer 58 - II. 左旋转字符串【API】

剑指 Offer 62. 圆圈中最后剩下的数字【约瑟夫环】

剑指 Offer 65. 不用加减乘除做加法【位运算】

剑指 Offer 29. 顺时针打印矩阵【API】【矩阵】

剑指 Offer 55 - I. 二叉树的深度【二叉树】【bfs】

剑指 Offer 54. 二叉搜索树的第 k 大节点【二叉树】【二叉搜索树】

剑指 Offer 55 - II. 平衡二叉树【二叉树】【平衡二叉树】

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先【二叉树】【二叉搜索树】【最近公共祖先】

剑指 Offer 68 - II. 二叉树的最近公共祖先【二叉树】【最近公共祖先】

31. 下一个排列【排列组合】

153. 寻找旋转排序数组中的最小值【双指针】

33. 搜索旋转排序数组【双指针】

34. 在排序数组中查找元素的第一个和最后一个位置【双指针】

39. 组合总和【排列组合】

46. 全排列【排列组合】【回溯】

48. 旋转图像【矩阵】

165. 比较版本号【API】

647. 回文子串【回文】

最长回文子串【回文】

22. 括号生成【DFS】

55. 跳跃游戏【贪心】【动态规划】

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

98. 验证二叉搜索树【二叉树】【二叉搜索树】

49. 字母异位词分组【哈希表】

56. 合并区间【区间】

62. 不同路径【路径】【动态规划】

78. 子集【回溯】

79. 单词搜索【DFS】

64. 最小路径和【路径】

96. 不同的二叉搜索树【二叉树】【二叉搜索树】

114. 二叉树展开为链表【二叉树】

128. 最长连续序列【哈希表】

148. 排序链表【链表】

152. 乘积最大子数组【】

287. 寻找重复数【哈希表】