首页
写文章
阅读
注册

算法的数学原理

算法的数学原理 2021年08月01日 00:08 Misaka 0 评论 398 阅读

1. 二叉树遍历

二叉树定义模板

Python

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, rigth=None,None

Java

public class TreeNode {
  public int val;
  public TreeNode left, right;
  public TreeNode(int val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

二叉树遍历模板

Python

def preorder(self, root):
  if root:
    self.traverse_path.append(root.val)
    self.preorder(root.left)
    self.preorder(root.right)
def inorder(self, root):
  if root:
    self.inorder(root.left)
    self.traverse_path.append(root.val)
    self.inorder(root.right)
def postorder(self, root):
  if root:
    self.postorder(root.left)
    self.postorder(root.right)
    self.traverse_path.append(root.val)

Java

public void preorder(root):
  if (root != null){
    this.traverse_path.append(root.val);
    preorder(root.left);
    preorder(root.right);
  }
public void inorder(root):
  if (root != null){
    inorder(root.left);
    this.traverse_path.append(root.val);
    inorder(root.right);
  }
public void postorder(root):
  if (root != null){
    postorder(root.left);
    postorder(root.right);
    this.traverse_path.append(root.val);
  }

2. 递归

盗梦空间：

  • 向下进入到梦境中；向上又回到原来一层
  • 通过声音同步回到上一层
  • 每一层的环境和周围的人都是一份拷贝，主角等几个人穿越不同层级的梦境（发生和携带变化）

Python

def recursion(level, param1, pamram2, ...):
  # recursion terminator: 终结条件
  if level > MAX_DEVEL:
    # process_result
    return

  # process logic in current level：当前层逻辑
  process(level, data...)

  # drill down：下探到下一层
  self.recursion(level + 1, p1, p2)

  # reverse the current level status if needed：清除当前层全局变量

Java

public void recursion(level, param1, pamram2, ...):
  // recursion terminator: 终结条件
  if (level > MAX_DEVEL){
    // process_result
    return;
  }

  // process logic in current level：当前层逻辑
  process(level, data...);

  // drill down：下探到下一层
  recursion(level + 1, p1, p2);

  // reverse the current level status if needed：清除当前层全局变量

要点：

  • 不要人肉递归（画状态树）
  • 找到最近最简方法，将其拆解为可重复解决的问题（重复子问题）
  • 数学归纳法

递归函数的复杂度=递归函数调用的次数 * 递归函数本身的复杂度

实战：爬楼梯和括号生成等问题

  1. 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢

f(n)：爬到第 n 阶的方法总数

# 1: 1
# 2: 2
# 3: f(1) + f(2) 无重复子问题
# 4: f(2) + f(3)

# f(n) = f(n-1) + f(n-2)

f(n) = f(n-1) + f(n-2) 可以用动态规划进行优化

括号生成

  1. 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

``` 示例 1：

输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2： 输入：n = 1 输出：["()"] ```

public List<String> generateParenthesis(int n) {
    _generate(0, 2 * n, ""); // 第 0 层， 参数: 字符个数 2n, 初始字符串空串
  return null;
}

public List<String> generateParenthesis(int n) {
    _generate(0, 2 * n, "");
  return null;
}

private void _generate(int level, int max, String s) {
  // recursion terminator: 
  if (level >= max){
    // process_result
    System.out.println(s);
    return;
  }
  // 每个位置要么左括号，要么右括号
  // process logic in current level：left, right
  String s1 = s + "(";
  String s2 = s + ")";

  // drill down：下探到下一层
  _generate(level + 1, max, s1);
  _generate(level + 1, max, s2);
}

上面的代码输出所有可能的字符串组合

public List<String> generateParenthesis(int n) {
    _generate(0, 2 * n, "");
  return null;
}

private void _generate(int level, int max, String s) {
  // recursion terminator: 
  if (level >= max){
    // process_result
    // 可以在这里判断字符串是否合法
    System.out.println(s);
    return;
  }
  // 每个位置要么左括号，要么右括号
  // process logic in current level：left, right
  String s1 = s + "(";
  String s2 = s + ")";

  // drill down：下探到下一层
  _generate(level + 1, max, s1);
  _generate(level + 1, max, s2);
}

分析：

左括号 left 随时可以加，只要别超过 n 个

右括号 right 右个数 > 左个数

所以左括号和右括号都不超过 n 个，函数可改造为下方

public List<String> generateParenthesis(int n) {
    _generate(0, 0, n, "");
  return null;
}

private void _generate(int left, int right, int n, String s) {
  // recursion terminator: 
  if (left == n && right == n){
    // process_result
    // 可以在这里判断字符串是否合法
    System.out.println(s);
    return;
  }
  // 每个位置要么左括号，要么右括号
  // process logic in current level：left, right
  if(left < n) {
    _generate(left + 1, right, n, s + "(");
  }
  if(left > right) {
    _generate(left, right + 1, n, s + ")");
  }
  // reverse status
}

3. 动态规划

动态规划可以从上面的递归方程中进行优化。

动态规划的特点

  • 重叠子问题
  • 状态转移方程
  • 最优子结构

题型：求最值

核心：穷举

解题套路

  1. 明确「状态」
  2. 明确「选择」
  3. 明确 dp 函数/数组的定义
  4. 明确 base case （初始值，或者边界）

动态规划解法代码框架

# 初始化 base case
d[0][0][..] = base
# 进行状态转移
for 状态1 in 状态1的所有值：
    for 状态2 in 状态2的所有值：
    for ...:
      d[状态1][状态2][..] = 求最值(选择1，选择 2...)

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

最长公共子序列问题是典型的二维动态规划问题。

发表评论

评论内容
 

评论列表, 共 0 条评论

@copyright belongs to jianping.zhang.