牛客后端开发面试题2

微软2021

1、给你一个凸多边形，你怎么用一条线，把它分成面积相等的两部分

将凸多边形的任意一个顶点作为顶点，然后连接另外两个相邻的顶点，将凸多边形划分成多个三角形。 计算每个三角形的面积，并且累加面积，得到凸多边形的总面积。 使用二分查找找到一个位置，使得分割线左边的面积为总面积的一半。 最后的分割线即为所求。

2、判断两个单链表是否有交叉

????????该函数实现结果：如果有交叉则返回第一个交叉结点，如果没有返回nullptr

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2)
    {
        ListNode *p1=pHead1,*p2=pHead2;
        while(p1!=p2)
        {
            p1=p1==nullptr?pHead2:p1->next;
            p2=p2==nullptr?pHead1:p2->next;
        }
        return p1;
    }

3、怎么判断两棵二叉树是否是同构的

两个树的先中后序遍历结果一样则同构.

两个树要么一模一样，要么互为镜像

参考牛客题目BM31?对称的二叉树

?

bool isIsomorphic(TreeNode p, TreeNode q)
{
    if (p == nullptr && q == nullptr)
    {
        return true;
    }
    if (p == nullptr || q == nullptr)
    {
        return false;
    }
    if (p->val != q->val)
    {
        return false;
    }
    return (isIsomorphic(p->left, q->left) && isIsomorphic(p->right, q->right)) || (isIsomorphic(p->left, q->right) && isIsomorphic(p->right, q->left)) || (isIsomorphic(p->right, q->left) && isIsomorphic(p->left, q->right));
}

4、按层次打印一个二叉树

vector<vector<int> > levelOrder(TreeNode* root) {
        //因为队列是先进先出
        vector<vector<int>> res;
        if(!root) return res;
        queue<TreeNode*> qu;
        qu.push(root);
        while(!qu.empty())
        {
            vector<int> vec;
            int size=qu.size();
            while(size--)
            {
                TreeNode* cur=qu.front();
                qu.pop();
                vec.push_back(cur->val);
                if(cur->left)  qu.push(cur->left);
                if(cur->right) qu.push(cur->right);
            }
            res.push_back(vec);
        }
        return res;
    }

5、给你一个数n（最大为10000），怎么求其阶乘

int Num(int n)
{
	if (n == 0 || n == 1) return 1;
    int num=n;
	for (int i = 1; i < n; i++)
	{
		num *= i;
	}
	return num;
}

? ? ? ?对于较大的数，计算阶乘时使用传统的循环乘法效率很低，可以使用数学方法来求解。 一种常用的方法是斯特林公式（Stirling's approximation），公式如下： n! ≈ √(2πn) * (n/e)^n 其中e是自然对数的底数，π是圆周率。 这个公式的精度较高，在n比较大的时候计算出来的结果已经非常接近真实值。

迅雷2021

1、使用C++写一个字符串插入的函数

void StringInsert(char* source,char* insert,int pos)
{
	int len1 = strlen(source);
	int len2 = strlen(insert);
	int newlen = len1 + len2;
	//为了安全，申请一个新的空间放字符串，避免在原字符串上申请空间失败数据丢失
	char* newstr = new char[newlen + 1];
	//拷贝插入位置前面的字符串
	for (int i = 0; i < pos; i++)
	{
		newstr[i] = source[i];
	}
	//拷贝要插入的字符串
	for (int i = 0; i < len2; i++)
	{
		newstr[pos + i] = insert[i];
	}
	//拷贝pos位置后面的字符串
	for (int i = pos; i < len1; i++)
	{
		newstr[i + len2 ] = source[i];
	}
	//新字符串尾部添加'\0'
	source[newlen] = '\0';
	//释放原来字符串的空间
	delete[] source;
	//将原字符串指针指向新字符串的地址
	source = newstr;
}

2、关于虚函数底层的实现，你了解多少？

????????虚函数可以实现运行时多态。由于编译器在编译时不能确定被调用的函数来自基类还是派生类，所以叫虚函数。

? ? ? ? 在底层实现中，C++的虚函数通过虚函数表和虚函数指针实现。可以通过基类指针或引用调用子类的虚函数。类的对象都有一个指向虚函数表的虚函数指针，虚函数表中存放该类的虚函数地址，创建一个新对象时，虚函数指针被初始化为指向该类的虚函数表的虚函数指针。当调用虚函数时，实际上是通过虚函数指针间接的调用虚函数表中的函数地址。

? ? ? ? 在继承关系中，子类继承父类的虚函数表，子类可以覆盖父类的虚函数。当父类虚函数在子类中重写时，父类虚函数表中父类的函数地址也会被替换为子类的。当使用父类指针或引用调用子类的函数时实际上调用的也是子类的虚函数。

? ? ? ? 由于虚函数的使用需要额外的空间和运行时开销，因此在不需要多态时尽量用普通函数代替虚函数，以提高程序执行效率。

3、请实现快排。

http://t.csdnimg.cn/fEgCd快排及快排优化

4、请实现堆排序。

//最小堆，左右子树小于双亲
void FilterDown(vector<int> &nums, int start, int end)
{
	int i = start, j = i * 2 + 1;
	int tmp = nums[i];
	while (j <= end)
	{
		if (j < end&&nums[j] > nums[j + 1]) j += 1;//找小的
		if (tmp <= nums[j]) break;
		else
		{
			nums[i] = nums[j];
			i = j;
			j =i * 2 + 1;
		}
	}
	nums[i] = tmp;
}
void HeapSort(vector<int>& nums, int n)
{
	if (n < 2) return;
	int pos = (n - 2) / 2;//n-1是最后一个元素的下标，再减一除二是双亲的位置
	while (pos >= 0)
	{
		FilterDown(nums, pos, n - 1);
		pos--;
	}
	pos = n - 1;
	while (pos > 1)
	{
		swap(nums[0], nums[pos]);
		pos--;
		FilterDown(nums, 0, pos);
	}
}

5、关于TCP、UDP，你了解多少？

1 、 TCP 面向连接（如打电话要先拨号建立连接） ;UDP 是无连接的，即发送数据之前不需要建立连接

2 、 TCP 提供可靠的服务，也就是说，通过 TCP 连接传送的数据，无差错，不丢失，不重复，且按序到 达;UDP 尽最大努力交付，即不保证可靠交付

3 、 TCP 面向字节流，实际上是 TCP 把数据看成一连串无结构的字节流 ;UDP 是面向报文的

UDP 没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如 IP 电话，实 时视频会议等）

4 、每一条 TCP 连接只能是点到点的 ;UDP 支持一对一，一对多，多对一和多对多的交互通信

5 、 TCP 首部开销 20 字节 ;UDP 的首部开销小，只有 8 个字节

6 、 TCP 的逻辑通信信道是全双工的可靠信道， UDP 则是不可靠信道

7.因为tcp有各种机制（确认应答，拥塞控制，窗口控制，超时重传）所以慢，而且容易被攻击。