YaPiBlog

You look look you one day day de

数据结构(七)线段树

线段树平衡树平衡树，即平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树、SBT等线段树不是一个完全二叉树，但是是一颗平衡二叉树，如果把最下层空节点看成空的节点，那么它也是一颗满二叉树。对于一颗满二叉树来说有...

Created by YaPi on August 25, 2019

数据结构(六)堆和优先队列

优先队列普通队列：先进先出、后进后出优先队列：出队顺序和入队顺序无关；和优先级有关操作系统中进行任务的调用就是优先队列，会动态的选择优先级最高的任务执行。优先队列经典问题在N个元素中选出M个元素使用优先队列，维护当前看到的前M的元素使用最小堆，每次将根节点的那个最小的元素提出来 java 中的PriorityQueue默认实现就是最小堆堆堆的基本结构最...

Created by YaPi on August 25, 2019

数据结构(五)树-二分搜索树

二叉树二叉树具有唯一跟节点二叉树中每个节点最多有两个孩子没有孩子的节点称为叶子节点二叉树中每个节点只能有一个父亲节点二叉树不一定是满的一个节点也是二叉树 NULL 空也是二叉树二分搜索树二分搜索树是二叉树二分搜索树的每个节点的值都大于其左子树的所有节点的值二分搜索树的每个节点的值都小于其右子树的所有节点的值每一棵子树也是...

Created by YaPi on August 24, 2019

数据结构(四)动态数据结构-链表

链表 Linked List 最简单的动态数据结构数据存储在节点中真正的动态，不需要处理固定容量的问题丧失了随机访问的能力数组与链表的对比数组最好用于索引有语意的情况数组支持快速查询链表不适合用于索引有语意的情况链表的最大优点:动态时间复杂度分析如果要对链表进行随机的新增、查询、修改、删除的操作的话，这些操作的时间复杂度都是...

Created by YaPi on August 23, 2019

数据结构(三)栈、队列

栈基础特点栈也是一种线性结构相比数组，栈对应的操作是数组的子集只能从一段添加元素，也只能从一段取出元素添加(入栈)或取出(出栈)的那一段称之为栈顶后进先出 (Last In First Out) LIFO 栈的应用无处不在的Undo操作(撤销操作) 操作系统或程序会将你的操作放进一个栈中。点击撤销的时候，将最后添加的操作出栈。程...

Created by YaPi on August 22, 2019

数据结构(二)时间复杂度分析+自定义数组

简单的时间复杂度分析 O(1)、 O(n)、 O(lgn)、 O(nlogn)、大O描述的是算法的运行时间和输入数据之间的关系例： public static int sum(int[] nums){ int sum = 0; for(int num : nums)sum += num; return sum; } 上述的时间复杂度是 O(n)...

Created by YaPi on August 21, 2019

数据结构(一) 入门

入门什么是数据结构？数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据或者修改数据。近乎所有的算法都需要数据结构做为基石。总的来说可以分为三种结构线性结构数组、栈、队列、链表、哈希表… 树结构二叉树、二分搜索树、AVL、红黑树、Treap、Splay、堆、Trie、线段树、K-D树、并查集、哈夫曼树… 图结构领结矩阵、邻接表

Created by YaPi on August 20, 2019

Go标准库-time

Time Time 代表一个纳秒精度的时间点。程序中应使用Time类型值来保存和传递时间,而不是指针。就是说,表示时间的变量和字段应为time.Time类型,而不是*time.Time类型。一个Time类型的值可以被多个go程同时使用。时间点可以使用Before、After、Equal方法进行比较。Sub方法让两个时间点相减,生成一个Duration类型值(代表时间段)。Add方法给...

Created by YaPi on August 18, 2019

Go标准库-testing

test - Go包的⾃动化单元测试测试文件的文件名需要以_test.go结尾,测试用例需要以TestXxxx的样式存在 testing 基本用例测试 testing/iotest - io测试 testing/quick 进⾏⿊盒测试的辅助功能包 net/http/httptest 提供测试 HTTP 的⼯具 Test TestXxxx(t *testi...

Created by YaPi on August 18, 2019

Go标准库-进程、os、sync、atomic

创建进程在Unix中，创建⼀个进程，通过系统调⽤fork实现（及其⼀些变种，如vfork、clone）。在Go语⾔中，Linux下创建进程使⽤的系统调⽤是clone。很多时候，系统调⽤fork、execve、wait和exit会在⼀起出现。此处先简要介绍这4个系统调⽤及其典型⽤法 fork: 允许⼀进程（⽗进程）创建⼀新进程（⼦进程）。具体做法是，新的⼦进程⼏近于对⽗进程的翻版：...

Created by YaPi on August 18, 2019