优先队列

2017-09-24 -数据结构与算法

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

排序算法

2017-09-23 -数据结构与算法

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

并查集

2017-09-23 -数据结构与算法

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

吐槽关于许鹏飞

2017-09-18 -小记

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

吐槽关于许鹏飞

2017-09-18 -小记

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

二叉树

2017-09-11 -数据结构

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.两个小概念：满二叉树：所有的节点排满了完全二叉树:按顺序从左向右排放...

HouseRobber

2017-09-07 -LeetCode

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will a...

IntersectionOfTwoLinkedLists

2017-09-07 -LeetCode

Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b...

归并排序

2017-09-05 -LeetCode

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。 1234567891011121314151617181920//将有序数组a[]和b[]合并到c[]中 void MemeryArray(int a[], int...

LinkedListCycle

2017-09-04 -LeetCode

Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space? 分析一开始使用了复杂度O(n^2)的方法，使用两个指针a, b。a从表头开始一步一步往前走，遇到null则说明没有环，返回false；a每走一步，b从头开始走，如果遇到b==a.next，则说明有环true，如果遇到b==a，则说明暂时没有环，继续循环。后来找...