HalfStar

CS144 lab1 [TOC] 先放一张经典的图… Do you see the lab1 work ? The work 我们需要去实现一个流重载器，因为在进行数据的接收时都是无序的，需要进行重新的组合得到一个有序的数据。 The requirement The keypoint is the capacity. 这也是TCP实现限流的一个重要的手段 capacity 意味着从被读入到没有被组合的位置的长度不能大于capcaity，所以我们需要去定义额外的数据结果去保存我们的未被组装的数据。 The implement 实现思想是使用map去记录未被编码进入的数据，保存 index和string 和数据 每次加入一个新的数据时，先使用二分查找去在未被编码的数据中查找合适的数据集合，对这些有重合/可连接的数据进行操作 连接，直接前面相连或者后面相连 重合，将重合的部分去掉，合并为一个未被编码的数据 随后尝试将第一个数据加入到ouput中 小于等于_next，将合理数据加入进去 大于_next, 直接返回 然后判断结束情况 有eof标识，设置结束index 如果结 ...

Archlinux 打包规则 1. 创建pkgbuild 1touch PKGBUILD 2. 设置变量 先来看pacman中提供的模板 12345678910111213141516171819202122232425262728293031323334353637383940414243444546# Maintainer: Your Name <youremail@domain.com>pkgname=NAMEpkgver=VERSIONpkgrel=1epoch=pkgdesc=""arch=()url=""license=('GPL')groups=()depends=()makedepends=()checkdepends=()optdepends=()provides=()conflicts=()replaces=()backup=()options=()install=changelog=source=("$pkgname-$pkgver.tar.gz" & ...

子网规划和地址规划 1. 子网掩码 子网掩码：用于区分网络地址，主机地址，广播地址是表示网络地址和子网大小的重要指标。 子网掩码的形式是网络号部分全部为1,主机号部分全部都是0，掩码也可以使用“从左到右连续的1的总数”来表示。 2. IP地址和子网规划 当知道了子网的地址，子网掩码就可以知道网络地址，广播地址，子网能够容纳的最大主机数 网络地址 = 子网掩码 and 子网地址 广播地址 = 子网掩码 and 子网地址 or (~子网地址) 子网范围 = 子网地址 ～ 广播地址 子网能够最大主机数 = 2^主机位 - 2 当知道了网络的掩码，如果网络分为2N2^N2N的子网，将掩码的后面N位设置为1。

图论算法All in one 1. 最长路/最短路 1.1 拓扑求解 首先去判断入度为0的点，然后将入度为0的点加入到队列，遍历队列中的点进行数据的更新， 如果一个点的入度也变为0,那么此时将这个点加入到队列，直到最终的队列为空，所有的点完成了更新。 注意这种解法只能适用于DAG（有向无环图！！！） 1.1.1 最长路 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include <vector>#include <string.h>#include <queue>#include <map>#include <stack>#include <string>#include <climits>#include <algorithm>using namespace s ...

linux fstab and 我修fstab()悲 What’s the fstab fstab用于定义磁盘分区，各种其他块设备或者远程文件系统应如何装入文件系统, 存放的位置在/etc/fstab The basic format 1# <file system> <dir> <type> <options> <dump> <pass> UUID 以32个16进制的数字表示，被连字符分割为5组(8 4 4 4 12)，现在大多数的linux系统都 使用UUID挂载分区 挂载目录 文件系统类型 相应的挂载选项 会被dump检查，设置为0来禁止检查 设置引导时文件系统检查的顺序 dump 是用于检查文件系统判断是否需要进行被备份。 文件系统标识 在/etc/fstab中可以使用内核名称，标签，UUID三种方式去表示文件系统，一般优先选择的是UUID 如果你使用名称的话当你的内存分布发生了改变，那么此时这个名称也会改变，但是UUID是不会发生改变的 当然了当这个分区消失的时候，对应的 ...

链表排序 简单来说就是给你一个链表，每个节点都有一个相应的value,按照value的大小对其进行排序。 由于是链表，所以可能选择插入排序是更为合理的选择，但是正真写起来发现处理逻辑过于复杂，此时选择使用 归并排序可能是更好的选择。 将一个列表分为两个列表，对两个列表再进行排序，再进行链表的合并 code 12345678910111213141516171819202122232425262728293031class Solution {public: ListNode* sortList(ListNode* head) { if (head==NULL||head->next == NULL) return head; ListNode* slow = head ,*fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fa ...

C++ 网络编程 1. socket概念 socket是一种进程通信机制，被称为是套接字，引入一个标准名字空间进行进程之间的通信。 socket相当于是在传输层协议TCP/UDP之上的一层抽象层级更高的协议，方便应用程序进行使用。 socket主要使用在客户/服务器模型而设计的，针对客户和服务器程序需要提供不同的socket系统调用，运行在 客户端的被称为是clientSocket，运行在服务器端的是serverSocket 套接字之间的连接主要分为三个步骤 服务器监听：服务器端套接字不定位具体的客户端套接字，而是处于等待的状态，实时监控网络状态 客户端请求：是指客户端的套接字提出连接请求，要连接的目标是服务器端的套接字。 为此客户端的套接字必须描述其要连接的服务器的套接字，指出服务器套接字的地址和端口号，然后 提出连接请求 连接确认：是指当服务器套接字监听到或者说接收到客户端套接字的连接请求，就响应客户端 套接字的请求，建立一个新的进程，把服务器套接字的描述发送给客户端，一旦客户端确认了次描述 连接就建立完成。 2. socket 函数 函数原型 12#include & ...

circle algorithm 1. Floyd判圈算法 1.1 算法思路 使用一个快指针和一个慢指针，一个每次前进2步，一个每次前进一步。 当两个指针相遇的时候，说明此时是存在环的，如果有一个遇到了结束节点，那么此时说明 存在环，从这个相遇节点开始，再次进行行走，最终相遇的时候慢的环所走的步数就是环的长度。 如果要求出环的起点，那么对于将一点放在相遇的节点上，一个点放回到原来的起点，那么此时两个点之间的距离是 环长度的整数倍。 1.2 代码实现 C++ version 返回开头 12345678910111213141516171819class Solution {public: ListNode *detectCycle(ListNode *head) { ListNode *fast = head; ListNode *slow = head; while (fast && fast->next) { slow = slow->next; ...

Single Number 大意 在一个数组中，有一个数字只出现了一次，其他的数字都出现了两次，求在O(1)的额外空间 和O(n)的额外时间内如何求出只出现一次的数字。 思路 对于出现两次的数字x,有如下的性质 xx=0x ^ x = 0xx=0 对所有的数字进行一次异或，最终剩下的数字就是那个只出现了一次的数字 code C++ version 12345678910class Solution {public: int singleNumber(vector<int>& nums) { int ans = 0; for (auto i : nums) { ans ^= i; } return ans; }}; Single Number II 大意 在一个数组中，有一个数字只出现了一次，其他的数字都出现了3次，求在O(1)的额外空间和 O(n)的时间内如何求出只出现一次的数字。 思路 对于出现3次的数 ...

CS144 lab3 Lab3的任务是实现一个TCPsender。 1. TCPsender 的功能 将ByteStream中的数据以TCP报文的形式持续传输给接受者 根据ackno和windows size，追踪接受者的传输状态，同时检测丢包 当超出一定的时间后还没有接受到数据，那么进行重新传输 2. project 2.1 bytes_in_flight 表示已经被发出但是没有被接受的字节数 为了满足这个函数，我们需要添加一个成员outgoing_bytes表示这些没有被确认的字节数目 2.2 fill_windows 从我们的_stream中尽可能多地读取字节，当我们的窗口大小大于未被确认的字节，持续进行发送。 在发送的时候，如果没有发送SYN信号，那么此时发送SYN信号，设置segment.head().syn = true 随后设置发送段的seqno和payload, 对于payload的大小，为最大负载和当前窗口大小 - 未被确认的字节 - 是否有syn标志位的较小值。 判断结束的时候，需要满足三个条件 没有发送过fin标志 ...