烦躁

​ 下午两点过一点,从宿舍走出来,外面还是淅淅沥沥下着小雨。心里不是很舒服,一直不喜欢下雨,阴冷的天气,总是让人觉得不适,什么都不适合,不适合上课不适合看书,就想让人躺在床上。躺在床上就不经意间会回忆到以前,想到种种。 ​ 算了不管了,还是去实验室一个人清净一会,这里就我一个人。拉上窗帘根本看不到外面在下雨,就好像一个晴天的夜晚。 ​ 打开电脑准备看看 Coursera 上面的算法,可是静不下心来,真的静不下心来!我尽力让自己平静,关掉了窗口,算了!刷题吧,连续点开了三道...

Read More

1-d range

​ 1d range 的问题主要就是讨论,在某两个符号之间存在多少个其他的符号。首先这里用到了二叉排序树,然后我们利用了二叉排序树的 rank 操作就能直接得到两个符号之间的 range 数

Read More

平衡搜索树

2-3树​ 其实仔细来看2-3树好像是 B 树的一个特例,它规定了一个节点要么有一个 key 要么有两个 key。 如果有一个 key 那么他就有两个子节点,左边小于这个 key 右边大于这个 key 如果有两个 key 那么他就有三个子节点,左边小于,中间处于两者之间,右边大于 ​ 这样一来就会发现他其实也会处在插入的时候出现分裂的情况,当一个节点需要插入的时候我们先让他插入,这时候可能出现一个节点有三个 key 的情况,我们就打出四个分支,然后我们把中间的那个 ...

Read More

优先队列

优先队列基本介绍​ 优先队列又叫做堆,他是一种比较特殊的完全二叉树。所谓完全二叉树就是一层层的堆叠,本层不满就不能堆放下一层。并且优先队列还有一个特点就是如果他是大根堆那么父节点不小于子节点,如果是小根堆父节点不大于子节点。这也是一个递归定义。 为什么要是用优先队列? 首先如果我们需要查找一个第 k 大的数字,毫无疑问这个是最方便的 他的插入操作和删除操作都是 logn 的复杂度,所以说他是最经济的方式 优先队列的常用操作插入插入的时候我们一般采用的方式就是上滤,也就是把要插入的...

Read More

排序算法

选择排序:​ 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。 ​ 但是这个算法的复杂度比较高,为$$n^2/2$$​ 那为什么是这个值,假若我们放一张 n x n 的表格,然后我们在排序的过程中用灰色表示不变的元素,然后用黑色表示变化的元素。这样一来我们会发现这个表格是一个以对角线分隔的一个矩阵。很统一看到我们进行了二分之一的 n^2 扫描。 ​ 这个算法的另外一个问题就是无论我们的序列本来是否有序,我们...

Read More

并查集

​ 在我们需要判断某一些事物之间是否存在一定的关系的时候,我们最好的办法不是使用图而是使用并查集。因为我们关心的是他们之间是否有关系,而不是关心的他们到底存在怎样的关系。 ​ 并查集,简单来说就是 n 个集合,我们通过 union 操作来建立两个节点之间的关系。通过 connected 来判断两个节点之间的关系。那么现在我们知道了 并查集的基本操作就是 union 和 connected 。 逻辑结构:并查集一开始我们初始化都是初始化 n 个不相关的独立集合。然后我们在做 un...

Read More

吐槽关于许鹏飞

​ 今年的微机原理的老师竟然叫许鹏飞,这个我也没什么好吐槽的。本来上学期以来对伟明哥教的计算机组成原理还是蛮感兴趣的,最后成绩也还不错。没想到今年又学一点计算机的基本原理和体系结构能丰富一下自己对计算机的理解增长一点见识。不过到目前为止计算机的知识我都是没增长多少,对这个老师的态度真的不是很好。首先他说他是经管院的考研考到计算机专业的,当时还是挺佩服的。 ​ 然而他后来的种种举措导致我对他的影响非常不好: 文科生+理科生的教学方式,自己理解的不是很透彻的就硬背,程...

Read More

吐槽关于许鹏飞

​ 今年的微机原理的老师竟然叫许鹏飞,这个我也没什么好吐槽的。本来上学期以来对伟明哥教的计算机组成原理还是蛮感兴趣的,最后成绩也还不错。没想到今年又学一点计算机的基本原理和体系结构能丰富一下自己对计算机的理解增长一点见识。不过到目前为止计算机的知识我都是没增长多少,对这个老师的态度真的不是很好。首先他说他是经管院的考研考到计算机专业的,当时还是挺佩服的。 ​ 然而他后来的种种举措导致我对他的影响非常不好: 文科生+理科生的教学方式,自己理解的不是很透彻的就硬背,程...

Read More

二叉树

1.二叉树的性质1.具有 n 个节点的二叉树第 n 层最多2的 n-1 次方个节点2.具有 n 个节点的二叉树最多有 2 的 n 次方减 1 个节点3.度为 0 的节点数等于度为 2 的节点数加 1 节点度的关系 n=n0+n1+n2边的条数就是 n-1 ,也就是节点的关系的个数 另外一方面就是从父亲的方面来看就是利用度来计算 n0*0+n1*1+n2*2也就是从不同的角度来理解这个东西获得一个等式从而得到的 2.两个小概念:满二叉树:所有的节点排满了完全二叉树:按顺序从左向右排放...

Read More


Powered by Hexo and Hexo-theme-hiker

Copyright © 2015 - 2021 昨夜凛雨 All Rights Reserved.

UV : | PV :