一、算法训练首先给大家带来校招程序员考察的核心技能训练:算法,不管你用什么语言,数据结构与算法一定是最核心的基本功。说得实际和功利一点 算法是你进入大厂的敲门砖还能帮你在工作中快速地弯道超车 所以一定得搞懂哦~~~ 另外现在现在大厂的笔试很多采用ACM模式,面试手撕代码则多为力扣模式 (核心代码模式)今天给大家带来中大厂笔试训练1.拓扑顺序这是 2018 年研究生入学考试中给出的一个问题以下哪个选项不是从给定的有向图中获得的拓扑序列现在请你编写一个程序来测试每个选项。输入格式第一行包含两个整数 N 和 M分别表示有向图的点和边的数量。接下来 M 行每行给出一条边的起点和终点。点的编号从 1 到 N。再一行包含一个整数 K表示询问次数。接下来 K 行每行包含一个所有点的排列。一行中的数字用空格隔开。输出格式在一行中输出所有不是拓扑序列的询问序列的编号。询问序列编号从 0 开始。行首和行尾不得有多余空格保证存在至少一个解。数据范围1≤N≤1000,1≤M≤10000,1≤K≤100输入样例6 81 21 35 25 42 32 63 46 451 5 2 3 6 45 1 2 6 3 45 1 2 3 6 45 2 1 6 3 41 2 3 4 5 6输出样例3 4解析:首先了解一下拓扑排序的定义:在图论中拓扑排序Topological Sorting是一个有向无环图DAG, Directed Acyclic Graph的所有顶点的线性序列。且该序列必须满足下面两个条件1.每个顶点出现且只出现一次。2.若存在一条从顶点 A 到顶点 B 的路径那么在序列中顶点 A 出现在顶点 B 的前面。有向无环图DAG才有拓扑排序非DAG图没有拓扑排序一说。1234567891011121314151617181920212223242526272829303132333435363738394041//这题根据条件性质解题即可#includebits/stdc.husingnamespacestd;constintN10050;intnodes[N],a[N],b[N],p[N];intn,m;intmain(){cinnm;inti,j;for(i0;im;i){cina[i]b[i];}intk;cink;boolflag;vectorint v;for(i0;ik;i){flag1;for(j1;jn;j){cinnodes[j];p[nodes[j]]j;}for(j0;jm;j){if(p[a[j]]p[b[j]])flag0;}if(!flag)v.push_back(i);}for(i0;iv.size();i){if(i0) coutv[i];elsecout v[i];}coutendl;}2.功夫传人12345678910111213141516171819202122232425262728293031323334353637383940414243//这题用邻接表存储一下信息,然后再dfs配合回溯即可#includebits/stdc.husingnamespacestd;constintN1e550;vectorint v[N];intn,st[N];doublez,r,sum;voiddfs(intu,doublep){if(st[u]){sump*v[u][0];return;}for(inti0;iv[u].size();i)dfs(v[u][i],p*(1-r/100));}intmain(){cinnzr;inti,x;for(i0;in;i){intk;cink;if(k0){st[i]1;cinx;v[i].push_back(x);}else{while(k--){cinx;v[i].push_back(x);}}}dfs(0,z);cout(int)sum;}3.二叉树中的最低公共祖先树中两个结点 U 和 V 的最低公共祖先LCA是指同时具有 U 和 V 作为后代的最深结点。给定二叉树中的任何两个结点请你找到它们的 LCA。输入格式第一行包含两个整数 M 和 N分别表示询问结点对数以及二叉树中的结点数量。接下来两行每行包含 N 个不同的整数分别表示二叉树的中序和前序遍历。保证二叉树可由给定遍历序列唯一确定。接下来 M 行每行包含两个整数 U 和 V表示一组询问。所有结点权值均在 int 范围内。输出格式对于每对给定的 U 和 V输出一行结果。如果 U 和 V 的 LCA 是 A且 A 不是 U 或 V则输出 LCA of U and V is A.如果 U 和 V 的 LCA 是 A且 A 是 U 或 V 中的一个则输出 X is an ancestor of Y.其中 X 表示 AY 表示另一个结点。如果 U 或 V 没有在二叉树中找到则输出 ERROR: U is not found. 或 ERROR: V is not found. 或 ERROR: U and V are not found.数据范围1≤M≤1000,1≤N≤10000输入样例6 87 2 3 4 6 5 1 85 3 7 2 6 4 8 12 68 17 912 -30 899 99输出样例LCA of 2 and 6 is 3.8 is an ancestor of 1.ERROR: 9 is not found.ERROR: 12 and -3 are not found.ERROR: 0 is not found.ERROR: 99 and 99 are not found.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162//常规方法建树再按题目要求做即可#includebits/stdc.husingnamespacestd;constintN1e450;intm,n;intin[N],pre[N],depth[N],p[N];intbuild(intil,intir,intpl,intpr,intd){introotpre[pl];intkroot;depth[root]d;if(ilk) p[build(il,k-1,pl1,pl1(k-1-il),d1)]root;if(kir) p[build(k1,ir,pl1(k-1-il)1,pr,d1)]root;returnroot;}unordered_mapint,int pos;intmain(){cinmn;inti;for(i0;in;i){cinin[i];pos[in[i]]i;}for(i0;in;i){cinpre[i];pre[i]pos[pre[i]];}inta,b,x,y;build(0,n-1,0,n-1,0);while(m--){cinab;xa,yb;if(pos.count(a)pos.count(b)){apos[a],bpos[b];xa,yb;while(a!b){if(depth[a]depth[b])ap[a];elsebp[b];}if(a!xa!y)printf(LCA of %d and %d is %d.\n,in[x],in[y],in[a]);elseif(ax)printf(%d is an ancestor of %d.\n,in[x],in[y]);elseprintf(%d is an ancestor of %d.\n,in[y],in[x]);}elseif(pos.count(a)0pos.count(b)0)printf(ERROR: %d and %d are not found.\n,x,y);elseif(pos.count(a)0)printf(ERROR: %d is not found.\n,x);elseprintf(ERROR: %d is not found.\n,y);}}二、工程项目训练项目实习对于秋招来说意义重大,一份好的实习可以让招聘方看到你的工作能力Tips:工作能力:工作能力指的是你工作相关的能力是在目标岗位上的专业能力通过实习可以积累你的实战经验也可以向公司表明你在实际工作中的实操能力。但是没有实习也并不代表你秋招无法找到一份好的工作:你可以将在校期间的社团、竞赛等相关在校经历补充在简历上另外如果掌握某种和工作相关的知识或技能也要尽可能写得详细一些一定要表明你是如何把上述这些知识技能运用于工作中的。这样可以表现出你很善于学习新知识的特点给自己加印象分。另外要勤做项目,使自己的项目经历与自己求职的目标岗位相契合,当我们能在简历中通过自己过往的经历证明自己的能力优势并且这个能力优势又是企业需要的那么我们拿到面试机会的可能性就会很大。下面由小学徒给大家带来Qt的项目学习秘籍,希望大家喜欢。day1.Qt(串口的使用)这里必须夸下Qt Creator的帮助(不同于其他IDE帮助需要联网)学习图形界面开发肯定离不开帮助文档的使用因为它不像 C 语言那样就那么几个函数接口(api)图形接口的接口可以用海量来形容但我们只需要记住常用的几个即可,君子性非异也善假于物也。大家要善于借助外物的力量遇到不熟悉的直接去帮助文挡查看用法。我们在日常使用中使用 Qt 帮助文档有几个需要关注的点:1)类使用的相关介绍2)查看部件的信号3)查看部件的事件(其所对应的虚函数如何编写)4)查看所用部件(类)的相应成员函数(功能参数返回值)1)类使用的相关介绍Qt另一个方便之处在于光标移动到类名字的地方接着按“F1”即可跳转到所对应的帮助文件可将光标移到类名字这里,然后按F1即可跳转到所对应的帮助文档。2)查看部件的信号以QplainTextEdit(纯文本输入框)为例我们来看到它的公有函数公有函数:共有成员可以被程序中的任何代码访问等等Summary:Qt上手还是非常的容易自带的帮助文档中的内容非常详细还有示例代码如果想着重学习UI的话:Qt Designer能让你通过以拖动控件放置的方式可视化的设计UI界面当你设计好界面编译完成后在构建目录中会找到文件名形如“ui_XXXX.h”的头文件这是Qt根据你的UI自动帮你生成的C代码内容就是UI的C实现方式大家可以跟着它自动生成的这段代码学来学习UI是怎么实现的这个比自己看文档要来的直观很多。而且对于初学者来说一个可拖拽位置可改变尺寸的有趣窗口要比一个黑框控制台程序要有意思的多。三、总结到此这篇关于C/C后端学习与练习深入的文章就介绍到这了