数据结构

数据结构与算法知识点归纳

数据结构

并查集

  • 并查集
    • 确定元素属于哪一个集合，将两个子集合并成同一个集合
    • 环
    • 最小生成树
    • 无向图才能正确处理强联通分量

散列表(哈希表)

哈希表

  • 缓存管理，快速实现变量在内存中的读取
  • DNS 解析，快速转化
  • 扩容时间：O(n)

哈希函数

  • 文件校验，key的快速查询
  • 加密
  • 分布式，一致性哈希

一致性哈希

  • 分布式哈希算法，主用用来解决分布式系统中的负载均衡问题
  • 为了解决增加候选集的时候，哈希的值尽可能不变
  • 没有固定的顺逆时针

散列表平均查找长度：

  • 先对所有元素取余
  • 不存在冲突的长度为 1，存在冲突的从 1 开始累加
  • 平均查找长度 = 所有元素的查找长度之和 / 元素个数
  • 访问时间复杂度 O(1)，查找时间复杂度 O(n)

队列

队列

  • 先进新出
  • 用于广度优先搜索

堵塞

  • 在队满时插入
  • 在队空时删除

循环队列

  • front 是队头，rear 是队尾

线性表

线性表分类

  • 顺序表
  • 链表
    • 指针实现
      • 单链表
      • 双链表
      • 循环链表
    • 数组实现
      • 静态链表

单向链表

  • 相交，则尾节点一定相同
  • 快慢指针判断环，有环的和无环的不可能相交

链表

  • 适合实现稀疏图的邻接关系

树

不存在环的图

Trie 树

  • 用于统计和排序大量字符串
  • 可以进行深度优先，不适合广度优先

算法

各种算法

  • Floyd-Warshall 算法
    • 用于解决带权图中任意两点之间的最短路径问题
  • Dijsktra 算法
    • 用于求带权图中某一点到其他所有点的最短路径
    • 挑选离源点最近的点，然后更新其他点到源点的距离
  • Prim 算法
    • 用于求加权连通图的最小生成树，适用于稠密图
  • Kruskal 算法
    • 用于求加权连通图的最小生成树，适用于稀疏图

遍历

  • 先序遍历
    • 中左右
  • 中序遍历
    • 左中右
  • 后序遍历
    • 左右中
  • 层次遍历
    • 类比广度优先遍历

排序

有序数组用堆排序最快。

  • 不稳定排序
    • 快排
    • 堆排序

分治

一定要独自子问题。

  • 使用分治法
    • 二分查找
    • 排序算法
      • 快排
      • 归并

动态规划

  • 最长公共子序列时间复杂度 O(mn)
  • KMP 时间复杂度 O(m+n)
设计模式

设计模式知识点归纳

设计模式

  • 创建型模式
    • 简单工厂模式
      • 通过一个工厂类来创建不同的类的实例
    • 工厂方法模式
      • 定义一个用于创建对象的接口，让子类决定实例化哪一个类
    • 抽象工厂模式
      • 提供一个创建一系列相关或相互依赖对象的接口，而无需指定它们的具体类
    • 建造者模式
      • 将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示
      • Director 类与抽象工厂的工厂类类似，负责返回一个产品族的所有产品
    • 单例模式
      • 保证一个类仅有一个实例，并提供一个访问它的全局访问点
    • 原型模式
      • 用原型实例指定创建对象的种类，并且通过拷贝这些原型创建新的对象
  • 结构型模式
    • 适配器模式
      • 将一个类的接口转换成客户希望的另一个接口，从而使得原本因接口不匹配而无法在一起工作的类可以一起工作
    • 代理模式
      • 为其他对象提供一种代理以控制对这个对象的访问
      • 和适配器模式最为相似
    • 桥接模式
      • 将抽象部分与它的实现部分分离，使它们都可以独立的变化
    • 过滤器模式
      • 使用不同的标准来过滤一组对象
    • 组合模式
      • 将对象组合成树形结构以表示部分-整体的层次结构
      • 分为透明式和安全式
      • 包含抽象构件 Component、叶子构件 Leaf、容器构件 Composite
    • 装饰模式
      • 动态的给一个对象添加一些额外的职责
      • 包括抽象组件角色 Component、抽象组件实现 ConcreteComponent、装饰器 Decorator、装饰器实现 ConcreteDecorator
    • 外观模式
      • 为子系统中的一组接口提供一个一致的接口，使得子系统更容易使用
    • 享元模式
      • 运用共享技术有效的支持大量细粒度的对象
  • 行为型模式
    • 责任链模式
      • 为请求创建一个接收此次请求对象的链
      • 设置一个默认处理器来处理未被处理的请求
    • 命令模式
      • 将一个请求封装为一个对象，从而使你可用不同的请求对客户进行参数化
    • 解释器模式
      • 给定一个语言，定义它的文法的一种表示，并定义一个解释器
    • 迭代器模式
      • 提供一种方法顺序访问一个聚合对象中的各个元素，而又不暴露其内部的表示
    • 中介者模式
      • 用一个中介对象来封装一系列的对象交互，处理多个类之间的交互
      • 同事类依赖于中介者
    • 备忘录模式
      • 在不破坏封装的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态
      • 符合迪米特法则
    • 观察者模式
      • 定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新
      • 避免发送者和接受者的耦合
      • 包括抽象主题、具体主题、抽象观察者、具体观察者
    • 状态模式
      • 允许一个对象在其内部状态改变时改变它的行为
    • 空对象模式
      • 用一个对象代表空值
    • 策略模式
      • 定义一系列算法，把它们一个个封装起来，并且使它们可以相互替换
      • 涉及多选一、多重条件选择或所有的策略类
    • 模板模式
      • 定义一个操作中的算法的框架，而将一些步骤延迟到子类中
    • 访问者模式
      • 添加新的操作到已经存在的对象结构中去

原则

  • 单一职责原则
    • 一个类只负责一个功能
  • 开闭原则
    • 对扩展开放，对修改关闭
  • 里氏替换原则
    • 子类可以替换父类
  • 依赖倒置原则
    • 高层模块不应该依赖底层模块，两者都应该依赖抽象
  • 接口隔离原则
    • 使用多个专门的接口，而不使用单一的总接口
  • 迪米特法则
    • 一个对象应该对其他对象保持最少的了解
  • 合成复用原则
    • 尽量使用合成/聚合，而不是继承
软件工程

软件工程与技术知识点归纳

各种图

  • 数据流图：数据流动，数据字典
  • 实体关系图：数据库
  • UML 图
    • 结构图
      • 类图：对象关系，继承和关联
      • 对象图：对象的属性，对象的快照
      • 构(组)件图：组件的关系
      • 组合结构图：组合关系
      • 包图：包的关系
      • 部署图：软件和硬件的部署
      • 制品图：物理部署
    • 行为(交互)图
      • 时序图：时间轴顺序
      • 序列(顺序)图：对象之间的交互和顺序
      • 通信(协作)图：对象之间的消息传递和协作
      • 状态图：状态变化
      • 活动图：活动流程
      • 用例图：用户和系统的交互
      • 交互概述图

开发模型

  • 快速原型：需求不明确时，确保相关利益方对需求理解一致
  • 螺旋模型：每个阶段结束时有一个评审。每个阶段都使用瀑布模型
  • 瀑布模型
  • 敏捷模型：强调团队协作和客户参与

工具

  • 需求分析阶段
    • 结构化分析(SA)
    • 数据流程图(DFD)
  • 概要设计阶段
    • 系统结构图(SC)
  • 详细设计阶段
    • 问题分析图(PAD)
小程序

小程序相关知识点

自定义组件

  • 新建自定义组件目录，生成目录结构
  • 自定义组件内容
  • 在要使用的页面的 json 文件中配置 usingComponents，引入组件
  • 以标签的形式在页面中使用该组件即可
  • 传递数据和 vue 一样，通过自定义属性，然后在组件里通过 properties 接收就可以了

小程序与 web-view 交互

  1. 小程序调用 web-view 的方法
    • web-view 组件的 src 属性设置为一个网页地址，使用 & 来附加参数
    • 每次小程序向页面传参都会刷新一次页面
  2. web-view 调用小程序的方法
    • web-view 加载的页面中，引入jweixin.js，通过调用 JSSDK 的 wx.miniProgram.postMessage 方法向小程序发送消息
    • 小程序监听 bindmessage 事件，通过 e.detail.data 获取数据

传递数据

传递数据的方式有：

  • 路由 URL 传值
  • 使用全局变量 globalData
  • 使用本地缓存 wx.setStorageSync，存在 storage 中
  • 通信通道 wx.navagateTo
  • 使用页面栈 getCurrentPages
  • 通过数据库
Vue

Vue相关知识点

Vue 生命周期

Vue 数组更新

slice、concat 都会返回新的数组，不会引起视图的更新。

Vue 优化方案

  1. 代码层面
  • v-if 和 v-show 区分场景使用
  • computed 和 watch 区分场景使用
  • v-for 添加 key，避免同时使用 v-if
  • 事件的销毁
  • 懒执行
  • 图片资源懒加载
  • 路由懒加载
  • 第三方插件按需引入
  • 优化列表性能
  • 离线包
  • 预加载
  • SSR或预渲染
  1. webpack 层面
  • 图片和代码压缩，图片base64，开启 production
  • ES6开启 tree shaking
  • 减少 ES6 转化为 ES5 的冗余代码
  • 提取公共代码
  • 模板预编译
  • 优化 sourceMap
  • 拆包代码，按需加载
  • 构建结果输出分析
  1. 基础 web 技术层面
  • DNS 预解析
  • gzip 压缩
  • 浏览器缓存
  • 静态资源的强缓存与协商缓存
  • 静态资源用 CDN
  • 使用 Chrome Performance 查找性能瓶颈
  • HTTP2
    • 多路复用
    • 首部压缩
  • HTTPS
    • 传输安全，SSL 443
  • Webworker

Vue 内存泄漏

  • 自定义指令，绑定后没有解绑
    • unbind 钩子中解绑
  • v-if 判断为 false，销毁了父组件，但是没有销毁引入的第三方库插入的 DOM 片段
    • 可以保留对元素片段的引用，在 v-if 判断为 false 时，调用 destroy 方法销毁
  • router 跳转时，子元素的 DOM 片段可能没有销毁
    • 利用 beforeRouteLeave 钩子销毁