DFS和BFS
特征
DFS
BFS
数据结构
stack
queue
储存空间
只用储存一条路的数值，所以跟高度或者路的长度有关 O(h)，使用空间较少
每次储存一层的数值，所以是指数增长 O(2^h)，使用空间较多
常用场景
不具有最短性
因为是一层一层地搜索，所以可以最快搜索到最短路径(特别是权重为1的时候)
深度优先搜索 DFS一条路一直搜索下去，然后后退。
题目例子：排列数字
给一个数n，将1~n排成一排，按字典顺序输出所有的排列方法。
12345678Input: 3Output:1 2 31 3 22 1 32 3 13 1 23 2 1
DFS代码：123456789101112131415161718192021222324252627282930313233343536373839#include <iostream>#include <vector>using namespace std;const int N = 10;int n;int path[N];bool used[N];void dfs(int level)&# ...
C++面试准备
这里是自己搜罗准备的C++面试八股文常用题目，持续更新。
Static关键字作用
基本概念
静态数据成员
静态成员函数
Extern关键字作用
指针和引用
动态库和静态库的区别
虚函数和纯虚函数的区别
虚函数
纯虚函数
友元的应用
友元函数
友元类
BFS与DFS的实现
BFS Bread-First Search 广度优先搜索
DFS
STL常用容器和算法
List和Set
红黑树
二叉搜索数
HashMap的原理
堆和栈的区别
如何解决死锁
Static关键字作用基本概念
使用目的：
在 C++ 中，需要一个数据对象为整个类而非某个对象服务,同时又力求不破坏类的封装性,即要求此成员隐藏在类的内部，对外不可见时，可将其定义为静态数据。
存放位置
DATA 段（全局初始化区）存放初始化的全局变量和静态变量；BSS 段（全局未初始化区）存放未初始化的全局变量和静态变量。其中BBS段在程序执行之前会被系统自动清0，所以未初始化的全局变量和静态变量在程序执行之前已经为0。存储在静态数据区的变量会在程序刚开始运行时就完成初始化，也是唯一的一次初始化。
使用 ...
C++常用设计模式
工厂模式(Factory)简单工厂只有一个工厂，即一个类负责创建不同类的实例。通常使用static静态方法来创建对象，不需要传递工厂类来创建实例。
优点：
单一工厂类，实现简单
缺点：
扩展性差，添加新类，新产品时，需要修改工厂类代码
代码实现：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <iostream>using namespace std;class Car{public: virtual void drive() = 0; // 创建纯虚函数，让每个子类实现 virtual ~Car() {} // 析构虚函数，保证子类析构时能正确调用子类析构函数};class BydCar : public Car{public: void drive() override { cout << " ...
SFML C++ 项目
项目简介
项目Setup
项目代码
项目简介这是一个跟着COMP4300的课程记录制作的项目，因不公开提供代码资料，所以我自己整理了一份方便其他人使用，放在网页上的代码和文档都test过，请放心使用。
这个项目利用SFML来制作一个含有各种图形四处悬动的窗口，示例如下：
要求从config.txt文件中读取窗口大小，生成要求的图形（positionX, positionY, speedX, speedY, r, g, b, (height, width) or radius），图形需要根据自身的速度在窗口中移动，当碰到边框时进行反弹（速度变成相反的），图形需要在正中间显示图形名字：12345678Window 1280 720Font fonts/KillerTech.ttf 36 128 128 255Circle CGreen 100 100 -3 2 0 255 0 50Circle CBlue 200 200 2 4 0 0 255 100Circle CPurple 300 300 -2 -1 255 0 255 75Rectangle RRed 200 200 4 4 ...
函数指针
函数指针是指向函数的指针，跟指向变量的指针没差。
函数的一个属性就是其地址指明了函数体在内存中的位置，在调用函数时，系统将控制权给这个位置来执行函数。
用一个函数来举例
1234double f(double x){ return 2*x;}
这里，f是指向函数f()的指针，*f()是函数本身， (*f)(7)是调用这个函数并取得值，其本质跟f(7)没有任何差别，只是在大多数编程语言中（包括 C 和 C++），编译器会自动理解f是一个函数指针并进行适当的解引用。
函数指针一般在需要函数作为一个变量的时候起到作用，即函数作为参数传递，如当要求n到m之间用函数f的总和时：12345678double sum(double (*f)(double), int n, int m){ double result = 0; for (int i = n; i <= m ; ++i) result += f(i); return result}
这里，double (*f)(double)是指f为指向一个返回 ...
指针vs引用
指针：
指向值，但本身值为地址。
可以有null pointer，指向特殊地址0
初始化后可以被改变
引用：
相当于const指针，int& r = n等同于int *const r = &n
因为是int *const所以初始化之后，r本身的值不能改变，也就是不能改变它指向的地址了
关于int *const r:
表示一个常量指针，指向一个整数。
指针是常量：一旦初始化，指针本身的值（即它指向的地址）不能改变。
指向的数据是可变的：可以通过这个指针修改它指向的整数的值。
123456int value1 = 10;int value2 = 20;int *const ptr = &value1; // 常量指针，指向 value1，可以将const后面的(ptr)单独看，它是指针本身，所以是指针本身不能变，也就是ptr所储存的地址不能变*ptr = 15; // 这是可以的，因为可以修改指针指向的数据，所以也可以更改被引用的变量的值// ptr = &value2; // 报错，因为不能修改指针本身的值
相应的有const int *：
...
复制构造函数
复制构造函数的用途就是解决：当将数据从一个对象复制到另一个对象时，其中的指针数据成员没有被正确处理的情况。
如：12345678910struct Node{ char *name; int age; Node(char *n=" ", int a = 0) { name = strdup(n); // strdup是用来分配一个新的内存并返回该指向该字符串的指针 age = a; }}
当这样带char *name指针的对象，经历复制时，会遇到以下问题
12345678Node node1("node1", 10); // Create object node1Node node2(node1); // Create a node1 copy named node, 同样可写为： Node node2 = node1;strcpy(node2.name, "changedName"); // 将node2的name改为" ...
双指针算法
双指针算法主要思想：
帮助优化双循环算法，原本算法为O(n^2)：
12for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)
可以将算法优化为O(n)，此时双指针就像弹簧一样，i在前面扯着j往前移动，然后check它们中间那一段是否合格：
12for (int i = 0, j = 0; i < n; ++i) while (j < i && check(i, j)) j++;
基础题给一个字符串，单词用空格隔开，输出每个单词
12345678910111213141516171819202122232425#include <iostream>#include <string>using namespace std;int main(){ string input; getline(cin, input); for (int i = 0; input[i]; i++) { // mark the ...
经典笔试刷题集合
牛客 HJ17 坐标移动（中等）开发一个坐标计算工具， A表示向左移动，D表示向右移动，W表示向上移动，S表示向下移动。从（0,0）点开始移动，从输入字符串里面读取一些坐标，并将最终输入结果输出到输出文件里面。
输入：
合法坐标为A(或者D或者W或者S) + 数字（两位以内），坐标之间以;分隔。（如：A10;S20;W10;D30;X;A1A;B10A11;;A10;）
非法坐标点需要进行丢弃。如AA10; A1A; $%$; YAD; 等。
起点（0,0），A10 = （-10,0），S20 = (-10,-20)
数据范围：1 <= n <= 10000
1
有趣轶事
有趣轶事参加SIG event day的搞笑事情