X02笔记【精华】
2024-12-15 17:13:38
发布于：浙江
day 01：
算法：
有穷性：有限时间；
确定性：有实际含义；
可行性：可以办到；
零个或多个输入；
一个或多个输出；
时间复杂度：
程序的效率或速度；
时间复杂度的符号：T(n)、O(n)；
O(1)代表所有常数的时间复杂度；
O(T(3))=1；
O)(T(2n+3))=O(n);
修改后的时间频度函数T(n)，只保留最高阶;
O(T(1+2n+n2))=O(n2);
记M^T = N 则T = log^M(N) 已M为底数计算N的对数；
O(T(2*log^2(n)+2))=O(log(n));
若最高阶的系数存在且不是1，则删除该常数；
快 慢
O(1)<O(logN)<O(N)<o(NlogN)<O(N2)<O(N3)<O(2^N)<O(N!);
一千毫秒 = 一秒 = 10^8次;
空间复杂度：
算法的空间复杂度是对
一个算法在运行过程中 临时 占用存储空间大小的一个量度；
最坏 最好 空间 稳定性
冒泡排序 O(N^2) O(N) O(1) 稳定
选择排序 O(N^2) O(N^2) O(1) 不稳定
插入排序 O(N^2) O(N) O(1) 稳定
桶排序 O(N+M) O(N+M) O(M) 稳定
稳定性：
同样数字在不同排序中相对顺序的变化；
bool=bitset 慢 快;
const 常量(无法改变);
今日代码：
#include<bits/stdc++.h>
using namespace std;
const int N=100000010;
bitset<N> vis;
void init(int n){
vis[1]=1;
vis[2]=0;
for(long long i=2;i<=n/i;i++){
if(vis[i])continue;
for(long long j=2*i;j<=n;j+=i){
vis[j]=1;
}
}
}int main(){
int n,cnt=0;
cin>>n;
init(n);
for(int i=1;i<=n;i++){
if(vis[i]==0)cnt++;
}cout<<cnt;
return 0;
}
day 02:
vector<数组类型> 数组名(初始长度,value);
value 为数组的每个元素的初始这位value;
数组名.size() 数组的元素个数;
v.size() 返回元素个数；
v.front() 返回第一个元素；
v.back() 返回最后一个元素；
v.resize(n) 调整大小为n，如果n大于当前大小，新的元素会被默认初始化；
v.reserve(n) 预分配内存，确保至少可以容纳n个元素，不影响vector的大小；
排序：
sort(v.begin(),v.end(),cmp);
#include <algorithm>;
贪心选择的性质：
每一步贪心必选出来当前最优解;
进制：
2 BIN;
8 OCT;
10 DEC;
16 HEX;
2:8 整数部分从右往左三个三个,小数部分从左往右;
2:16 整数部分从右往左四个四个,小数部分从左往右;
abcd.efg(k)=;
ak^3+ ;
bk^2+ ;
ck^1+ ;
dk^0+ ;
ek^-1 ;
+fk^-2 ;
+g*k^-3 ;
短除法：
整数：除k取余，逆序排列;
小数：乘k取整，顺序排列;
day 03:
原码、反码、补码:
计算机存储一个具体数字的编程方式，数值在计算机是已补码的方式存储;
机器数:
一个数在计算机中的二进制表示形式叫这个数的机器数，机器数是带符号的，最高位为0表示正数,为1表示负数;
机器数所代表的值,是它的真值;
原码:
符号位+数值位来表示
反码:
正数的反码与正数的原码一样，负数的反码是其符号位不变，数值位上取反;
补码:
正数的补码与正数的原码一样，负数的补码是负数的反码+1;
再取一次补码的补码是原码;
数值位上取反+1;
&:都为1时，结果为1，其余为0;
| :都为0时，结果为0，其余为1;
~:0变1,1变0;
对于非负整数X：~X=(X+1)；
^:跟各位相同为0，不同为1;
:>>a就将二进制数右移a位，高位补0，低位丢弃;
<<:<<a就将二进制数左移a位，高位丢弃，低位补0;
n>>m=n/2^m(整除);
n<<m=n*2^m;
格雷码:
两个相邻的二进制为只有1位不同;
将二进制的最高位不变,格雷码的其余为二进制码对应位与其上一位的异或;
将格雷码的最高位不变,二进制的其余为格雷码码对应位与二进制的上一位的异或;
一字节=8比特;
字节 B;
Byte=8bit 八位二进制数=一个字节;
1KB=1024B 1MB=1024KB 1GB=1024MB 1TB=1024GM;
求字节长度:
sizeof();
二分查找:
每次对半找;
复杂度:log^2n;
二分求下界:
下界:找到首个大于等于的元素位置，如果不存在，返回n+1;
1.R的右边始终都是>=x;
2.L的左边始终都是<x;
3.下界是L;
查找下界:
lower_bound(开始，结束，值)……地点;
upper_bound(开始，结束，值)……地点;
地点-开始=下标;
二分例子:
对于给定的一个长度为N的正整数数列 A1∼NA 1∼N ，
现要将其分成 M（M≤NM≤N）段，并要求每段连续，且每段和的最大值最小。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],n,m;
bool check(int x){
int cnt=1,sum=a[1];
for(int i=2;i<=n;i++){
if(sum+a[i]<=x)sum+=a[i];
else{sum=a[i];}
}return cnt<=m;
}int main(){
cin>>n>>m;
int l=0,r=n+1;
int ans=0;
for(int i=1;i<=n;i++)cin>>a[i];
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
r=mid-1;
}else{
l=mid+1;
}
}cout<<l;
return 0;
}
day 04:
栈(stack)又叫堆栈;
先进后出;
s=(……);
出栈 进栈;
栈顶 栈顶元素 push ;
栈底 栈底元素 pop ;
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=1100;
int st[N];
int top=0;
void push(int x){
top++;
st[top]=x;
}void pop(){
top--;
}bool e(){
return top0;
}int size(){
return top;
}void minn(){
int m=1001;
for(int i=1;i<=top;i++){
if(m>st[i])m=st[i];
}
cout<<"min="<<m<<endl;
}int main(){
int n;
cin>>n;
while(n--){
string a;
cin>>a;
if(a"push"){
int x;
cin>>x;
push(x);
}
else if(a=="pop"){
if(e())cout<<"pop fail"<<endl;
else pop();
}else{
cout<<"top="<<st[top]<<endl;
cout<<"bottom="<<st[1]<<endl;
minn();
for(int i=1;i<=top;i++)cout<<st[i]<<" ";
cout<<endl;
}
}return 0;
}
代码2:
#include <bits/stdc++.h>
using namespace std;
const int N=1100;
string st[N];
int head=0,tail=0;
void push(string x){
st[tail++]=x;
}void pop(){
head++;
}bool e(){
return headtail;
}string f(){
return st[head];
}
int main(){
string a;
while(cin>>a){
if(a"end")break;b
if(a=="out"){
int x;
cin>>x;
if(e()){
cout<<"empty"<<endl;
}else{
while(x--){
if(e())break;
cout<<f()<<" ";
pop();
}cout<<endl;
}
}else{
push(a);
}while(!e()){
cout<<f()<<" ";
pop();
}return 0;
}
队列(queue);
只可以一端插入，在另一端删除;
先进先出;
出队 队首元素 队尾元素 入队;
head tail;
取对头队尾元素;
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=1100;
int st[N];
int head=0,tail=0;
void push(int x){
st[tail++]=x;
}void pop(){
head++;
}bool e(){
return headtail;
}int main(){
int n;
cin>>n;
while(n--){
string a;
cin>>a;
if(a"push"){
int x;
cin>>x;
push(x);
}else if(a=="pop"){
if(e())continue;
else pop();
}
}for(int i=head;i<tail;i++)cout<<st[i]<<" ";
return 0;
}
STL:
队列：
queue<数组类型>数组名;
队伍头front();
栈：
stack<数组类型>数组名;
增加栈顶stk.push();
删除栈顶stk.pop();
判断栈是否为空stk.empty;
栈的长度stk.size();
输出栈顶stk.top();
打开文件：freopen("文件名","r",stdin);
打开文件：freopen("文件名","w",stdout);
输出文件：fclose(stdin);
输出文件：fclose(stdout);
排列:从给定的元素中，取出排序;
组合:从给定的元素中，仅仅取出;
0!=1;
从n个元素中，取出m个元素排列;
Anm=n!/(n-m)!;
从n个元素中，取出m个元素组合;
Cnm=n!/m!*(n-m);
A排列;
C组合;
Anm=CnmAmm;
n!/(n-m)!=Cnmm!;
Cnm=Anm/m!;
m!=Amm
Cnm = n!/m!(n-m)! = Cn n-m;
day 05:
前中后缀表达式:
中缀表达式 a+b;
前缀表达式=波兰式 +a b 全都没有括号;
后缀表达式=逆波兰式 a b+ 全都没有括号;
中缀表达式转后缀表达式;
a+bc-(d+e)=
((a+(bc))-(d+e))=
((a(bc*)+)(de+)-)=
abc*+de+-
运算方式:
从左往右扫描，
遇到运算符，把运算符发在左边两个数中间计算(将运算符左边第一个为右操作数，将运算符左边第二个作为左操作数)，
并将计算结果作为下次计算的操作数;
没有运算符优先级之分;
中缀表达式转前缀表达式;
a+bc-(d+e)=
((a+(bc))-(d+e))=
(-(+a(bc))(+de))=
-+abc+de+-
运算方式:
从右往左扫描，
遇到运算符，把运算符发在左边两个数中间计算(将运算符右边第一个为左操作数，将运算符右边第二个作为有操作数)，
并将计算结果作为下次计算的操作数;
没有运算符优先级之分;
后缀表达式转中缀表达式;
abc*+de+-=
(a+(bc)-(d+e))=
a+bc-(d+e)
遇到运算符，把运算符发在左边两个数中间，括号起来,
去掉不影响计算顺序的括号;
前缀表达式转中缀表达式;
+abc+-de=
(a+(bc)-(d+e))=
a+b*c-(d+e)
遇到运算符，把运算符发在右边两个数中间，括号起来,
去掉不影响计算顺序的括号;
先根据计算优先级加括号，移动运算转到前后，去括号;
后缀表达式:
操作数，入栈;
运算符，从栈中取两个操作数,(第一个为右操作数，第二个为左操作数),并将结果入栈;
辗转相除法;
最大公约数代码:
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
if(a%b==0)return b;
return gcd(b,a%b);
}int main(){
int a,b;
cin>>a>>b;
cout<<gcd(a,b);
}
最小公倍数代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int gcd(LL a,LL b){
if(a%b==0)return b;
return f(b,a%b);
}LL lcm(LL a,LL b){
return a*b/gcd(a,b);
}int main(){
LL a,b;
cin>>a>>b;
cout<<lcm(a,b);
}
day 06:
代码:
#include <bits/stdc++.h>
using namespace std;
int n,ans=0,a[100];
bool p(int n){
if(n<=1)return false;
for(int i=2;i<n;i++){
if(n%i0)return false;
}return true;
}void dfs(int deep,int sum,int xuan){
if(deepn+1){
if(p(sum))ans++;
return;
}if(a[deep-1]!=a[deep]||(a[deep]a[deep-1]&&xuan1)){
dfs(deep+1,sum+a[deep],1);
dfs(deep+1,sum,0);
}
}int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n);
dfs(1,0,0);
cout<<ans;
return 0;
}
代码2:
#include <bits/stdc++.h>
using namespace std;
vector<int> g[1000005];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}for(int i=1;i<=n;i++){
cout<<"i="<<i<<":";
for(int j=0;j<g[i].size();j++){
cout<<g[i][j]<<" ";
}cout<<endl;
}
}
day 07:
ACCII=char类型=一个字节;
int类型=四个字节;
long long=六十四个字节;
机械语言=二进制;
BFS:
让第一个上厕所；
标记；
当前队列非空；
拿出队首；
弹出队首；
寻找新的好朋友；
那些没上过厕所（没被标记）；
把好朋友加入队列；
标记；
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=1e3;
int vis[N][N];
int n;
int a[N][N];
bool check(int x,int y){
if(x<1||x>n||y<1||y>n)return false;
if(vis[x][y]==1)return false;
return true;
}struct node{
int x,y;
};
int dir_x[4]={-1,1,0,0};
int dir_y[4]={0,0,-1,1};
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}queue<node>q;
q.push({1,1});
vis[1][1]=1;
while(!q.empty()){
node u=q.front();
int x=u.x,y=u.y;
cout<<a[x][y]<<" ";
q.pop();
for(int i=1;i<4;i+=2){
int nx,ny;
nx=x+dir_x[i],ny=y+dir_y[i];
if(check(nx,ny)){
q.push({nx,ny});
vis[nx][ny]=1;
}
}
}
}
day 08:
线性表，是由不连续的存储块储存;
数组，连续;
结点，链表的一个存储单元;
数据域 指针域；
数据 下一结点的位置;
int p=&a; a的地址p;
*p=100; 改变a的值;
cout<<p; 输出p的值；
struct node{
int x;
}
node a=new node;
a->x=1; 改变x的值；
struct node{
char data;数据域；
nodenxt;指针域；
}
node head=new node;
head->data='A';
nodek=now node;
k->data='E';
head->nxt;
pre 前驱结点;
nxt 后继结点;
代码:
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
node *next, *prev;
};node *head, *tail;
void print_lst() {
node *step = head;
while (step) {
cout << step->data << ' ';
step = step->next;
}
}void print_lst_re() {
node *step = tail;
while (step) {
cout << step->data << " ";
step = step->prev;
}
}void append_data(int x) {
if (tail == NULL) {
head = tail = new node;
tail->data = x;
tail->prev = NULL;
tail->next = NULL;
} else {
node *new_node = new node;
new_node->data = x;
new_node->next = tail->next;
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}void insert_node(node *p, int d) {
node *new_node = new node;
new_node->data = d;
new_node->next = p->next;
p->next = new_node;
new_node->prev = p;
if (p == tail) tail = new_node;
else { new_node->next->prev = new_node; }
}void del_data(int d) {
node *step = head;
if (step == NULL) return ;
while (step) {
if (step->data == d) {
if (step == head) {
head = head->next;
if (head == NULL) {
tail = NULL;
} else {
head->prev = NULL;
}
delete step;
} else if (step == tail) {
tail = tail->prev;
if (tail == NULL) {
head = NULL;
} else {
tail->next = NULL;
}
delete step;
} else {
step->prev->next = step->next;
step->next->prev = step->prev;
delete step;
}
break;
}
step = step->next;
}
}int main () {
head = tail = NULL;
append_data(1);
append_data(2);
append_data(3);
append_data(4);
print_lst();
cout << endl;
print_lst_re();
cout << endl;
node *step = head;
while (step) {
if (step->data == 3) {
insert_node(step, 5);
step = step->next;
}step = step->next;
}print_lst();
cout << endl;
print_lst_re();
cout << endl;
del_data(4);
print_lst();
cout << endl;
print_lst_re();
cout << endl;
return 0;
}
1.链表的内存不是连续的，不支持随机访问（下标）;
2.链表的查询O(n);
3.插入节点O(1);
4.删除结点O(1);
5.动态扩张;
list<node>list1;定义;
push_back();
list.front();第一个;
list.back();最后一个;
list1.begin();
list.end();
输出
list<node>::iterator it=list1.begin();
while(it != list1.end()){
cout<<it->data1<<" ";
it++;
}
输出
auto it=lt.begin();
auto step=lt.begin();
for(it;it!=lt.end();it++){
cout<<*lt<<" ";
}
删除
while(step!=lt.end){
if(*step==100){
break;
}
step++;（不能+=2）；
}
lt.erase(step);
day 09:
树:非线性结构;
是由n个结点的集合，除根结点外，其他结点分为m个互不相交的集合;
其中每个集合本身又是一棵树，称为根结点的子树;
树的度，结点拥有的子树数量为结点的度，度为0的结点称为叶子结点;
一棵树的度为所有结点中，度最大值;
除根结点外，其余结点都有唯一一个前驱点又称父亲结点;
每个结点可以有多个后继结点，被成为孩子;
另外，结点公用一个父亲结点，则它们互称兄弟结点;
从根结点为第一层，往下每个结点都为一层，树的层数又称深度;
一个n个结点的树，有n-1条边;
结点大于等于0;
二叉树最大的度为二;
每一层最多有2^i-1个结点;
复杂度为O(2^k);
k层最多有2^k-1个结点;
度为0的结点为n0，有两个结点的结点为n2；
n0和n2一定满足，n0=n2+1;
n1+n2+n0=n;
n1+2*n2+1=n;
深度为：log2(n)+1;
左孩子为2i;
右孩子为2i+1;
图：是由顶点和边组成;
自环，一条边的两端连接的是同一个顶点;
重边，顶点之间存在多条边连接;
简单图：不存在自环和重边;
多重图：存在自环的重边;
权值，指边上的值;
度,是指一个顶点连接的边的数量;
有向图，入度，是指指向该顶点的边数;
出度，是指从该顶点出发的边的数量;
环路，是指一路径的起点和终点是同一个顶点，且路径上的顶点可重复;
简单环路：是指路径是的顶点均不重复;
若不包含任何简单环路，可称为无环路;
连通性，若某图中的任意两个顶点都存在路径，则称为连通图;
无向图，至少需要n-1条边组成连通图;
路径：是指从一个顶点到另一个顶点;
简单路径，是指没有重复使用一条边;
重复利用的不是;
无向完全图，任意两条顶点都存在边;
至少n*(n-1)/2条边；
有向完全图，是指任意两个顶点之间都存在方向相反的两条边;
至少n*(n-1)条边;
有帮助，赞一个