0%

语言考试的事情终于可以暂时放一下了,最近重新看起了计算机网络的网课,感觉自己算法这块还是得加强一二,得刷题啊。

12/25

网课笔记啥的我实在是没时间做(),就记录一下自己做的网课作业吧

作业要求在这里:实验0

1.实现一个webget程序,使用操作系统的TCP协助和流套接抽象获取网络上的网页

主要需要编写的就是这一个函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void get_URL(const string &host, const string &path) {
// Your code here.

// You will need to connect to the "http" service on
// the computer whose name is in the "host" string,
// then request the URL path given in the "path" string.
TCPSocket sock1;
sock1.connect(Address(host, "80"));

string req = "GET ";
req.append(path);
//一开始写的时候根本没理解“每行都需要\r\n“的意思,
//只在整个链接的最后使用了\r\n,可把我难住了
req += " HTTP/1.1\r\nHost: ";
req.append(host);
//这里的Connection: close没有的话会持续输出空行,或者等待后关闭(取决于具体代码)
//后面的sock1.close();感觉在提供输出上没啥用,可能是作用于本机socket的运行状态
//req += "\r\nConnection: close\r\n\r\n";
req += "\r\n\r\n";


//auto recvd = sock1.read();
sock1.write(req);

// Then you'll need to print out everything the server sends back,
// (not just one call to read() -- everything) until you reach
//谢谢你的原注释这里把eof用双引号括起来哈,我还以为是字符串"eof"呢,结果不是
// the "eof" (end of file).
//看仓库文档的示例之后,我以为需要创建两个socket,一个读一个写,结果是我理解错了
//不过从原理来看也应该是一个socket才对
//auto recvd = sock2.read();
//cout << recvd << endl;

接下来输出的一个错误示例,网上的答案好像也跟这写得差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    for(;;){
if(!sock1.eof()){
auto recvd2 = sock1.read();
//在一个链接的过程中究竟读了几次呢?我测试了一下,
//第一次读出了状态码等东西(这个是叫请求头吧?)和网页内容
//第二次读了一个空行
//取决于传输内容的速率,传输过来的内容会随机换行(读的次数也不一样)
cout << recvd2 << endl;
}
else{
sock1.close();
break;
}

}
}

判定的程序会报错不匹配,于是我翻找了一下这个小程序的检验条件,在项目目录下的tests文件夹里,是一串固定的字符

所以接下来这段才是正确的写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
   string resp;
for(;;){
if(!sock1.eof()){
auto recvd = sock1.read();
//组合在一起就不会有薛定谔的空行了
resp.append(recvd);
}
else{
break;
}
}
string split = "Content-type:";
//要删掉请求头和后面的一个换行和回车,不过我这里如果Content-type的内容字符数变了就gg了
size_t pos = resp.find(split) + 26;
if(pos != string::npos){
//cout << "position:"<< pos << endl;
resp = resp.substr(pos);
}
size_t str_size = resp.size();
//结尾还有一个换行/回车
resp.erase(str_size - 1);
cout << resp << endl;
//记得注释掉原文件里的两行报错

2.在内存中实现一个可靠的字节流

头文件里主要是加一些私有变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class ByteStream {
private:
// Your code here -- add private members as necessary.
std::deque<char> _queue;
size_t _capacity_size;
size_t _written_size;
size_t _read_size;
bool _end_input;
bool _error{}; //!< Flag indicating that the stream suffered an error.
public:
ByteStream(const size_t capacity);

//! \name "Input" interface for the writer
//接口函数还没有试验过
class InputInterface {
private:
ByteStream* _input_stream;
public:
InputInterface(ByteStream* stream) : _input_stream(stream) {}
size_t write(const std::string &data){
return _input_stream->write(data);
}
};
//! Write a string of bytes into the stream. Write as many
//! as will fit, and return how many were written.
//! \returns the number of bytes accepted into the stream
size_t write(const std::string &data);

//! \returns the number of additional bytes that the stream has space for
size_t remaining_capacity() const;

//! Signal that the byte stream has reached its ending
void end_input();

//! Indicate that the stream suffered an error.
void set_error() { _error = true; }
//!@}

//! \name "Output" interface for the reader
//接口函数还没有试验过
class OutputInterface {
private:
ByteStream* _output_stream;
public:
OutputInterface(ByteStream* stream) : _output_stream(stream){}
std::string peek_output(const size_t len){
return _output_stream->peek_output(len);
}
void pop_output(const size_t len){
_output_stream->pop_output(len);
}
};
//! Peek at next "len" bytes of the stream
//! \returns a string
std::string peek_output(const size_t len) const;

//! Remove bytes from the buffer
void pop_output(const size_t len);

//! Read (i.e., copy and then pop) the next "len" bytes of the stream
//! \returns a string
std::string read(const size_t len);

//! \returns `true` if the stream input has ended
bool input_ended() const;

//! \returns `true` if the stream has suffered an error
bool error() const { return _error; }

//! \returns the maximum amount that can currently be read from the stream
size_t buffer_size() const;

//! \returns `true` if the buffer is empty
bool buffer_empty() const;

//! \returns `true` if the output has reached the ending
bool eof() const;
//!@}

//! \name General accounting
//!@{

//! Total number of bytes written
size_t bytes_written() const;

//! Total number of bytes popped
size_t bytes_read() const;
//!@}
};

因为读写在数据中的位置在两端,需要使用双端队列的数据结构

这些代码只是实现基本功能,如何判断写了多少,没写进去的是否要重写的不用考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include "byte_stream.hh"

//template <typename... Targs>
//void DUMMY_CODE(Targs &&... /* unused */) {}

using namespace std;
//别忘了初始化类中的变量
ByteStream::ByteStream(const size_t capacity)
: _queue(), _capacity_size(capacity), _written_size(0), _read_size(0), _end_input(false), _error(false){}

size_t ByteStream::write(const string &data) {
//先判断边界条件
if(_end_input)return 0;
//注意内存限制
size_t write_size = min(data.size(), _capacity_size - _queue.size());
_written_size += write_size;
for(size_t i = 0; i < write_size; i++){
_queue.push_back(data[i]);
}
return write_size;
}

//! \param[in] len bytes will be copied from the output side of the buffer
string ByteStream::peek_output(const size_t len) const {
size_t pop_size = min(len, _queue.size());
return string(_queue.begin(), _queue.begin() + pop_size);
}

//! \param[in] len bytes will be removed from the output side of the buffer
void ByteStream::pop_output(const size_t len) {
size_t pop_size = min(len, _queue.size());
_read_size += pop_size;
for(size_t i = 0; i < pop_size; i++){
_queue.pop_front();
}
}

//! Read (i.e., copy and then pop) the next "len" bytes of the stream
//! \param[in] len bytes will be popped and returned
//! \returns a string
std::string ByteStream::read(const size_t len) {
string data = this->peek_output(len);
this->pop_output(len);
return data;
}

void ByteStream::end_input() {_end_input = true;}
bool ByteStream::input_ended() const { return _end_input; }
size_t ByteStream::buffer_size() const { return _queue.size(); }
bool ByteStream::buffer_empty() const { return _queue.empty(); }
bool ByteStream::eof() const { return _end_input && _queue.empty(); }
size_t ByteStream::bytes_written() const { return _written_size; }
size_t ByteStream::bytes_read() const { return _read_size; }
size_t ByteStream::remaining_capacity() const { return _capacity_size - _queue.size(); }

试着做一个微信小程序的项目,还不知道会遇到多少坑……

4/26

网页后端体系架构(自下而上):

数据库:存储字段(列)组成的实体集(表)

通过MyBatisPlus将数据库实体集与Java对象建立联系,其中实体集中的字段与Java类中的属性一一对应。

DAO层/Mapper层:提供CRUD的Java方法,处理/提供data object

DO即数据库实体集对应的Java对象。

Service层:统一业务逻辑处理,为不同服务提供可复用的调用接口;为CRUD方法赋予实际业务意义;处理param数据,提供VO对象

将从controller层拿到的param数据转化成DO对象,传至DAO层;将DAO层提供的DO对象转化成VO对象,提供给controller层。

Controller层:分配URL,接受来自页面的请求,向下处理后,拿到返回数据返回页面。

从页面拿到param数据提供给service层,接受service层传递的VO对象给页面展示。

更多关于数据结构层的介绍:https://blog.csdn.net/qq_27022241/article/details/112002345

在b站看斯坦福CS144作为教程,打算后期跟着《计算机网络 自顶向下方法》(Kurose&Ross版)再过一过。

突然发现看了英文教程再看中文版书有点不理解一些概念用语😂,想看纯英文版的书又怕自己看不懂,纠结了。

3/17

(摘自Kurose&Ross的《计算机网络 自顶向下方法》)

什么是套接字(socket):

套接字说同一台主机内应用层与传输层之间的接口,由于该套接字是在网络上建立网络应用程序的可编程接口,因此也将套接字称为应用程序和网络之间的应用程序编程接口(Application Programming Interface,API)。

什么是传输层的多路复用(multiplexing)和解复用(demultiplexing,多路分解):

多路复用和多路分解是因特网中的基本传输层服务。

从源主机的不同套接字中收集数据块,并为每个数据块封装上首部信息(这将在多路分解时使用)从而生成报文段,然后将报文段传递到网络层的工作称为多路复用。

将运输层报文段中的数据交付到正确的套接字的工作称为多路分解。

4/22

一个连异或怎么算都记不住的人今天看到了一个神解释:异或=不进位二进制加法

绝了!

虽然遇到了一些问题,不过都很快找到方法解决了。看来之前安装VS和openCV的坑不是白踩的。

Maxw终于有了自己的博客啦!有点激动,也有点犹豫跟纠结,虽然理由已经充分到说服自己无数遍,但我仍无法预测自己毅然走出专业的圈走进写代码的坑是不是更加正确的选择…

2/23-2/24

git初试

follow 枫叶的教程
problem occur:
can’ t clone existing repostory with git bash reports timeout
or OpenSSL SSL_read: Connection was reset, errno 10054

从GitHub上clone仓库的时候,试了几次,有时git bash报错10054,有时timeout。

我先是按网上教程改了git的global config,还是报错

想到自己上GitHub都要科学方法,就觉得应该是代理的问题。git应该并非使用系统代理设置,而是需要自行设置,果不其然。

solve:
setup proxy for git, following git设置代理

需要注意的是,git bash和github desktop在提交仓库更新的时候似乎是冲突的,不能同时使用。

博客搭建

follow 枫叶的教程合集

感谢枫叶大佬的教程,有时间一定上知乎评论区里发个反馈。

安装node.js与插件的过程中报错属于node.js本地的文件夹无法访问。一开始觉得很奇怪,明明特意从c盘卸载了安别的盘,后来我想起来那个盘是我从c盘分出去的了,草(感叹词)。所以应该是因为也需要管理员权限(也可能是我把git安到c盘了?)。果然管理员启动bash之后,安装就顺畅了。

枫叶的教程里面设置npm的环境变量那里可能有点问题,设置好之后应该是不需要像网上一些教程说的那样安装两遍npm的。npm所在目录需要保留而不是更改,再按教程添加node的目录。在系统变量里添加node的路径后,path里需要添加对应的%NODE_PATH%,这也是教程里未提及的。

其他问题应该就只是跟版本有关了,比如GitHub把主分支从master改成main,创建个人网页的setting单独分页了等等。以及博客更新后无需删除.git重新上传,hexo的操作估计是有延迟的。

我跳过了教程里设置自己的域名的部分。(以后博客里内容多了再为它花钱吧)

在菜单中增加新页面需要同时hexo new page以及在主题的config文件中设置(参考枫叶的教程)

一些感叹

虽然我对于文件系统和权限的理解仅限一鳞半爪,但在配置网站的过程中,这些知识还是帮了我不少忙。不愧是程序员的基本功。

一些bug

git报错the remote end hung up unexpectedly:照此教程解决了:

https://jingyan.baidu.com/article/afd8f4de38d87174e386e967.html

这两天感觉做题的速度快起来了!可以一到一个半小时做完一道题(当然是比较简单的题目啦)。

试着做了一点牛客网上的面试题库,发现数据结构这块果然不能一点书不看(之前我是不是飘了?),准备看数据结构书了。

最近发现了力扣的笔记功能,虽然题目集的笔记和题目的笔记是分开的,有点坑,不过还是打算不写博客的时候先记在题目集笔记里,方便之后翻阅整理。

3/2-3/11

(累了,摸会🐟)

心血来潮想找几个javascript小游戏玩玩,github上找到了untrusted这个游戏。

3/18

想打开网页直接玩来着,结果网页显示一些资源无法访问。于是按issues里的问题换了源,还是没办法。看来只好搭个本地服务器了。

直接down zip文件到了本地(文件有点大 怕git拉到本地中途出问题),git bash安装了http-server,http-server可以这么启动:

http-server [path]

结果跟网页端一样无法显示…一看报错发现没有编译.js文件出来,这就网上搜一圈看看怎么弄。

下载git bash的时候就看到附带了mingw,结果不能直接用make命令,而是得用mingw32-make,好家伙,然而整完还报错:

Makefile:14: *** File mods/default/intro.js not found!. Stop.

本来以为是下载的时候出了问题,上github一看,人家的描述是会自动生成这个文件,那我这是哪里出了问题?

整了挺久累了,下次再更🕊~

对了!make不能用cmd,会报奇怪的错!git bash就不会。

3/18

在github的issues里找到了这个解决换源,虽然说的是网页问题,但也可以改下载下来的code解决404问题。

Here’s a solution:

  1. Right click and click “Save As…”
  2. Edit the html file that just saved, overwrite jQuery reference <script src="//ajax.googleapis.com/ajax/libs/jquery/1.10.2/jquery.min.js"></script> as <script src="http://libs.baidu.com/jquery/1.11.3/jquery.min.js"></script> or other reference you trust.
  3. run the html.

最后就是上面的file缺失问题了,我找到了一个较早的branch,copy了里面untrusted.js的代码并整到本地的对应文件夹

E:\works\untrusted-master\scripts\build

这样就不用make了,虽然感觉可能会出些错,但是我只是想玩个游戏,先这样啦~

对了,别忘了

http-server *:/.../untrusted-master

(*:code所在盘符,…:code所在目录)

终于可以玩了!

这个游戏里用setPhoneCallback蛮多次的,在这里存下这些代码,免得往回翻了。

1
2
3
4
5
6
7
8
9
10
11
12
13
map.getPlayer().setPhoneCallback(function () {
var player = map.getPlayer();
if(player.getColor() == "#0f0"){
return player.setColor("#f00");
}
else if(player.getColor() == "#f00"){
return player.setColor("#ff0");
}
else if(player.getColor() == "#ff0"){
return player.setColor("#0f0");
}

});

刷了有快一周leetcode题目了,感觉算法这块进度偏慢,一天可能刷一两道题就是极限了。

刷的是leetcode学习栏里的初级算法选题。有时候感觉自己的记忆力真是差到一定程度了,有好两道题刷完后才发现自己在算法竞赛入门里看过,就是记不起来,结果还是用了最笨的方法…

可以预感到自己学了有些方法,例如双指针,之后还需要适应…太难了!一步一步来吧

(以下所有题目来源力扣cn官网)

2/25-3/1

LC26. 删除有序数组中的重复项

给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int a=0;
int b=nums.size();
if(b<=1) return b;
for(int i=0;i<(b-1);i++){
if(nums[i]!=nums[i+1]){
nums[a]=nums[i];
a++;
}
}
nums[a]=nums[b-1];
return a+1;
}
};

这里(重新)学到了双指针的思想,熟悉了下许久未见的cpp。选cpp语言来学其实只是因为自己以前选的好几本(算法跟opencv)教程都是cpp的,虽然听说cpp面试在语言特性上挺严格的,但是感觉比起另一个我学过一点的python,这个更能展现一些语言内部的设定吧,python总感觉隐去了不少细节,对我之后代码风格不是太有利。

这道题其实还好,后面有在原值上修改的题,就一定要用vector<int>& nums这种传引用的方式。

在写这道题的时候发现自己各种函数都快忘完了,.size()/memset()/.length() 都不记得了,哎。

122. 买卖股票的最佳时机 II

给定一个数组 prices ,其中 prices[i] 表示股票第 i 天的价格。

在每一天,你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它,然后在 同一天 出售。
返回 你能获得的 最大 利润 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int maxProfit(vector<int>& prices) {
int day=0;
int count=0;
bool st=false;
if(prices.size()==1)return 0;
for(int i=0;i<prices.size()-1;i++){
if(prices[i]<prices[i+1]&&i+1!=prices.size()-1&&st==false){
day=i;
st=true;
}
if(prices[i]>prices[i+1]&&st==true){
count+=prices[i]-prices[day];
st=false;
}
if(prices[i]<=prices[i+1]&&i+1==prices.size()-1){
if(st==true)count+=prices[i+1]-prices[day];
if(st==false)count+=prices[i+1]-prices[i];
}
}
return count;
}
};

做这道题的时候我想到了要在下降的最低日买,上升的最高日卖,然后就捅了if窝……不过这几个条件想合并确实有点难吧。

然后我一想到这个解决方法就乐起来了,完全没想到自己之前在教程里看过一个更简单的解法,就是求每一个前后两日差,然后求其中正数的和。其实我思考题目的时候想到了是不是可以利用每一段买入到卖出可以拆解成这段时间每天都买入卖出,但是没想到啥好的利用方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int maxProfit(vector<int>& prices) {
for(int i=0;i<prices.size()-1;i++){
prices[i]=prices[i+1]-prices[i];
}
int pf=0;
for(int j=0;j<prices.size()-1;j++){
if(prices[j]>0)pf+=prices[j];
}
return pf;
}
};

哦对,还可以代码复用一下

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int maxProfit(vector<int>& prices) {
int pf=0;
for(int i=0;i<prices.size()-1;i++){
prices[i]=prices[i+1]-prices[i];
if(prices[i]>0)pf+=prices[i];
}
return pf;
}
};

这样看起来就简洁多了!需要注意的是最后一天没有别的天数来减(买了不卖也是亏),在第二个循环中不用加上。

48.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

1
2
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[[7,4,1],[8,5,2],[9,6,3]]

这题显然是有一定的规律可以利用的,否则一边一边写旋转,代码有点太多了。看到题目强调矩阵这个概念,我就想到了可以把矩阵操作一下,比如转置之类的。

第一次做这题时,我想到可以先转置,再看看怎么调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
int tri = 0;
for (int i = 0; i < n; i++) {
for (int j = 0+tri; j < n; j++) {
int tr=matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tr;
}
tri++;
}
for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(),matrix[i].end());
}
}
};

果然,转置过后,每一行reverse一下就行了。不过需要注意的是转置时遍历一个三角即可,不然是转置两次。

后来重做了一遍,我是倒过来想的,先reverse列,再转置。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); i++) {
for (int j = i; j < matrix[i].size(); j++) {
int ori = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = ori;
}
}
}
};

这次我学聪明了,知道遍历三角可以j = i,少几行代码。不过这样写使用内存居然比第一次多!我把这个想法也改成用j = 0+tri的形式(其他没变),内存使用变成和第一次一样了。这是为什么呢?

我想去stackoverflow上问问,就去了leetcode英文站看看英文题目描述,顺手再提交了两次题目,发现内存占用又一样了…但是我用最开始的写法时间更快。好吧,看来这或许不是我现阶段能了解的问题。