学习笔记

哈希表

相关题目：

有效的字母异位词

字母异位词分组

两数之和

思路：

有效的字母异位词

1. 在哈希表中存储字母出现的次数，遇到第一个字符串的字母则把出现次数+1，遇到第二个字符串的字母则把出现次数-1，最后判断是否存在不为0的次数，不为0则说明两个字符串的字母出现次数不等。
2. 因为小写字母一共就26个，我们可以直接用size为26的数组来做哈希表，利用下标（0-25）来对应每个字母存储位置，值为字母出现的次数，这也是key-value的映射，下标代表a-z，值为a-z出现的次数。最后判断思路和上面一样。

字母异位词分组

1. 此问题主要在于哈希表的key的设计，我们可以将字符串进行排序作为哈希表的key，对应的值用数组保存，只要存在于哈希表中就继续添加到值中，没有则添加到新的key对应的值中。
2. 和判断有效字母异位词一样，我们可以统计字母出现次数，然后拼接为字符串作为哈希表的key。

两数之和

直接利用哈希表来存储target和每个元素的差值，然后我们只需要在哈希表中查找该差值是否存在即可。

总结

哈希表主要便于存储和查找，因为其为key-value映射表，查询通常只为O(1)的时间复杂度，所以一些关于查找和存储的操作，我们可以用哈希表来优化时间复杂度。然后就是哈希表的key设计，有些很奇妙，很有趣，比如上面字母相关题目的key设计就很巧妙。

树

生活中很多事物都是存在多个分支的，而不是单个分支的。比如人和人的关系，以自我为中心，会延伸到很多人，然后其他人也会延伸到很多人。

二叉树的遍历

前序遍历：根节点-左子节点-右子节点

中序遍历：左子节点-根节点-右子节点

后序遍历：左子节点-右子节点-根节点

可以看出，顺序的改变主要是根节点的遍历顺序改变。

递归代码：

// 前序遍历
const dfs = (root) => {
  if (root) {
    console.log(root.val)
    dfs(root.left)
    dfs(root.right)
  }
}

// 中序遍历
const dfs = (root) => {
  if (root) {
    dfs(root.left)
    console.log(root.val)
    dfs(root.right)
  }
}

// 后序遍历
const dfs = (root) => {
  if (root) {
    dfs(root.left)
    dfs(root.right)
    console.log(root.val)
  }
}

树非常适合用递归来操作，因为其本身的结构就是递归性的，以二叉树举例，节点存在左右子节点，然后子节点也类似。而递归就是处理重复性子问题的，对于一棵树的操作，我们操作其子节点也是一样的。

不用递归，我们手动实现栈也可以实现，因为递归其实就是系统帮我们维护了一个栈，自己写循环遍历就是模拟系统栈来实现。比如二叉树前序遍历代码：

const preorderTraversal = function(root) {
  let res = [], stack = []

  if (root) stack.push(root)

  while (stack.length > 0) {
    const curr = stack.pop()

    res.push(curr.val)

    if (curr.right) stack.push(curr.right)
    if (curr.left) stack.push(curr.left)
  }

  return res
}

二叉搜索树

其特点就是左子树的所有节点的值都小于根节点的值，而右子树的所有节点的值都大于根节点的值。中序遍历是有序的。

堆

堆是一种抽象的数据结构，实现方式有很多种，比如二叉堆、斐波那契堆、严格斐波那契堆。其主要是在一组数据中快速找到最大值或者最小值。一般把最大值或最小值放在顶端，称为大顶堆/小顶堆。

图

图有点右边，点即节点，边即节点之间的关系。然后根据是否有权重分为有权图和无权图，根据节点关系是否对称分为是否有向。

总结

堆和图实践还很少，后续继续补充。