- 博客(102)
- 收藏
- 关注
RSS订阅原创 base64
base64有些协议是文本协议，但是需要传输二进制数据。base64正是将二进制数据转换为可显示字符集的一种编码。思想标准ascii中127个字符，[0-31]和127是不可显式的字符。那么[32-126]这个区间，94个字符是可以显示的。base64只选用了其中的64个字符，为什么选用64个呢，这个算法实现是有关联的。字符肯定和数据是联系起来的，为了能表示64个字符，需要6位的二进制数据...
2019-02-14 18:30:36
284
原创 snowflake
文章目录snowflake原理优点缺点源码解读包变量解读节点生成一个节点生成ID关于作者snowflake这个算法是twitter开源的，作用是分布式下生成全局唯一的ID。原理Each time you generate an ID, it works, like this.A timestamp with millisecond precision is stored using 4...
2019-01-31 17:04:41
434
原创 trie
前缀树前缀树主要用于词频统计，一些补全也可以实现。特点根节点不包含字符，除根节点意外每个节点只包含一个字符。从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。每个节点的所有子节点包含的字符串不相同。结构type node struct { pass int end int child map[byte]*node}pass：节点添加的次数...
2019-01-17 18:02:33
261
原创 4-主引导程序
文章目录主引导程序加载位置显卡显卡如何控制显示器显存中的信息如何解释显存映射实验程序代码疑问实战操作关于作者主引导程序主引导程序的用处应该是通过一个中间程序加载操作系统或者直接加载操作系统，但此处只做学习，所以此处主引导程序的作用是打印一些文本内容。主引导区用来存储主引导程序，但是主引导区的大小只有512字节，难道主引导程序只有这么大？那就看看吧。位置：位于存储介质最开始处，大小512字...
2019-01-16 17:37:06
949
1
原创 Morris先序中序遍历
文章目录Morris先序中序遍历实现原理先序遍历中序遍历疑问总结关于作者Morris先序中序遍历这里把Morris实现先序中序遍历放在一起记录是因为先序和中序原理相同。这两者都和各自的递归版本有着很强的联系性。实现原理在上一节Morris遍历文章中，阐述了递归的本质。再来熟悉下：递归实现前中后序遍历二叉树的算法非常简单，但是深入探究背后，会发现三者其实是统一的。为什么这么说，这是因为三...
2019-01-14 18:20:42
412
原创 3-主引导区
文章目录主引导区硬盘原理主引导扇区关于作者主引导区主引导区通常是外存的前512字节，因为外存的前512字节存放主引导程序。硬盘相对于内存来说，一个相对的概念是外存，比如常见的软盘，硬盘，光盘，U盘等。这些外存的作用都是相同，这里着重讲解硬盘。原理硬盘可以只有一个盘片，也可以有多个盘片。每个盘片都有两个磁头，上面一个，下面一个。可以分为扇区，磁道和柱面。主引导扇区对于硬盘来...
2019-01-14 16:44:21
310
原创 2-BIOS
文章目录BIOS内存容量组成映射范围及用途计算机架构BIOS功能为什么BIOS是第一个运行的程序BIOS控制权转移总结关于作者BIOS内存无论什么汇编寻址都无外乎3中，立即数，寄存器和内存。最复杂的当属于内存。因为程序都是存储于内存中的，所以在将第一个运行的程序（BIOS）时先介绍内存。容量8086的内存有1MB的容量，但是这1MB分别映射到不同的器件上。组成内存由三部分组成：R...
2019-01-14 16:21:04
238
原创 1-段寄存器由来和策略
文章目录段寄存器问题解决思路解决方案段地址的要求为什么要整除16关于作者段寄存器在汇编的时候操作的都是物理地址，简单粗暴，却也带来了一些问题。问题在汇编程序结束后，如果发给他人使用，必须将程序加载到固定的内存位置，否则程序将出错。同时这样也使得多任务的运行更加困难。问题的根本原因在于程序无法重定位。解决思路8086提出了分段的策略，程序中使用偏移地址，间接的通过“段地址:偏移地址”确...
2019-01-14 15:58:38
382
原创 Morris遍历算法
文章目录Morris遍历概念步骤再论递归遍历Morris序分析后续关于作者Morris遍历二叉树有前中后序遍历，还有层次遍历，为什么还需要Morris遍历呢？考虑一下前中后序的遍历，这三种的空间复杂度总是逃不过O(h)，h=height(root)，层次遍历的空间复杂度也不可能达到O(1),恰巧Morris遍历就是空间复杂度为O(1)的遍历，而且时间复杂度依旧保持O(N)。概念对二叉树进...
2019-01-12 23:47:46
482
原创 搜索二叉树的判断
文章目录搜索二叉树的判断搜索二叉树思路1思路2关于作者搜索二叉树的判断比较常见的面试题。搜索二叉树概念不说了，相信各位同学都是知道的，不知道的Google一下。思路1起初看到这个题，本来想着直接找递归公式，递归的判断，尝试了一下。发现不行。把尝试的代码贴出来吧。func isValidBST(root *TreeNode) bool { return middleTranve...
2019-01-11 15:55:41
383
原创 完全二叉树的判断
文章目录完全二叉树的判断完全二叉树思路代码关于作者完全二叉树的判断各种二叉树的判断是经常出现的题目，这里给出的是完全二叉树的判断。完全二叉树第一次看到概念觉得很晦涩，但是结合图一下就知道是不是一棵完全二叉树。不知道的完全二叉树的同学先自行搜索相关概念。思路既然树的题目逃不过遍历，那么在四种遍历挑选一种同学们觉得哪种遍历能够解决问题，直觉告诉我就是层次遍历，不要说这是瞎扯，结合完全二叉树...
2019-01-11 15:53:42
936
原创 二叉树中的一个节点的后继节点
文章目录二叉树中的一个节点的后继节点题目方法普通方法进阶方法二叉树中的一个节点的后继节点这是第一次接触二叉树中后继节点这个概念，觉得很好玩就来看一看。所谓的后继节点就是中序遍历二叉树后这个节点后面的那个节点。题目二叉树的定义多了一个指向父节点的指针，根节点的父节点指针为空。struct node { int Value *node Left *node Right...
2019-01-10 14:59:17
1832
原创 redis-intset
文章目录intset结构源码预备知识判断整数编码类型根据类型获得pos位置的元素设置函数查询函数升级函数移动函数添加函数移除函数总结关于作者intset整数集合，是有序存储的，且不包含重复的元素。结构typedef struct intset { uint32_t encoding; uint32_t length; int8_t contents[];} int...
2019-01-07 12:38:51
261
原创 redis-dict下
文章目录dict函数添加dictAdddictAddRow查找_dictKeyIndexdictAddOrFinddictFinddictFetchValue删除更改释放关于作者dict 终于到了哈希表的最后一篇了，终于又到了源码部分了。只要理解了前两篇的原理部分，那么源码解读其实就是把原理转换成代码的过程。也可以说是对我们阐述的原理的验证。废话不说，直接干。函数所有的数据结构都是围绕增...
2019-01-07 12:37:23
292
原创 redis-dict中
文章目录dict解决哈希冲突为什么出现哈希碰撞解决方法rehash为什么要rehash什么时候需要rehashredis的rehash渐进rehash使用两个哈希表定时rehash优化函数创建总结关于作者dict 今天是哈希表的中篇，花了很大的篇幅来描述哈希表，足以证明这个结构的重要性了。redis就是基于哈希的一个设计，而且如今的分布式都和哈希有着密切的关系。redis的数据结构部分结束后...
2019-01-07 12:35:40
440
原创 redis-dict上
文章目录哈希表哈希函数作用特点结构节点哈希表字典总结问题dictIteratorAPI创建类函数_dictResetdictCreatedictInit查找类操作dictFind增加类操作dictAddRawdictReplace关于作者哈希表花哨的算法比简单算法更容易出 bug、更难实现。尽量使用简单的算法配合简单的数据结构。只要掌握了数据结构中的四大法宝，就可以包打天下，他们是：arr...
2019-01-07 12:34:03
184
原创 redis-adlist
文章目录adlist1 数据结构1.1 节点的表示1.2 迭代单元1.3 链表2 宏解析3 函数3.1 创建3.1.1 listCreate3.2 增加3.2.1 头插法3.2.2 尾插法3.2.3 节点前后法3.3 删除3.3.1 删除单个节点3.3.2 删除所有节点3.4 更改3.4.1 旋转链表3.4.2 合并链表3.5 查询3.5.1 获取索引节点3.5.2 判断节点存在3.6 释放3.6...
2019-01-07 12:31:18
372
原创 ASCII-Unicode-UTF-8
文章目录字符编码ASCII标准ASCII扩展ASCIIUnicode目的UTF-8编码规则UTF-8演示特点关于作者字符编码ASCII标准ASCII一个字节的低7位存储数据，最高位用作奇偶检验位。扩展ASCII一个字节全部用来存储数据。UnicodeUnicode不是编码，而是字符集，字符集为每个“字符”都规定了一个码点（二进制的序列）。目的为了统一所有文字的编码。UTF-8...
2019-01-07 12:27:59
135
原创 回溯法
文章目录回溯思想适用范围经典解空间树子集树排列树关于作者回溯回溯的思想比较简单，但是却可以解决很多问题。思想回溯的思想是穷举所有可能的结果去尝试，如果走的通就继续前进，否则就退回重新选择。在穷举的过程中可以利用剪枝去过滤一部分不可能的结果。适用范围回溯法是穷举，那么必然会得到一个问题的全部解，进而又可以得到一个问题的最优解。这两点也正是回溯法的适用范围。这两种不同的情况又引出了两个属...
2019-01-07 12:20:50
1334
原创 平衡二叉树的判断
文章目录平衡二叉树的判断开门题问题思路实现树的高度平衡性的判断关于作者平衡二叉树的判断二叉树是比较常见的树，而且树的平衡具有非常重要的特性。如果一颗搜索二叉树的平衡性不是很好，那么搜索的效率就不会很高了。开门题前几天考研，今年人大计科的编程题就是判断一棵树是否为平衡二叉树。所以就先拿这个题热热身。问题既然要判断一棵树是否为平衡二叉树，那么久需要先理解什么是平衡树。空树是一颗平衡树...
2019-01-07 12:18:06
667
原创 完全二叉树节点个数
文章目录完全二叉树节点个数完全二叉树实现遍历借助完全二叉树的特点完全二叉树的层数原理第一种情况第二种情况实现时间复杂度关于作者完全二叉树节点个数最简单的解法就是遍历这棵树，时间复杂度是O(N)，如果只是这一种解法，就不会有本文了。本文中给出两种解法。完全二叉树第一次看到完全二叉树的定义比较懵，搜索到的定义如下：设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到...
2019-01-07 12:15:25
2623
原创 搜索二叉树中两个节点的最近公共祖先
搜索二叉树中两个节点的最近公共祖先Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.According to the definition of LCA on Wikipedia: “The lowest common ancestor i...
2019-01-07 12:11:37
1192
原创 树的遍历
文章目录普通遍历递归遍历先序遍历中序遍历后序遍历递归总结层次遍历非递归遍历先序遍历中序遍历后序遍历普通遍历普通遍历的意思是时间复杂度为O(N)，空间复杂度为O(h)的遍历算法，区别于后边学习的Morris遍历递归遍历 树的定义本身就是递归的，所以非常适合用递归解决问题，树的遍历同样可以用递归来解决。递归的模型非常简单。先中后序的基本都是一样的。先序遍历func preOrder(...
2018-11-06 18:55:33
222
原创 sds
文章目录sds结构数据结构宏解析函数解析sdslen最基本的创建函数最基本的追加扩容机制sds结构数据结构这里比较有意思的是GNU C的零长度数组 sizeof(char buf[0]) == 0关于这篇内容的C语言技巧改日写一篇文章阐述struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* used *...
2018-10-17 19:59:31
842
原创 sds-1
sds结构-1数据结构这里比较有意思的是GNU C的零长度数组，sizeof(char buf[0]) == 0， 关于这篇内容的C语言技巧改日写一篇文章阐述struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* used */ uint8_t alloc; /* excluding the header a...
2018-10-15 23:53:39
391
原创 LRU
最近频繁的看到LRU这个关键词，而且在公司也听到了，于是乎趁着国庆无聊就搜索了解了一下，本来以为是多么玄乎的技术，发现只是比较简单的两个数据结构的结合。为什么需要LRU缓存是很重要的一项技术，可以加速我们的访问。但是缓存是有容量的，不能无限制的缓存，所以我们缓存一定量的时候就需要淘汰缓存中的内容，那么我们根据什么来进行这个淘汰的过程呢？读到这里也就可以明白了,我们需要缓存机制来指导这个淘汰...
2018-10-06 21:08:08
2047
原创 Top K Frequent Elements
Top K Frequent Elements要求Given a non-empty array of integers, return the k most frequent elements.Example 1:Input: nums = [1,1,1,2,2,3], k = 2Output: [1,2]Example 2:Input: nums = [1], k = 1Ou...
2018-10-05 20:00:38
100
原创 Decode String
Decode Stringexamples = "3[a]2[bc]", return "aaabcbc".s = "3[a2[c]]", return "accaccacc".s = "2[abc]3[cd]ef", return "abcabccdcdcdef".思路
2018-10-05 00:18:54
443
原创 Group Anagrams
Group AnagramsGiven an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat&quo
2018-10-04 20:00:04
138
原创 makefile-变量的基础
前言 前面我们说了makefile的作用，以及构成。它有着自己的规则，可以说makefile就是一门脚本语言，抛开这么细的分类，它的本质还是一门程序设计语言，那么肯定会有程序设计语言中的各个元素或者元素的影子，这篇文章要将的就是程序设计中最基础的知识—变量。引申 我是从C语言学习的，在我的印象中定义变量就是：type varName[= val]，使用一个变量前必须要...
2018-07-16 01:36:41
290
转载 从逻辑思维角度提升自己的表达技巧
逻辑性从事软件开发行业的同学们或多或少都具有相当不错的逻辑性，毕竟编程开发本身就是逻辑性较强的任务。但是大家是否考虑过这种逻辑性应该怎么应用到社交技巧上？下面就跟着笔者一起来详细分析下吧。逻辑思维当逻辑性上升到软技能(社交技巧)层面，就成了逻辑思维。逻辑思维一直是职场社交和个人职业发展中最重要的软技能之一。它的本质就是在遇到问题时，给你提供一种梳理问题、分析问题及解决问题的方法论。...
2018-07-11 19:19:46
4776
转载 转载CSDN博客
对于喜欢逛CSDN的人来说，看别人的博客确实能够对自己有不小的提高，有时候看到特别好的博客想转载下载，但是不能一个字一个字的敲了，这时候我们就想快速转载别人的博客，把别人的博客移到自己的空间里面，当然有人会说我们可以收藏博客啊，就不需要转载，(⊙o⊙)… 也对。。实现 因为我自己当初想转载的时候却不知道该怎么转载，所以学会了之后就把方法写出来，帮助那些想转载却不知道该怎么转载的人（大神勿...
2018-07-11 19:16:26
209
原创 makefile-伪目标
通过前面的一篇博客知道规则是组成makefile的基本单位，而规则中又包含了三部分，先决条件其实也是目标，那么就可以分为目标和命令两大类，这里就有一个问题了，目标究竟是什么？ 前面我们也说过目标的含义，应该是要生成的可执行文件，或者已经存在为文件。因为make涉及出来就是为了自动维护编译C的源码，所以make默认目标都应该对应着文件，make通过比较文件的依赖去编译最终生成可执行...
2018-07-11 17:17:30
720
原创 makefile的结构
makefile是有一些列规则组成的，规则分为目标，先决条件和命令三个部分，先决条件和命令都是可以省略的。 targets是目标，可以有多个，中间用空格分隔。prerequisites是先决条件，也可以有多个，中间也是用空格分隔，cmdx是需要执行的命令，需要注意的是命令前都是TAB键，不能用空格代替，空格和TAB在makefile中是严格区分的，可以说TAB键可以告诉我们这...
2018-07-10 14:19:44
1456
原创 make与makefile
make 是什么： 一种脚本解析的工具 为什么： 1、解析源程序之间的依赖关系 2、根据依赖关系自动维护编译工作 3、可以执行宿主操作系统中的那种命令makefile 是什么： 一种配置文件 为什么： 1、定义了一系列的规则用于指定源文件编译的先后顺序 2、能够直接支持宿主操作...
2018-07-10 13:35:13
215
原创 tinyhttpd—4—cat，serve_file
这一篇当中的两个函数也都是代码量很小，功能很简单的函数。void cat(int client, FILE *resource){ char buf[1024]; fgets(buf, sizeof(buf), resource); while (!feof(resource)) { send(client, buf, strlen(buf), 0); fgets(bu...
2018-07-07 00:31:17
193
原创 tinyhttpd—3—not_found，unimplimented，bad_request，cannot_execute，headers
这一篇看似介绍的函数很多，其实这些函数都有一个特点，就是他们只是很简单的响应报文，无非就是把符合http协议的字符串写到缓存发送给客户端了。至于每一个报文的具体意思就不解释了，知道他们代表的大概意思能帮助我们去理解http sever的原理就够了。void bad_request(int client){ char buf[1024]; sprintf(buf, "HTTP/1.0...
2018-07-06 17:23:57
189
原创 tinyhttpd—2—getline
这一篇分析一下getline，为后面的accept_request做铺垫。int get_line(int sock, char *buf, int size){ int i = 0; char c = '\0'; int n; while ((i < size - 1) && (c != '\n')) { n = recv(sock, &c...
2018-07-06 13:04:30
167
原创 tinyhttpd—1—startup
上一篇分析了main函数的流程，startup也出现在其中，也说了startup的作用。这篇分析startup的源码。int startup(u_short *port){ int httpd = 0; struct sockaddr_in name; //申请一个socket httpd = socket(PF_INET, SOCK_STREAM, 0); if (http...
2018-07-06 11:40:08
236
原创 tinyhttpd — 0 — main
原来一直都在做单片机，大三上学期刚准备做互联网，所以开始学C++，数据结构。一直都在学最基础的东西，没有用过框架，也基本没有熟悉那么多API，所以想通过接触一个小的开源程序学习，目的很多，想学习web sever的工作原理，因为将来肯定会做相关的业务，不了解一个本质不利于深入。 要做一个http sever肯定要了解一下基础的知识，必须要清楚的就是浏览器输入一个url后是怎么和服务器...
2018-07-04 22:23:01
166
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人