简介

这篇博客记录了做算法题过程的一些心得，目前的想法是先把网课的习题做完提交完，然后学习C语言面向对象的知识，然后去刷题平台上去刷题

Openjudge

• 题目链接
• iostream头文件包含了cin与cout
• int &a=b中&的用法是C++中的引用用法，变量的引用就是变量的别名，这样就可以实现在函数中向实参传递值
• ~的用法之一是按位取反运算，即数的每一位都取反，^的用法之一是按位异或运算
• stdio.h是C语言的标准库，包含了C语言常用的输入输出函数，比如文件的读写函数fopen/fclose，格式化输入输出函数scanf/printf，为了适配C++，变成了cstdio
• strlen()是string.h的一个函数，可以返回字符串的长度，原理是读到结束字符\0后停止
• 字符串变量可以通过cin读取键盘输入的字符串，对于由0/1组成的字符串而言，可以考虑用整型存储，然后通过按位运算对整型的每一个bit进行操作
• memcpy()是cstring中的一个函数，使用时需要引用cstring头文件，memcpy(char * a, char * b, int c)表示将字符串b拷贝到字符串a，c表示字符串的大小
• 可以将递归嵌套在循环中完成穷举
• 全排列的实现有固定的套路: 对排列的每一位进行循环，如果有用过的元素，就标记一下，在下次选取的时候不考虑该元素，这样按着顺序选元素就可以实现全排列，具体见问题3，全排列也是一个穷举的过程
• 定义字符串或者一维数组时，最好还是把元素个数给大一点
• 在循环中可以通过bool值来控制某一个元素取还是不取，比如004中的加号可以由布尔值控制
• cin.peek()可以读取当前输入的字符且不取走，cin.get()可以读取当前输入的字符并且取走
• n = scanf("%c", &c)，如果当前输入停止，则n=EOF
• while(cin >> a)可以实现对某种类型的变量a的持续输入
• 用二分法解决问题时，端点尽量最优化设计，并且除了取中点外，还可以通过左端点逐步加1/右端点逐步减1来寻找最优点
• 关于PI的数值，可以通过acos(-1.0)取值
• #include<iomanip>引用的是iomanip库，主要用于控制输入输出流的精度，比如setprecision(int n)用于控制输出流浮点数的精度，整数n代表有效数字个数(四舍五入)，使用cout<<fixed<<setprecision(n)可以保留浮点数的n位有效小数
• 分治，或者说归并的思想，就是对每一步分而治之，确定每一小步的操作后，递归到归并的最小单元进行操作，常见的分治算法为归并排序与快速排序
• 利用#include<fstream>可以进行file的读写，步骤为: 实例化ifstream infile->打开文件infile.open("in.txt")->读文件infile.getline(...)->关闭文件infile.close()
• #include <algorithm>中的方法max_element可以返回数组的最大值所在的地址，*max_element可以返回数组的最大值
• scanf("%s", a)可以直接把字符串读入a
• char *比int *占用内存少
• 为了节省内存，可以试试将数组降维
• 结构体的构造函数和普通函数的定义类似，只不过函数名变成了结构体的名称
• 直接对字符'0'进行转型不会得到0
• memset(array, int, size)一般用来对数组进行初始化，初始化的值为int
• 结构体中重载运算符: type operator+(...){}其中operator和运算符一起出现可以视为函数名，type为返回值类型
• 更改结构体元素前三思
• ostream & operator <<(ostream & o, ...){}可以让自己定义的结构体能用cout输出
• int的取值范围为-2147483648 ~ 2147483647，long就是int，long long的取值范围为-9223372036854775807 ~ 9223372036854775807
• 动规的方向很重要，有时候从0开始递归简单，有时候从最后递归简单
• memset()是#include <cstring>的方法
• 深搜可以和动规结合
• 针对路径问题，在发现某一条路走不通后需要恢复该节点的访问状态，以便其他路径能访问该节点
• 队列的使用方法: queue<T> q来初始化队列q，q.front()来得到队列的头且不删除，q.pop()删除队列的头，q.push(T)向队列q的队尾添加元素
• 考虑一个节点的访问状态时一定要考虑仔细
• 结构体的构造函数:

struct node{
    int data;
    string str;
    char x;
    // 自定义构造函数
    void init(int a, string b, char c){
        this->data = a;
        this->str = b;
        this->x = c;
    }
    // 无参数构造函数, 这里顺序随意, 初始化时须以定义顺序初始化, 建议这里也以定义顺序书写
    node(): data(), str(), x(){}
    // 有参数构造函数
    // 在建立结构体数组时, 如果只写带参数的构造函数将会出现数组无法初始化的错误, 须先写无参数构造函数
    node(int a, string b, char c) :data(a), str(b), x(c){}
};

• 考虑深搜问题的状态时，最好考虑一下如此设置的话是否方便剪枝
• 在深搜的过程中可以根据终点和当前节点的位置关系来改变深搜的顺序
• 考虑剪枝时，可以考虑多种剪枝方法一起放到dfs中尝试
• 广搜其实就是给节点分层了，从第一层开始按层搜索，这样只要找到可行的解就是最优解，具体来说就是利用队列实现，每加入一个新节点就往队尾加入它的子节点，这样便可以实现逐层搜索
• 如果需要输出广搜过程的节点，那么需要用自定义的数组来实现，用头和尾指数来实现数组的添加和指数的移动，每个节点包含上一个节点的指数
• 用int或者bool数组来读取cin时，如果没有空格，可能会读取到不想要的结果
• 如果有需要用数字代表字符串的情况，可以考虑用switch来实现，比如下面的情况:

switch(result[i].mov) 
{
	case 1: //FILL
		cout << "FILL(" << result[i].src << ")" << endl;
		break;
	case 2: //DROP	
		cout << "DROP(" << result[i].src << ")" << endl;
		break;
	case 3:
		cout << "POUR(" << result[i].src << "," << result[i].dest << ")" << endl;
		break;
}

• 优先队列的用法:
  • 引用: #include <queue>
  • 实例化: priority_queue<T> q, 默认为降序排列，数据类型就是T，如果是自定义结构的话，需要重载小于运算符
  • 方法: 和队列类似，.pop()是删除头部元素，.push()是加入元素
• 贪心算法就是每一步都考虑最优的情况
• 有时候基本上一摸一样的想法和代码，但是我的代码在openjudge跑不通，不知道为什么

leecode热题HOT100及OOP习题

• 网页链接
• 动规的时候如果要使用滑动窗口来减少内存使用量，一定要注意是顺序遍历还是逆序遍历比较合理，一般来说逆序遍历会比较合理
• 如果不规定数组的大小的时候，可以这么初始化数组int[]={1,2,3}
• 一个问题如果从正面不好进行搜索的话，可以尝试从反方向进行搜索，比如戳气球的问题，从正面开始搜索不好弄，因为每次戳气球都会改变气球的相对位置，但如果从反方向开始搜索，看成填充气球，那么会简单很多
• 动规的循环方向很重要
• cin.getline(字符数组名,字符个数,结束字符)可以读取长度为字符个数的输入到字符数组，如果结束字符缺省，则默认为\0
• strtok(char s[],const char * delim)可以将字符串s进行分解，delim为分隔符字符，如果传入的是一个字符串，那么字符串的每一个字符均为分隔符，返回一个分解完毕的字符串，如果要再次调用，需要将s设置为NULL
• char * strchr(const char * s, char c)这个函数表示在字符串s中查找字符c，返回字符c第一次出现在字符串s的位置，返回值指向这个位置，如果找不到，就返回NULL
• sscanf通常用来解析并转换字符串
• 类的构造函数一定要加分号
• 可以通过char c : str的方式遍历一个字符串，常用于for循环中
• unordered_set是c++ 11 为STL标准库新添加的容器，称作无序容器或哈希容器，unordered_set不会对存储的数据进行排序，容器内存储的元素互不相同，添加元素的方法是insert()
• vector中push_back()与emplace_back()的关系: 两者都是在向量的尾部添加元素，但是emplace_back()会调用构造函数原地构造，不会触发复制构造函数和移动构造，更快
• auto是C++语言存储类型，初始化可为任何表达式
• .size()可以返回vector的大小
• .size()也可以返回string的大小，str[i]可以访问字符串的第i个字符
• str.substr(a,b)可以返回字符串的子字符串，从a到b，左闭右开
• 构造结构体的时候最好初始化一下，就是在定义的时候就算没有输入参数也可以初始化，这样可以避免很多bug
• sort()进行排序的时候默认是升序，如果需要降序，需要在sort里加入greater<>()
• 在for循环中，如果没有定义循环指数如何变化，一定要注意其边界条件是否正确
• 在接雨水这个题目中，把能接水的坑细分成一个个柱子进行接水
• C++中哈希表的定义unordered_set<T> name
• C++中空指针可以用NULL，也可以用nullptr
• C++中哈希表的使用: .count()用于判断是否有某个元素，.insert()表示在哈希表中插入某个元素
• 环形链表双指针法，一个指针走快(2步)，一个指针走慢(1步)，这样可以实现快速找到入环点，这样可以节省空间
• 合并链表这个事儿，一般是设定一个虚拟的指针，然后从这个指针开始，指向需要合并的链表的头
• 优先队列就是有排序的队列，会按照设定的大小关系对队列中的元素进行排序
• 分治一般能把时间复杂度从n降到logn
• 结构体中定义了构造函数后，使用向量或者其他数据结构时需要用大括号把参数括起来插入数据结构
• 给二叉树新增节点时，不能通过定义一个节点，然后取它的地址的方法来新建，得用指针new一块内存空间，然后给它赋初始值，然后让二叉树的左节点或者右节点指向它
• 一般来说，log()时间复杂度对应的方法有可能是二分查找
• 队列是先进先出，栈是先进后出
• 栈可以用Deque实现，Deque是双端数组，既可以对数组的前端进行删除或者插入的操作，也可以对数组的后端进行删除或插入的操作
• 动态规划中存储中间计算结果的数组可以用二维向量实现:vector<vector<int>>=f(m,vector<int>(n)), f表示向量名称
• C++中也有类似于python中lambda函数实现的方法:

  auto matches = [&](int i, int j){
    ...
  }
  

• 滑动窗口解决最小覆盖子串的问题
• 用哈希表存储两个变量时这么定义:unordered_map<char, int> name，如果p是哈希表中的一个元素，那么可以通过p.first和p.second分别访问第一个值和第二个值，存储值时可以像字典一样name[c]++，其中c是字符, .find(c)用来寻找哈希表中是否存在字符c，如果没有，会返回name.end()
• 栈的实例化: stack<int> name,删除元素: .pop()，取顶部的元素.top()，添加元素.push()
• list中a.erase(a.begin())就是删除了列表头部的元素
• 双端队列deque中，q.front()是队首元素，q.pop_front()是删除队首元素，q.back()是队尾元素，q.pop_back()是删除队尾元素
• 哈希表unordered_map<int,int>中，寻找某个key是否存在的方法是.find()，如果找到key，那么返回key所在元素的指针，如果没找到，那么会返回name.end()
• 哈希表的优势在于查询和删除非常快，哈希表的key值不能重复，如果重复了，下次添加的时候会覆盖前者相同key值的value
• 空指针是没有相关结构的相关参数值的
• substr(i, len)的作用是返回string字符串的子字符串，从原string的i出发，返回长度为len的子字符串
• 链表的题目可以在链表的头部前面并上一个虚拟的头部，有时候能节省很多麻烦的逻辑判断
• 利用位运算可以把布尔数组的空间复杂度降低

Quehry

Student