0%

什么是单调栈

顾名思义,单调栈即满足单调性的栈结构。与单调队列相比,其只在一端进行进出。
为了描述方便,以下举例及伪代码以维护一个整数的单调递增栈为例。

  • 单调递增栈:单调递增栈就是从栈底到栈顶数据是从大到小
  • 单调递减栈:单调递减栈就是从栈底到栈顶数据是从小到大

单调栈的特性

对于单调递增栈。若当前进栈元素大于栈顶元素,则会把栈顶元素弹出栈。这个性质能保证栈顶元素是栈内小于它的元素遇到的第一个大数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def findFirstGreatNum(arr):
# stack存放arr的元素下标
stack = []
result = [-1] * len(arr)
for (i, n) in enumerate(arr):
while stack and n > arr[stack[-1]]:
# 说明n是第一个大于arr[stack[-1]]的数
idx = stack.pop()
result[idx] = n
stack.append(i)
print result


arr = [3,4,2,6,4,5,2,3]
# 6是第一个大于4,2的元素
findFirstGreatNum(arr)

输出:[4, 6, 6, -1, 5, -1, 3, -1]

摩尔投票法

摩尔投票法的核心思想为对拼消耗。

每次从序列里选择两个不相同的数字删除掉(或称为「抵消」),最后剩下一个数字或几个相同的数字,就是出现次数大于总数一半的那个元素。

首先我们考虑最基本的摩尔投票问题,比如找出一组数字序列中出现次数大于总数21的数字(并且假设这个数字一定存在)。

简介

线段树(Segment Tree)主要用于维护区间信息(要求满足结合律)。与树状数组相比,它可以实现 O(logN)的区间修改,还可以同时支持多种操作(加、乘),更具通用性

定义

并查集是一种树形的数据结构,用来表示不相交集合的数据。并查集中的每个子集是一棵树,每个元素是某棵树中的一个节点。树中的每个节点有一个指向父节点的指针,树的根节点的指针指向它自己。

合并和查找

并查集支持两种操作,即合并和查找。合并操作将两个子集合并成一个集合,只需要将一个子集对应的树的根节点的指针指向另一个子集对应的树的根节点。

Read more »

机器数和真值

1、机器数

一个数在计算机中的二进制表示形式,叫做这个数的机器数。机器数是带符号的,最高位存放符号,正数为0,负数为1。

比如,十进制中的数 +3 ,计算机字长为8位,转换成二进制就是00000011。如果是 -3 ,就是 10000011 。
那么,这里的 00000011 和 10000011 就是机器数。

2、真值

因为第一位是符号位,所以机器数的形式值就不等于真正的数值。例如上面的有符号数 10000011,其最高位1代表负,其真正数值是 -3 而不是形式值131(10000011转换成十进制等于131)。

Read more »

写在前面

iospeed

磁盘IO主要的延时是由(以15000rpm硬盘为例):
机械转动延时(机械磁盘的主要性能瓶颈,平均为2ms) + 寻址延时(2~3ms) + 块传输延时(一般4k每块,40m/s的传输速度,延时一般为0.1ms)
决定。(平均为5ms)

网络IO服务器响应延时 + 带宽限制 + 网络延时 + 跳转路由延时 + 本地接收延时
决定。(一般为几十到几千毫秒,受环境干扰极大)
Read more »

二叉搜索树

二叉搜索树(Binary Search Tree),它或者是一棵空树,或者是具有下列性质的二叉树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
  • 它的左、右子树也分别为二叉搜索树
    Read more »

前缀树

又名字典树,单词查找树,Trie树,是一种多路树形结构,是哈希树的变种,和hash效率有一拼,是一种用于快速检索的多叉树结构

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

Read more »