笔试

笔试时间：2022年8月19日

1 下一个较大元素（leetcode503 变型）

不是找i索引后面第一个比它大的元素，而是找i索引后面比它大的最大元素

2 正则表达式匹配（leetcode10 原题）

3 计算最大利润

计算送外卖的最大利润。每一单需要一个单位时间，每一单都有一个截止时间，如果在截止时间及之前送这一单，就可以获取其利润。计算最大可能获取利润

输入：

可工作的时间

N行，每行为 截止时间 本单利润

输出：

最大利润

输入样例1：

3
2 10
1 7
1 3

输出样例1：

17

解释：在时间1完成1 7这一单，在时间2完成2 10这一单，总利润17

输入样例2：

4
3 5
3 10
1 7
1 3

输出样例2：

22

解释：在时间1完成1 7这一单，在时间2完成3 5这一单，在时间3完成3 10这一单，总利润22

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;


int main()  // 最大外卖利润
{
    int totalTime;
    cin >> totalTime;
    map<int, vector<int>, greater<int>> profitMap;
    int deadTime;
    int profit;
    while (cin >> deadTime >> profit)
    {
        if (deadTime > totalTime)
            continue;

        if (profitMap.count(deadTime) == 0)
            profitMap[deadTime] = vector<int>();
        profitMap[deadTime].push_back(profit);
    }

    int maxProfit = 0;
    for (int index = totalTime; index >= 1; index--)
    {
        if (profitMap.empty())  // 如果没有订单可做了
            break;

        int currentDeadTime = profitMap.begin()->first;
        if (currentDeadTime < index)
            continue;

        vector<int> currentV = vector<int>(profitMap.begin()->second);  // 注意要拷贝赋值
        sort(currentV.begin(), currentV.end(), greater<int>());
        maxProfit += currentV[0];
        profitMap.erase(profitMap.begin());
        currentV.erase(currentV.begin());
        if (!currentV.empty())  // 如果本时间点还有剩余订单，则融入到前一个时间点中
        {
            if (profitMap.count(index - 1) == 0)  // 如果没有前一个时间点，则自创一个
                profitMap[index - 1] = currentV;
            else
            {
                vector<int>& nextV = profitMap.begin()->second;
                nextV.insert(nextV.end(), currentV.begin(), currentV.end());
            }
        }
    }

    cout << maxProfit << endl;
}

4 Protobuf编码与解码

输入样例1：

100
0XE70X07

输出样例1：

0X64
999

一面

1 C#中堆和栈的区别

2 什么时候会执行GC

3 C#的委托是什么

4 数组和链表的区别

5 中心点和锚点的区别

6 链表如何判环？如何找入口节点？

7 有公共部分的两个链表有可能有哪些形状？各种情况如何判断是否相交？

8 长度为N-1的有序数组，数值范围为1-N，如何找到缺失的那一个元素？如果是无序数组呢？

9 现场共享屏幕，手撕第8题的有序情况（二分）

二面

0 自我介绍

1 为什么转到计算机方向？怎么学习的？（问的很细，看什么书，怎么学的）

2 vector的底层实现？vector是哪两个属性记录容量和数量？vector的resize和reserve的区别？

3 红黑树？查找、插入操作的时间复杂度？长什么样？怎么建立的？

4 指针占多大内存？存储在哪里？

5 哈希冲突如何解决？

6 共享屏幕手撕剑指 Offer II 026. 重排链表（要求空间复杂度为O(1)，自己创建结点的结构，相当于acm模式）

7 判断两个单向链表是否有共同节点（只需要返回bool值即可）

注意分有环无环情况讨论

三面

1 C#垃圾回收时，如果某个对象已经被回收了，后续却又需要调用它，会发生什么问题？如何解决这个问题？你会如何设计垃圾回收机制来解决这个问题？三代标记增量清除算法的时间复杂度是多少？如何计算这个复杂度？

2 红黑树和哈希表进行查找时的时间复杂度？为什么红黑树是logN而不是根号N？哈希表O(1)就一定比红黑树快么，时间是恒定的么？如果我想用长度1亿的字符串作为key存在哈希表中会怎么样？存到红黑树中呢？红黑树和哈希表的空间复杂度相关问题？一个项目需求给你，要怎么判断要用红黑树还是哈希表（并不知道元素是否会经常发生哈希冲突）？红黑树的迭代器是怎么实现的？你会如何设计这个迭代器？

3 嘴撕算法：无重叠区间（leetcode435）

————

后续：已寄