数据结构-Treap

今天的算法课上,老师讲了一个比较有意思的数据结构:Treap。它的名字就比较有意思,为什么叫Treap呢?是Tree + Heap两个单词的结合,所以这个数据结构也就是二叉树和二叉堆的结合了。

简介

Treap也是平衡二叉搜索树的一种。

Balanced Binary Search Tree 也可以简称为 Balanced Search Tree,为了方便区分我下面会简称为BBST

Read More

Java基础-ArrayList和LinkedList

相对与HashMapArrayListLinkedList都算比较简单的数据结构,通过这篇文章分别的了解一下它们。

Read More

Java基础-HashMap源码简析

基于HashMapJDK1.8中的源码

参考前辈们的成果,简单的分析HashMap的源码,了解一下HashMap的存储结构,主要方法工作原理和线程安全这几个方面。

Read More

Java基础-Object的11个方法

一切从对象开始。在Java中Object类是是所有类的父类,也是根类。它一共有11个方法。

Read More

Java基础-目录

接下来应该会写一系列Java基础的笔记吧,之前虽觉得自己已经熟悉Java,但都没有系统的做笔记和整理,而且Java也是自学的,很多知识都没有巩固和涉及,所以会顺着这个技能图谱写下去,可以在这个tag下找到这些笔记。为了准备春招,加油啊(

Read More

2018年

The article has been encrypted, please enter your password to view.

Read More

乞丐版Vi编辑器的实现2-原始输入输出

实现乞丐版Vi的第二步,主要完成的功能有读取键盘的输入,键位映射和移动光标。

Read More

乞丐版Vi编辑器的实现1-Raw mode

参考 Entering raw mode

这一节的内容可能比较枯燥,是一些底层的 Terminal 的属性:canonical mode,回显(echoing),键盘按键对应的 ASCII 码(可以发现一些按键不止对应一个编码,还有些按键对应的是同一个编码)和一些杂项设置…通过改变这些设置,让 Terminal 进入所谓的 “raw mode”。

Makefile

我使用 make 来构建 VIP,因为只有两个源文件,所以 Makefile 很简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
CC = gcc
CFLAGS = -Wall -Wextra -pedantic -std=c99 -O3

all: vip

debug:
$(CC) $(CFLAGS) vip.c -g -o vipd

re:
make clean;make

clean:
rm -f vip vipd

CFLAGS 里使用 c99 标准;使用-O3进行编译优化,主要是对内联函数进行优化;-Wall -Wextra -pedantic会打印一些额外的警告,对 debug 有帮助。

Read More

乞丐版Vi编辑器的实现0-想法

逛 GitHub 的时候发现了一个大概几百行 C 代码实现的命令行编辑器,但是看了一些代码,感觉好垃圾。于是 Google 一下,发现一个Build Your Own Text Editor的教程。直觉告诉我,一般这种英文的 booklet 都是小而精的,果然这次也没有让我失望。看它的简介:

Read More

CSAPP Data Lab 思路和笔记

Data Lab[Updated 11/2/18]

11/2/18 新鲜出炉的 Data Lab,不同时期的 lab 内容会不一样。

肝了两天还是没有全部做出来,之前很以为很简单呢(

最近也终于买了 CS:APP3e 英文版,配合 CMU 的课程视频食用更佳。顺便可以练习英语听力和阅读,阅读已经可以流畅了,这种英文书基本看得懂,但是听力就不行(

解题的思路一般会写在注释里的。

bitXor

1
2
3
4
5
6
7
8
9
10
11
12
13
/*s
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitXor(int x, int y) {
// 德摩根定律
// a xor b = (~a | ~b) & (a | b)
// = ~(a & b) & ~(~a & ~b)
return ~(~x & ~y) & ~(x & y);
}

虽然这题比较简单,但我还是想了好久。主要是我把这个德摩根定律忘得差不多了,记得在离散数学里讲过。

利用的性质主要是:

  • a ^ b = (~a | ~b) & (a | b)
  • (~a | ~b) = ~(a & b)

Read More