參加8.19的鏈家內推筆試，總體來說題目難度不大，20個選擇題還有三道編程題。

選擇題，里面有兩道關于IP地址計算的題目，有點忘了，不知道最后的計算有沒有問題，所以還需要復習學習完的知識，

因為不知道什么時候就會遇到相關的問題。

編程題，自我感覺，難度是偏簡單的，如果不能達到兩道AC，那就是不合格了。

?

1. 給定的一個1,2,3組成的數字序列，排成升序所需的最少交換次數?。

樣例輸入：

9

2

2

1

3

3

3

2

3

1

樣例輸出：
4

?

思路：

應使用貪心算法。

分析：先存入數組，然后記錄有多少個1，多少個2，多少個3，然后記錄應該是1的領地里不是1的個數，記錄2的領地里3的個數，記錄3的領地里2的個數 則我們要做的是把1的領地里非1的元素同后面兩個區域里的1交換， 在1的領地里把2同 2的領地里的1 交換，把3同 3的領地里的1 進行交換 。 完了會出現2和3里面分別有3和2的情況,取2和3里的非自己人的最大數，同1里的為自己人數相加即為需要交換的最小次數。

即ans=x+max（y，z）；

?

總結： 統計在應該是1的位置出現2的個數為a1;

??????????統計在應該是2的位置出現1的個數為a2；

??????????統計應該是1、2的位置出現3的個數為a3；

??????????那么最少交換次數為：a3 + (a1 > a2 ? a1: a2)

代碼如下：

?

#include<iostream> #include<vector> #include<cmath> #include<cstring>using namespace std;int main(){int x=0,y=0,z=0;//分別存放1的位置非1的個數，2的位置3的個數和3的位置2的個數；int n;cin>>n;vector<int> vec;//存放要輸入的序列；int b[3];//用于存放序列中1，2，3的個數各是多少；int num;b[0]=0;//之前用memset初始化，結果存在很大問題。b[1]=0;b[2]=0;for(int i=0;i<n;i++){cin>>num;vec.push_back(num);}for(int i=0;i<n;i++){b[vec[i]-1]++;}for(int i=0;i<b[0];i++){if(vec[i]!=1){x++;}}for(int i=b[0];i<b[0]+b[1];i++){if(vec[i]==3){y++;}}for(int i=b[0]+b[1];i<n;i++){if(vec[i]==2){z++;}}int res=x+max(y,z);cout<<res;system("pause");return 0; }

?

反思：這道題目自己做的時候，思路不對，而且沒有認真去思考當要求交換最少的時候，實際上是為了盡可能一次交換使得兩個數字歸位。

所以，應該嘗試去寫一寫，多試幾個例子。

?

問題：為什么這樣用memset不能清零

#include<stdio.h>
#include<string.h>
int main()
{
???int i,a[100];
???memset(a,0,100);//改memset(a,0,sizeof(a));或memset(a,0,100*sizeof(int));就可以了
???for(i=0;i<100;i++)
?????? printf("%d ",a[i]);
???return 0;

}

解決：memset(a,0,100);//改memset(a,0,sizeof(a));或memset(a,0,100*sizeof(int));就可以了

原因：void *memset(void *s, int ch, unsigned n)函數的作用：將s所指向的某一塊內存中的每個字節（注意這里是每個字節，你可能用字符串習慣了）的內容全部設置為ch指定的ASCII值,memset 工具塊的大小由第三個參數指定,這個函數通常為新申請的內存做初始化工作, 其返回值為指向S的指針。?

原本定義的是整型， 占一個字節? memset(a,0,100*sizeof(int)) 這樣是100個4個字節的內存

?

?

?

2. 類似牛客上原題，獎學金；

小v今年有n門課，每門都有考試，為了拿到獎學金，小v必須讓自己的平均成績至少為avg。每門課由平時成績和考試成績組成，滿分為r。現在他知道每門課的平時成績為a_i?,若想讓這門課的考試成績多拿一分的話，小v要花b_i?的時間復習，不復習的話當然就是0分。同時我們顯然可以發現復習得再多也不會拿到超過滿分的分數。為了拿到獎學金，小v至少要花多少時間復習。
鏈接：https://www.nowcoder.com/questionTerminal/cee98a512ec246a2918ea8121f7612c8 來源：牛客網

?

示例1

輸入

5 10 9
0 5
9 1
8 1
0 1
9 100

輸出

43

?

代碼如下：

?

#include <iostream> #include <vector> #include <algorithm>using namespace std;bool cmp(const pair<int, int>p1,const pair<int, int>p2){return p1.second<p2.second; }int main() {int n,r,avg;while(cin>>n>>r>>avg){vector<pair<int, int> > vec;int a = 0;int b = 0;for(int i=0;i<n;i++){cin>>a>>b;vec.push_back(make_pair(a,b));}long long target = vec.size()*avg;long long score_cur = 0;long long time = 0;for(int i=0; i<vec.size(); ++i){score_cur += vec[i].first;}if(score_cur >= target){cout<<"0"<<endl;}else{sort(vec.begin(),vec.end(),cmp);for(int i=0;i<vec.size();i++){score_cur += (r - vec[i].first);if(score_cur >= target){score_cur -= (r - vec[i].first);time += (target - score_cur)*vec[i].second;cout<<time<<endl;break;}elsetime += (r - vec[i].first)*vec[i].second;}}}return 0; }

反思：對于這道題目的求解思路沒有問題，但是在實現上有問題。對于容器的熟練度不夠，除了vector，set，map等之外，還應該知道pair，熟練使用，這會很方便。

?

3. 應該是最簡單的一道，數組的去重排序，用set容器非常方便；

利用set自帶特性，直接簡要去重的數組依次插入即可。

?

代碼如下：

?

#include <iostream> #include<set> using namespace std; int main(int argc, char *argv[]) {int n;set<int> s;cin >> n;int num;for (int i = 0; i<n; i++){cin >> num;s.insert(num);}//set<int>::iterator it;for (auto it = s.begin(); it != s.end(); it++){if (it == --s.end())cout << *it << endl;elsecout << *it << " ";}system("pause");return 0; }

?

?反思：題目很簡單，但是要熟練迭代器。

?

總結：從這些題目，應該能看出容器的作用了。一定要熟練。

?

2018.8.22

?

?

?

?

?

?

?

?

轉載于:https://www.cnblogs.com/Allen-rg/p/7410872.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的链家秋招内推编程笔试题目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。