CS61B学习记录
java基础知识 在java中，只有八种基本类型（byte,short,int,double,float,long,char,boolean）在调用时是值传递的调用，其他类型均为地址传递（引用） 所以，创建一个string类型的数组时，存放的是每个string类型的地址 创建一个数组的方法 123x = new int[3];y = new int[]{1,2,3,4,5};int [] z = {9,213,41,12}; 类可以进行嵌套。如SLList里嵌套了IntNode类，IntNode只是SLList的一个子功能 泛型实例化不能直接对数组使用，而要通过 1items = (T[]) new Object[9]; 语句实现 IntList 123456789101112131415161718public class IntList{ public int first; public IntList rest; public static void main(String[] args) ...
离散化与树状数组
离散化 特征：操作次数不多，相关点不多 离线与在线 离线：先存操作/询问后执行操作 在线：输入一次数据执行一次操作 找出相关点并存下/收集所有需要离散化的值 将相关点排序并去重 大点(小点)到小点(大点)的映射 通过二分实现大点映射到小点（根据值找位置->二分），通过离散化数组实现小点映射到大点 将操作全部转化为小点上 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556/*输入：n 个添加操作，每个操作包含一个坐标 x 和一个权重 w。q 个查询操作，每个查询包含一个区间 [l, r]。目标：对每个查询，计算区间 [l, r] 内所有 x 的权重和。*/#include<bits/stdc++.h>using namespace std;const int N = 3e5 + 9;using ll = long long;int a[N];vector<int> LS;struct...
DFS与BFS
模板 123456789101112131415161718192021222324252627void dfs(int dep)//dep代表递归层数或要填的第几个空{ if(所有空都填完了) { 判断最优解/记录答案； } for(枚举这个空能填的选项) if(这个选项是合法的) { 记录下这个空（保存现场）; dfs(dep+1); 取消这个空（恢复现场）; }}void bfs(int x){ queue<int> q; q.push(初始状态)//将初始状态入队 while(q.size()) { int u = q.front(); q.pop(); for(枚举所有可扩展状态)//找到u的所有可达状态v ...
单调栈与单调队列
单调栈与单调队列一般存在以下三种形式：存值，存下标，数组实现，数组实现的优点在于在清空栈时只需top=0即可 单调栈 伪代码： 12345678for(i=1->n)//n为元素数量{ ① while(栈非空且入栈元素优于栈顶元素)栈顶出栈//维持栈的单调性 //while结束的两种可能的判断 ② 如果(栈顶元素优于入栈元素)更新一次答案，此时栈顶即为最优解 否则 不存在答案 ③ 将新元素入栈} eg:输入n个数字 输出每个数字左侧距离该数字最近的比它小的元素，不存在则输出-1 in 5 7 8 5 6 7 out -1 7 -1 5 6 1234567891011121314151617181920212223//存值int a[N],ans[N];//a[N]用来存放输入的数字，ans[N]用于存放答案stack<int> stk;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){ ...
图
基本介绍 图(G)是由顶点集(V)和边集(E)组成的有序对，G=(V,E)，可以用|V|，|E|表示图中的顶点数量和边数量 图既可以是有向的，即单向链接，也可以是无向的，即双向链接。 只包含有向边的图称为有向图，只包含无向边的图称为无向图 若边关联了权重/成本，则叫做权重图，反之叫做非权重图 图的属性 一条边的两个端点为同一个顶点，称为自环 同一条边出现了不止一次，称为多重边 不包含自环或多重边的图称为简单图 边的数量 在一个简单图中，给定顶点的数量n(|V|=n) 有向图：0≤|E|≤n*(n-1) 无向图：0≤|E|≤n*(n-1)/2 若图中的边的数量接近最大的可能边数(顶点数量的平方)，则称这个图是稠密的。 若图中的边的数量接近顶点数量，则称这个图是稀疏的。 对图进行处理时，根据图的稠密/稀疏做出决策，如...
前缀和与差分
要对原数组a[N]进行修改与查询，需要用到前缀和数组和差分数组 diff求和——>a 求和——>prefix diff<——a差分<——prefix差分 一维前缀和与差分 前缀和 前缀和可用于求指定区间的和 求出前缀和数组 1前缀和数组的计算:prefix[i] = prefix[i-1] + arr[i] (此处及下文写法i均从1开始，以防止越界问题) 得出区间和 12由前缀和的可加性:sum[1,k] + sum[k+1,n] = sum[1,n]得到sum[l,r] = sum[1,r] - sum[1,l-1]，即sum=prefix[r]-prefix[l-1] 差分 差分可用于修改指定区间的值 求出差分数组 1diff[i] = a[i] - a[i-1]，它具有两个性质，一是可以通过求和得到a[i]，二是可以对后缀区间进行修改 对指定区间[l,r]的值进行修改 12diff[l] += x;diff[r + 1] -= x; 求出diff的前缀和数组，得到修改后的数组 1a[i] = a[i-1] +...