常用算法思想

本篇文章可以收获的知识：

什么是分而治之
什么是动态规划
什么是贪心算法
什么是回溯算法
九道LeetCode算法题巩固常用算法思想
如何分析时间复杂度和空间复杂度

分而治之

分而治之是一种算法设计思想，不是数据结构也不是一种算法，它将一个问题分成多个和原问题相似的小问题，再将结构合并以解决原来的问题。

在排序算法中，归并排序和快速排序使用的就是分而治之的思想，归并排序：分：把数组从中间一分为二，解：递归地对两个子数组进行排序，合：合并有序子数组，快速排序：分：选基准，按基准把数组分成两个子数组，解：递归地对两个子数组进行快速排序，合：对两个子数组进行合并。

动态规划

动态规划是一种算法设计思想，不是数据结构也不是一种算法，它将一个问题分解为相互重叠的子问题，通过反复求解子问题，来解决原来的问题。

使用动态规划解决斐波那契数列问题：1、定义子问题：F(n) = F(n - 1) + f(n - 2)，2、反复执行：从2循环到n，执行公示。

动态规划和分而治之的区别：子问题是独立的是分而治之，子问题是重叠的是动态规划。

贪心算法

贪心算法是一种算法设计思想，不是数据结构也不是一种算法，期盼通过每个阶段的局部最优选择，从而达到全局的最优，但是结果并不一定是最优的。

通过一个例子认识贪心算法：

// 零钱兑换
const coins = [1, 2, 5]
const amount = 11
// 11 = 5 + 5 + 1
// 输出的是3，这个时候的贪心算法满足最优结果

const coins = [1, 3, 4]
const amount = 6
// 输出3
// 6 = 4 + 1 + 1
// 这时候贪心算法不是最优解

通过上面的例子，不难知道贪心算法得到的结果并不一定是最优解，但是并不能说贪心算法不能用，在某些场景下是可以使用贪心算法的，后面的算法题中会有贪心算法的解决方案。

回溯算法

回溯算法是一种算法设计思想，不是数据结构也不是一种算法，是一种渐进式寻找并构建问题解决方式的策略，会从一个可能的动作开始解决问题，如果不行，就会回溯并选择另一个动作，直到将问题解决。

什么问题适合用回溯算法：有很多路，这些路里，有死路，也有出路，通常需要递归来模拟所有的路。

通过文字理解算法思想有点难理解，下面通过算法题来深入了解算法思想的使用。

LeetCode算法题：题号100，相同的树

解题思路：

两个树：根结点相同，左子树相同，右子树相同
符合：“分、解、合”特性
考虑使用分而治之

解题步骤：

分：获取两个树的左子树和右子树
解：递归地判断两个树的左子树是否相同，右子树是否相同
合：将上述结果合并，如果根结点也相同，树就相同

代码实现：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
  const isSame = (t1, t2) => {
    if (!t1 && !t2) {
      return true
    }

    if (
      t1 &&
      t2 &&
      t1.val === t2.val &&
      isSameTree(t1.left, t2.left) &&
      isSameTree(t1.right, t2.right)
    ) {
      return true
    }
    
    return false
  }

  return isSame(p, q)
}

代码中使用了递归，递归的次数最大是树的节点树，所以时间复杂度是O(n)，n是树的节点树。

代码中虽然没有定义线性增长的数据结构，但是有递归，递归的堆栈最大是树的高度，树均匀分布的情况下是logn，所以空间复杂度是O(n)或者是O(logn)。

LeetCode算法题：题号101，对称二叉树

解题思路：

转化为：左子树和右子树是否镜像
分解为：左子树的左节点是否和右子树的右节点镜像并且左子树的右节点是否和右子树的左节点镜像
符合分、解、合特性，使用分而治之

解题步骤：

分：获取树的左子树和右子树
解：递归地判断左子树的左节点是否和右子树的右节点镜像并且左子树的右节点是否和右子树的左节点镜像
合：如果上述都成立，且根节点相同，两个树就镜像

代码实现：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
  if (!root) {
    return true
  }
  const isMirror = (left, right) => {
    if (!left && !right) {
      return true
    }
    if (
      left &&
      right &&
      left.val === right.val &&
      isMirror(left.left, right.right) &&
      isMirror(left.right, right.left)
    ) {
      return true
    }
    return false
  }
  return isMirror(root.left, root.right)
}

代码中使用了递归，递归的最大次数是树的节点树，所以时间复杂度是O(n)，n是树的节点树。

代码中虽然没有使用线性增长的数据结构，但是使用了递归，递归的调用堆栈最大是树的高度，树均匀分布的情况下是logn，所以空间复杂度是O(n)或者O(logn)。

LeetCode算法题：题号226，翻转二叉树

解题思路：

先翻转左右子树，再将子树换个位置
符合“分、解、合”特性
考虑使用分而治之

解题步骤：

分：获取左右子树
解：递归地翻转左右子树
将翻转后的左右子树换个位置放到根结点上

代码实现：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
  if (!root) return null
  return {
    val: root.val,
    left: invertTree(root.right),
    right: invertTree(root.left),
  }
}

代码中使用了递归，递归的最大次数是树的节点树，所以时间复杂度是O(n)，n是树的节点树。

LeetCode算法题：题号70，爬楼梯

解题思路：

第n阶可以在第n - 1阶爬1个台阶，或者在n - 2阶爬2个台阶
F(n) = F(n - 1) + F(n - 2)
使用动态规划

解题步骤：

定义子问题：F(n) = F(n - 1) + F(n - 2)
反复执行：从2循环到n，执行上述公式

代码实现：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n <= 1) {
    return 1
  }
  let dp0 = 0
  let dp1 = 1
  for (let i = 1; i <= n; i++) {
    const tmp = dp0
    dp0 = dp1
    dp1 = tmp + dp1
  }
  return dp1
}

代码中使用了for循环，循环的次数是n，所以时间复杂度是O(n)。

代码中没有用到线性增长的数据结构，所以空间复杂度是O(1)。

LeetCode算法题：题号198，打家劫舍

实现思路：

f(k) = 从前k个房屋中能偷窃到的最大金额
ak = 第k个房屋的金额
f(k) = Math.max(ak + f(k - 2), f(k - 1))
考虑使用动态规划

解题步骤：

定义子问题：f(k) = Math.max(ak + f(k - 2), f(k - 1))
反复执行：从数组的第二位循环到n，执行上述公式

代码实现：

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  if (!nums.length) return 0
  let dp0 = 0
  let dp1 = nums[0]
  for (let i = 1; i < nums.length; i++) {
    const dp2 = Math.max(nums[i] + dp0, dp1)
    dp0 = dp1
    dp1 = dp2
  }
  return dp1
}

代码中使用了for循环，循环的次数是数组的长度减2，所以时间复杂度是O(n)。

代码中没有用到线性增长的数据结构，所以空间复杂度是O(1)。

LeetCode算法题：题号455，分发饼干

解题思路：

局部最优：既能满足孩子，还消耗的饼干最少
先将“较小的饼干”分给“胃口最小”的孩子
考虑使用贪心算法

解题步骤：

对饼干数组和胃口数组进行升序
遍历饼干数组，找到能满足胃口最小的孩子的饼干
遍历结束后返回返回结果

代码实现：

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function (g, s) {
  const sortFn = (a, b) => a - b
  g.sort(sortFn)
  s.sort(sortFn)
  let i = 0
  s.forEach((n) => {
    if (n >= g[i]) {
      i += 1
    }
  })
  return i
}

代码中使用了foreach循环，循环的次数是饼干数组的长度，所以时间复杂度是O(n)。

代码中没有用到线性增长的数据结构，所以空间复杂度是O(1)。

LeetCode算法题：题号122，买卖股票的最佳时机 II

解题思路：

前提：上帝视角，找到未来的价格
局部最优：见好就收，见差就不动，不做任何长远的打算
考虑使用贪心算法

解题步骤：

新建一个变量，用来统计总利润
遍历价格数组，如果当前价格比昨天高，就在昨天买，今天卖，否者不交易
遍历结束后返回总利润

代码实现：

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

代码中使用了for循环，循环的次数是数组的长度减1，所以时间复杂度是O(n)。

代码中没有用到线性增长的数据结构，所以空间复杂度是O(1)。

LeetCode算法题：题号46，全排列

解题思路：

要求：1、所有排列情况，2、没有重复元素
有出路、有死路
考虑使用回溯算法

解题步骤：

用递归模拟出所有的情况
遇到包含重复元素的情况，就回溯
手机所有到达递归终点的情况，并返回

代码实现：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const res = []
  const backtrack = (path) => {
    if (path.length === nums.length) {
      res.push(path)
      return
    }
    nums.forEach((c) => {
      if (path.includes(c)) {
        return
      }
      backtrack(path.concat(c))
    })
  }
  backtrack([])
  return res
}

代码中有foreach循环并且内嵌递归，正常不做return的情况下，时间复杂度是O(n^2)，但是由于重复元素不进行递归，所以会发现一个规律，每一个满足的元素进行1x2x3x4...n循环，所以时间复杂度是O(n!)。

代码中虽然没有使用线性增长的数据结构，但是使用了递归，递归的最大堆栈是数组的长度，所以空间复杂度是O(n)。

LeetCode算法题：题号78，子集

解题思路：

要求：1、所有子集，2、没有重复元素
有出路、有死路
考虑使用回溯算法

解题步骤：

用递归模拟所有情况
保证后面接的数字都是后面的数字
收集所有到达递归终点的情况，并返回

代码实现：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const res = []
  const backtrack = (path, l, s) => {
    if (path.length === l) {
      res.push(path)
      return
    }
    for (let i = s; 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
}

代码中for循环嵌套递归，递归里面的时间复杂度是2^{n，因为每个元素只有存在和不存在的可能性，所以时间复杂度是O(n*2}n)。

代码中使用到了递归，递归的堆栈大小是数组的大小，所以空间复杂度是O(n)。

最后，希望读者可以通过本篇文章对常用算法思想有一定的认识和觉悟。。。。。。

分而治之

动态规划

贪心算法

回溯算法

LeetCode算法题：题号100，相同的树

LeetCode算法题：题号101，对称二叉树

LeetCode算法题：题号226，翻转二叉树

LeetCode算法题：题号70， 爬楼梯

LeetCode算法题：题号198，打家劫舍

LeetCode算法题：题号455，分发饼干

LeetCode算法题：题号122，买卖股票的最佳时机 II

LeetCode算法题：题号46，全排列

LeetCode算法题：题号78，子集

排序与搜索

LeetCode算法题：题号70，爬楼梯