4399c++游戏开发2023届实习笔试_4399秋招笔试游戏开发选择题

十个选择题

1. tcp三次握手状态转换
2. 光追踪算法用到光反射还是投射
3. 类对象占内存多少https://blog.csdn.net/m0_46663240/article/details/125367595?spm=1001.2014.3001.5502
4. 字符串数组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

3个编程题

7. 柱状图中最大的矩形

暴力超时版本：但思想比较清晰，就是对于每一个柱子，都有一个以该柱子长为宽，以它最长底边为底所构造的矩形，求出每一个然后求面积最大即可。

两个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
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

单调栈解法

如何保证当前高度被出栈的这些高度不会之后的柱子不会被用到呢？
如 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

主要是把一个点忘了，就是栈里面存的是下标，所以for循环的时候不能和栈元素大小比，应该和栈元素做下标时的高度作比较

while(!sta.empty() && heights[i] <= heights[sta.top()]){

1
2

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

9. 字符串中存在重复元素
   但是好像时间复杂度。。。：
   

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

滑动窗口解

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

11. 会议室
    非常牛逼，代码太优雅了，不想改
    大概思路就是：
    转化成上下车的问题，然后算车上最多多少人
    输入：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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

**

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

vector<pair<int, int>> meetings;
比map方便，主要是少了迭代器这个操作

四个问答题

1.成就感
完成了三次半马，坚持锻炼了一年多时间，从三公里到五公里，从五公里到十公里，第一次半马在雨里跑完的，非常舒爽！
2.最失败的一件事情
没有特别失败的事情，就感觉每件事情都有它的意义，我是那种享受过程的人，要说比较遗憾的话就是走了挺多弯路的。
2.发展性格因素

3.沟通上司