蓄水池算法（reservoir sampling）是一种随机算法，用于从数据流中等概率地选择k个元素，其中数据流的大小或数量未知或非常大。该算法适用于需要对数据流进行随机抽样的问题，例如在线随机抽样和统计分析。

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。

遇到poweshell 不识别 nodemon 命令的问题

1

The term 'nodemon' is not recognized as a name of a cmdlet

删除repo中的隐私数据

Sometimes，在写代码的过程中，一些variable带有隐私信息，尽管时候在github上删除相关内容，但是在history commit中仍然存在，所以得想其他的办法

思路

【思路】：建立新的分支 -> 删除原本分支 -> 将新分支作为主分支

实现

1. 创建并切换到新的分支

git checkout --orphan lateset_branch

1. 添加所需文件(假设所有)

git add -a

1. 提交当前分支的修改

git commit -m 'something u wanna say'

1. 删除本地 main 分支

git branch -d master

1. 重命名当前分支

git branch -m main

1. push 到远程仓库

git push -f origin main

Deque 双端队列

295场周赛T4，01BFS用到双端队列，之前很少接触这个数据结构

Double-ended queues are sequence containers with the feature of expansion and contraction on both ends.

由此可见，双端队列也就是一个可以在front-end和back-end两端插入或删除的数据罢了

用法

• 例子：

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

// CPP Program to implement Deque in STL
#include <deque>
#include <iostream>

using namespace std;

void showdq(deque<int> g)
{
	deque<int>::iterator it;
	for (it = g.begin(); it != g.end(); ++it)
		cout << '\t' << *it;
	cout << '\n';
}

int main()
{
	deque<int> gquiz;
	gquiz.push_back(10);
	gquiz.push_front(20);
	gquiz.push_back(30);
	gquiz.push_front(15);
	cout << "The deque gquiz is : ";
	showdq(gquiz);

	cout << "\ngquiz.size() : " << gquiz.size();
	cout << "\ngquiz.max_size() : " << gquiz.max_size();

	cout << "\ngquiz.at(2) : " << gquiz.at(2);
	cout << "\ngquiz.front() : " << gquiz.front();
	cout << "\ngquiz.back() : " << gquiz.back();

	cout << "\ngquiz.pop_front() : ";
	gquiz.pop_front();
	showdq(gquiz);

	cout << "\ngquiz.pop_back() : ";
	gquiz.pop_back();
	showdq(gquiz);

	return 0;
}

Output

1
2
3
4
5
6
7
8
9
10

The deque gquiz is :     15    20    10    30

gquiz.size() : 4
gquiz.max_size() : 4611686018427387903
gquiz.at(2) : 10
gquiz.front() : 15
gquiz.back() : 30
gquiz.pop_front() :     20    10    30

gquiz.pop_back() :     20    10

KMP 字符串匹配

普通的字符串匹配算法十分直观易懂，但是遇到特殊情况效率极低，因此KMP算法是一种高效的字符串匹配算法

算法的核心思路是减少重复匹配的次数从而降低时间复杂度

• 普通匹配算法的时间复杂度 O(mn)

• KMP算法的时间复杂度 O(m+n)

Vector用法总结

好久没更新博客了，最近狂刷LeetCode，总结一下遇到的常用的Vector容器的用法

vector定义

• 创建一个vector

vector<T> arr

• 创建n个size的vector

vector<T> arr(int n)

• 创建n个size，值全为t的vector

vector<T> arr(int n, T t)

• 拷贝另一个vector

vector<T> arr(vector<T> anotherArr)

• 拷贝另一个vector的一部分

vector<T> arr(anotherArr.start(), anotherArr.end())

纲要

本地文件

第一章 计算机系统概述

世界上第一台电子数字计算机

第七章 图

图的基本概念

相邻

关联