FE System

Appearance

算法 ​

树 ​

js
const tree = {
  name: "root",
  children: [
    {
      name: "branch 1",
      children: [
        {
          name: "leaf 1"
        },
        {
          name: "leaf 2"
        }
      ]
    },
    {
      name: "branch 2",
      children: [
        {
          name: "leaf 3"
        },
        {
          name: "leaf 4"
        }
      ]
    }
  ]
};

深度优先遍历 DFS ​

Deep First Search

先遍历完所有左子树，再遍历完所有右子树。

方法：

  • 1、访问根节点

  • 2、对根节点的children挨个进行深度优先遍历（递归）

  • 时间复杂度 O(n) n为树的节点数量，因为对于每一个节点，我们都访问一次并且只访问一次

  • 空间复杂度 O(h) h为树的深度

js
const dfs = (tree) => {
  console.log(tree.name)
  tree.children?.forEach(fn)
}

dfs(tree)
// root
// branch 1
// leaf 1
// leaf 2
// branch 2
// leaf 3
// leaf 4

广度优先遍历 BFS ​

Breadth First Search

同级遍历完，再遍历下一级别；

方法：根据队列，依次进队出队

  • 1、新建一个队列，然后根节点入队

  • 2、把队头出队

  • 3、将出队的队头里的children挨个入队

  • 4、重复2、3步，直到队列为空

  • 时间复杂度 O(n) n为树的节点数量

  • 空间复杂度 O(n) n为树的节点数量

js
const bfs = tree => {
  const que = [tree]

  while(que.length) {
    const task = que.shift()
    console.log(task.name)
    task.children?.forEach((child) => {
      que.push(child)
    })
  }
}
// root
// branch 1
// branch 2
// leaf 1
// leaf 2
// leaf 3
// leaf 4

二叉树 ​

js
const tree = {
  value: 1,
  left: {
    value: 2,
    left: {
      value: 4,
      left: null,
      right: null
    },
    right: {
      value: 5,
      left: null,
      right: null
    }
  },
  right: {
    value: 3,
    left: {
      value: 6,
      left: null,
      right: null
    },
    right: {
      value: 7,
      left: null,
      right: null
    }
  }
};

二叉树的前序遍历 ​

也叫先序遍历

像树的深度优先遍历，根->左->右

js
// 递归：递归遍历左子树，然后递归遍历右子树
const treeMap = tree => {
  let arr = []
  if (tree) {
    arr.push(tree.value)
    // console.log(tree.value)
    arr = [...arr, ...treeMap(tree.left), ...treeMap(tree.right)]
  }
  return arr
}
console.log(treeMap(tree))

// 栈：右边先入栈（后出），然后左边再入栈
const treeMapByStack = tree => {
  const stack = []
  const arr = []

  stack.push(tree)

  while (stack.length) {
    const task = stack.pop()
    arr.push(task.value)
    task.right && stack.push(task.right)
    task.left && stack.push(task.left)
  }
  return arr
}
console.log(treeMapByStack(tree))

// 1
// 2
// 4
// 5
// 3
// 6
// 7

二叉树的中序遍历 ​

左->根->右

js
// 递归：递归遍历左子树，然后递归遍历右子树

const treeMap = tree => {
  let arr = []

  const fn = (root) => {
    if (!root) return
    fn(root.left)
    arr.push(root.value)
    fn(root.right)
  }

  fn(tree)
  return arr
}

console.log(treeMap(tree))

二叉树的后序遍历 ​

左->右->根

js
function postorderTraversal(root: TreeNode | null): number[] {
    const res = []
    function fn(node: TreeNode | null) {
        if (!node) return
        if (node.left) fn(node.left)
        if (node.right) fn(node.right)
        res.push(node.val)
    }
    fn(root)
    return res
}

diff ​

给定两个二叉树，我们需要找出从第一个树转换到第二个树需要进行的最小改变数量。这里的改变包括节点的插入、删除和值的修改。 假设我们有以下两个二叉树：

树1：

ts
    1
   / \
  3   2

树2:

js
    1
   / \
  3   4

从树1转换到树2，我们需要将节点2的值改为4，因此最小改变数量为1。

请你编写一个函数，输入两个二叉树，输出从第一个树转换到第二个树所需的最小改变数量。

你可以假设每个节点的值都是正整数，并且每个树的节点数量不超过100。

js
function TreeNode(val, left, right) {
  this.val = (val === undefined ? 0 : val)
  this.left = (left === undefined ? null : left)
  this.right = (right === undefined ? null : right)
}

let tree1 = new TreeNode(1, new TreeNode(3), new TreeNode(2));
let tree2 = new TreeNode(1, new TreeNode(3), new TreeNode(6));
console.log(minChanges(tree1, tree2))

/*
递归；先序遍历；
时间复杂度是 O(n)，其中 n 是两棵树中节点数量较多的那棵树的节点数量，因为在最坏的情况下，需要访问所有的节点。
空间复杂度是 O(h)，其中 h 是两棵树中较高的那棵树的高度，这是因为你需要使用栈空间来存储递归调用。
*/
function minChanges(tree1, tree2) {
  if (!tree1) return getNodeNumber(tree2)
  if (!tree2) return getNodeNumber(tree1)
  let diff = 0

  if (tree1.val !== tree2.val) diff++
  diff = diff + minChanges(tree1.left, tree2.left) + minChanges(tree1.right, tree2.right)
  return diff
}


function getNodeNumber (tree) {
  if (!tree) return 0
  let len = 1
  len = len + getNodeNumber(tree.left) + getNodeNumber(tree.right)
  return len
};

// console.log(getNodeNumber(tree))

分治 ​

一个大问题，分成多个小问题，递归解决小问题，将结果合并从而解决大问题。小问题都是相互独立的；

动态规划 ​

基于分治，但是分治中很多计算是重复的，所以将子问题的计算结果用表保存下来，避免重复计算，是动态规划的基本思路。

爬楼梯

ts
// 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

// 动态规划
// 找规律：
// 1:1
// 2:2
// 3:3
// 4:5
// n: f(n-1)+f(n-2)
function climbStairs(n: number): number {
  // 记录每一步的值
  const res = [1, 1];
  if (n === 1) return res[n]
  for (let i = 2; i <= n; i++) {
    res[i] = res[i -1] + res[i-2]
  }
  return res[n]
};

贪心算法 ​

是一种在每一步选择中都采取在当前状态下最优的选择，从而希望导致结果是最好或最优的算法。 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

步骤：

  • 创建数学模型来描述问题。
  • 把求解的问题分成若干个子问题。
  • 对每一子问题求解，得到子问题的局部最优解。
  • 把子问题的解局部最优解合成原来解问题的一个解。

实现该算法的过程： 从问题的某一初始解出发；while 能朝给定总目标前进一步 do，求出可行解的一个解元素； 最后，由所有解元素组合成问题的一个可行解。

e.g.

买卖股票的最佳时机 II

ts
// 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
// 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
// 返回 你能获得的 最大 利润 。
// 如：
// 输入：prices = [7,1,5,3,6,4]
// 输出：7
// 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
//      随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
//      总利润为 4 + 3 = 7 。

// 思路：假设初始解max=0，
// 如果是 prices[i] > prices[i - 1]，说明能朝给定总目标前进一步。则max加上该差值，然后继续求解。直到循环结束
function maxProfit(prices: number[]): number {
  let max = 0

  for (let index = 0; index < prices.length; index++) {
    const element = prices[index];
    const pre =  prices[index - 1];
    if (element > pre) {
      max+= element - pre
    }
  }

  return max
};