2021.3.23 富途牛牛筆試

大學期間第一次筆試

19:00開始的場，當天給我發了三四個消息，有牛客發來的也有富途發來的，牛客的叫我登入網頁登入考試，我登入牛客找了半天沒找到入口，加了什麼hr解答公衆号也沒有通過，本來都想算了，19:10幾又給我發個資訊，我就想：再去加個牛客的公衆号試試得了，結果終于綁定了牛客賬号之後才找到考試入口…

然後是在牛客上的筆試，需要開攝像頭，網頁錄屏，手機監控等，一開始不知道是在牛客筆試，在宿舍考的，有點吵。

20道單選題，2道程式設計題

選擇題

提出點我記得的部分：

機率論（簡單的像高中數學）：4個不同球放在4個不同箱子。他題目并沒有給出需要每個箱子都放滿，那應該是 4 4 4^4 44，結果沒有這個答案，那就隻能是 4 ! 4! 4! 了…就很迷

16進制與運算： i = 0 x F E 78 D A 45 ， j = 0 x A C 3189 B 2 i=0xFE78DA45，j=0xAC3189B2 i=0xFE78DA45，j=0xAC3189B2，求 i i i^ j j j ，我一開始以為是 i j i^j ij的，不會，看了一眼答案，就标記之後看下一題，全部寫完之後回來看才發現是 i i i^ j j j 。

二分查找：給一個數組，一個數字，問你二分查找這個數字的比較次數。這個不多說，比較 e z ez ez

好多道計網和資料庫的題我不會…

程式設計題

一、給一個連結清單跟一個值，讓你把這個連結清單裡小于這個值的都放在連結清單左邊，等于這個值的都放在中間，大于這個值的都放在連結清單右邊。

思路一開始就想到了快排的思路，但是md以前寫題都幾乎沒用過結構體連結清單，這下子總算吃了虧。

struct ListNode{
	int val;
	ListNode *next;
} //結構體連結清單
           

就這樣的連結清單，我隻知道指向性跟指派，不知道怎麼建立節點等，而且我想的是head指向的下一個值才是第一個數…結果他竟然head的值是第一個數，我最後幾分鐘才發現。

是以最後走了個小技巧，就是把連結清單中所有的值都整到vector裡，然後再通過vector來調序，最後再指派回連結清單裡。

ListNode *tmp=head;
ListNode *ans=head;
vector<int>v;
while(tmp!=NULL) {
	v.emplace_back(tmp->val);
	tmp=tmp->next;
}
int l=0,r=v.size()-1;
while(l<r) {
	while(l<r&&v[l]<=piovt) l++;
	while(l<r&&v[r]>=pivot) r--;
	if(l<r) swap(v[l],v[r]);
}
int q=0;
while(ans!=NULL) {
	ans->val=v[q++];
	ans=ans->next;
}
           

我是這樣寫的。樣例能過，但是隻有70%通過率。現在還是沒整明白為什麼。1e6 按理來說不可能逾時才對。

二、給一個n，表示01字元串的大小，問長度為n的01字元串中，有多少個01字元串所有’0’的左邊必定有個’1’ 。

這題目也是沒有說明白到底是左邊一位有’1’才行，還是左邊多少位有’1’都行。看了樣例之後才明白是左邊一位。然後随便寫了幾個

1->1，2->2，3->3，4->5，5->8

猜了個斐波那契，結果秒了。

總結：連結清單還是得練練。。否則像今天這樣就很悲催。