4399c++遊戲開發2023屆實習筆試

十個選擇題

tcp三次握手狀态轉換
光追蹤算法用到光反射還是投射
類對象占記憶體多少https://blog.csdn.net/m0_46663240/article/details/125367595?spm=1001.2014.3001.5502
字元串數組https://blog.csdn.net/m0_46663240/article/details/125368629?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22125368629%22%2C%22source%22%3A%22m0_46663240%22%7D&ctrtid=udrHO

1.tcp三次握手

tcp協定處理後的資料會加上tcp頭部，這個頭部是20多位的數字，不同段不同含義

發送方端口号+接收方端口号+序号（seq發送方告訴接收方現在發送的是總發送位元組的第幾個)+ACK号（确認，接收方告訴發送方已經接收到了哪些位元組）+ 資料偏移量 + 保留 + 控制位（常見的SYN和FIN就屬于這個，還有URG、ACK、PSH、RST總共6位）+視窗 + 校驗和 + 緊急指針 + 可選字段

seq 序列号

syn 表示現在是在溝通建立連接配接

ack是确認收到，ack = seq+1是表示和誰建立聯系

1.syn = 1,seq = x，x是随機的，防止被人利用搞破壞

2.syn = 1,ack = x + 1, seq = y

3.ack = y + 1

fin 表示現在在溝通斷開連接配接

seq

ack

1.fin = 1,seq = x

2.fin = 1,ack = x + 1,seq = y

3.fin = 1,ack = x + 1,seq = z

4.fin = 1,ack = z + 1,seq = h

4399c++遊戲開發2023屆實習筆試

3個程式設計題

柱狀圖中最大的矩形

暴力逾時版本：但思想比較清晰，就是對于每一個柱子，都有一個以該柱子長為寬，以它最長底邊為底所構造的矩形，求出每一個然後求面積最大即可。

4399c++遊戲開發2023屆實習筆試

兩個for循環就是找邊界，在哪個範圍可以用它做寬，就是在其他柱子都不比它矮的情況下可以

左邊有個邊界，右邊有個邊界，求出內插補點乘以他高度就可以了

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if(n == 1)return heights[0];
        vector<int>left(n);
        vector<int>right(n);
        left[0] = 0;
        right[n-1] = n-1; 
        for(int i = 1; i < n; i++){
            left[i] = i;//左右都比它小的情況如圖中6
            //找左邊第一個比它小的，然後加1的下标就是它能延申的最大邊界
            for(int j = i; j >= 0; j--){
                if(heights[j] >= heights[i]){
                    left[i] = j;
                }else{
                    left[i] = j + 1;
                    break;
                }
            }
        }
        for(int i = n-2; i >= 0; i--){
            right[i] = i;
            for(int j = i; j < n; j++){
                if(heights[j] >= heights[i]){
                    right[i] = j;
                }else{
                    right[i] = j - 1;
                    break;
                }
            }
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            res = max(res,heights[i] * (right[i] - left[i] + 1));
        }
        return res;
    }
};

單調棧解法

如何保證目前高度被出棧的這些高度不會之後的柱子不會被用到呢？

如 1 2 3 4 5 2

先維護一個棧1 2 3 4 5

在2的高度下，棧會變成1 2

如何保證出棧的2 3 4 5 之後來的元素不會用到呢？

比如

1 2 3 4 5 2 3

來的比2大，那2會擋住，不需要前面的，這個可以了解

如果來的比2小，不如現在是

1 2 3 4 5 2 1

這時候2 比 1 打，那大于2的肯定比1更大，是以在2的情況下出棧的，1的情況下也會出棧

想清楚簡單

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if(n == 1)return heights[0];
        vector<int>left(n);
        vector<int>right(n);
        stack<int>sta;
        for(int i = 0; i < n; i++){
            while(!sta.empty() && heights[i] <= heights[sta.top()]){
                sta.pop();
            }
            sta.empty() ? left[i] = -1 : left[i] = sta.top();
            sta.push(i);
        }
        sta = stack<int>();
        for(int i = n - 1; i >= 0; i--){
            while(!sta.empty() && heights[i] <= heights[sta.top()]){
                sta.pop();
            }
            sta.empty() ? right[i] = n : right[i] = sta.top();
            sta.push(i);
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            res = max(res,heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
};

6.24溫故而知新

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int>sta;
        vector<int>left(n);
        for(int i = 0; i < n; i++){
            while(!sta.empty() && heights[i] <= heights[sta.top()]){
                sta.pop();
            }
            left[i] = (sta.empty()? -1 : sta.top());
            sta.push(i);
        }
        sta = stack<int>();
        vector<int>right(n);
        for(int i = n-1; i >= 0; i--){
            while(!sta.empty() && heights[i] <=  heights[sta.top()]){
                sta.pop();
            }
            right[i] = (sta.empty()? n : sta.top());
            sta.push(i);
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            res = max((right[i]-left[i]-1) * heights[i],res);
        }
        return res;
    }
};

主要是把一個點忘了，就是棧裡面存的是下标，是以for循環的時候不能和棧元素大小比，應該和棧元素做下标時的高度作比較

4399c++遊戲開發2023屆實習筆試

7月2日溫故而知新

這次問題出在用pushback添加了，應該是直接指派的

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int>sta;
        int n = heights.size();
        vector<int>left(n);
        for(int i = 0; i < n; i++){
            while(!sta.empty() && heights[i] <= heights[sta.top()]){
                sta.pop();
            }
            if(sta.empty()){
                left[i] = -1;
            }else{
                left[i] = sta.top();
            }
            sta.push(i);
        }
        sta = stack<int>();
        vector<int>right(n);
        for(int i = n-1; i >= 0; i--){
            while(!sta.empty() && heights[i] <= heights[sta.top()]){
                sta.pop();
            }
            if(sta.empty()){
                right[i] = n;
            }else{
                right[i] = sta.top();
            }
            sta.push(i);
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            res = max(res,(right[i]-left[i]-1)*heights[i]);
        }
        return res;
    }
};

字元串中存在重複元素

但是好像時間複雜度。。。：

4399c++遊戲開發2023屆實習筆試

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        map<int,int>map;
        for(int i = 0; i < n; i++){
            if(map.find(nums[i]) == map.end()){
                map[nums[i]] = i;
            }else{
                if(i - map[nums[i]] <= k){
                    return true;
                }else{
                    map[nums[i]] = i;
                }
            }
        }
        return false;
    }
};

滑動視窗解

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> s;
        int length = nums.size();
        for (int i = 0; i < length; i++) {
            if (i > k) {
                s.erase(nums[i - k - 1]);
            }
            if (s.count(nums[i])) {
                return true;
            }
            s.emplace(nums[i]);
        }
        return false;
    }
};

會議室

非常牛逼，代碼太優雅了，不想改

大概思路就是：

轉化成上下車的問題，然後算車上最多多少人

輸入：intervals = [[0,30],[5,10],[15,20]]

輸出：2

以這個輸入為例

0 對應 +1

30 對應 -1

5 對應 +1

10對應-1

15對應+1

20對應-1

轉換成：

0 5 10 15 20 30

1 1 -1 1 -1 -1

求出他們和的最大值

1

1+1

1+1-1

1+1-1+1

1+1-1+1-1

1+1-1+1-1-1

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
 
        if (intervals.size() == 0) return 0;

        vector<pair<int, int>> meetings;
        for (const vector<int>& interval : intervals) {
            meetings.push_back({interval[0], 1});
            meetings.push_back({interval[1], -1});
        }
        sort(meetings.begin(), meetings.end());

        int cnt = 0, maxValue = 0;
        for (const pair<int, int>& meeting : meetings) {
            cnt += meeting.second;
            maxValue = max(maxValue, cnt);
        }
        return maxValue;
        
    }
};

作者：muluo-2
連結：https://leetcode.cn/problems/meeting-rooms-ii/solution/tu-jie-zhuan-hua-wei-shang-xia-che-wen-t-uy2q/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

6.24做的.不夠優雅

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<map<int,int>>v;
        int m = intervals.size();
        int n = intervals[0].size();
        for(int i = 0; i < m; i++){
            map<int,int>map1;
            map1[intervals[i][0]] = 1;
            v.push_back(map1);
            map<int,int>map2;
            map2[intervals[i][1]] = -1;
            v.push_back(map2);
        }
        sort(v.begin(),v.end());
        int res = 0,sum = 0;
        for(int i = 0; i < 2*m; i++){          
            auto it = v[i].begin();
            sum += it->second;
            res = max(res,sum);
        }
        return res;
    }
};

pair,7.2回顧

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int m = intervals.size();
        int n = intervals[0].size();
        vector<pair<int, int>> meetings;
        for (const vector<int>& interval : intervals) {
            meetings.push_back({interval[0], 1});
            meetings.push_back({interval[1], -1});
        }
        sort(meetings.begin(),meetings.end());
        int res = 0;int count = 0;
        for(int i = 0; i < 2*m; i++){
            count += meetings[i].second;
            res = max(res,count);
        }
        return res;
    }
};

vector<pair<int, int>> meetings;

比map友善，主要是少了疊代器這個操作

四個問答題

1.成就感

完成了三次半馬，堅持鍛煉了一年多時間，從三公裡到五公裡，從五公裡到十公裡，第一次半馬在雨裡跑完的，非常舒爽！

2.最失敗的一件事情

沒有特别失敗的事情，就感覺每件事情都有它的意義，我是那種享受過程的人，要說比較遺憾的話就是走了挺多彎路的。

2.發展性格因素

3.溝通上司

4399c++遊戲開發2023屆實習筆試

十個選擇題

3個程式設計題

單調棧解法

pair,7.2回顧

四個問答題

繼續閱讀

2021年銀行從業考試考情介紹,果斷收藏!

證券從業合格證書什麼時候列印？有哪些注意事項？

【幹貨滿滿】初級銀行從業考試《個人理财》重點梳理

2020年經濟師考試，難嗎？

初級銀行從業資格證有什麼用？

MBA提前面試純幹貨分享

MBA值得學麼

30歲以上的程式員何去何從。。。

IT牛們的bat面試心得與經驗總結

新鮮傳媒CEO紀中展：經濟危機對年輕人是機會新鮮傳媒CEO紀中展：經濟危機對年輕人是機會紀中展：加入創業團隊初期不要考慮名利紀中展：創業者骨子裡要有霸氣紀中展：創業是颠覆過去的過程

Java經典面試題詳解：帶你手撸紅黑樹總結

python面試題之Python 的特點和優點是什麼

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

測試理論面試題

軟體測試面試題整理

軟體測試工程師跳槽：收到面試電話後，我會做的事。