常用算法和数据结构讲解,面试算法题/leetcode解题,提供golang/js版本
用通俗易懂的语言来介绍工作和面试中常见的数据结构和算法,提供golang/cpp/js实现。另外提供面试中常见算法题,尤其是leetcode题目的讲解和golang/cpp代码实现。
增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表,简称跳表。跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。
这里采用redis底层类似的实现,在每层上增加了偏移量的记录,好处是在按排行取元素的时候可以先从上层按偏移量快速定位到目标位置,不需要在底层链表进行遍历定位。
LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最久未使用的页面予以淘汰。
LFU(least frequently used (LFU) page-replacement algorithm)。即最不经常使用页置换算法,要求在页置换时置换引用计数最小的页,因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多,但以后就不再使用,这类页将会长时间留在内存中,因此可以将引用计数寄存器定时右移一位,形成指数衰减的平均使用次数。
堆是一种带有顺序结构的完全二叉树,分为大根堆和小根堆,根据完全二叉和父子大小关系,利用数组结构比较容易实现堆结果。 golang源码中也实现了一个小根堆(代码在container/heap/),采用接口化的设计,实用性大大提升,值得好好学习一番,主要亮点:
golang实现的单链表和双链表结构和源码分析。 golang源码的双向链表实现(代码在container/list/)亮点:
做任何算法的时候,都要先弄清需求!如果是需要构造一个函数,那一定要弄清楚函数的调用方式、各参数的含义,多举几个例子说明。只有弄懂了这个函数应该是怎样的,才有可能写出符合要求的函数
LeetCode解题(golang)
golang实现:
js实现: