算法基础-数据结构：链表
链表与邻链表0.传统的链表创建方式在运算速度上非常慢
struct ListNode{ int val; struct ListNode* next;};new struct ListNode();//new一次很慢,因为new是动态分配
1.数组模拟单链表数组模拟链表，也成为静态链表
链表的实现方式：
一开始用head指针存储链表头节点，head之后就是空指针
之后让head之后的指针指向新节点，以此类推，直到最后一个节点，再让下一个节点指向空指针
定义e[n]为该节点的值，ne[n]为该节点的next指针
e[0] = 3,ne[0] = 1(指节点1)
e[1] = 5,ne[1] = 2(指节点2)
…
e[3] = 9,ne[3] = -1(空节点)
如何在头节点插入一个节点（算法题常用）链表需要数形结合
1.将所想要插入的值的next指针指向0节点
2.将head的next指针指向该值
3.存储该值
代码实现
void add_to_head(int &x)//把一个值插 ...
算法基础：区间合并
区间合并 概念：在有序升序序列中，如果某一区间合另一区间存在交集，则两个区间可以合并为一个区间
思考情况：
1.绿色区间在蓝色区间内部2.橙色区间与蓝色区间有交集3.粉色区间与蓝色区间无关联
最终得到新的合并区间[ st , ed ]
st全称start，ed全称end
例题题目描述给定 n 个区间 [li , ri]，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。输出合并完成后的区间个数。例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。输入格式第一行包含整数 n。接下来 n 行，每行包含两个整数 l 和 r。输出格式共一行，包含一个整数，表示合并区间完成后的区间个数。数据范围1 ≤ n ≤ 100000 ,−1e9 ≤ li ≤ ri ≤ 1e9
输入样例
51 22 45 67 87 9
输出样例
3
题解#define _CRT_SECURE_NO_WARNINGS 1//将所有 有交集的区间合并#include <iostream>#include <vector>#include <algorit ...
算法基础：离散化
整数离散化离散化的概念对一组序列进行升序排列，然后用0映射，代表序列的最小数，1映射第二小的数，以此类推，与利用数组存储相似
如果序列中有重复元素，应当先去重删除重复元素再排序映射
对序列1 2 2 3 5离散化排序得到1 2 2 3 5去重并删除得到1 2 3 5离散化映射序列1 2 3 5映射0 1 2 3
模板int main(){ vector<int> alls;//存储将要离散化的数据 sort(alls.begin(), alls.end());//对所有值排序 //unique对所有元素去重，重复的元素会被放在最后 //unique返回值为去重排序后前排未去重元素的总数 //用erase函数对已放在后排的元素删除 alls.erase(unique(alls.begin(), alls.end()),alls.end());
例题1//寻找序列离散化后特定值对应的映射坐标#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>#include <vector>#i ...
算法基础：位运算
位运算 最常用的两种操作
1.n的二进制表示中第k位是几 比如
n = 15 的 二进制 （1111） 从个位起算第0位，十位为第二位，以此类推
操作符>>把n的第k位移到最后一位
比如
n = 16, k = 3;n == (0001 0000)n >> k == (0010)n = 15,k = 3n == (0000 1111)n >> k == (0000 0001)
2.n的二进制个位是多少比如
n = 2n == (0010)n的个位为0
操作符&按位与&，两个操作数按位与时，二进制某一位相同则为1，不同则为0
比如
n == 2,k = 1n == (0010)k== (0001)四位都不相同n&1 ==(0000)
3.进阶运算 计算某数二进制某一位是多少
//计算一个数二进制某一位是多少#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>using namespace std;int main(){ int ...
算法基础：双指针算法
第一类 两个指针分别指向两个序列，例如归并排序
第二类 两个指针都指向一个序列，一个在区间的开头，另一个在区间的结尾,例如快排
双指针算法并非一定要用指针来表示
核心思想先写出一种暴力做法，然后观察i与j之间是否存在关联，比如单调性，从而优化代码
for(int i = 0;i < n;++i) for(int j = 0;j < n;++j) if(check(i,j)) ...
将上方原先O（n^2)的朴素算法优化为O（n）
通用模板for(i = 0,j = 0;i < n; ++i){ //符合条件 j++ while(j < i && check(i,j)) j++; //每道题后面的具体逻辑}
举例#define _CRT_SECURE_NO_WARNINGS 1//实现以空格为分隔符换行打印一个带有多个空格的字符串#include <iostream>#include <string>using namespace std;int main(){ strin ...
c语言基础难关：按位取反
1.理解按位取反的前提符号位二进制最前端的1代表负数，0代表正数，符号位一般会占据最前端比如1字节数的0可以表示为
[0000 0000]
1个字节最大存储数为
[0111 1111] 或 [1111 1111]分别是2的8次方-1，即 255 和 -255符号位占据了一个比特位
原码反码补码的相互转化 正数的相互转化 原码：符号位为0，其后将十进制转化为二进制，得到的就是其原码反码：与原码相同补码：与原码相同
负数的相互转化 原码：符号位为1，其后将十进制转化为二进制，得到的就是其原码反码：符号位不变，其余都进行取反，原先为1的变为0，原先为0的变为1补码：反码+1
举例
正数 1 --- [0000 0001]原 --- [0000 0001]反 --- [0000 0001]补负数 -1 --- [1000 0001]原 --- [1111 1110]反 --- [1111 1111]补
2.按位取反的具体逻辑 得到新补码后要注意符号位是什么，如果为1则继续推演，如果为0，则得到的新补码就是新原码 步骤
（1）得到该数的补码（2）对补码取反，得到新的补码（3） 对新补码反 ...
