技术

数据湖 高性能计算与存储 Linux2.1.13网络源代码学习 《大数据经典论文解读》 三驾马车学习 Spark 内存管理及调优 Yarn学习 从Spark部署模式开始讲源码分析 容器狂占内存资源怎么办? 多角度理解一致性 golang io使用及优化模式 Flink学习 c++学习 学习ebpf go设计哲学 ceph学习 学习mesh kvm虚拟化 学习MQ go编译器 学习go 为什么要有堆栈 汇编语言 计算机组成原理 运行时和库 Prometheus client mysql 事务 mysql 事务的隔离级别 mysql 索引 坏味道 学习分布式 学习网络 学习Linux go堆内存分配 golang 系统调用与阻塞处理 Goroutine 调度过程 重新认识cpu mosn有的没的 负载均衡泛谈 单元测试的新解读 《Redis核心技术与实现》笔记 《Prometheus监控实战》笔记 Prometheus 告警学习 calico源码分析 对容器云平台的理解 Prometheus 源码分析 并发的成本 基础设施优化 hashicorp raft源码学习 docker 架构 mosn细节 与微服务框架整合 Java动态代理 编程范式 并发通信模型 《网络是怎样连接的》笔记 go channel codereview gc分析 jvm 线程实现 go打包机制 go interface及反射 如何学习Kubernetes 《编译原理之美》笔记——后端部分 《编译原理之美》笔记——前端部分 Pilot MCP协议分析 go gc 内存管理玩法汇总 软件机制 istio流量管理 Pilot源码分析 golang io 学习Spring mosn源码浅析 MOSN简介 《datacenter as a computer》笔记 学习JVM Tomcat源码分析 Linux可观测性 学习存储 学计算 Gotty源码分析 kubernetes operator kaggle泰坦尼克问题实践 kubernetes扩缩容 神经网络模型优化 直觉上理解深度学习 如何学习机器学习 TIDB源码分析 什么是云原生 Alibaba Java诊断工具Arthas TIDB存储——TIKV 《Apache Kafka源码分析》——简介 netty中的线程池 guava cache 源码分析 Springboot 启动过程分析 Spring 创建Bean的年代变迁 Linux内存管理 自定义CNI IPAM 共识算法 spring redis 源码分析 kafka实践 spring kafka 源码分析 Linux进程调度 让kafka支持优先级队列 Codis源码分析 Redis源码分析 C语言学习 《趣谈Linux操作系统》笔记 docker和k8s安全访问机制 jvm crash分析 Prometheus 学习 Kubernetes监控 容器日志采集 Kubernetes 控制器模型 容器狂占资源怎么办? Kubernetes资源调度——scheduler 时序性数据库介绍及对比 influxdb入门 maven的基本概念 《Apache Kafka源码分析》——server Kubernetes类型系统 源码分析体会 《数据结构与算法之美》——算法新解 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 ansible学习 Kubernetes源码分析——从kubectl开始 jib源码分析之Step实现 jib源码分析之细节 线程排队 跨主机容器通信 jib源码分析及应用 为容器选择一个合适的entrypoint kubernetes yaml配置 《持续交付36讲》笔记 mybatis学习 程序猿应该知道的 无锁数据结构和算法 CNI——容器网络是如何打通的 为什么很多业务程序猿觉得数据结构和算法没用? 串一串一致性协议 当我在说PaaS时,我在说什么 《数据结构与算法之美》——数据结构笔记 PouchContainer技术分享体会 harbor学习 用groovy 来动态化你的代码 精简代码的利器——lombok 学习 《深入剖析kubernetes》笔记 编程语言那些事儿 rxjava3——背压 rxjava2——线程切换 spring cloud 初识 《深入拆解java 虚拟机》笔记 《how tomcat works》笔记 hystrix 学习 rxjava1——概念 Redis 学习 TIDB 学习 如何分发计算 Storm 学习 AQS1——论文学习 Unsafe Spark Stream 学习 linux vfs轮廓 《自己动手写docker》笔记 java8 实践 中本聪比特币白皮书 细读 区块链泛谈 比特币 大杂烩 总纲——如何学习分布式系统 hbase 泛谈 forkjoin 泛谈 看不见摸不着的cdn是啥 《jdk8 in action》笔记 程序猿视角看网络 bgp初识 calico学习 AQS——粗略的代码分析 我们能用反射做什么 web 跨域问题 《clean code》笔记 《Elasticsearch权威指南》笔记 mockito简介及源码分析 2017软件开发小结—— 从做功能到做系统 《Apache Kafka源码分析》——clients dns隐藏的一个坑 《mysql技术内幕》笔记 log4j学习 为什么netty比较难懂? 递归、回溯、动态规划 apollo client源码分析及看待面向对象设计 学习并发 docker运行java项目的常见问题 OpenTSDB 入门 spring事务小结 分布式事务 javascript应用在哪里 《netty in action》读书笔记 netty对http2协议的解析 ssl证书是什么东西 http那些事 苹果APNs推送框架pushy apple 推送那些事儿 编写java框架的几大利器 java内存模型和jvm内存布局 java exception Linux IO学习 netty内存管理 测试环境docker化实践 netty在框架中的使用套路 Nginx简单使用 《Linux内核设计的艺术》小结 Go并发机制及语言层工具 Linux网络源代码学习——数据包的发送与接收 《docker源码分析》小结 docker namespace和cgroup zookeeper三重奏 数据库的一些知识 Spark 泛谈 链式处理的那些套路 netty回顾 Thrift基本原理与实践(二) Thrift基本原理与实践(一) 回调 异步执行抽象——Executor与Future Docker0.1.0源码分析 java gc Jedis源码分析 深度学习泛谈 Linux网络命令操作 JTA与TCC 换个角度看待设计模式 Scala初识 向Hadoop学习NIO的使用 以新的角度看数据结构 并发控制相关的硬件与内核支持 systemd 简介 quartz 源码分析 基于docker搭建测试环境(二) spring aop 实现原理简述 自己动手写spring(八) 支持AOP 自己动手写spring(七) 类结构设计调整 分析log日志 自己动手写spring(六) 支持FactoryBean 自己动手写spring(九) 总结 自己动手写spring(五) bean的生命周期管理 自己动手写spring(四) 整合xml与注解方式 自己动手写spring(三) 支持注解方式 自己动手写spring(二) 创建一个bean工厂 自己动手写spring(一) 使用digester varnish 简单使用 关于docker image的那点事儿 基于docker搭建测试环境 分布式配置系统 JVM执行 git maven/ant/gradle/make使用 再看tcp kv系统 java nio的多线程扩展 《Concurrency Models》笔记 回头看Spring IOC IntelliJ IDEA使用 Java泛型 vagrant 使用 Go常用的一些库 Python初学 Goroutine 调度模型 虚拟网络 《程序员的自我修养》小结 Kubernetes存储 访问Kubernetes上的Service Kubernetes副本管理 Kubernetes pod 组件 Go基础 JVM类加载 硬币和扑克牌问题 LRU实现 virtualbox 使用 ThreadLocal小结 docker快速入门

架构

多集群及clusternet学习 AutoML和AutoDL 特征平台 实时训练 分布式链路追踪 helm tensorflow原理——python层分析 如何学习tensorflow 数据并行——allreduce 数据并行——ps 机器学习中的python调用c 机器学习训练框架概述 embedding的原理及实践 tensornet源码分析 大模型训练 X的生成——特征工程 tvm tensorflow原理——core层分析 模型演变 《深度学习推荐系统实战》笔记 keras 和 Estimator tensorflow分布式训练 分布式训练的一些问题 基于Volcano的弹性训练 图神经网络 pytorch弹性分布式训练 在离线业务混部 RNN pytorch分布式训练 CNN 《动手学深度学习》笔记 pytorch与线性回归 多活 volcano特性源码分析 推理服务 kubebuilder 学习 mpi 学习pytorch client-go学习 tensorflow学习 提高gpu 利用率 GPU与容器的结合 GPU入门 AI云平台梳理 tf-operator源码分析 k8s批处理调度 喜马拉雅容器化实践 Kubernetes 实践 学习rpc BFF openkruise学习 可观察性和监控系统 基于Kubernetes选主及应用 《许式伟的架构课》笔记 Kubernetes webhook 发布平台系统设计 k8s水平扩缩容 Scheduler如何给Node打分 Scheduler扩展 controller 组件介绍 openkruise cloneset学习 controller-runtime源码分析 pv与pvc实现 csi学习 client-go源码分析 kubelet 组件分析 调度实践 Pod是如何被创建出来的? 《软件设计之美》笔记 mecha 架构学习 Kubernetes events学习及应用 CRI 资源调度泛谈 业务系统设计原则 grpc学习 元编程 以应用为中心 istio学习 下一代微服务Service Mesh 《实现领域驱动设计》笔记 serverless 泛谈 概率论 《架构整洁之道》笔记 处理复杂性 那些年追过的并发 服务器端编程 网络通信协议 架构大杂烩 如何学习架构 《反应式设计模式》笔记 项目的演化特点 反应式架构摸索 函数式编程的设计模式 服务化 ddd反模式——CRUD的败笔 研发效能平台 重新看面向对象设计 业务系统设计的一些体会 函数式编程 《左耳听风》笔记 业务程序猿眼中的微服务管理 DDD实践——CQRS 项目隔离——案例研究 《编程的本质》笔记 系统故障排查汇总及教训 平台支持类系统的几个点 代码腾挪的艺术 abtest 系统设计汇总 《从0开始学架构》笔记 初级权限系统设计 领域驱动理念入门 现有上传协议分析 移动网络下的文件上传要注意的几个问题 推送系统的几个基本问题 用户登陆 做配置中心要想好的几个基本问题 不同层面的异步 分层那些事儿 性能问题分析 当我在说模板引擎的时候,我在说什么 用户认证问题 资源的分配与回收——池 消息/任务队列

标签


以新的角度看数据结构

2016年03月15日

前言

《算法通关之路》学习算法像拓扑排序,若没有任何的解题经验,普通人不可能创造一个算法来解决问题。积累经验是十分关键的,当我们积累经验达到一定程度的时候,就可以从新问题中找到旧问题的影子,进一步联想过去所使用的解法,并加以转换,从而解决新问题了。

衡量 CPU 的计算能力:比如一个 Intel 的 i5-2520M @2.5 Ghz 的处理器,则其计算能力 2.5 * 4(4核) = 10 GFLOPS,一个 GFLOPS(gigaFLOPS)等於每秒拾亿(=10^9)次的浮点运算,对于一个O(n^2)复杂度的题目来说, n=2500 就要CPU花1s来计算了。

整体介绍

数据结构分为逻辑结构、存储结构以及对应结构的数据运算,

逻辑结构

数据元素间抽象化的相互关系,与存储无关,比如可以用一个数组表示一个图,也可以用链表存储一个图,或者一个图中包含数组和链表。主要包括:

  1. 集合结构中的数据元素之间除了 “同属于一个集合”的关系外,别无其他关系。
  2. 线性结构,数据元素之间只存在一对一的关系。⼀般⽽⾔,有前驱和后继的就是线性数据结构
  3. 非线性结构,有了线性结构,我们为什么还需要⾮线性结构呢? 为了⾼效地兼顾静态操作和动态操作,我们⼀般使⽤树去管理需要⼤量动态操作的 数据。比如平衡⼆叉搜索树的查找和有序数组的⼆分查找本质都是⼀样的,只是数据的存储⽅式不同罢了。那为什么有了有序数组⼆分,还需要⼆叉搜索树呢?原因在于树的结构对于动态数据⽐较友好,⽐如数据是频繁变动的,⽐如经常添加和删除,那么就可以使⽤⼆叉搜索树。
    1. 树形结构结构中的数据元素之间存在一对多的关系。
    2. 图状结构或网状结构结构中的数据元素之间存在多对多的关系。

每种逻辑结构包含一些基本的运算,包括遍历,增减节点等。

存储结构

主要包括:

  1. 顺序存储:把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里,元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取,每个元素占用最少的存储空间;缺点是只能使用相邻的一整块存储单元,因此可能产生较多的外部碎片。
  2. 链接存储:不要求逻辑上相邻的元素在物理位置上也相邻,借助指示元素存储地址的指针表示元素之间的逻辑关系。其优点是不会出现碎片现象,充分利用所有存储单元;缺点是每个元素因存储指针而占用额外的存储空间,并且只能实现顺序存取。
  3. 索引存储:在存储元素信息的同时,还建立附加的索引表。索引表中的每一项称为索引项,索引项的一般形式是:(关键字,地址)。其优点是检索速度快;缺点是增加了附加的索引表,会占用较多的存储空间。另外,在增加和删除数据时要修改索引表,因而会花费较多的时间。
  4. 散列存储:根据元素的关键字直接计算出该元素的存储地址,又称为Hash存储。其优点是检索、增加和删除结点的操作都很快;缺点是如果散列函数不好可能出现元素存储单元的冲突,而解决冲突会增加时间和空间开销。

存储/物理结构通常绕不开寻址问题,以及增删改查的效率问题。我们可以观察到集中存储结构的演进:

  1. 顺序存储,直接放在一起
  2. 链接存储,数据和位置信息放在一起
  3. 索引存储,数据和位置信息完全独立,位置信息存在单独的索引表中。比如磁盘的某些格式
  4. 直接寻址表,数据和位置信息完全独立,位置信息存在单独的数组中,数据直接作为数组下标。
  5. 哈希表,直接寻址表的改进。

线性结构

数组和链表

各种数据结构,不管是队列,栈等线性数据结构还是树,图的等⾮线性数 据结构,从根本上底层都是数组和链表。不管你⽤的是数组还是链表,⽤ 的都是计算机内存,物理内存是⼀个个⼤⼩相同的内存单元构成的。数组和链表是使⽤物理内存的两种⽅式。PS:同样是存储结构,数组和链表更底层一些

  1. 数组是连续的内存空间,通常每⼀个单位的⼤⼩也是固定的,因此可以按下标随机访问。
  2. 链表不⼀定连续,⼀般我们是通过⼀个叫 next 指针来遍历查找。链表其实就是⼀个结构体。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由⼀系列结点(链表中每⼀个元素称为结点)组成,结点可以在运⾏时动态⽣成。链表是⼀种递归的数据结构,因此采⽤递归的思想去考虑往往事半功倍。

数组对查询特别友好,对删除和 添加不友好,为了解决这个问题,就有了链表这种数据结构。链表适合 在数据需要有⼀定顺序,但是⼜需要进⾏频繁增删除的场景。

有没有想过为啥只有⼆叉树,⽽没有⼀叉树?实际上链表就是特殊的树,即⼀叉树。单链表只有⼀个后继指针。因此只有前序和后序,没有中序遍历。值得注意的是,前序遍历很容易改造成迭代,为什么呢?前序遍历容易改成不需要栈的递归,⽽后续遍历需要借助栈来完成。由于后续遍历的主逻辑在函数调⽤栈的弹出过程,⽽前序遍历则不需要。

  1. 由于链表不⽀持随机访问,因此如果想要获取数组中间项和倒数第⼏项等特定元素就需要⼀些特殊的⼿段,⽽这个⼿段就是快慢指针。⽐如要 找链表中间项就搞两个指针,⼀个⼤步⾛(⼀次⾛两步),⼀个⼩步⾛(⼀次⾛⼀步),这样快指针⾛到头,慢指针刚好在中间。 如果要求链 表倒数第 2 个,那就让快指针先⾛⼀步,慢指针再⾛,这样快指针⾛到头,慢指针刚好在倒数第⼆个。
  2. 单链表⽆法在 O(1) 的时间拿到前驱节点,这也是为什么我们遍历的时候⽼是维护⼀个前驱节点的原因。但是本质原因其实是链表的增删操作都依赖前驱节点,这是链表的基本操作,是链表的特性天⽣决定的。
  3. 如果要移动单链表的节点,可以使用一个伪头部(dummy head)标记 移动节点后链表的头部。遍历链表时,可以用cur 来标记当前节点。但遍历+移动节点时,cur 本身不能指向待移动的节点,因为cur 会移动,为此要为cur 记录pre,且要记录next = cur.Next以便cur 一会儿指回来。干脆 cur.Next 指向待移动的节点。
  4. 在双向链表的实现中,使用一个伪头部(dummy head)和伪尾部(dummy tail)标记界限,这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

功能函数

解决链表问题的时候,先把基本的头插、尾插、遍历、排序(归并法,取中点切分)、反转、找中点、找环等方法备好,结合go 语言的高阶函数,可以大大提高的代码的可读性。比如反转链表,有下面TraverseList 的加持,就比在一个函数里撸业务逻辑 + 遍历逻辑要方便很多,可读性也好很多。

// 插入节点
func InsertAfter(cur, node *ListNode) {
	next := cur.Next
	cur.Next = node
	node.Next = next
}
// 插入list,按list顺序
func InsertAfterByOrder(cur, l *ListNode) {
	next := cur.Next
	TraverseList(l, func(i int, node *ListNode) {
		cur.Next = node
		cur = cur.Next
	})
	cur.Next = next
}
// 插入list,按list 逆序,也就是头插
func InsertAfterByReverseOrder(cur, l *ListNode) {
	next := cur.Next
	TraverseList(l, func(i int, node *ListNode) {
		InsertAfter(cur, node)
	})
	l.Next = next
}
// 此处的 handler 在遍历的过程中还个了node的元信息,即node的索引
func TraverseList(head *ListNode, handler func(i int, node *ListNode)) {
	cur := head
	i := 0
	for cur != nil {
		next := cur.Next // node 可以被handler 挪用
		handler(i, cur)
		i++
		cur = next
	}
}
// 将 list 分为 k 个长度子list 并遍历子list
func TraverseKList(head *ListNode, k int, handler func(head, tail *ListNode, len int)) {
	l := &ListNode{}
	cur := l
	count := 0
	TraverseListByNode(head, func(i int, isTail bool, node *ListNode) {
		cur.Next = node
		cur = cur.Next
		count++
		if (i+1)%k == 0 || isTail {
			handler(l.Next, cur, count)
			l = &ListNode{}
			cur = l
			count = 0
		}
	})
}
func Print(l *ListNode) {
	for l != nil {
		fmt.Println(l.Val)
		l = l.Next
	}
}

滑动窗口

对于数组和字符串来说,除了元素遍历外,还可以遍历连续子序列(滑动窗口),非连续的子序列(xx数之和),元素可以重复多次或无限次的话子序列就更多了(零钱兑换问题)。

func TraverseChildSequence(nums []int, handler func(nums []int, start, end int)) {
	for i := 0; i < len(nums); i++ {
		for j := i; j < len(nums); j++ {
			handler(nums, i, j)
		}
	}
}
// 另一种常见结构
func TraverseChildSequence(nums []int){
    n := len(nums)
    l := 0
    r := 1
    result := xx
    for r < n && l <= r{
        seq := nums[l:r]
        if ok := function(seq);ok{    // 判断函数  也可以是 function(nums,l,r)
            r++             // 扩大窗口
            result = xx     // 更新一个可行解
        }else{
            l++             // 缩小窗口
        }
    }
    return result
}

在算法优化方面,针对平方阶算法,由于通常必须至少遍历数据一次,无法省略最外层循环,优化重点应考虑是否能降低内层操作的时间复杂度,无论优化到对数阶还是常数阶,算法的效率都会有相当可观的提高。比如i,j 可以认为是滑动窗口的左右指针,但因为j 一定大于i,可以将嵌套的循环展开(正常遍历 子序列/字串 要多层循环),通过减少内层循环的次数来降低算法的时间复杂度,o(n*n) 变为o(n)

  1. 窗口的作用是 排除不可能的解/去除冗余计算,一般来说,固定窗口的某个边界后(左或右),当某个长度的窗口 满足要求或不满足要求时,更长或更短的窗口便不用考虑了,直接考虑下一个固定边界的窗口即可。比如 无重复字符的最长子串pwwkew,当r 探测到第二个w时, 对于l=0,r 再向右探测已经没有意义,此时l 也要向右移,放弃考虑l=0。PS:没有二分这么直接,毕竟二分是O(logn),窗口是O(n)
  2. 窗口长度固定或不固定,左右指针的右移不一定是连续的 ==> 窗口的收缩、扩展、平移。
  3. 窗口有整体右移的,可增可减、只增不减、只减不增(从两边最大缩到最小的,比如“乘最多水的容器”)。
    1. 整体右移:本质是遍历数组、字符串的时候,如果[i,j] 不符合要求则不用等j移到右边界就提前右移i,i、j都只会右移不能左移。形象化一点就是,窗口大小可变,但整体在朝右滑动。如果仅靠右移无法解决问题,还要回溯,或者每一次移动后无法继续判断是右移i还是右移j,上面的模板套不上去,就不适合用窗口解决了。
    2. 滑动窗口一般伴随判断函数,判断当前窗口的子序列是否符合要求。判断函数需要辅助的数据结构,比如双端队列(右侧指针右移是加入,左侧指针右移是移除,且保持元素原有的相对顺序)、字典等,记录窗口内元素的特性:比如最大值、最小值、包含某些元素、和等,并与目标进行对比
  4. 滑动窗口法的核心:right 啥时候右移,left啥时候右移,什么时候算满足条件的一个解。
    1. 一般来说,滑动窗口法要求解空间有连续的性质,比如子串、连续子序列、xx面积。
    2. 即便题解有连续的性质,也不一定可以用。如果尝试用滑动窗口去解决,窗口从xx 移动到了xx,无法解决问题,就是说明问题在o(n) 时间解决不了,得找o(n^2)的算法了。比如求子序列的最大和,右边是个正数要右移,是个负数也得右移(兴许负数右边的正数更大),右移的终止条件不明确(或者说只能移到右边界才可以终止,此时就退化为暴力遍历了),本质是右侧某个数的正反关系不大,如果右侧某个区域和是正数,就ok了。没有「剪枝」加快计算的效果。PS:为什么有的题滑动窗口不可以非得靠dp

队列

教科书上一说队列,就是四个字“先进先出”,这四个字是无法表述队列的巨大作用的.

  1. 合并请求的一种实现,假设一个方法或类负责管理一个资源,在多线程环境下,这个类便需要”线程安全”
    1. 将这个类改造成线程安全的类
    2. 调整这个类的调用方式.利用生产者消费者模式,所有想要使用这个资源的的线程(生产者)先提交请求到一个队列,由一个专门的线程(消费者)负责接收并处理请求.
  2. 轮询的一种实现,假设我们有一个集合,对集合中的元素实现轮询效果。
    1. 我们可以标记一个index,记住上一次使用的元素,进而实现轮询。
    2. 用环形队列存储集合,即天然具备轮询效果。

这两种方式,在多线程环境下,还需注意线程安全问题。

DOM 树是⼀种树结构, ⽽ HTML 作为⼀种 DSL 去描述这种树结构的具体表现形式。如果你接触 过 AST,那么 AST 也是⼀种树,XML 也是树结构。

树其实是⼀种特殊的图,是⼀种⽆环连通图,是⼀种极⼤⽆环图,也是⼀种极⼩连通图。

树的遍历分为两种,分别是深度优先遍历和⼴度优先遍历。PS:遍历方法只是用于遍历,不太适用于对树进行删除节点等操作

  1. DFS 沿着树的深度遍历树的节点,尽可能深的搜索树的分⽀。 当节点 v 的所在边都⼰被探寻过,搜索将回溯到发现节点 v 的那条边的起 始节点。这⼀过程⼀直进⾏到已发现从源节点可达的所有节点为⽌。如果 还存在未被发现的节点,则选择其中⼀个作为源节点并重复以上过程,整 个进程反复进⾏直到所有节点都被访问为⽌,属于盲⽬搜索
    1. 树的不同深度优先遍历又分为前中后序。前中后序实际上是指的当前节点相对⼦节点的处理顺序。遍历得从根节点开始访问,然后根据⼦节点指针访问⼦节点,但是 ⼦节点有多个(⼆叉树最多两个)⽅向,所以⼜有了先访问哪个的问题,这造成了不同的遍历⽅式。如果先处理当前 节点再处理⼦节点,那么就是前序。如果先处理左节点,再处理当前节 点,最后处理右节点,就是中序遍历。后序遍历⾃然是最后处理当前节点了。中序多⽤于⼆叉搜索树,因为⼆叉搜索树的中序遍历是严格 递增的数组。
    2. 从另⼀个⻆度看,树是⼀种递归的数据结构。因此树的遍历算法使⽤递归去完 成⾮常简单,幸运的是树的算法基本上都要依赖于树的遍历。但是递归在计算机中的性能⼀直都有问题,如果你使⽤迭代式⽅ 式去遍历的话,可以借助栈来进⾏,可以极⼤减少代码量。PS:树,递归,栈
    3. DFS 是树的从上到下,还有从下到上(后序遍历,要借助辅助变量,比如二叉树的最大路径和问题),从左到右遍历。从根到叶子,非根到非叶子,部分子树的左中右路径,最右边的节点(根右左顺序)。PS:真的是只有想不到,没有做不到
    4. 如果能使用参数 和节点本身的值 来决定应该传递给它的子节点 的参数,那么就用前序遍历。如果知道子节点的答案,才能计算出当前节点的答案,就用后续遍历。
  2. BFS细分为带层的和不带层的。锯齿形遍历,找每一层的最右节点,每一层的最大值,每一层的平均值。
    1. 层次遍历和 BFS 是完全不⼀样的东⻄,层次遍历就是⼀层层遍历树。层序遍历要求我们区分每一层,也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组,无法区分每一层。为此层次遍历在每一层遍历开始前,先记录队列中的结点数量 nn(也就是这一层的结点数量),然后一口气处理完这一层的 nn 个结点
    2. BFS 的核⼼在于求最短问题时候可以提前终⽌,这才是它的核⼼价值, 比如求(无权)最短距离,这个提前终⽌不同于DFS 的剪枝的提前终⽌,⽽是找到最近⽬标的提前终⽌。⽐如我要找距 离最近的⽬标节点,BFS 找到⽬标节点就可以直接返回,⽽ DFS 要穷举 所有可能才能找到最近的。
    3. BFS 采⽤横向搜索的⽅式, 在数据结构上通常采⽤队列结构。

由于链表只有⼀个 next 指针, 因此只有两种遍历。⽽⼆叉树有两个指针,因此常⻅的遍历有三个,除了 前后序,还有⼀个中序。如果是前序遍历,那么你可以想象上⾯的节点都处理好了,怎么处理的不 ⽤管。相应地如果是后序遍历,那么你可以想象下⾯的树都处理好了,怎 么处理的不⽤管。前后序对链表来说⽐较直观。对于树来说,其实更形象地说应该是⾃顶向 下或者⾃底向上。

正常使用一维数组存储一棵二叉树套路是

不管是DFS 还是BFS,本质上都是搜索,且通常来说都是暴力搜索(f(n) 展开为f(n-1),跟暴力搜索差不多了 ),因此需要对问题的所有可能情况进行穷举时,可以使用DFS和BFS,回溯法也是DFS 的一种,即回溯法也是一种保留搜索方法,只不过会涉及前进和回溯的过程。不管是DFS 还是BFS ,如果是在二维矩阵或图上进行搜索,通常都需要使用visited 来记录节点访问状态,树不存在环,也就不需要visited。

DFS

DFS算法流程

  1. ⾸先将根节点放⼊stack中。
  2. 从stack中取出第⼀个节点,并检验它是否为⽬标。如果找到所有的 节点,则结束搜寻并回传结果。否则将它某⼀个尚未检验过的直接⼦ 节点加⼊stack中。
  3. 重复步骤 2。
  4. 如果不存在未检测过的直接⼦节点。将上⼀级节点加⼊stack中。 重 复步骤 2。
  5. 重复步骤 4。
  6. 若stack为空,表示整张图都检查过了——亦即图中没有欲搜寻的⽬标。结束搜寻并回传“找不到⽬标”。

这⾥的 stack 可以理解为⾃⼰实现的栈,也可以理解为“调⽤栈”。如果是“调⽤栈”的时候就是递归,如果是⾃⼰实现的栈的话就是迭代。

⼀个典型的通⽤的 DFS 模板可能是这样的:

const visited = {}  
function dfs(i) {
    if (满⾜特定条件){
        // 返回结果 or 退出搜索空间
    }
    visited[i] = true       // 将当前状态标为已搜索
    for (根据i能到达的下个状态j) {
        if (!visited[j]) {  // 如果状态j没有被搜索过
            dfs(j)
        }
    }
}

上⾯的 visited 是为了防⽌由于环的存在造成的死循环的。 ⽽我们知道树 是不存在环的,因此树的题⽬⼤多数不需要 visited,因此⼀个树的 DFS 更多是

function dfs(root) {
    if (满⾜特定条件){
        // 返回结果 or 退出搜索空间
    }
    for (const child of root.children) {
        dfs(child)
    }
}

⽽⼏乎所有的题⽬⼏乎都是⼆叉树,因此下⾯这个模板更常⻅。

function dfs(root) {
    if (满⾜特定条件){
        // 返回结果 or 退出搜索空间
    }
    dfs(root.left)
    dfs(root.right)
}

其实二叉树的递归遍历,只要包含以上代码,就可以了,而针对不同的题目,我们会设置一些递归的返回值,设计递归函数的参数,或者用外部变量记录的方式,来达到题目的要求。而返回值、参数、外部变量是不影响递归的进行的(只要有以上代码),这时候就是发挥人类智慧,开始设计递归的时候。

PS:这段代码有点抛开数据结构 描述算法的味道。数据结构是为算法服务的,算法通常也要建立在某一种或几种数据结构之上。因为没有数据结构直接满足业务问题的需求,所以你可以先假设存在这个数据结构,看看算法怎么做,慢慢剥洋葱,去掉外围、表象,先定义需求再想实现,慢慢跟已有的经验靠拢。

// 前序遍历
function dfs(root) {
    if (满⾜特定条件){
        // 返回结果 or 退出搜索空间
    }
    // 主要逻辑
    dfs(root.left)
    dfs(root.right)
}
// 后序遍历
function dfs(root) {
    if (满⾜特定条件){
        // 返回结果 or 退出搜索空间
    }
    l = dfs(root.left)
    r = dfs(root.right)
    // 主要逻辑,通常会对l 和r 进行一些操作,比如问题依赖左右子树的返回值,此时应该给dfs 定义返回值
}

树是一个递归结构,因此大部分算法可以先用递归实现,然后看看要求再转为迭代实现。

BFS

本质就是不断访问邻居,把邻居逐个加入队列,根据队列先进先出的特点,把每一层节点访问完后,会继续访问下一层节点。

  1. ⾸先将根节点放⼊队列中。
  2. 从队列中取出第⼀个节点,并检验它是否为⽬标。 如果找到⽬标,则结束搜索并回传结果。 否则将它所有尚未检验过的直接⼦节点加⼊队列中。
  3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜索的⽬ 标。结束搜索并回传“找不到⽬标”。
  4. 重复步骤 2。
const visited = {}
function bfs() {
    let q = new Queue() // 如果在带权图上进行BFS,则可以考虑使用优先级队列来完成
    q.push(初始状态)
    while(q.length) {   // 队列不空,⽣命不⽌
        let i = q.pop()
        if (visited[i]) continue
        if (i 是我们要找的⽬标) return 结果
        for (i的可抵达状态j) {
            if (j 合法) {
                q.push(j)
            }
        }
    }
    return 没找到 
}

二叉搜索树

二叉搜索树的各种花活:查找某个节点(第k小、第k大);删除[a,b] 范围之外的节点;删除某个节点;校验是否是合法的二叉搜索树;最近公共祖先。

深度优先和广度优先遍历,{初始状态,目标状态,规则集合}在寻找最佳策略上的应用,不管你是什么算法,肯定都要遍历的

  1. 遍历要考虑几点:树的根,树有几个分叉(先遍历哪个分叉,再遍历哪个分叉),如何记录遍历的结果
  2. 不管是哪⼀种遍历, 如果图有环,就⼀定要记录节点的访问情况,防⽌死循环。 DFS 和 BFS 只是⼀种算法思想,不是⼀种具体的算法,因此其有着很强的适应性,⽽不是局限于特点的数据结构的,图 可以⽤,前⾯讲的树也可以⽤(树的前序、中序、后序就是以根节点为起点的 DFS 和 BFS 遍历)。实际上, 只要是⾮线性的数据结构都可以⽤

DFS 一般用栈实现,BFS 一般用队列实现,可以看看这些算法在工业界的运用,比如BFS 如何应用于跟踪垃圾回收。

岛屿类问题的通用解法、DFS 遍历框架岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。我们把数字为 0 的格子看成海洋格子,数字为 1 的格子看成陆地格子,这样相邻的陆地格子就连接成一个岛屿。在这样一个设定下,就出现了各种岛屿问题的变种,包括岛屿的数量、面积、周长等。不过这些问题,基本都可以用 DFS 遍历来解决。

堆其实就是⼀种数据结构,数据结构是为了算法服务的,那堆这种数据结构是为哪种算法服务的?它的适⽤场景是什么? 这是每⼀个学习堆的⼈ 第⼀个需要解决的问题。给⼤家⼀个学习建议 - 先不要纠结堆怎么实现的,咱先了解堆解决了什么问题。当你了解了使⽤背景和解决的问题之后,然后当⼀个调包侠,直接⽤现成的堆的 api 解决问题。等你理解得差不多了,再去看堆的原理和实现。

假如你是⼀个排队挂号系统的技术负责⼈。该系统需要给每⼀个前来排队 的⼈发放⼀个排队码(⼊队),并根据先来后到的原则进⾏叫号(出 队)。 除此之外,我们还可以区分了⼏种客户类型, 分别是普通客户, VIP 客 户 和 ⾄尊 VIP 客户。

  1. 如果不同的客户使⽤不同的窗⼝的话,我该如何设计实现我的系统? (⼤家获得的服务不⼀样,⽐如 VIP 客户是专家级医⽣,普通客户是 普通医⽣)
  2. 如果不同的客户都使⽤⼀个窗⼝的话,我该如何设计实现我的系统? (⼤家获得的服务都⼀样,但是优先级不⼀样。⽐如其他条件相同情 况下(⽐如他们都是同时来挂号的),VIP 客户 优先级⾼于普通客户)

堆的两个核⼼ API 是 push 和 pop。

  1. push : 推⼊⼀个数据,内部怎么组织我不管。对应我上⾯场景⾥ ⾯的排队和插队。
  2. pop : 弹出⼀个数据,该数据⼀定是最⼩的,内部怎么实现我不 管。对应我上⾯场景⾥⾯的叫号。

简单总结下就是,堆就是动态帮你求极值的。当你需要动态求最⼤或最⼩ 值就就⽤它。

堆两种常⻅的实现

  1. ⼀种是基于链 表的实现- 跳表。不借助额外空间的情况下,在链表中查找⼀个值,需要按照顺 序⼀个个查找,时间复杂度为 O(N)。我们从链表中每两个元素抽出来,加⼀级索引,⼀级索引指 向了原始链表。如果元素继续增⼤, 继续增加索引的层 数,建⽴⼆级,三级。。。索引,使得链表能够实现⼆分查找,从⽽获得 更好的效率。但是相应地,我们需要付出额外空间的代价。以空间换时间
  2. ⼀种是基于数组的实现 - ⼆叉堆。⼆叉堆就是⼀颗特殊的完全⼆叉树。它的特殊性只体现在⼀ 点,那就是⽗节点的权值不⼤于⼉⼦的权值(⼩顶堆)。那么很⾃然能推导出树 的根节点就是最⼩值。这就起到了堆的取极值的作⽤了。那动态性呢?⼆叉堆是怎么做到的呢?出堆:弹出根节点,使用最右侧节点(数组最后一个元素,方便访问)作为根节点,下沉以便符合堆的性质。 入堆:新节点作为最后一个节点,上浮以便符合堆的性质。
  3. 基于红⿊树 的实现。

一些算法

  1. ⼆分法的中⼼ - 折半。即⼆分法⽆论如何我们都可以舍弃⼀半解,也就是⽆论如何都可 以将解空间砍半。难点就是:什么条件 和 舍弃哪部分。 这是⼆分法核⼼要解决的问题。⼆分的本质是将问题规模缩⼩到⼀半,因此⼆分和数据结构没有本质关系,但是不同的数据结构却给⼆分赋予了不同的⾊ 彩。⽐如跳表就是链表的⼆分,⼆叉搜索树就是树的⼆分等。二分是分治思想的体现,分治是分解为几个规模更小的子问题, 直至子问题可以直接求解,二分是直接排除一半。对于最长重复字串问题, 我们可以将原问题拆分为两个子问题,然后在较优的时间复杂度内依次解决它们。
    1. 在 1 到 N 中枚举子串的长度; 对于k(子串长度),如果搜索发现包含重复子串,则增加k值,因为还可能存在更长的子串;如果不包含重复子串,则减小k值,因为不可能有比这更大的了;因为依次加减k效率很低,所以利用二分法操作k值。PS:这个时候,left和right 只是为了计算k,不直接选与选左侧还是选右侧的逻辑。
    2. 对于枚举的长度 L,检查字符串中是否有长度为 L 的重复子串。
    3. 不一定是 f(mid) == target,往往是中间元素和题目的目标值、左右相邻元素以及左右边界元素等存在一定的关联,根据这些关联可以将查找范围缩小一半。
  2. 前缀树的核⼼思想是⽤空间换时间,利⽤字符串的公共前缀来降低查询的时间开销。⽐如给你⼀个字符串 query,问你这个字符串是否在字符串集合中出现 过,这样我们就可以将字符串集合建树,建好之后来匹配 query 是否出 现,那有的朋友肯定会问, hashmap 岂不是更好?我们想⼀下⽤百度搜索时候,打个“⼀语”,搜索栏中会给出“⼀语道破”, “⼀语成谶(四声的 chen)”等推荐⽂本,这种叫模糊匹配,也就是给出⼀个模糊的 query,希望给出⼀个相关推荐列表,很明显,hashmap 并不容易做到模糊匹配,⽽ Trie 可以实现基于前缀的模糊搜索。前缀树的 api 主要有以下⼏个:
     insert(word) : 插⼊⼀个单词
     search(word) :查找⼀个单词是否存在
     startWith(word) : 查找是否存在以 word 为前缀的单词
    

为什么查询和排序是数据结构的基本操作

以缓存为例,一个缓存(cache)系统主要包含下面这几个操作:

  1. 往缓存中添加一个数据
  2. 从缓存中删除一个数据
  3. 在缓存中查找一个数据

这三个操作都涉及到查找操作,换句话说,对数据的操作无外乎crud,而cud都离不开查询。进而很明显,基于有序结构的查询速度是最快的,也就引出了排序算法的重要性。PS:查找 ==> 遍历(线性结构是遍历,树形图形结构是回溯) ==> 排序、动态规划、贪心等加速遍历(排序也可以作为预处理的一种手段)

  1. 查找基本办法是遍历,不同的数据结构不同的遍历方法,迭代、递归(f(n)展开为f(n-1) 也是一种遍历)等等,遍历即暴力搜索,需要利用“搜索目标的特性”在遍历过程中剪枝。一般要充分利用解空间的特性、规律 来加速遍历,有序是规律的一种。
  2. 针对不同的数据结构,查找的概念也会泛化。比如图中的查找最短路径,查找数组内符合某个条件的连续子序列(两个指针)/子序列/排列(可以认为是一个多叉树)
  3. 遍历有多种方式,比如线性表的从左到右、从右到左、左右一起遍历(比如快排、回文字串),一次遍历多个元素(比如双指针、快慢指针),比如树和图的深度优先、广度优先,遍历所有路径、遍历所有根到叶子节点路径、从左到右、从下到上。遍历可以轮询数据结构的每个节点,也可以是轮询数据结构的每个可能的子结构(比如字符串、数组的子序列)。比如遍历子串,可以i、j分别代表子串的头尾,也可以使用l、i分别代表子串的长度和起始的位置。
  4. 查找/遍历有多种目的,遍历的过程中找到符合某个条件的节点等等。解空间元素之间的关系,比如两个相等的子序列。遍历可能操作数据,比如把一个数通过限定操作变为1。
  5. 复杂结构的排序比较少见,排序一般可以加速单重遍历(毕竟不用一个个找了),对于子序列/排列问题,涉及到多重遍历(层数由子序列/排列的长度决定),有时根据“搜索目标的特性”,多重遍历的部分层遍历可以是并列关系(比如结果元素不重复且此消彼长,“三数之和+结果不重复”问题,可以使用头尾指针分别从头尾开始遍历,一层当两层用),因此排序也可以减少多重遍历的层数。

整体脉络:数据结构 ==> 增删改查、遍历方法 ==> 基于基本方法之上的,找到符合某一个/多个特征的元素 的算法 ==> 加速遍历

  1. 一般需要暴力法先列出所有解空间,解空间的描述很多样:窗口、树等。
  2. 解空间的分解也有先后,比如求一个字符串S的最长重复子序列,在S的所有子串中找到两个相等的、最长的。你可以先看S1开头的子串有没有重复的,再看S2的….。也可以先查询是否存在长度为len(S)的子串,然后再看长度为len(S)-1的子串…。区别是后者可以“剪枝”,因为如果能找到 长度为k的重复子串,那么k-1的就不用考虑了。
  3. 遍历的过程一般伴随有判断(实现时一般抽出来作为一个函数)的过程,比如是不是两数之和,是不是最长回文子串等
  4. 解空间的遍历,是依次遍历(for i:=0;i<len;i++{...}),从左到右,从中间到两边。还是取一些巧,二分遍历、跳跃着遍历(知道了当前步骤的结构,下一步或几步明显不符合结果),下一步是否可以直接通过当前步算出来而无需调用判断函数(本质就是动态规划)。脉络是时间复杂度从低到高:先试试O(logn)(二分),不行再试试O(n)(滑动窗口),实在不行O(n^2),此时遍历可以是暴力的,可以继续试试能不能减少判断函数的执行(动态规划,状态转移公式)
  5. 很多思路就是从暴力法来的,从笨方法优化而来,这是最稳妥的。暴力法不需要想思路,就是遍历所有可能,判断其是否是解,而不是去拼凑一个解。你直接想一个精巧的方法, 很可能不符合所有情况。很多思路都是优化中得到的思路,最后再冠以一个合理的解释,我们要是直接学了这些解释,很容易就碰到具体的问题又忘了。PS:这也是《算法通关之路》不厌其烦的每道题先讲一下暴力法。
  6. 暴力法之所以有问题,一方面是因为它产生重复的计算;另一方面暴力法往往还会去执行一些根本不可能是结果的代码。可以通过辅助数据结构、剪枝、滑动窗口来优化。注意,你要砍掉的是不可能是结果的遍历,而不是想办法去拼凑解,因为你总是很难罗列所有情况。PS:字节一面算法题的教训

碎碎念

查询的不同意涵

数据结构,model the application data,it is generally a requirement for any application to insert, edit and query a data store. Data structures offer different ways to store data items, while the algorithms provide techniques for managing this data. 不管什么样的数据结构,都跑不掉insert、edit、和query。尤其是query ,对于不同的数据结构,意涵很丰富

  1. 查询的入参不同,可能是index、数据的某个属性、范围、数据的某个特征(比如第k大的数)
  2. 查询返回的结果不同,可能是数据本身、数据集合、也可能是多个数据的组合(比如图的最优路径)

多重查询

  1. 数组 + hash 构成了散列表,根据index 查询和 key 查询 都是O(1)
  2. 假设 既想根据学号 又想根据成绩 查询学生,则可以先按学号递增组织学生数据,再按照分数构造一个散列表(该思想对应到数据库上,就是针对主键另外建了一个非聚簇索引)。

为什么散列表和链表经常会一起使用?

  1. 链表只能基于一个维度来构建有序数据,也只能基于这个维度来查询数据。基于链表构建一个散列表 则相当于 构建了一个“非聚簇索引”,增加了查询维度。
  2. 散列表中数据是经过散列函数打乱之后无规律存储的,在散列表上加链表(使用指针将散列表的n 个拉链 串起来),则可以支持散列表按照插入或访问顺序遍历数据,比如java中的LinkedHashMap。

设计数据结构的过程是一种“映射”

Data StructureComputer solution of a real-world problem involves designing some ideal data structures, and then mapping these onto available data structures (e.g. arrays, records, lists, queues, and trees) for the implementation. 先假设存在一种理想结构(以及它的api是啥,具体的说输入输出是啥),用流程 + 数据结构 将问题解决,然后再考虑着 组合基本结构去实现。

我们说面向的对象的四个基本特性:抽象、封装、继承、多态。在四个基本特性之上呢,一群类的组合,有了各种设计模式。

数组 + 哈希函数 就成了一个散列表。 也就是 基本特性的组合,是否也有设计模式一说呢? 对于跳表来说,与其说数据结构本来就是那样子,还不如说为了在链表上提高查询速度而衍生的数据结构。亦或者说B+树,我们也可以说先有底层那一条叶子链,再有的上层索引结构。

数据结构与业务设计

一般的业务系统要建立数据库表,数据库表要建立索引。笔者有一个经验,不要一开始建立索引。而是业务代码完毕后,观察常查询的属性,然后对这些数据建立索引。如果你愿意,索引 + 数据库表,就是一种数据结构,数据结构的构建(比如建立索引) 要反应业务的“意志”。

Definition of a Data Structure & AlgorithmsComputing applications use many different types of data. Some applications model data within database systems, in which case the database system handles the details of choosing data structures, as well as the algorithms to manage them. However, in many cases, applications model their own data. When programmers decide what type of data structure to use for a particular set of data in an application, they need to take into account the specific data items to be stored, the relationships between data items and how the data will be accessed from within the application logic. ddd(一)——领域驱动理念入门 也提到,一般业务以数据库ER设计为驱动,数据库设计代表了对业务的认识深度,也是业务的精华所在。 由此看, 数据库完成了一个项目本身应有的数据结构与算法的活儿,我们不用直接进行数据结构设计(这由数据库封装),而是通过ER表设计来间接影响数据库进行实际的数据结构设计。

Algorithms for managing data structures sometimes involve recursion. With recursion, an algorithm calls itself, which means it repeats its own processes as part of a looping structure, with each step simplifying the problem at hand. Recursive algorithms can allow programmers to implement efficient sorting and searching techniques within their applications. However, writing recursive algorithms can be difficult for beginners, as it does require a significant amount of practice. 这段有一个很有意义的观点,Recursive algorithms 一般要对应 looping structure,是不是可以笼统的说:递归的算法一般对应着可以递归的数据结构。

建模

数据结构 + 数据结构 ==> 某方面更优秀的数据结构。算法也要类似的特点,计算机只能执行:顺序;循环;选择。leetcode上成千上万道算法题,最后只归结到十几类题目,比如“排序+自定义排序策略”,就可以解决很多实际问题。数据结构 + 算法 ==> 更优秀的数据结构。

基于冯诺依曼体系结构的计算机本质上是一个状态机,为什么这么说呢?因为 CPU 要进行计算就必须和内存打交道。内存就是用来保存状态(数据)的,内存中当前存储的所有数据构成了当前的状态,CPU 只能利用当前的状态计算下一个状态。我们用计算机处理问题,无非就是在思考:如何用变量来储存状态,以及如何在状态之间转移:由一些变量计算出另一些变量,由当前状态计算出下一状态。基于这些,我们也就得到了评判算法的优劣最主要的两个指标:

  1. 空间复杂度:就是为了支持计算所必需存储的状态
  2. 时间复杂度:就是初始状态到最终状态所需多少步

有两个容量分别为x升和y升的水壶及无限多的水,请判断能够通过使用这两个水壶,得到恰好z升的水?如果可以,请用以上水壶中的一或两个来盛放取得的z升水。允许你:装满任意一个水壶/清空任意一个水壶/从一个水壶向另一个水壶倒水,直到装满或倒空。

我们用(x,y)这样的元组来表示水壶的盛水状态,那么初始状态就是(0,0),可以采取的行动有以下6种。

  1. 将x的水倒空
  2. 将y的水倒空
  3. 将x的水盛满
  4. 将y的水盛满
  5. 将x的水全部倒给y(x可能倒不完,同时y可能溢出)
  6. 将y的水全部倒给x(y可能倒不完,同时x可能溢出) 每一种行动之后,都对应一个状态,同样元组表示。

描述解空间 ==> 在解空间中搜索/查找(基础是遍历) ==> 复杂数据结构与算法 ==> 基本数据结构 + 顺序;循环;选择

其它

在面试中,会有很多设计题,设计一些数据结构,以高效的实现某些操作。

数据结构的”基本类型化”:较早出现的编程语言,比如c语言,基本类型只包括:int,char,long等,string、map等则需要引用库。而对于新兴语言,比如go和python等,则在语言层面支持string、map等复杂结构。这一趋势,甚至扩展到了一些内存数据库。