C/C++后端學(xué)習(xí)與練習(xí)深入
一、算法訓(xùn)練
首先給大家?guī)硇Ｕ谐绦騿T考察的核心技能訓(xùn)練:算法,不管你用什么語言,
數(shù)據(jù)結(jié)構(gòu)與算法一定是最核心的基本功。說得實(shí)際和功利一點(diǎn)， 算法是你進(jìn)入大廠的敲門磚，還能幫你在工作中快速地彎道超車， 所以一定得搞懂哦~~~ 另外現(xiàn)在現(xiàn)在大廠的筆試很多采用ACM模式,面試手撕代碼則多為力扣模式 (核心代碼模式)今天給大家?guī)碇写髲S筆試訓(xùn)練
1.拓?fù)漤樞?/h3>
這是 2018 年研究生入學(xué)考試中給出的一個(gè)問題：
以下哪個(gè)選項(xiàng)不是從給定的有向圖中獲得的拓?fù)湫蛄校?/p>
現(xiàn)在，請(qǐng)你編寫一個(gè)程序來測(cè)試每個(gè)選項(xiàng)。
輸入格式
第一行包含兩個(gè)整數(shù) N 和 M，分別表示有向圖的點(diǎn)和邊的數(shù)量。
接下來 M 行，每行給出一條邊的起點(diǎn)和終點(diǎn)。
點(diǎn)的編號(hào)從 1 到 N。
再一行包含一個(gè)整數(shù) K，表示詢問次數(shù)。
接下來 K 行，每行包含一個(gè)所有點(diǎn)的排列。
一行中的數(shù)字用空格隔開。
輸出格式
在一行中輸出所有不是拓?fù)湫蛄械脑儐栃蛄械木幪?hào)。
詢問序列編號(hào)從 0 開始。
行首和行尾不得有多余空格，保證存在至少一個(gè)解。
數(shù)據(jù)范圍
1≤N≤1000,
1≤M≤10000,
1≤K≤100
輸入樣例：
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6
輸出樣例：
3 4
解析:首先了解一下拓?fù)渑判虻亩x:在圖論中，拓?fù)渑判颍═opological Sorting）是一個(gè)有向無環(huán)圖（DAG, Directed Acyclic Graph）的所有頂點(diǎn)的線性序列。且該序列必須滿足下面兩個(gè)條件：
1.每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次。
2.若存在一條從頂點(diǎn) A 到頂點(diǎn) B 的路徑，那么在序列中頂點(diǎn) A 出現(xiàn)在頂點(diǎn) B 的前面。
有向無環(huán)圖（DAG）才有拓?fù)渑判?，非DAG圖沒有拓?fù)渑判蛞徽f。
//這題根據(jù)條件性質(zhì)解題即可
#include<bits/stdc++.h>
using namespace std;
const int N=10050;
int nodes[N],a[N],b[N],p[N];
int n,m;
int main()
{
cin>>n>>m;
int i,j;
for(i=0;i<m;i++)
{
cin>>a[i]>>b[i];
}
int k;
cin>>k;
bool flag;
vector<int> v;
for(i=0;i<k;i++)
{
flag=1;
for(j=1;j<=n;j++)
{
cin>>nodes[j];
p[nodes[j]]=j;
}
for(j=0;j<m;j++)
{
if(p[a[j]]>p[b[j]])
flag=0;
}
if(!flag)
v.push_back(i);
}
for(i=0;i<v.size();i++)
{
if(i==0) cout<<v[i];
else cout<<" "<<v[i];
}
cout<<endl;
}2.功夫傳人
//這題用鄰接表存儲(chǔ)一下信息,然后再dfs配合回溯即可
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
vector<int> v[N];
int n,st[N];
double z,r,sum;
void dfs(int u,double p)
{
if(st[u])
{
sum+=p*v[u][0];
return;
}
for(int i=0;i<v[u].size();i++)
dfs(v[u][i],p*(1-r/100));
}
int main()
{
cin>>n>>z>>r;
int i,x;
for(i=0;i<n;i++)
{
int k;
cin>>k;
if(k==0)
{
st[i]=1;
cin>>x;
v[i].push_back(x);
}
else
{
while(k--)
{
cin>>x;
v[i].push_back(x);
}
}
}
dfs(0,z);
cout<<(int)sum;
}
3.二叉樹中的最低公共祖先
樹中兩個(gè)結(jié)點(diǎn) U 和 V 的最低公共祖先（LCA）是指同時(shí)具有 U 和 V 作為后代的最深結(jié)點(diǎn)。
給定二叉樹中的任何兩個(gè)結(jié)點(diǎn)，請(qǐng)你找到它們的 LCA。
輸入格式
第一行包含兩個(gè)整數(shù) M 和 N，分別表示詢問結(jié)點(diǎn)對(duì)數(shù)以及二叉樹中的結(jié)點(diǎn)數(shù)量。
接下來兩行，每行包含 N 個(gè)不同的整數(shù)，分別表示二叉樹的中序和前序遍歷。
保證二叉樹可由給定遍歷序列唯一確定。
接下來 M 行，每行包含兩個(gè)整數(shù) U 和 V，表示一組詢問。
所有結(jié)點(diǎn)權(quán)值均在 int 范圍內(nèi)。
輸出格式
對(duì)于每對(duì)給定的 U 和 V，輸出一行結(jié)果。
如果 U 和 V 的 LCA 是 A，且 A 不是 U 或 V，則輸出 LCA of U and V is A.
如果 U 和 V 的 LCA 是 A，且 A 是 U 或 V 中的一個(gè)，則輸出 X is an ancestor of Y.其中 X 表示 A，Y 表示另一個(gè)結(jié)點(diǎn)。
如果 U 或 V 沒有在二叉樹中找到，則輸出 ERROR: U is not found. 或 ERROR: V is not found. 或 ERROR: U and V are not found.
數(shù)據(jù)范圍
1≤M≤1000,
1≤N≤10000
輸入樣例：
6 8
7 2 3 4 6 5 1 8
5 3 7 2 6 4 8 1
2 6
8 1
7 9
12 -3
0 8
99 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.
//常規(guī)方法建樹再按題目要求做即可
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+50;
int m,n;
int in[N],pre[N],depth[N],p[N];
int build(int il,int ir,int pl,int pr,int d)
{
int root=pre[pl];
int k=root;
depth[root]=d;
if(il<k) p[build(il,k-1,pl+1,pl+1+(k-1-il),d+1)]=root;
if(k<ir) p[build(k+1,ir,pl+1+(k-1-il)+1,pr,d+1)]=root;
return root;
}
unordered_map<int,int> pos;
int main()
{
cin>>m>>n;
int i;
for(i=0;i<n;i++)
{
cin>>in[i];
pos[in[i]]=i;
}
for(i=0;i<n;i++)
{
cin>>pre[i];
pre[i]=pos[pre[i]];
}
int a,b,x,y;
build(0,n-1,0,n-1,0);
while(m--)
{
cin>>a>>b;
x=a,y=b;
if(pos.count(a)&&pos.count(b))
{
a=pos[a],b=pos[b];
x=a,y=b;
while(a!=b)
{
if(depth[a]>depth[b])
a=p[a];
else
b=p[b];
}
if(a!=x&&a!=y)
printf("LCA of %d and %d is %d.\n",in[x],in[y],in[a]);
else if(a==x)
printf("%d is an ancestor of %d.\n",in[x],in[y]);
else
printf("%d is an ancestor of %d.\n",in[y],in[x]);
}
else if(pos.count(a)==0&&pos.count(b)==0)
printf("ERROR: %d and %d are not found.\n",x,y);
else if(pos.count(a)==0)
printf("ERROR: %d is not found.\n",x);
else
printf("ERROR: %d is not found.\n",y);
}
}二、工程項(xiàng)目訓(xùn)練
項(xiàng)目&實(shí)習(xí)對(duì)于秋招來說意義重大,一份好的實(shí)習(xí)可以讓招聘方看到你的工作能力：
Tips:工作能力:工作能力指的是你工作相關(guān)的能力，是在目標(biāo)崗位上的專業(yè)能力，通過實(shí)習(xí)可以積累你的實(shí)戰(zhàn)經(jīng)驗(yàn)，也可以向公司表明你在實(shí)際工作中的實(shí)操能力。
但是沒有實(shí)習(xí)也并不代表你秋招無法找到一份好的工作:
你可以將在校期間的社團(tuán)、競(jìng)賽等相關(guān)在校經(jīng)歷補(bǔ)充在簡(jiǎn)歷上；另外如果掌握某種和工作相關(guān)的知識(shí)或技能，也要盡可能寫得詳細(xì)一些，一定要表明你是如何把上述這些知識(shí)技能運(yùn)用于工作中的。這樣可以表現(xiàn)出你很善于學(xué)習(xí)新知識(shí)的特點(diǎn)，給自己加印象分。另外要勤做項(xiàng)目,使自己的項(xiàng)目經(jīng)歷與自己求職的目標(biāo)崗位相契合,當(dāng)我們能在簡(jiǎn)歷中通過自己過往的經(jīng)歷證明自己的能力優(yōu)勢(shì)，并且這個(gè)能力優(yōu)勢(shì)又是企業(yè)需要的，那么我們拿到面試機(jī)會(huì)的可能性就會(huì)很大。
下面由小學(xué)徒給大家?guī)鞶t的項(xiàng)目學(xué)習(xí)秘籍,希望大家喜歡。
day1.Qt(串口的使用)
這里必須夸下Qt Creator的幫助(不同于其他IDE幫助需要聯(lián)網(wǎng))
學(xué)習(xí)圖形界面開發(fā)，肯定離不開幫助文檔的使用，因?yàn)樗幌?C 語言那樣就那么幾個(gè)函數(shù)接口(api)，圖形接口的接口可以用海量來形容，但我們只需要記住常用的幾個(gè)即可,君子性非異也，善假于物也。
大家要善于借助外物的力量，遇到不熟悉的直接去幫助文擋查看用法。
我們?cè)谌粘Ｊ褂弥惺褂?Qt 幫助文檔，有幾個(gè)需要關(guān)注的點(diǎn):
1)類使用的相關(guān)介紹
2)查看部件的信號(hào)
3)查看部件的事件(其所對(duì)應(yīng)的虛函數(shù)如何編寫)
4)查看所用部件(類)的相應(yīng)成員函數(shù)(功能，參數(shù)，返回值)
1)類使用的相關(guān)介紹
Qt另一個(gè)方便之處在于光標(biāo)移動(dòng)到類名字的地方，接著按“F1”即可跳轉(zhuǎn)到所對(duì)應(yīng)的幫助文件：
可將光標(biāo)移到類名字這里,然后按F1即可跳轉(zhuǎn)到所對(duì)應(yīng)的幫助文檔。
2)查看部件的信號(hào)
以QplainTextEdit(純文本輸入框)為例我們來看到它的公有函數(shù)
公有函數(shù):共有成員可以被程序中的任何代碼訪問等等
Summary:Qt上手還是非常的容易，自帶的幫助文檔中的內(nèi)容非常詳細(xì)，還有示例代碼，如果想著重學(xué)習(xí)UI的話:Qt Designer能讓你通過以拖動(dòng)控件放置的方式，可視化的設(shè)計(jì)UI界面，當(dāng)你設(shè)計(jì)好界面編譯完成后，在構(gòu)建目錄中會(huì)找到文件名形如“ui_XXXX.h”的頭文件，這是Qt根據(jù)你的UI，自動(dòng)幫你生成的C++代碼，內(nèi)容就是UI的C++實(shí)現(xiàn)方式，大家可以跟著它自動(dòng)生成的這段代碼學(xué)來學(xué)習(xí)UI是怎么實(shí)現(xiàn)的，這個(gè)比自己看文檔要來的直觀很多。而且對(duì)于初學(xué)者來說一個(gè)可拖拽位置可改變尺寸的有趣窗口要比一個(gè)黑框控制臺(tái)程序要有意思的多。
三、總結(jié)
到此這篇關(guān)于C/C++后端學(xué)習(xí)與練習(xí)深入的文章就介紹到這了,更多相關(guān)C++后端內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)拼圖小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要介紹了C++ 虛函數(shù) virtual的相關(guān)資料,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-03-03
本文主要介紹了如何使用C語言實(shí)現(xiàn)一個(gè)通訊錄。實(shí)現(xiàn)通訊錄的過程中，會(huì)大量用到C語言的知識(shí)點(diǎn)，包括但不限于：函數(shù)、自定義類型、指針、動(dòng)態(tài)內(nèi)存管理、文件操作，感興趣的可以了解一下2023-05-05
今天小編就為大家分享一篇關(guān)于C語言程序打豆豆(函數(shù)版)，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-02-02
利用C++和QT實(shí)現(xiàn)Log自定義日志系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了如何利用C++和QT實(shí)現(xiàn)Log自定義日志系統(tǒng),文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,有需要的小伙伴可以參考下2023-12-12
這篇文章主要介紹了C++中簡(jiǎn)單使用HP-Socket，HP-Socket 是一套通用的高性能 TCP/UDP /HTTP 通信 框架 ，包含服務(wù)端組件、客戶端組件和 Agent 組件，廣泛適用于各種不同應(yīng)用場(chǎng)景的 TCP/UDP /HTTP 通信系統(tǒng)，下面來看看更具體的介紹吧2021-11-11
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)車牌定位，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
這篇文章主要介紹了C語言memset函數(shù)使用方法詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家掌握這樣的方法，需要的朋友可以參考下2017-10-10
C語言編程簡(jiǎn)單卻重要的數(shù)據(jù)結(jié)構(gòu)順序表全面講解
這篇文章主要為大家介紹了C語言編程中非常簡(jiǎn)單卻又非常重要的數(shù)據(jù)結(jié)構(gòu)順序表的全面講解，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-10-10
Crypto++ (CryptoPP) 是一個(gè)用于密碼學(xué)和加密的C++庫(kù),它是一個(gè)開源項(xiàng)目,提供了大量的密碼學(xué)算法和功能,本文小編給大家介紹了C++通過CryptoPP計(jì)算Hash值的過程,文中通過代碼示例給大家介紹的非常詳細(xì),需要的朋友可以參考下2023-11-11