kapizheng

原创 Redis设计与实现（笔记）

文章目录Redis设计与实现第二章 字符串SDS是redis的默认字符串表示。第三章 链表列表键的底层实现之一第四章 字典数据库和 哈希键的底层实现之一redis字典使用哈希表作为底层实现，一个哈希表里面有多个哈希表节点，每个哈希表节点就保存了字典中的一个键值队。第五章 跳跃表有序集合键的底层实现之一跳跃表有点类似于ST表，对数据的操作是logN。第六章 整数集合是集合键的底层实现之一。其结构体含有编码方式（int16,int32,int64)，元素数量和元素数组第七章 压缩列表是列表键和哈希键的底层实现之

原创 6.824Lab1

原创 CSAPP AttackLab

缓冲区溢出破坏返回地址让程序执行本来不愿意的函数使用系统调用启动一个shell程序。执行一些未授权的任务。如何解决病毒攻击栈随机化，操作系统每次执行程序的时候，在栈上分配一段0~n字节之间的随机大小的空间，要足够大又要足够小，不至于浪费程序太多的空间。被添加多个nop破解，只要攻击者能猜中就可以了。该技术是地址空间布局随机化技术（ASLR）中的一种。栈破坏检测GCC的栈保护者机制：在返回地址和缓冲区之间存储一个特殊的值，称为哨兵值，是在程序每次运行时随机产生的。函数返

原创 CSAPP BombLab

该lab的主要目的有两个：让你看懂汇编，让你会用gdb下面简单写几个本Lab会用用到的知识点，包括指令和一些bomb的解答方案建议读者熟记phase1之前的所有内容，去做一下这个lab试试。如果不会再去百度上搜索该lab，或者到本lab中去看。指令gdb 执行文件名再调用layout asm切换到汇编模式IF的底层有两种形式一种是条件控制，该方法是一开始直接cmp，然后跳转一种是条件传送，该方法是一开始计算出所有的结构，最后采用条件传送方式赋值。switch跳转指令底层.

原创 CSAPP DataLab

前言找到实习之后就一直想着把csapp的lab给补一补，最后也只补了3个左右的lab，后面的cacheLab和mallocLab，可能以后再来了（总共不止5个，值得做的可能是5个哈哈）因为cache那一章讲的是如何优化之类的，而mallocLab讲的是os的内存分配。介于找到实习后，干劲不够，因此也只艰难地写了前三个lab。dataLab能让你很好的熟悉数字在计算机中是如何表示的，假如有好好的读过第二章且做过一二星的题，那么应该可以解答大多数的题目。假如答不出的话，可能是你不知道有哪些kill，本文

原创 黑马程序员|网络编程笔记1

网络字节序：htonl：本地->网络（IP）htons：本地->网络（PORT）ntohl：网络->本地（IP）ntohs：网络->本地（PORT）IP地址转换：int inet_pton(int af,const char *src,void *dst)将本地转网络af：协议簇：AF_INET、AF_INET6src：传入，IP地址（点分十进制）dst：传出，转换后的网络字节序的IP地址。成功返回1异常返回0失败返回-1const char* inet

原创 第9章 IO复用

select系统调用在一段指定时间内，监听用户感兴趣的文件描述符上的可读，可写和异常事件。int select(int nfds,fd_set* readfds,fd_set* writefds,fd_set* exceptfds,struct timeval*timeout);nfds表示监听的文件描述符总数readfds、writefds和exceptfds分别指向可读，可写和异常事件对应的文件描述符集合。timeout设置select函数的超时时间。poll系统调用poll系统

原创 操作系统

什么是进程由程序段、相关的数据段和PCB段三部分便构成了进程实体。进程的定义进程是程序的一次执行。进程是一个程序及其数据在处理机上顺序执行时所发生的活动。进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。进程的特征动态性：进程的实质是进程实体的执行过程，因此，动态性就是进程的最基本的特征。并发性：是指多个进程实体同存于内存中，且能在一段事件内同时运行。独立性：在传统的OS中，独立性是指进程实体是一个能独立运行，独立获得资源和独立接受调度

原创 Java旧笔记|5

线程第一种方法：继承Thread类package j2;public class C extends Thread{ public void run() { for(int i=0;i<20;i++){ System.out.println("run:"+i); } }}package toy;import j2.C;import java.util.*;public class ttt { /

原创 Java旧笔记|4

Collection1、常用功能package toy;import java.util.ArrayList;import java.util.Collection;/*Collection接口，里面定义了所有单列集合共性的方法任意的单列集合都可以使用Collection接口中的方法* */public class ttt { public static void main(String[] args){ Collection<String> Cs

原创 Java旧笔记|3

Object类是Java语言的根类。toString方法直接打印对象的名字，其实就是调用对象的toString方法p=p.toString();重写需要重写Object类的toString方法，可以Alt+Enter重写equals方法日期时间类2.1Date类Date d2 = new Date(10000000);//把毫秒转换为时间。Daate date = new Date();long time = date.getTime();//把当前时间转换为毫秒2.2Da

原创 java旧笔记|2

抽象抽象方法：就是加上abstract关键字，然后去掉大括号，直接分号结束。抽象类：抽象方法所在的类，必须是抽象类才行。在class之前协商abstract就可以。不能直接用抽象类和抽象方法。1、不能直接创建new抽象类对象。2、必须使用一个子类来继承抽象父类。3、子类必须覆盖重写父类当中所有的抽象方法。注意：1、抽象类不能创建对象。2、抽象类中，可以有构造方法，提供子类创建对象时候，初始化父类对象用的。3、抽象类中，不一定包含抽象方法。4、抽象类的子类，必须重写抽象父类中所有的抽

原创 Java旧笔记|1

类匿名对象只有右边的对象，没有左边的名字和赋值运算符。new person().方法名/变量名方法或者变量只用一次的情况可以使用。Random在包java.util.Random里面。import java.util.Random;public class Java_try { public static void main(String[] args) { Random ran = new Random(); int r=ran.nextInt()

原创 Linux高性能服务器编程|第8章高性能服务器框架

高性能服务器框架I/O处理单元。四种I/O模式，两种高校事件处理模式逻辑单元。两种搞笑并发模式，有限状态机。存储单元（本书不讨论）CS模型启动后，创建一个或多个监听socket，并调用bind函数对其绑定到服务器感兴趣的端口上，然后调用listen函数等待客户连接。稳定后，客户端可以调用connect向服务器发起连接了。由于客户端连接请求是随机到达的异步事件，服务器要用某种I/O模型来监听。经常使用select系统调用。当监听到请求连接后，就调用accept函数接受它，并分配一个逻辑单元

原创 Linux高性能服务器编程|第7章服务器程序规范

服务器程序规范Linux服务器程序一般以后台程序形式运行，后台进程又称守护进程。它们没有控制终端，不会意外收到用户通知。守护进程的父进程通常是init进程（PID为1的进程）Linux服务器通常有一套日志系统，它至少能输出日志到文件。Linux服务器一般以某个专门的非root身份运行，如mysqld、httpd、syslogd等后台程序，分别拥有自己的运行账户mysql、apache和syslog。Linux服务器程序通常是可配置的，如果运行选项太多，则可用配置文件来配置。Linux服务器进程通

原创 计算机网络面试知识

数据链路层作用：实现了网卡接口的网络驱动程序ARP协议（Address Resolve Protocol，地址解析协议）用来将IP地址转换为物理地址RARP（Reverse Address Resolve Protocol，逆地址解析协议）通过网卡上的物理地址来查询IP地址，通常用在无盘工作站上（个人猜想是如路由器之类的）。网络层作用：实现数据报的选路和转发。IP协议（Internet Protocol因特网协议）：IP协议根据数据包的目的IP地址来决定如何投递它。ICMP协

原创 GIT错误收集

1、The current branch master has no upstream branch原因：没有将本地的分支与远程仓库的分支进行关联自己瞎搞：把本地和远程的分支保持一致[rejected]master -> master (non-fast-forward)”的解决方法本地没有git上的文件好像是...

原创 window指令收集

systeminfo ：查看系统信息如内存使用

原创 IDEA格式化（CV记录一下）

1，单个文件打开后，直接快捷键Ctrl+Alt+L就可将当前文件格式化2，快捷键Ctrl+Alt+O可将import格式化（删除无用的import）3，如果需要格式化整个项目的所有代码，在项目名上右键，找到Reformat Code单击即可，参考如下图：...

原创 计算机组成原理复习资料

课本是红皮的。第5，6，8较全。前面的就没怎么写了。估计是不会怎么更新了，希望对有缘人复习有用。如果你也写了一个类似这样子的整理的话，可以联系我将这个博客补全嘛，嘻嘻嘻~CPU的四个功能指令控制、操作控制、时间控制、数据加工。CPU的基本组成控制器，运算器（ALU）CPU中的主要寄存器1、数据缓冲寄存器（DR）2、指令寄存器（IR）3、程序计数器（PC）4、数据地址寄存器（AR）5、通用寄存器6、程序状态字寄存器（PSWR）第二章一个定点数由符号位和数值域两部分组成。按小数点.

原创 Git简单笔记

1、本地初始化git init​ 作用：会出现一个.git的文件，保存与本地库相关的文件2、设置签名1、项目级别：​ git config user.name _____​ git config user.email ____2、系统级别​ git config --global user.name _____​ git config --global user.email _____3、查看​ git config3、库与库操作git status表示目前所有库的状态

原创 Linux基础学习，黑马程序员视频笔记

一、关机shutdown-h（关电源）halt（关闭内存）init 0二、VMware中的备份和克隆备份快照侧重点在于短期备份，需要频繁备份的时候用快照，开启关闭都可以备份只能在__关闭__的时候使用1、在“虚拟机”，“快照”，”拍摄快照“克隆右键当前系统找到管理->克隆。一般选择完整克隆。三、Linux的文件bin放二进制文件dev放外接设备，不能直接使用需要被挂载etc配置文件Home除了root用户的其他用户的家目录，类似于windows的user/用

原创 每日dp(E. Increasing Frequency)最大子数组和

题目链接：我好菜啊给你一个队列，可以进行一次操作：选择一个区间对其中全部元素+k(k是整数)。要求使得最后队列中为c的个数最多是多少？对于这种区间操作问题而且又涉及到全部可以考虑双指针？类似于对于同一个数字。最优的操作一定是两个相同的数字之间的全部数字进行操作，所以显然要计算如果对这些数字进行操作后对全部的贡献，可以知道操作后的贡献为2-...

原创 每日dp，啊这去掉思维就是01水题

入口题目：给你2*n的数组。构造两个n的数组，使得两个数组可以按着前面小的先排列构造一个成2*n的数组。如上所示，2314由31和24构成，2和3出2，3和4出3，4和1出1，最后4。可以发现，需要后面的数要是比前小，一定是不可能放到别的队列里的，所以统计背包的物品个数就为一段连续的，且第一个数字最大的序列的个数，然后就上代码。#include<bits/stdc++.h>using namespace std;struct node{ int l,r;

原创 Drainage Ditches POJ - 1273

网络流板子题：贴下dinic的板子吧，原理直接百度博客就可以知道了#include<iostream>#include<cstring>#include<queue>#include<cstdio>using namespace std;const int N=200006;const int maxn=200006;int cost[N];int head[maxn];struct edge{ int v,nxt,w;}e[

原创 2020牛客暑假多校第二场A. All with Pairs（ac自动机+kmp)

题目链接不看代码：树状数组+dfs序列ORdfs维护子树大小（这个子树大小指的是叶子节点个数），对于一个ac自动机来说，建fail后，其父节点状态为子节点状态的后缀。反过来说，当前结点的子树大小为拥有该后缀的字符串个数。所以把所有串丢到ac自动机，计算每个子树大小。对于aaabbb，我们跑ac自动机，之后计算每个状态其子树的贡献。具体细节可以想想。主要是这个去重，这个我没想出kmp来搞。例如aaaaa和baaaa，如果能匹配就是aaaaa和baaaa。按着上面的方法跑了前4个贡献是a，aa，aaa

原创 Largest Common Submatrix（每日dp(划）每日一题）

给两个矩阵，其中数字由1到n*m，求两个矩阵的公共最大矩阵。。。啊啊啊啊我好菜#include<bits/stdc++.h>using namespace std;char str[1005];int dp[1005][1005];int a[1005][1005];int b[1006][1006];int sum[1006][1006];int len[1006][1006];struct MP{ int x,y;}mp[1005*1005];int

原创 Two Strings CodeForces - 223B每日dp(划），每日思维*

题意：我也是看别人的题意得诶。给两个字符串，S，T，求多次T中的序列能不能覆盖掉S。一开始想不到。跑完步回来洗澡后就想到了维护最右的点，然后balabala，wa25,wa27。看看一开始的代码吧#include<bits/stdc++.h>using namespace std;char str[1005];int dp[30];int main(){ string a,b; cin>>a>>b; map<char,i

原创 Resource Archiver HDU - 3247（ac自动机+TSP+BFS)

题意：给多个字符串然后和病毒串，求一个最小串包含全部字符串，但没有病毒串。这题一开始看了下数据范围，时间10秒，诶，n<=10，状压待定。有两种串，那么我们都读进去，存上模式串在自动机上的位置，每次跑bfs，不经过病毒串，之后就嘿嘿嘿得到一个dis数组，之后有距离+有状压=TSP= =#include<bits/stdc++.h>using namespace std;const int maxn=2e5+10;map<int,int> mp;int dis[1

原创 稳蓝冲紫之——做过的题也能忘」」」」Equalizing by Division (hard version)

题目如题这样，一开始想着啪啦啪啦用map然后各种秀操作，放了两三天一直不敢动手，发给队友后：然后就emmm然后发现这题emm，是第二次打cf的场。。。= =那时候菜到这题看了看题解，然后就点开了之前的代码不到一秒，看了行数。。。那好好想想，纸笔上来Orz…，然后就巴拉巴拉各种，发现诶，排序之后，越大的数字到越小的数字的操作次数会越来越大，然后palapala那就一个数组放数字个数，一个数组放操作数，然后就过了emmm…啊啊啊啊啊思维题，干嘛想成码力题。。。。所以做题还是不能看题解啊啊啊啊Orz

原创 Loli, Yen-Jen, and a cool problem（广义后缀自动机，裸题）

题意：给一颗字符串树，求从哪个结点向上L长度的字符串出现了多少次题目链接诶，感觉也没什么好讲的。可记下一个特性：求一个状态向前长度为L的出现次数不需要跑自动机，只需要跳fa结点，跳到其fa<L就可以，直接cnt[p]，因为拓扑排序已经将cnt计算出来了。#include<bits/stdc++.h>using namespace std;const int maxn=6e5+10;struct node{ int fa,ch[26],len;}no[maxn];

原创 每日dpPawn CodeForces - 41D

可以跳左上或者跳右上，注意k范围比较小，所以开3维dp搞搞就ok啦。要注意的是%(k+1)而不是(k)，记录路径套路（开个数组）一下，还有就是答案可能是零，所以ans初始化不要是0…#include<bits/stdc++.h>using namespace std;const int maxn=1e6+10;int dp[105][105][11];int path[105][105][11];int tu[105][105];int main(){ int .

原创 Tree （树形dp，换根，逆元)

联通点集如何计算，我们求dp[u]为该子树的联通集个数有：dp[u]=∏v(dp[v]+1)dp[u]=\prod_v(dp[v]+1)dp[u]=∏v​(dp[v]+1)那么先求一次dfs求得每个字数的dp值，之后我们需要有一个数组存放其结点向上的一个贡献有demo[u]=ans[f]/(dp[u]+1)demo[u]=ans[f]/(dp[u]+1)demo[u]=ans[f]/(dp[u]+1)。换根的思想。ans的答案为ans[u]=(demo[u]+1)∗dp[u]ans[u]=(demo[u].

原创 CF稳蓝上紫之_Paint the Digits CodeForces - 1209C

题意： 染色，如何使得，1和2部分连接起来为上升序列，看数据能想到枚举0到9，但emmm卡在了处理问题，之后知道可以枚举就瞎写判断a了。要大胆些emmm，应该20分钟搞定的害…#include<bits/stdc++.h>using namespace std;const int maxn=3e5+10;int sum[maxn];int a[maxn];int dp[maxn];int h[maxn];char ans[maxn];int n;bool check(in

原创 Towers CodeForces - 229D（每日DP)*

题意：给你一排的塔，可以一座塔可以叠在他的左边和右边。，求变成LCS的最小操作。一开始看到数据以为要O(N)好吧其实5000可以On。。。其他塔向左还是向右这没区别我们用dp[i]来表示到这个塔的最小操作，每次操作是一个区间需要的次数就是i-j-1这下直接两个for可以了。但是有一个情况是操作后塔高要如何处理= =，然鹅有些题解直接开了一个数组存放最小的塔高（解锁新操作），就这样直接搞满足区间累加高度本来高度以及操作后的最小塔高就可以了。#include<bits/stdc++.h>

原创 HDU - 4641 K-string(SAM,后缀自动机)

题目大意：先给一个串，然后有多次操作，每次可以+一个字符，或者查询超过k次的子串。很明显，+一个字符的操作是有后缀自动机的感觉，但是需要在线查询且复杂度不能太高，这时候就需要边+边维护答案。设置一个cut数组，由于后缀自动机的fa指向的是该状态前面的后缀，由于数据太少，我们可以每次累加cnt，向fa指的方向跑，要注意判断的是重复计算的问题，如果大于k次我们是一定不要再次进行计算的了。还有新建结点的时候数据的转移…只要大于k说明其状态的子串够格可以累加了。也就有no[now].len-no[no[now]

原创 写写博客吧，记录下一些特性Orz

BEGING

原创 力扣第165场周赛

作者：HCHO来源公众号：甲醛实验室第一题A 和 B 在一个 3 x 3 的网格上玩井字棋。井字棋游戏的规则如下：玩家轮流将棋子放在空方格 (" ") 上。第一个玩家 A 总是用 “X” 作为棋子，而第二个玩家 B 总是用 “O” 作为棋子。“X” 和 “O” 只能放在空方格中，而不能放在已经被占用的方格上。只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。如果...

原创 力扣第164场周赛

第一题平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi]。请你计算访问所有这些点需要的最小时间（以秒为单位）。你可以按照下面的规则在平面上移动：每一秒沿水平或者竖直方向移动一个单位长度，或者跨过对角线（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。必须按照数组中出现的顺序来访问这些点。示例 1：输入：points = [[1,1],[3...

原创 力扣第163场周赛

题目1：给你一个 n 行 m 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。每次「迁移」操作将会引发下述活动：位于 grid[ i ] [ j ]的元素将会移动到 grid[i] [j + 1]。位于 grid[i] [m - 1] 的元素将会移动到 grid[i + 1] [0]。位于 grid[n - 1] [m - 1] 的元素将会移动到 grid[...