Eden Mo Blog

之前放在数据结构算法题目（二）：回溯、贪心、动态规划与图论略显臃肿，现在单独拎出来，记录了动态规划的一维压缩问题，有一些问题二维解法更加直观（大部分），但是有些解法一维解法更加简便（例如组合总和Ⅴ），而且一维解法性能往往更高，希望能加深理解。 二维解法理解参考上文或卡哥原文，本文基本不会记录从0进行二维递推。 规律 一维化的遍历顺序是有基本规律的，例如遍历顺序是如何的、是否需要记录上一层值，本文涉及的问题主要有以下： 当前值来自左边和正上方，从上到下、从左往右更新，注意第一列初始条件是否适合一维化。（机器人走方格图的不同路径问题）。 当前值来自正上方dp[i-1][j]和左上方dp[i-1][j-n]，例如01背包问题：从上往下、从右往左遍历。 为什么01背包是从右往左遍历：一直的写法是遍历种类i，i每循环一次，代表dp[j]更新一次，代表i个物品自由组合，和二维dp数学意义一致；遍历j代表遍历背包容量，要从右往左遍历，是因为j大，代表背包容量大，j较小的值得到的最大价值一定是j值大的最大价值的子集问题。例如j=2和j=4，j=2的最大价值组合，也一定包含在j= ...

表间数据关系 一个数据库可以有很多表，表和表之间数据记录可能存在联系，MySQL定义了若干种关系，包括一对一、一对多、多对多和自我引用。 一对一（少用）：两张表主键完全一对一，例如学生的成绩表、学生的身份证表，二者主键（学生）一一对应，没有额外的对象。 一对多（常见）：一张表的对象作为另一张表的主键，或称另一张表多个外键指向当前表的主键。例如部门表和员工表，客户和订单表、分类和商品表。（心中默念：一个部门有多个员工，一个员工不能多个部门；一个客户多个订单，一个订单不可能多个客户......就是一对多） 多对多：默念不过关就是多对多。 自我引用：本表中创建一个外键，外键指向本表的主键。例如现在数据库记录了若干个回复评论的人，现在创建一个"回复对象"字段（外键），那么回复对象一定指向原来回复评论的人（主键），就是一种自我引用关系。 逐表查询与笛卡尔积错误 假设现在具有一对多关系的部门表和员工表，现在需要通过员工姓名，查找其部门名称；首先查询员工表通过姓名查询部门id，从部门表通过部门id查找部门name： 1234567SELECT department_idFRO ...

数据库相关概念 数据库（Database，DB）：本质是一个文件系统，保存了一系列有组织的数据。 数据库管理系统（Database Management System，DBMS）：操作和管理数据库的大型软件，用户通过此访问和管理数据库数据。 结构化查询语言（Structure Query Language，SQL）：数据库交互语言。 关系型与非关系型数据库 RDBMS RDBMS（RDBMS，Relational~）：最古老的数据存储形式，使用二维表格的形式（行、列）来存储数据。 优点：支持复杂查询和事务处理（加锁等）、数据以表格形式存储，表间可以建立关系（多表查询）。 缺点：扩展性较差、大数据处理性能较弱，难以存储非结构化数据。 常用关系型数据库：MySQL、Oracle、SQLites等 非关系型数据库 键值型数据库：按Key-Value形式存储，Key是唯一标识符，查找速度极快。但是不支持条件过滤，如果不清楚具体数据位置，就要遍历所有的键，消耗性能，经典的使用场景是作内存缓存。最流行的键值型数据库——Redis。 其他：文档数据库、搜索引擎数据库（倒排索 ...

Lab1 Stitching substrings into a byte stream Lab1实验手册: https://vixbob.github.io/cs144-web-page/assignments/lab1.pdf(2021 Fall) 部分实验目的和内容摘抄自手册。 在Lab0的Warm up实验，我们完成了一些小实验，它们来自应用层的协议，例如过时的telnet协议，邮箱发送的smtp协议等，通过coding，完成了两个简单设计，包括简单的TCP的socket传输，以及实现一个deque的读写缓冲区； 进入Lab1——Lab4，我们将逐步实现一个TCP协议：Lab1的任务是实现一个流重组器；互联网TCP下层的所有协议，例如IP、以太网协议等均不会提供可靠的传输服务，可靠传输服务依靠TCP服务实现。数据报的传输是一种分组转发，如何将切片数据报重组成一个完整、无误的数据报，是TCP协议要实现的重要依靠。 实验目的 实现一个类，这个类就是实现流重组的类，初始定义如下，为了直观，删除了所有注释并改写中文注释如下： 12345678910111213cla ...

贪心算法篇 1. 划分数组为连续数字的集合 给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。 如果可以，请返回 true；否则，返回 false。 输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3 输出：true 解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。 哈希表+贪心算法 假设数据可被划分多个连续数组，就从单个连续数组构造开始。哈希表统计各元素个数，nums[i]到nums[i]+k-1尝试构造k个数（因此num[i]应该有序），并且消耗个数，只有哈希表个数全为0，才可能划分成功。 1234567891011121314151617181920212223class Solution {public: bool isPossibleDivide(vector<int>& nums, int k) { sort(nums.begin(),nums.e ...

记录了计算机网络相关基础知识，参考书是谢希仁教授的《计算机网络》（第八版）以及美国Jim Kurose和Keith Ross所著的《计算机网络：自顶向下方法》（陈铭 译），前者是国内大学常用的计算机网络教材，注重历史发展、基础理论、常用的协议细节等描述，后者是网络应用领域的权威教材，横向技术内容比较全面，在国内也很受欢迎，贴两个大佬整理好的读书笔记： 计算机网络-自顶向下方法 GuoYi:《计算机网络-自顶向下方法》笔记 无论是哪本教材，经典的网络协议和理论是绕不开的，因为初次接触计算机网络是自底向上的逻辑，这个影响了笔者的一些逻辑接受方式。本文旨在从网络底层开始记录这些重要的理论，计算机网络发展的近半个世纪，各层的协议已经比较垄断，了解太多古老且边缘协议帮助不大，本文对于计网的入门应该是比较完整的体系。 计算机网络概述 互联网两个基本特点：连接性与共享 发展三个阶段 ARPANET向互连网发展；单个分组交换到互连网络；1983年TCP/IP成为阿帕网标准协议，不同系统可以在该协议上进行通信，形成互联网。 形成三级结构互联网；主干网、地区网、企业网（校园网）； ...

之前偷懒一直没看这部分，现在开始看很多C++风格代码确实离不开C++ 11引入的新特性，尤其智能指针、右值引用等，本来只想写这两个，但是用到的auto、python风格的for循环、lambda表达式等小特性也逐渐影响了设计者的代码风格，我在一段时间十分抗拒使用这种非常巧妙的写法，慢慢又变成会看不会写了，用和不用相当忐忑，因此就有了这个总结，确保忘记了也能很快拾起来；这里只记录用到且必要的，逐渐记录，追求完整版的还是移步官方文档。 RAII机制 资源获取即初始化(Resource Acquisition Is Initialization，RAII)不是C++11的新特性，而是C++之父很早提出的编程思想。RAII就是将资源和对象的生命周期绑定，对象创建自动获取资源，对象生命周期内资源始终有效，对象生命周期结束资源释放，避免了内存泄漏的问题。RAII类模板是申请、释放资源的基本手段，智能指针就是RAII的其中一种典型应用。 C++智能指针 智能指针是C++ 11引入重要新特性，用于解决raw指针需要手动管理问题，例如由malloc、free或者new、delete操作错误 ...

mmap实验 这个实验算是我花时间最长的实验了，定位问题和解决问题的时间大概是4：1，除了信手沾来的大佬，我认为很难按照hints从头写到尾写完解决完所有报错就顺利过关，因为有时候甚至很难确定问题的具体位置。这个实验很有必要听从Robert教授的之前教导，不要想着一次实现所有功能，尝试先实现一点，调试成功再去继续；因此本次实验概述既参考了hints本身固有逻辑，更多是从调试步骤解决，我相信这样的思路会为读者省下很大一部分定位问题的时间。另外，这个实验设计应该是有bug的，这部分疑惑连同debug问题被记录在Q&A； 实验目的 这个实验意在为xv6加入文件映射内存特性，所谓文件映射内存，就是将文件直接map到某个内存，直接对文件进行读写，绕过了read/write文件调用系统调用、将数据读到内核缓冲区再拷贝用户空间的过程，实现高效率的文件修改；文件映射内存涉及的内容还是比较综合的，要求有文件操作、内存映射，此外文件不可能常驻内存，因此必然采用了Page Fault机制来进行懒分配、就需要处理系统陷入，可见它几乎综合了前面的所有实验特性，设计不能不说别出心裁； 此外，本实 ...

卡内基·梅隆大学的这个CSAPP项目，几乎是计算机科学领域受众最广的项目了，在国内这个项目的参与者更是数不胜数，该项目涉及很多方面，例如汇编编译、操作系统、网络、并行等领域，项目使用的编程语言是C，分为八个Lab，深受CS专业、Java/Go以及11408选手们的爱戴。尽管博主是平平无奇的EE学生，四舍五入也算CS的半个同行了，这个项目在我这里优先级并不大，就当作一些阅读和记录随写了，时间会拉很长，可能做完这个项目就差不多过年了。 环境搭建 基本环境： Ubuntu 18.04 VMware 16 Vscode+SSH 虽说博客很多，但是从环境搭建开始介绍的还真没多少，但还是找到了林夕的gitee仓库，佬将安装命令都整理成脚本了，Ubuntu 20.04及以下的都可以直接使用这个脚本安装，因此我记录下的基本都是这个脚本的内容，请参考大佬的origin分支installAll.sh即可； 可以直接运行并安装： 1wget https://gitee.com/lin-xi-269/csapplab/raw/origin/installAll.sh&& ...

Lab0 Networking Warmup Lab0实验手册: https://vixbob.github.io/cs144-web-page/assignments/lab0.pdf(2021 Fall) 部分实验目的和内容摘抄自手册。 Networking by hand 这一小节只是简单的网络实验，不涉及代码，围绕telnet、netcat的一些操作展开，无兴趣的可以跳过。 Fetch a Web page 打开浏览器，访问http://cs144.keithw.org/hello，你会看到Hello, CS144!； 现在虚拟机可以做同样的事情，Linux下运行： 1telnet cs144.keithw.org http 这个命令建立你和另一台计算机（cs144.keithw.org）的可靠字节流，并且运行万维网使用的http(Hyper-Text Transfer Protocol，超文本传输协议)服务。telnet和ssh类似，都是用于远程登录或管理设备的网络协议，但telnet的数据以明文发送，仅支持基本用户名-命名验证，没有文件传输能力，基本 ...