大纲 ​

数据结构： 链表、 数组、 字符串、 栈、 队列、 树、 图、 散列表

基础算法： 排序、 双指针、 遍历查找、 回溯、 动态规划、 贪心、 分治、 位运算、 数学 正则

排序算法 ​

• 插入排序
• 希尔排序
• 选择排序
• 冒泡排序
• 归并排序
• 快速排序
• 堆排序
• 基数排序
• 165.比较版本号

双指针 ​

双指算法是基于暴力解法的优化，是指用两个变量在线性结构上遍历而解决的问题。

• 对于数组，指两个变量在数组上相向移动解决的问题；
• 对于链表，指两个变量在链表上同向移动解决的问题，也称为「快慢指针」问题。

算法练习

• 350.两个数组的交集 II
• 11.盛最多水的容器
• 15.三数之和
• 18.四数之和
• 42.接雨水
• 344.反转字符串
• 61.旋转链表
• 141.环形链表
• 234.回文链表

遍历查找 ​

// 一维数组遍历
for (let i = 0; i < array.length; i++) {
    const el = array[i];
}
// 矩阵数组横向遍历
for (let row = 0; row < array.length; row++) {
    for (let col = 0; col < array[row].length; col++) {
        const el = matrix[row][col];
    }
}
// 矩阵数组纵向遍历
for (let col = 0; i < array[0].length; i++) {
    for (let row = 0; row < array.length; row++) {
        let el = matrix[col][row];
    }
}
// 单向链表遍历
while (root) {
    root = root.next;
}
// 双向链表反向遍历
while (tail) {
    tail = tail.prev;
}

// 一维数组遍历
for (let i = 0; i < array.length; i++) {
    const el = array[i];
}
// 矩阵数组横向遍历
for (let row = 0; row < array.length; row++) {
    for (let col = 0; col < array[row].length; col++) {
        const el = matrix[row][col];
    }
}
// 矩阵数组纵向遍历
for (let col = 0; i < array[0].length; i++) {
    for (let row = 0; row < array.length; row++) {
        let el = matrix[col][row];
    }
}
// 单向链表遍历
while (root) {
    root = root.next;
}
// 双向链表反向遍历
while (tail) {
    tail = tail.prev;
}

算法练习

• 498.矩阵对角线遍历
• 318.二叉树的前序遍历
• 317.二叉树的中序遍历
• 316.二叉树的后序遍历
• 315.二叉树的层序遍历
• 314.二叉树的垂直遍历

二叉树遍历 ​

• 深度优先 DFS (DeepFirstSearch) ： 节点访问顺序是 1242521363731

  • 前序遍历(根左右): 1245367
  js

  // 递归 recursive
  function fn(root) {
      let res = [];
      function loop(node) {
          if (node === null) return;
          res.push(node.val);
          fn(node.left);
          fn(node.right);
      }
      loop(root);
      return res;
  }
  // 迭代 iterative
  function fn2(root) {
      if (root === null) return [];
      let res = [];
      let node = root;
      let list = [root]; // 根进栈
      while (list.length) {
          node = list.pop(); // 回溯
          res.push(node.val); // 记录
          node.right && list.push(node.right); // 右进栈，先进后出 ,后记录右
          node.left && list.push(node.left); // 左进栈，后进先出, 先记录左
      }
      return res;
  }

  // 递归 recursive
  function fn(root) {
      let res = [];
      function loop(node) {
          if (node === null) return;
          res.push(node.val);
          fn(node.left);
          fn(node.right);
      }
      loop(root);
      return res;
  }
  // 迭代 iterative
  function fn2(root) {
      if (root === null) return [];
      let res = [];
      let node = root;
      let list = [root]; // 根进栈
      while (list.length) {
          node = list.pop(); // 回溯
          res.push(node.val); // 记录
          node.right && list.push(node.right); // 右进栈，先进后出 ,后记录右
          node.left && list.push(node.left); // 左进栈，后进先出, 先记录左
      }
      return res;
  }

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  
  • 中序遍历(左根右): 4251637
  js

  // 递归 recursive
  function fn(root) {
      let res = [];
      function loop(node) {
          if (node === null) return;
          fn(node.left);
          res.push(node.val);
          fn(node.right);
      }
      loop(root);
      return res;
  }
  // 迭代 iterative
  function fn2(root) {
      if (root === null) return [];
      let res = [];
      let list = [];
      while (root) {
          let node = list.shift(); // stack 栈先进先出
          stack.push(root.left);
          res.push(root.val);
          stack.push(root.right);
      }
      return res;
  }

  // 递归 recursive
  function fn(root) {
      let res = [];
      function loop(node) {
          if (node === null) return;
          fn(node.left);
          res.push(node.val);
          fn(node.right);
      }
      loop(root);
      return res;
  }
  // 迭代 iterative
  function fn2(root) {
      if (root === null) return [];
      let res = [];
      let list = [];
      while (root) {
          let node = list.shift(); // stack 栈先进先出
          stack.push(root.left);
          res.push(root.val);
          stack.push(root.right);
      }
      return res;
  }

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  
  • 后序遍历(左右根): 4526731
  js

  // 递归 recursive
  function fn(root) {
      let res = [];
      function loop(node) {
          if (node === null) return;
          fn(node.left);
          fn(node.right);
          res.push(node.val);
      }
      loop(root);
      return res;
  }
  // 迭代 iterative
  function fn2(root) {
      let res = [];
      let list = [];
      while (root) {
          if (root === null) return;
          let node = list.shift(); // stack 栈先进先出
          stack.push(root.right, root.left);
          res.push(root.val);
          stack.push(root.right);
      }
      return res;
  }

  // 递归 recursive
  function fn(root) {
      let res = [];
      function loop(node) {
          if (node === null) return;
          fn(node.left);
          fn(node.right);
          res.push(node.val);
      }
      loop(root);
      return res;
  }
  // 迭代 iterative
  function fn2(root) {
      let res = [];
      let list = [];
      while (root) {
          if (root === null) return;
          let node = list.shift(); // stack 栈先进先出
          stack.push(root.right, root.left);
          res.push(root.val);
          stack.push(root.right);
      }
      return res;
  }

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  

• 广度优先 BFS (BreadthFirstSearch)：节点访问顺序是 11232345674567

  • 层序遍历(层左右): 1234567
  js

  var levelOrder = function (root) {
      if (root === null) return [];
      let list = [root];
      let res = [];
      while (list.length) {
          let n = list.length;
          let cList = [];
          for (let i = 0; i < n; i++) {
              let node = list.shift(); // 前出
              cList.push(node.val); // 层顺序记录
              node.left && list.push(node.left); // 后入
              node.right && list.push(node.right); // 后入
          }
          res.push(cList);
      }
      return res;
  };

  var levelOrder = function (root) {
      if (root === null) return [];
      let list = [root];
      let res = [];
      while (list.length) {
          let n = list.length;
          let cList = [];
          for (let i = 0; i < n; i++) {
              let node = list.shift(); // 前出
              cList.push(node.val); // 层顺序记录
              node.left && list.push(node.left); // 后入
              node.right && list.push(node.right); // 后入
          }
          res.push(cList);
      }
      return res;
  };

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  

动态规划 ​

动态规划，英文：Dynamic Programming，简称 DP， 如果某一问题有很多重叠子问题，使用动态规划是最有效的。 所以动态规划中每一个状态一定是由上一个状态推导出来的。

解题步骤

1. 确定 dp 数组（dp table）以及下标的含义
2. 确定递推公式
3. dp 数组如何初始化
4. 确定遍历顺序
5. 举例推导 dp 数组

解题练习

• 基础题目
  • 62.不同路径
  • 70.爬楼梯
  • 118.杨辉三角
  • 509.斐波那契数
• 背包问题
  • 01 背包
  • 完全背包
• 打家劫舍
  • 198 打家劫舍
  • 213 打家劫舍 2
  • 337 打家劫舍 3
• 股票问题
  • 121.买卖股票的最佳时机
  • 122.买卖股票的最佳时机 2
  • 123.买卖股票的最佳时机 3
• 子序列问题
  • 718.最长重复子数组
  • 1143.最长公共子序列

回溯算法 ​

回溯算法是暴力算法，具体表现是 N 叉树的递归遍历，存在固定程序模版：

function backtracking(list = []) {
    let res = []; // 全部结果
    let cache = {}; // 递归条件的依赖数据
    function recursion(arr = []) {
        // 递归终止条件
        if (arr.length === list.length) {
            // 保存递归得到的一种结果
            res.push(arr.slice());
            return;
        }
        // 遍历元素
        for (let i = 0; i < list.length; i++) {
            let value = list[i];
            if (cache[i]) {
                // 处理元素
                cache[i] = true;
                arr.push(value);
                // 递归处理
                recursion(递归参数);
                // 回溯处理
                arr.pop();
                delete cache[i];
            }
        }
    }
    recursion([]);
    return res;
}

function backtracking(list = []) {
    let res = []; // 全部结果
    let cache = {}; // 递归条件的依赖数据
    function recursion(arr = []) {
        // 递归终止条件
        if (arr.length === list.length) {
            // 保存递归得到的一种结果
            res.push(arr.slice());
            return;
        }
        // 遍历元素
        for (let i = 0; i < list.length; i++) {
            let value = list[i];
            if (cache[i]) {
                // 处理元素
                cache[i] = true;
                arr.push(value);
                // 递归处理
                recursion(递归参数);
                // 回溯处理
                arr.pop();
                delete cache[i];
            }
        }
    }
    recursion([]);
    return res;
}

回溯算法练习

• 组合问题
  • 77.组合
  • 216.组合总和 III
  • 17.电话号码的字母组合
  • 39.组合总和
  • 40.组合总和 II
• 分割问题
  • 131.分割回文串
  • 93.复原 IP 地址
• 子集问题
  • 78.子集
  • 90.子集 II
• 排列问题
  • 46.全排列
  • 47.全排列 II
• 棋盘问题
  • 51.N 皇后
  • 37.解数独
• 其他
  • 491.递增子序列
  • 332.重新安排行程

贪心算法 ​

贪心算法（又称贪婪算法）无固定套路，就是思考如何通过局部最优，推出整体最优。

• 举一个例子，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？ 指定每次拿最大的，最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

• 再举一个例子，有一堆盒子，你有一个背包体积为 n，如何把背包尽可能装满， 如果还每次选最大的盒子，就不行了。这时候就需要动态规划。

在对问题求解时，总是做出在当前看来是最好的选择，就能得到问题的答案。 贪心算法不是对所有问题都能得到整体最优解。 能使用贪心算法解决的问题必须具备「无后效性」， 即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

算法练习

• 122.买卖股票的最佳时机 II
• 11.盛最多水的容器
• 55.跳跃游戏
• 455.分发饼干
• 561.数组拆分
• 678.有效的括号字符串

分治算法 ​

分治法是构建基于多项分支递归的一种很重要的算法范式。字面上的解释是「分而治之」， 就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解， 原问题的解即子问题的解的合并。

这个技巧是很多高效算法的基础，如排序算法（快速排序、归并排序）、傅立叶变换（快速傅立叶变换）。

算法练习

• 4.寻找两个正序数组的中位数
• 169.多数元素
• 912.排序数组
• 105.从前序与中序遍历序列构造二叉树

正则 ​

算法练习

• 1410.HTML 实体解析器
• 10.正则表达式匹配
• 125.验证回文串
• 394.字符串解码

参考资料 ​

• 图解算法数据结构