算法分享

递归 Recursion

指在函数的定义中使用函数自身的方法

本身其实没啥好讲的

解题

递归乘法

解 1：

// 容易堆栈溢出
// 判断 A B 大小减少递归次数
const multiplyRecursionAdd = function(A, B) {
    if (A === 0) {
        return 0
    }
    return B + multiply(A - 1, B)
}

解2:

9 * 10 =

(4 * 10) + (5 * 10) =

(4 * 10) + (4 * 10) + 10 =

const multiply = function (A, B) {
  // 减少递归次数
  if (A > B) {
    return calculate(B, A)
  }
  return calculate(A, B)
}

const calculate = function (a, b) {
  if (a == 0) {
    return 0
  }
  if (a == 1) {
    return b
  }
  const halfA = a >> 1
  const halfAResult = calculate(halfA, b)
  return halfAResult + halfAResult + (a & 1 == 1 ? b : 0);
}

代码框架

function Foo (p) {
    // 边界条件
    if p then
        return
    end if
    // 调用自身递归
    Foo(p)
}

可以 get 的点

边界条件

工具函数，先处理边界（异常）逻辑，之后的逻辑就都是正常逻辑。

处理方式包括但不限于 return、throw

树 Tree

树是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n (n > 0) 个有限节点组成一个具有层次关系的集合。

树的分类

二叉树
- 平衡二叉树
- 二叉查找树
- 平衡二叉查找树
  - AVL 树
  - 红黑树
- 完全二叉树
- 满二叉树
多路查找树
堆
- 大/小顶堆
- ...
...

推荐练习题目

二叉树的中序遍历 N叉树的后序遍历二叉树的层序遍历二叉树的最大深度

进阶

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

...

前序遍历：ABDECFG 中序遍历：DBEAFCG 后序遍历：DEBFGCA 层序遍历：ABCDEFG

前序遍历（先序遍历）：自顶向下，从左往右

/**
 * 前序遍历 -- 递归写法
 */
function preOrder(TreeNode root) {
    if root == null then
        return
    end if
    
    // TODO: 前序遍历
    inOrder(root.left);
    inOrder(root.right);
}

/**
 * 前序遍历 -- 利用栈 迭代
 */
class Solution {
    void preOrder(TreeNode root) {
    }
}

中序遍历

如果是二叉搜索树，在中序遍历的结果就是递增排序

/**
 *  
 */
function inOrder(TreeNode root) {
    if root == null then
        return
    end if
        
    inOrder(root.left);
    // TODO 中序遍历
    inOrder(root.right);
}

/**
 * 中序遍历 -- 利用栈 迭代
 */
function inOrder(TreeNode root) {
    stack <- new Stack()
    current = root
       
    while current != null or !stack.isEmpty() do
        while current != null do
            stack.push(curr);
            curr = curr.left;
        end

        curr = stack.pop();
        // TODO 中序遍历
        curr = curr.right;
    end
}

后序遍历

/**
 * 后序遍历 -- 递归写法
 */
function postOrder(TreeNode root) {
    if root == null then
        return
    end if
        
    inOrder(root.left);
    inOrder(root.right);
    // TODO 后序遍历
}

/**
 * 后序遍历 -- 利用栈 迭代
 */
function postOrder (root) {
  const stack = [];
  let prev = null;

  while (root != null || stack.length > 0) {
    while (root != null) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    if (root.right == null || root.right === prev) {
      // TODO: 后序遍历
      prev = root
      root = null
    } else {
      stack.push(root)
      root = root.right
    }
  }
}

层序遍历

/**
 * 层序遍历 -- 利用队列辅助
 */
class Solution {
    void levelOrder(TreeNode root) {
    }
}

题解

二叉树的最大深度

var maxDepth = function(root) {
  if (root == null) {
    return 0
  }
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}

动态规划（Dynamic Programming）入门 - 背包问题

题目

斐波那契数

零钱兑换

进阶

零钱兑换 II

从斐波那契数开始入门

暴力解法

function fib (N) {
    if (N === 1 || N === 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

借助哈希表存储结果

class SolutionWithHashMap {
  public int fib(int N) {
    if (N < 1) {
      return 0;
    }

    HashMap<Integer, Integer> memo = new HashMap<>();

    return helper(memo, N);
  }

  int helper (HashMap<Integer, Integer> memo, int N) {
    if (N == 0) {
      return 0;
    }
    if (N == 1 || N == 2) {
      return 1;
    }

    if (memo.get(N) != null) {
      return memo.get(N);
    }
    memo.put(N, helper(memo, N - 1) + helper(memo, N - 2));
    return memo.get(N);
  }
}

使用 dp table 存储

class SolutionWithDpTable {
  public int fib(int N) {
    ArrayList<Integer> dp = new ArrayList<>(N + 1);

    dp.add(0);
    dp.add(1);
    dp.add(1);

    for (int i = 3; i <= N; i++) {
      dp.add(dp.get(i - 1) + dp.get(i - 2));
    }
    return dp.get(N);
  }
}

状态压缩，因为每次只用到了 dp table 的最后两个

class Solution {
  public int fib(int N) {
    if (N == 0) return 0;
    if (N == 1 || N == 2) return 1;

    int prev = 1;
    int curr = 1;

    for (int i = 3; i <= N; i++) {
      int sum = prev + curr;
      prev = curr;
      curr = sum;
    }
    return curr;
  }
}

零钱兑换

暴力解法

/**
 * 暴力遍历
 */
class SolutionDp {
  public int coinChange(int[] coins, int amount) {
    if (amount == 0) {
      return 0;
    }
    return getMinCoinNumber(coins, amount, 0);
  }

  int getMinCoinNumber (int[] coins, int amount, int num) {
    int res = Integer.MAX_VALUE;
    int nothingNum = 0;

    for (int i = 0; i < coins.length; i++) {
      int nextAmount = amount - coins[i];

      if (nextAmount == 0) {
        res = Math.min(res, num + 1);
      } else if (nextAmount < 0) {
        // -1
        nothingNum += 1;
      } else {
        res = Math.min(res, getMinCoinNumber(coins, nextAmount, num + 1));
      }
    }
    if (nothingNum == coins.length) {
      return -1;
    }
    return res;
  }
}

带备忘录的自上而下

/**
 * 带备忘录的递归（自上而下）
 */
class SolutionDpWidthMemo {
  public int coinChange(int[] coins, int amount) {
    HashMap<Integer, Integer> memo = new HashMap<>();
    return dp(coins, amount, memo);
  }

  int dp (int[] coins, int amount, HashMap<Integer, Integer> memo) {
    // base case
    if (amount == 0) {
      return 0;
    }
    if (amount < 0) {
      return -1;
    }

    if (memo.get(amount) != null) {
      return memo.get(amount);
    }

    int res = Integer.MAX_VALUE;
    for (int i = 0; i < coins.length; i++) {
      int subProblem = dp(coins, amount - coins[i], memo);
      if (subProblem == -1) {
        continue;
      }
      res = Math.min(res, subProblem + 1);
    }

    if (res == Integer.MAX_VALUE) {
      memo.put(amount, -1);
      return -1;
    }
    memo.put(amount, res);

    return res;
  }
}

dp table 迭代（自下而上）

class Solution {
  public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);

    dp[0] = 0;

    for (int i = 1; i < dp.length; i++) {
      for (int coin : coins) {
        if (i - coin < 0) {
          continue;
        }
        dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
      }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
  }
}

优化（装逼）技巧

Math.floor(a / 2) 相当于 a >> 1

a % 2 相当于 a & 1

算法分享

递归 Recursion​

推荐练习题目​

解题​

递归乘法​

代码框架​

可以 get 的点​

树 Tree​

树的分类​

推荐练习题目​

题解​

动态规划（Dynamic Programming）入门 - 背包问题​

题目​

从斐波那契数开始入门​

零钱兑换​

优化（装逼）技巧​

递归 Recursion

推荐练习题目

解题

递归乘法

代码框架

可以 get 的点

树 Tree

树的分类

推荐练习题目

题解

动态规划（Dynamic Programming）入门 - 背包问题

题目

从斐波那契数开始入门

零钱兑换

优化（装逼）技巧