理解至应用算法和数据结构

[baixiaoji]

这是什么东西？（明白该想project的定义）

改项目目标分两级别：

1. 理解常见的算法和数据结构知识（数据、字符串、二叉树、图）
2. 应用
   • 在工作中，比如如何设计并发上限的消息调度中心
   • 刷leetcode，有能力去面对中难题

为什么要做这个东西？（想想做这个东西的动机）

1. 并非科班毕业，缺少这部分知识
2. 毕业两年了，需要补充这部分知识，不然后期发展会很快落入仅是完成业务，以及如何更好完成业务实践方式在思维上会落入瓶颈

如何做这个东西？（拆解细节）

选择跟万门训练营，然后补充B站慕课大学课程。

回顾（项目过程中的执行、以及心态的变化）

2020-06-11 10:33:06 自己在这次面试其实已经过了一点基础，算是有基础的人了，从头再看起来有点浪费时间，需要自己去把控跟的进度。 2020-07-01 08:08:46 拖延了一个月，自己有点拖延了

[baixiaoji]

动态数据 ArrayList

数组是固定大小（fixed length）的，动态数组若当前长度不满足，会新建一个满足当前的连续空间的数组。

• 顺序存储数据，连续存储
• 索引访问

测试：

1. 扫雷 m n p

scransweep(m,n, p)

2. 矩阵0变换

3. 九宫格

[baixiaoji]

树

二叉树

• 特殊类型
  • 满二叉树（Full binary tree）
  • 完全二叉树（complete binary tree）c
• 遍历
  • 
  • 前序： 父左右
  • 中序：左父右
  • 后序：左右父

二叉树有哪几种存储方式？

• 基于指针或是二叉链式存储
• 基于数组顺序存储
  • 顺序逻辑：当前节点索引i，那么他的左节点索引 2i + 1，右节点 2i + 2 （数组索引起始位位0）
  • 如果是完全二叉树，存在一个问题，数组会存在较多空的问题 什么样的二叉树适合用数组来存储？
• 完全二叉树

二叉搜索树（BST）

• 特点：
  • 树中任意节点，其左子树中的每一个节点小于当前节点的值，右子树中的每一个节点都大于当前节点的值
  • 支持动态数据集合 快速插入 删除 查找操作
    • 删除操作三种情况
      • 无子代直接删除
      • 存在一个子代，指向子代
      • 存在两个子代，指向右子树中最小
        • 如何找到最大和最小

平衡二叉树

• 平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。

红黑树（R—B Tree）【有难度】

• 特点
  • 根节点是黑色
  • 叶子节点不存储数据，都是黑色的空节点（NIL）
  • 红色节点不能相邻，会被黑色节点隔开
  • 每个节点，到达叶子节点的所有路径，都包含同样多的黑色节点