北邮考研复试机试准备过程(已上岸)

纯自用请勿转载,用来给自己最后复习和捋思路用的,主要参考牛客网+王道机试指南,C、C++混用。考研人太久不写代码了…什么都不记得了,从头开始过一遍吧。
黑色代码段是要记住的重点函数/方法。每天下午做几个小时,一共不到一周完成。
C++

#include<algorithm>
#include<stack>
#include<queue>
#include<string.h>
using namespace std;
cin>>m//输入
cout<<n//输出
//听说cin、cout效率低会超时,后面没用

C

//常用库
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
scanf("%d",&m);//输入
printf("%d",m);//输出

一、牛客网北邮真题

先拿往年真题找找手感

1.KY187 二进制数

任务:int类型数转二进制数
思路: 函数内部递归、按位与n&1、>>右移
r=n&1; //r取n的二进制的最末位,[按位与]还可以用于判断奇偶性
n>>1;//n右移一位,例如1011变成101再变成10

2.KY198 找最小数

任务:输入n对数,找最小对
思路:很简单,每行边输入边比较,最后得到最小对
注意:cin>>x>>y中间有“ ”空格会报错,不知道为什么,但是输出的时候可以cout<<x0<<" "<<y0;

3.KY199 查找

//太简单了。。注意事项就是当数据量较大时,如果想要降低复杂度,则可以先对数组进行排序。对于小数据量直接用嵌套循环就能完成。

4.KY188 哈夫曼树

任务:哈夫曼树,输入数量n,以及n个权值,求得所有结点的值与权值的乘积之和的最小值
思路:所求值=所有非叶节点之和。所以先排序,按照构建哈夫曼树的方法,边自底向上构造,边计算sum值。每轮将两个结点结合之后再将整个数组重新排序,再次循环计算,直到将n-1个非叶节点(叶结点一共n个)全部累加完毕为止
排序可以用以下库函数qsort

int cmp(const void* a,const void* b){return *(int*)b-*(int*)a;
}
qsort(num,n,sizeof(num[0]),cmp);
5.KY190 查找第k小数

任务:每组输入n,然后输入n个整数(1<=n<=1000),再输入k,查找第k小的数(相同视为一样大)
思路:
第一种:输入过程做是否存在相同数的判断,相同大小不重复储存,使存数据的数组内都是不一样大小的数据。然后对数组内数据排序。最后找出第k个即可(没试过,用快排会很快!看到大佬有1ms的)

第二种:(我自己用的,傻瓜算法)直接设一个大小1000的数组,初始化全为0.接着输入循环,输入的整数为i,则将a[i]设置为1。最后找到数组中第k个为1的所在的位置m(用k–,判断到k=0跳出),输出m即可。感觉就是舍弃空间换时间的算法。

6.KY194 树查找

任务:每组输入一个n(1<=n<=1000),然后将树中的这n个节点依次输入,再输入一个d代表深度。输出该树中第d层得所有节点。
思路:对于完全二叉树而言,总结点数是2^depth-1,
对应第d层的节点个数为2^(d-1),就可以用一种很暴力的算法,先推总depth,再输出从d-1层到第d层的数。

#include <math.h>//求幂次的时候用到math库里面的pow函数,double类型可强制转换
pow(x,y);//求x的y次幂
7.KY223 二叉排序树

任务:建立二叉排序树,然后分别前序中序后序遍历
思路:难题。要写的代码很多。步骤1:如何建立二叉排序树?步骤2:三种遍历的实现
参考了王道的写法。。待补充,主体如下:
1结构体,create函数,insert函数,前中后序遍历函数
用到指针、初始化结点

8.KY191矩阵幂

任务:求n*n矩阵的k次幂
思路:简单题。就三个矩阵,一个是初始矩阵,一个是中间用来计算的矩阵,一个是最终矩阵。在求幂次的过程中不能把矩阵弄混了,否则会计算结果出错。
要不就用结构体,再用函数调用;
要不就直接写,因为结构体实现有一点麻烦。
注意:容易忽略k=1的情况导致边缘用例不通过!

二、王道机试指南(2013)

跟着王道系统学习

第二章经典入门

2-1排序*(重要!)

例2.1

法1:手写冒泡排序:
(1)当已经不再发生交换的时候就说明排序完成,用一个flag来监视。
(2)注意溢出,在内部循环中,比如可能j<n-1
法2:快排:可以直接用c++库函数!!

include <algorithm>
using namespace std;

比如你希望buf升序输出,用快排库函数

sort(buf,buf+n);//起始地址,结束地址

若希望降序输出,则

bool cmp(int x,int y){
return x>y;
}
sort(buf,buf+n,cmp);//第二种重载方式,+比较函数
例2.2

任务:按照学生的成绩从低到高排序,相同则按照姓名和年纪
思路:还是用sort,只是sort的对象的类型从int数组变成了Student数组,只需要在cmp中去具体定义每两个传进去的Student对象怎么比较就可以了
注意:

include <string.h> //1.为了用char数组要引入

比较两个名字(字符串)的名字字典序的方法,很重要!

int tmp = strcmp(x.name, y.name);
//两个字符串自左向右逐个字符相比(按ASCII值大小相比较)
if (tmp != 0) return tmp < 0;//结果:s1<=>s2对应tmp-0+

2-2 日期类

2.3日期差值

重点1:这类日期区间问题——把原区间问题统一到起点确定的区间问题上,相当于所有日期都与一个特定的原点日期去比较,再计算差值即可
重点2:闰年2月只有29天。闰年定义:【年数】无法被100整除,但是可以被4整除 或 能被400整除

#define ISYEAP(x) x%100!=0&&x%4==0||x%400==0?1:0
//定义宏判断是否是闰年

思路:(1)提前用二维数组存好一年中各月份的天数(普通年份,闰年)(2)创建日期类,定义计算函数(3)将进来的日期都与原点进行比较

例2.4求几天周几(复杂)

同上,取标准日期作比较,略复杂

2-3 Hash

例2.5 求某一分数的学生人数

很简单的题。。。
方法一:逐个与key比较,count++
方法二:由于分数有范围0~100,所以可以直接设置一个分数数组,在对应位置每次有一个学生就+1,最后输出对应key位置的值就是人数

例2.6 大n排序

当就算用nlog级别的算法排序时复杂度已经超过了千万级,说明不能再用排序算法了!!
解法:所以同上,用hash来统计每个数字是否出现1/0,然后找前m大仅需从后向前遍历,最多仅是百万级别复杂度

#define OFFSET 500000 //宏定义一个常量用来补偿数组下标偏移

2-4 排版题

例2.7 输出梯形

简单题,搞清楚规律就行

例2.8叠筐

对于这种跟输出习惯不一样的题,先将我们要输出的数据,按照希望输出的顺序存放在一个已经提前初始化好的二位数组(代替矩阵)中——计算对应的坐标所需要放置的字符是哪一个。
最后直接用二维数组按序输出实现即可

2-5 查找

例2.9 找x

方法一:遍历查找。直接用key跟数组中一一对比即可,没技术含量
方法二:二分查找。时间复杂度更低(在牛客网?还是leetcode做过,可以去看一下)

例2.10 查找学生信息

难点1:又是时间复杂度题!!
每次遍历查询数组则是O(n*m)的时间复杂度,达到了千万数量级,所以不能用了
难点2:序号是01,02…所以用字符串输入,在后面比较也要用字符串比较函数
解法:用二分查找,从中间开始比较key,每轮查找条件是【base<=top】

int tmp = strcmp(buf[mid], x);
//两个字符串自左向右逐个字符相比(按ASCII值大小相比较)
//结果:中间序号<=>要求序号 对应 tmp= -0+

2-6 贪心算法

每次总选择当前最优,但不会从整体把握。有时能得到最优解。

例2.11 FatMouse’ Trade

要求用给定的钱买到重量最重的物品总数
思路:(1)设置物品结构体goods,变量:重量、价值、性价比。(2)计算每个物体性价比,对性价比降序排序(3)购买各个物品,跳出条件为【物品有剩余&&钱>0】,先尝试是否能全部买下该物品,不能时就把money花完然后结束

例2.12 今年暑假不AC(思路很重要)

任务:根据电视节目的开始和结束时间,选出能看到最多完整电视节目数量的一个看电视策略
思路:贪心策略:每轮看完当前节目之后,选择【还未开始&&结束时间最早】的节目
(1)创建program结构体(2)按照结束时间升序排列所有节目[用sort+cmp](3)记录初始当前时间时间=0,每次看完节目将【当前时间=该节目结束时间】
贪心的思路:开始最早?持续最短?结束最早?可以找一些反例。。。

第三章 数据结构

3-1 栈的应用

引入模板库中的栈,使用方法如下

#include<stack>
stack<int> S;//保存数据类型为int的栈S
S.push(i); //压栈
int x=S.top();//取顶部元素
S.pop();//弹出栈顶元素
例3.1括号匹配

从左到右遍历字符串,用压栈+栈顶元素来判断是否有不可匹配的括号

for(int i=0;str[i]!=0;i++) // 判断字符串结束:ascii=0;遍历字符串的语法
if (s[i]=='(') {}//注意!是单引号哦,否则会报错

思路:(1)用了两个字符串来分别存储输入输出信息,在遇到不匹配括号的同时存入错误信息,这样一次遍历就能完成任务(2)栈是int类型,存数组下标,最后对没匹配完的左括号统一修改输出内容
!注意:当一个栈的栈顶没有信息时,调用取栈顶s.top()会报错,可以预存一个空格/先判断是否为空

if (s.empty()==false)//堆栈非空
例3.2 简单计算器(复杂)

经典利用堆栈对表达式求值题
思路:(1)两个(int和double)堆栈,分别存运算符和数字(2)需要一个比较函数,参数为两个运算符,返回两个运算符的优先级大小比较结果(3)运算符栈顶部人为存一个标记运算符,用来判断表达式运算是否结束
可以写

if(str[]>='0' && str[i]<='9')//表示当前字符为数字

将字符串转换为数字

for(;str[i]!=' ' && str[i]!=0;i++){retn*=10;retn+= str[i]-'0';//这里计算的是二者ASCII码的差值!!
}

判断输入只有一个0的语句

if (str[0]=='0' && str[1]==0) break;

每轮循环开始前还要清空栈——判断栈是否空

3-2 哈夫曼树*

目标:计算最小带权路径长度和:所有中间结点/非叶子节点的权值和
方法:用堆->优先队列(标准模板库)

#include<queue>
priority_queue<int> Q;//默认为大顶堆
priority_queue<int,vector<int>,greater<int>> 	Q;//小顶堆

用栈、队列等必须做:(1)操作前判断空+清空(2)判断堆中元素数量>1

while(Q.size()>1)

思路:每次累加完两个最小元素的和之后,要把该中间节点的值作为新的元素压回优先队列中,直到堆只剩一个根元素

3-3 二叉树*

必须要记住的怎么写:
1.结构体
2.初始化节点

BiNode Tree[N];
BiNode *Create_BST(){Tree[loc].lchild=Tree[loc].rchild=NULL;//初始化一个节点return &Tree[loc++];
}

二叉排序树的建树方法

BiNode *Insert(BiNode *T,int x){//传进来树的地址,返回一个地址if(T==NULL){T=Create_BST();//建立节点T->data=x;return T;}else if(x<T->data){T->lchild=Insert(T->lchild, x);}else if(x>T->data){T->rchild=Insert(T->rchild, x);}return T;
}
//在排序二叉树中插入节点的算法

3.遍历(递归)

void preOrder(BiNode *T){printf("%d ",T->data);if(T->lchild!=NULL){preOrder(T->lchild);}if(T->rchild!=NULL){preOrder(T->rchild);}
}//前序遍历
3.4二叉树遍历(没做)

任务:通过给出的前序、中序遍历,还原二叉树,输出后序遍历
方法:(1)用字符串保存前序、中序遍历结果。(2)用前序遍历的第一个字符作为根节点,申请空间,并找该根节点字符在中序遍历中的位置(3)对左右子树递归,先左后右

Node *build(int s1, int e1,int s2,int e2) { //由字符串的前序遍历和中序遍历还原树,并返回其根节点,其中前序遍历结果为由str1[s1]到str2[e1],中序遍历结果为str2[s2]到str2[e2]

3-4 二叉排序树*

3.5 二叉排序树

与牛客网重复

3.6 二叉搜索树

任务:判断两棵二叉树是否相同
方法:对每两棵树进行包括中序遍历在内的两种遍历,当结果相同时,就可以判断两棵树相同

第四章 数学问题

4-1 %运算符(没什么可看的)

4-2 数位拆解

例4.2 特殊乘法

两个数字都是亿级别以上的数字,求各位相乘之和。题不难,两种解法,感觉我选的那个更简单
方法一:对x做数位拆解,利用/和%,循环,分别将各位的数字拆分出来,再计算结果
方法二(我自己开始用的):将两个数字作为字符串读入,然后对他们每个字符遍历计算与’0’的ASCII码差值得到各位并求解

4-3 进制转换*

学习m到十进制和十进制到n进制的转换
10->2:对x%2再x/2…直到x%2的结果为0为止,每次x%2得到的都是从最低位开始的各位数字
m->10:就参考二进制就行

例4.2 又一版A+B

求十进制的m进制数,用ans数组来存放各位数字,可以用一个【size++】来对个数计数

for (int i = 0;( (k %m)!= 0)||((k/m)!=0); i++) {ans[i] = k % m;//求模k = k/m;//除以m}

!注意:因为a,b两个数字是最大在int范围内,而两个数字之和可能会超过int所能表示的最大值,导致溢出。所以选用long long数据类型,输出转义字符为%lld

例4.3 数制转换

思路:a进制转10进制,10进制转b进制
难点:如何区别和计算输入进来的数字/大写字母/小写字母??

int lenth=strlen(str)//可以求字符串长度,跟数组的n一样的
if(str[i]>='0'&&str[i]<='9'){x=str[i]-'0';//计算0~9之间的数字
}else if(str[i]>='a'&&str[i]<='z'){x=str[i]-'a'+10;//计算小写字母
}else{x=str[i]-'A'+10//计算大写字母
}

4-4 最大公约数GCD

求同时满足a%c=0,b%c=0的最大整数c
方法:用欧几里得算法:
当a、b全为0——最大公约数不存在
当a或b=0——最大公约数为非零的那个
a、b都不为0——令a=b,b=a%b,重复该过程(可以递归,return(b,a%b)即可))

4-5 最小公倍数LCM

求同时满足c%a=0,c%b=0的最大整数c
方法:最小公倍数=(a*b)除以他们的最大公约数

4-6 素数筛法

例4.6素数判定

测试一个数是不是素数:O(sqrt(n))
方法:对每个输入的值依次测试(1,其平方根] 的数字能否整除他即可。
利用sqrt开根函数

int bound = (int)sqrt(x)+1;//计算枚举上界,为防止double值带来的精度损失,所以采用根号值取整后再加1(多枚举一个)

依次枚举从2-bound的数能否整除x

if (x%i==0) return false;//只要有一个能则必不为素数
例4.7素数

找某范围内的所有素数
方法:每找到一个素数,即将它的所有倍数均标记为非素数。当遍历到一个数未被标记过,则确定他为素数,并继续标记它的所有倍数。

for(int j=i*i;j<=10000;j+=i){
mark[j]=true;
}//标记倍数的方法,注意j初始值和循环操作,减少时间复杂度,优化程序

最后未被标记过的所有数为素数

4-7 分解素因数

例4.8质因数的个数

求某个正整数n的所有质因数的个数(包括重复的)=求所有素因数的幂指数之和
方法:(1)提前找到在n的最大范围内的所有素数,存下来(2)对每个n,遍历所有素数,找出n的因数(3)通过/除确定每个因数的幂指数(4)累加幂指数

例4.9整除问题(很难…)

给定n,a,范围[2,1000],求最大的k,使n! 可以被a^k 整除``但不能被a^(k+1)整除
难点:n!和a^k可能数值很大,甚至连longlong都无法保存,因此不能直接用求余数来算
方法:分别对n!和a分解素因数,看n!的素因数中各数的幂指数,再对比a中相同素因数的幂指数,对应相除就可得到每个素因数的商,商最小值就是k

4-8 二分求幂(没看懂啊,有空再看吧,先用pow)

例4.10人见人爱A^B

求A^B∈[1,10000]的最后三位表示的整数
思路:不能直接算再求后三位,因为实在太大了。分解a^b变为``【若干个 a的2^k次的积】,

4-9 高精度整数(不太重要)

不能用任何数据类型的高精度整数,只能自己创建结构体来解答题目,把输入当做字符串进行保存。。。

第五章 图论

5-1基础知识

两种方法表示图:
(1)邻接矩阵:用二维数组来保存,edga[i][j],1表示存在边,0表示无边。还能用来保存权值(带权图),此时若不存在边则用特殊字符如-1来表示。
适合稠密图、频繁地判断某特定节点对是否相邻
(2)邻接链表:适合存在大量遍历邻接节点的操作,而较少判断两个特定结点之间的关系时
推荐用STL库中的标准模板std::vector

#include<vector>
struct Edge{int nextNode;//邻接下一个结点的编号int cost;//该边权重
};

创建一个数组,保存的是vector对象,edge[i]表示为结点i建立的单链表

vector<Edge> edge[N];

相关操作(背*):clear,pushback,size,erase

for(int i=0;i<N;i++){edge[i].clear(); //清空所有结点的单链表
}//初始化
Edge tmp;
tmp.nextNode=3;tmp.cost=38;
edge[1].pushback(tmp);
//把边tmp加入到结点1的单链表中
for(int i=0;i<edge[2].size();i++){int nextNode=edge[2][i].nextNode;//2号结点的第i条边所对应的邻接结点int cost=edge[2][i].cost;//读出权值
}
edge[1].erase(edge[1].begin()+i, edge[1].begin()+j+1);
//i是第一个要删除的元素编号,j是最后一个要删除元素的编号

5-2并查集

·路径压缩:查找某点的根节点时使在某点和根节点之间的所有结点都指向根节点。优化了后续查找工作。

int findRoot(int x){if(Tree[x]==-1) returnx;else{int tmp=findRoot(Tree[x]);Tree[x]=tmp;//将当前节点x的双亲结点设置成最后返回的根节点编号tmpreturn tmp;}
}
例5.1 畅通工程

任务:给出几条路径,令所有路径上的结点对之间都直接或间接相连
思路:每个结点开始都是孤立的连通变量,每次读入一条建成的边,就将边的两条顶点所在的集合合并,最后看有多少个集合就可以知道有多少个连通分量。road=set-1(根节点个数-1)

a=findRoot(a);
b=findRoot(b);
if(a!=b){Tree[a]=b;}
//两个顶点不在一个集合,则合并这两个集合

!注意:对于提前定义的全局变量/数组,一定要记得如果是多组输入的话,在每一轮的时候开头要将会用来判断的变量都初始化/复原成最开始的样子!!!!

例5.2 More is better

任务:同上,但最后要输出最大的集合的节点个数
方法:还是用findRoot,新增一个各集合的计数变量,在合并两点所在集合的同时在本集合的计数变量上加上对方的集合内的个数。最后判断哪个集合最大则输出哪个的节点数量

5-3最小生成树MST*(Kruskal算法)

·生成树:包含所有结点的、不存在回路的连通子图
·最小生成树:所有生成树中边权值和最小的
·常见问题(例):在基站间修光缆来使所有基站间可以通信,最少需要多长的光缆

例5.3还是畅通工程

任务:令所有城市连通且道路总长度最小
思路:(1)建立边结构体,包括:两点的编号、该边的权值(2)录入所有边,对它们从小到大排序(3)并查集,对权值从小到大的每一条边上的一对结点用findRoot,如果两节点不在同一集合,则合并两个集合,并累加该边的权值(4)输出结果

例5.4 Freckles

任务:求各点之间能连接的总长度最小
思路:一样求最小生成树,唯一的差别是边的权值不是直接给的,所以要先构建计算各点间距离,然后同上解题即可
提示:开根号sqrt(x),用double

5-4 最短路径*

找两个特定结点间的最短路径。
1.Floyd算法:
求每对顶点之间的最短路径(全源最短路)
步骤:(1)用邻接矩阵edge[i][j](二维数组),初始存i到j直达的距离。(2)考虑可以经过的结点增加了编号为1的结点,则比较edge[i][1]+edge[1][j]和edge[i][j]的大小,若前者小则更新edge[i][j]。循环增加结点至N
2.Dijstra算法
求从一特定起点出发到其他所有点的最短路径(单源最短路)
步骤:(1)从一个结点1出发,比较所有1的相邻结点的路径长度,选出距离最短的结点加入集合K(2)遍历所有与集合K中的元素U相邻的非集合K结点V,按照U的最短路径d,找到到下一个距离U最近的V,并把V加入K,设置它的最短距离为d+d(uv).(3)若集合K中已经包含了所有的点,算法结束,否则重复2
用vector模拟邻接链表

例5.5最短路

任务:求从点1到点N的最短路径
·方法1:用Floyd算法
步骤:(1)对邻接矩阵初始化,-1表示无穷,自己到自己为0(2)将所有路的信息赋值,要注意是无向图赋值。

ans[a][b]=ans[b][a]=c

(3)从1到N不断添加允许经过的中间结点编号,遍历所有ans[i][j]

if(ans[i][j]==-1||ans[i][k]+ans[k][j]<ans[i][j]){ans[i][j]=ans[i][k]+ans[k][j];//经过k可以获得更短的路径

(4)循环结束后输出ans[1][n]

方法2:用Dijstra算法
步骤:
(1)创建链表元素结构体、邻接链表(vector)

struct E{
int next;//相邻结点
int c;//边的权值
};
vector<E> edge[101];//邻接链表

(2)初始化邻接链表

for(int i=1;i<=n;i++) edge[i].clear

录入各边,双向都要录入

scanf("%d%d%d",&a,&b,&c);
E tmp;
tmp.c=c;
tmp.next=b;
edge[a].push_back(tmp);//从a到b方向的边加入邻接链表
tmp.next=a;
edge[b].push_back(tmp);//从b到a方向的边加入邻接链表

(3)一个数组mark标记各结点是否在集合K中,一个数组dis标记到每个节点的最短路径长度。初始化距离为-1,属于为false。
(4)从起始节点1开始,距离为0,属于k为ture。不断遍历与【新加入集合结点】直接相邻的边

for(int j=0;j<edge[newP].size();j++){//遍历newP的边int t=edge[newP][j].next;int c=edge[newP][j].c;if(Dis[t]==-1||Dis[t]>Dis[newP]+c)//若该点不可达,或可以更新该点最短到达距离Dis[t]=Dis[newP]+c;
}

(5)遍历所有节点,找到【还不在K内&&可达&&由1至它距离最小】的那个点,使它成为最新的newP,并加入K
(6)最后从dis数组中输出需要的最短路径

例5.6最短路径问题(没写,没时间了)

5-5 拓扑排序*

第六章 搜索

6-1枚举

6-2广度优先搜索BFS*

例6.2胜利大逃亡(较难,建议看看没时间不用复现)

任务:在三维坐标中,找到一条从原点到(A-1,B-1,C-1)的最短合法路径。
思路:从原点出发,对解答树进行遍历,每次状态转移时拓展出尽可能多的新状态。
剪枝——限制拓展,对于重复出现的点,不需再次重复拓展,则所需遍历的状态总数变为ABC
方法:结构体+队列实现,存储状态对象

struct N{
int x,y,z;
int t;
}
queue<N> Q;//存放状态

在Q中还有元素的情况下,得到队头状态

N now=Q.front();

接着判断该状态的相邻6结点,【在立方体内&&不是墙&&未得到过】的变成新的状态,耗时=now.t+1,标记并push入队列
最后当搜索结束(走到终点),返回耗时

6-3递归

6-4递归应用

6-5深度优先搜索DFS*

第七章 动态规划

7-1递归求解

一共有多少种方式呢?

例7.1 N阶楼上楼问题

代码不难,思路很重要——递推
思路:n>2时,只考虑每次上台阶的最后一步怎么走——即从n-1阶经走一步走到n阶,或者从n-2阶经走两步到n阶。这样最后一步都是确定的,所以可知到达n阶的总上楼方式为F[n]=F[n-1]+F[n-2]

例7.2 不容易系列之一

比较难这道题,求给n个人装信,全部都装错信封的概率。此处用的是错排公式:F[n]=(n-1)*F[n-1]+(n-1)*F[n-2].核心思想也是递推,分成两类状态,均与上一级相关,但是不好描述,建议看书上解释。

7-2最长递增子序列LIS

若在子序列中,当下标X>y,ax>ay,我们称这个子序列为原序列的一个递增子序列(子序列不是子串,不需要必须连续)
最长递增子序列的递推公式

例7.3 拦截导弹

任务:求最长不增子序列
思路:将以每个导弹结尾的最长不增子序列长度都计算出来(即F[i]全部算出来),存在一数组内。最后找出最大的F[i]输出
计算:两层循环。第一层是遍历顺序到达的每个导弹i,第二层遍历是导弹i之前的所有不比它小的导弹的F[j],找到一个最大值,+1存入F[i]

7-3最长公共子序列LCS*

在这里插入图片描述
可以看出,最长公共子串也是依靠递推的方法

例7.4 Coincidence

感觉王道的题目有点问题(不知道是不是我的问题),参考别的地方看来的解法:
(1)把两个字符串分别以行和列组成一个二维矩阵(2)两层循环,比较每个行列字符是否相等,相等为1,否则为0
(3)可以边判断,边存储每一个位置的最长公共子串长度,即

dp[i][j]=1+record[i-1][j-1]

(4)查找出值为1的最长对角线,即为最长公共子串

7-4状态与状态转移方程

7-5动态规划问题

7-6背包

01背包:通过求解子问题推导大问题
在这里插入图片描述

三、Practice

PTA平台、牛客网上的练习,练手

1.PAT (Basic Level) Practice

1025.反转链表

写了半天,挺难的,要分情况讨论,核心思想就是反转链表。
要注意的是:
(1)如果数据中有类似00100,00020的数,后面需要输出,要注意把它存为字符数组,否则int类型会自动去掉前面的0
(2)字符串的比较、赋值函数

strcmp(x,y);//按位比较ASCII码。x<y,返回-1;
strcpy(x,y);//字符串赋值

(3)指针p,如果是结构体类型,要用p->data,不能用p.data

2.牛客网

(1)求二叉树深度

int maxDepth(TreeNode* root) {if(!root) return 0;int lDepth = maxDepth(root->left);int rDepth = maxDepth(root->right);return 1+(lDepth>rDepth?lDepth:rDepth);//很常用,要记住哦}

最后一夜看了一些牛客网的题目。。没有记录了,方向供参考:
建树,算叶子结点,算深度
栈的匹配(符号匹配)
字符串(子串主串去重,匹配子串)
广度遍历
还有平时不常用的数据结构再复习一下,比如栈、优先队列、vector。。。

更新:最近好像很多同学在准备复试,补充一个小知识点,去年考一道题要求结果输出2位小数,C如果float类型输出格式应该就是%.2f,n位小数同理哈。这种简单的但是复习很容易漏掉的基础知识不要忘了看

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/50285.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【计算机考研】复试常见问题

操作系统 操作系统的特点&#xff1f; – 共享&#xff1a;资源可被多个并发执行的进程使用 – 并发&#xff1a;可以在同一时间间隔处理多个进程&#xff0c;需要硬件支持 – 虚拟&#xff1a;将物理实体映射成为多个虚拟设备 – 异步&#xff1a;进程执行走走停停&#xff0c…

会话存档-如何高性能存储海量聊天记录

场景 每天大约500w条数据&#xff0c;存档消息&#xff0c;并对消息进行统计分析。 大概计算一下&#xff1a; 每天的工作时间是8小时&#xff0c;大约是8小时处理400w条数据就足够了&#xff0c;为避免某时刻的峰值超负荷&#xff0c;还按照8小时处理500w条数据的标准来搭建…

开通会话存档查看聊天记录需要准备什么?

会话存档是腾讯企业微信推出的一项付费增值功能&#xff0c;开通会话存档之后企业可以通过会话存档API接口获取员工的聊天记录&#xff0c;可以获取到员工与员工之间的聊天记录、员工与客户的聊天记录&#xff0c;员工所在群的聊天记录&#xff0c;企业可以通过企小码会话存档存…

一个网站查遍所有英文文章 “会议地点及出版商”(亲测搜了80篇全部有效)

说明&#xff1a;本人用下面方法进行会议文章——会议地点及出版商 ——的搜索&#xff0c;连搜80篇文章没有任何问题&#xff01; 前提使用学校网络&#xff0c;可能有的学校没有买会议的权限 第一步&#xff1a;点击所有版本 打开谷歌学术镜像网站&#xff0c;不用翻墙的那…

全国跨境电商联合运营服务平台,定义跨境新力量!

近年来&#xff0c;我国跨境电商行业不断发展&#xff0c;预计2021年跨境电商进出口交易规模有望达到14.3万亿元&#xff0c;疫情催化的市场需求、不断扩大的市场规模、频繁释放利好的政府政策&#xff0c;让跨境的风愈吹愈旺&#xff0c;面对波谲云诡的市场环境&#xff0c;如…

跨境电商卖家,如何运营Facebook?

随着跨境电商的兴起&#xff0c;越来越多的卖家开始运营Facebook&#xff0c;以吸引更多的潜在客户和提高品牌知名度。那么&#xff0c;作为跨境电商卖家&#xff0c;我们可以在Facebook上做些什么呢&#xff1f; 首先&#xff0c;我们可以通过Facebook建立一个专业的品牌页面&…

新手运营适合哪个跨境电商平台

很多企业的网站被收录却没有排名&#xff0c;关键词优化不上去&#xff0c;网站也没有什么流量&#xff0c;不断更新文章&#xff0c;即使是原创&#xff0c;也排不上去&#xff0c;这究竟是由于哪些原因造成的呢&#xff1f;米贸搜作为专业的SEO平台&#xff0c;整理了以下几种…

跨境电商运营做什么的?跨境电商运营怎么样?

图片来源&#xff1a;123rf.com.cn 随着国内电商的逐渐饱和&#xff0c;越来越多的人涌入了跨境电商领域&#xff0c;那么作为一个跨境电商运营工作&#xff0c;每天是做什么工作呢&#xff1f;今天就主要为大家分析跨境电商运营做什么的&#xff1f;跨境电商运营怎么样&#x…

使用Foxmail登录阿里企业邮箱(钉钉邮箱)

pop服务器和SMTP服务器地址分别是&#xff1a;pop.qiye.aliyun.com smtp.qiye.aliyun.com 可以到邮箱里查&#xff1a; 开源项目&#xff1a; https://github.com/xutongbao/learn-chatgpt

第一批因 AI 失业的人已经出现!有公司直接裁掉一半人

点关注公众号&#xff0c;回复“1024”获取2TB学习资源&#xff01; 当大家还在讨论ChatGPT未来将如何发展的时候&#xff0c;第一批因AI失业的人已经出现了。 据媒体报道&#xff0c;已经有一众游戏公司迅速拥抱技术变革&#xff0c;将AI绘画引进工作流程&#xff0c;用以摆脱…

ChatGPT:AI不取代程序员,只取代的不掌握AI的程序员

作者&#xff1a;成都兰亭集势信息技术有限公司技术总监张雄 可能大家会有如下的问题&#xff0c;我就使用chatGPT这个AI工具的API来问一下。 问&#xff1a;chatGPT会替换掉程序员吗&#xff1f;如果能&#xff0c;预计好久&#xff1f; 答&#xff1a;作为一名 AI 语言模型&a…

我看世界杯——来自一个“假”球迷视角

世界杯还有一个星期就要结束了&#xff0c;说实话&#xff0c;我之前是一场球都没有&#xff0c;对足球知道也甚少&#xff0c;妥妥一个假球迷了。这次世界杯感觉离自己特别近&#xff0c;身边的很多朋友都在看&#xff0c;也不乏赌球的小伙伴&#xff0c;自己的感悟也比较深&a…

2022卡塔尔世界杯互动游戏|运营策略

2022世界杯将于11月20日-12月18日在卡塔尔举办&#xff0c;四年一度的全球最大狂欢节开启! 足球是世界上最受欢迎和追捧的竞技体育项目&#xff0c;超越了国界、性别、种族和年龄&#xff0c;是世界上最早的一项体育项目。但作为展现世界最高足球水平的世界杯&#xff0c;在足球…

【黄啊码】如何用小程序实现世界杯参赛队伍投票

本次只分享小程序端的代码实现&#xff0c;后端每个人都有自己的实现方法&#xff0c;就不写在此。 好了&#xff0c;先看实现样式&#xff1a; 本次投票实现需要一个页面和一个弹窗实现&#xff0c;我们做的是淘汰赛部分&#xff0c;在此&#xff0c;黄啊码将淘汰赛部分直接选…

华人AI女神:从洗碗工到谷歌首席科学家,她是如何逆袭的?

来源 | 北美留学生观察 ID | collegedaily “如果获得诺贝尔奖&#xff0c;我希望是以中国人的身份去领奖。” 提到人工智能&#xff0c;我们首先想到前段时间大火的ChatGPT&#xff0c;其实早在2009年&#xff0c;一位华裔女孩已经钻研起了人工智能&#xff0c;而当时在当时…

大模型时代的“Linux”生态,开启人工智能新十年

演讲 | 林咏华 智源人工智能研究院副院长 整理 | 何苗 出品 | CSDN&#xff08;ID&#xff1a;CSDNnews&#xff09; 2018 年以来&#xff0c;超大规模预训练模型的出现推动了 AI 科研范式从面向特定应用场景、训练专有模型&#xff0c;转变为大模型微调模型服务的AI工业化…

巴比特 | 元宇宙每日必读:关闭寄售市场,承诺的“元宇宙”不见踪迹,数字藏品平台iBox被指涉嫌诈骗,多地警方已立案...

摘要&#xff1a;据澎湃新闻报道&#xff0c;4月12日&#xff0c;多名iBox用户向澎湃质量观投诉平台反映&#xff0c;他们在海南链盒科技旗下iBox平台购买数字藏品时被诈骗。针对多名用户报案称被链盒科技诈骗&#xff0c;4月13日&#xff0c;海南省澄迈县公安局正式受理该案。…

外国小哥用 ChatGPT 完成 80% 工作,同时打 4 份工,笑疯。。

点击上方“Java基基”&#xff0c;选择“设为星标” 做积极的人&#xff0c;而不是积极废人&#xff01; 每天 14:00 更新文章&#xff0c;每天掉亿点点头发... 源码精品专栏 原创 | Java 2021 超神之路&#xff0c;很肝~中文详细注释的开源项目RPC 框架 Dubbo 源码解析网络应…

【设计欣赏】新颖包装设计欣赏

本组是16组设计新颖的包装设计&#xff0c;各具特色&#xff0c;请欣赏。

怎样设计食品包装袋,才能够吸引用户?-东莞吉祥包装

一般咱们去购买食物的时候&#xff0c;首要映入咱们眼帘的是食物的外包装袋子&#xff0c;因而一款食物能不能够卖的好&#xff0c;有很大的一部分原因取决于食物包装袋的好坏&#xff0c;有些产品即便自身的颜色可能不是那么的招引人&#xff0c;可是经过各种办法加以渲染&…