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效率高五、如何选择六、容器选择原则七、效率对比

测试理论面试题

软件测试面试题整理

软件测试工程师跳槽：收到面试电话后，我会做的事。