C/C++後端學習與練習深入

2022-07-22 22:02:28

一、演演算法訓練

首先給大家帶來校招程式設計師考察的核心技能訓練:演演算法,不管你用什麼語言,

資料結構與演演算法一定是最核心的基本功。說得實際和功利一點，演演算法是你進入大廠的敲門磚，還能幫你在工作中快速地彎道超車，所以一定得搞懂哦~~~ 另外現在現在大廠的筆試很多采用ACM模式,面試手撕程式碼則多為力扣模式 (核心程式碼模式)今天給大家帶來中大廠筆試訓練

1.拓撲順序

這是 2018 年研究生入學考試中給出的一個問題：

以下哪個選項不是從給定的有向圖中獲得的拓撲序列？

現在，請你編寫一個程式來測試每個選項。
輸入格式
第一行包含兩個整數 N 和 M，分別表示有向圖的點和邊的數量。

接下來 M 行，每行給出一條邊的起點和終點。

點的編號從 1 到 N。

再一行包含一個整數 K，表示詢問次數。

接下來 K 行，每行包含一個所有點的排列。

一行中的數位用空格隔開。

輸出格式
在一行中輸出所有不是拓撲序列的詢問序列的編號。

詢問序列編號從 0 開始。

行首和行尾不得有多餘空格，保證存在至少一個解。

資料範圍
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

解析:首先了解一下拓撲排序的定義:在圖論中，拓撲排序（Topological Sorting）是一個有向無環圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列。且該序列必須滿足下面兩個條件：

1.每個頂點出現且只出現一次。

2.若存在一條從頂點 A 到頂點 B 的路徑，那麼在序列中頂點 A 出現在頂點 B 的前面。

有向無環圖（DAG）才有拓撲排序，非DAG圖沒有拓撲排序一說。

//這題根據條件性質解題即可
#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.功夫傳人

//這題用鄰接表儲存一下資訊,然後再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.二元樹中的最低公共祖先

樹中兩個結點 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 表示 A，Y 表示另一個結點。

如果 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 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.

//常規方法建樹再按題目要求做即可
#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);
   }
}

二、工程專案訓練

專案&實習對於秋招來說意義重大,一份好的實習可以讓招聘方看到你的工作能力：

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++後端學習與練習深入的文章就介紹到這了,更多相關C++後端內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！