美团笔试

美团笔试AC3.85，加上两段团子实习，我要在团子横着走！

笔试时间：2024年03月23日历史笔试传送门：2023秋招笔试合集第一题题目：小美的01矩阵小美拿到了一个n行m列的矩阵，她想知道该矩阵有多少个 2*2 的子矩形满足 1 和 0 的数量相等？输入描述第一行输入两个正整数n,m用空格隔开。接下来的n行，每行输入一个长度为m的 01 串，用来表示矩阵。2<=n,m<=100输出描述一个整数，代表 1 和 0 的数量相等的 2*2 的子矩形数量。样例输入2 3110010样例输出1说明两个 2*2 的子矩形，只有一个是合法的。参考题解模拟题。由于子矩阵固定大小是22，因此不需要前缀和，直接模拟即可。只需要保证每一个22的子矩阵的和是2...

时间120分钟一、&nbsp;20个选择题，涉及知识：字符串子串个数、二叉树前中后序遍历、汇编语言三地址代码、SMTP、单例模型、MySQL触发器、MySQL&nbsp;Json解析、四元式序列、网络广播地址、堆、ARP、最短臂算法、进程响应比计算、常用排序算法。（选择、堆、希尔、归并、冒泡）二、&nbsp;3道编程题。1.&nbsp;一道签到打卡字符串题，判断输入字符串是否为合法端口。2.&nbsp;一道列表签到打卡题，给定一个列表nums，定义函数f(i)为将列表中第i个元素翻倍后数组中最大值，输出f(1)到f(n）。3.&nbsp;给定两个相同长度字符串s与t，每次操作可以选择某个字符串前缀将其改字符c，问最少经过多少次修改后s与t相同。示例：s&nbsp;=&nbsp;&quot;aabc&quot;&nbsp;t&nbsp;=&quot;abcc&quot;输出：22&nbsp;3&nbsp;b2&nbsp;2&nbsp;a解释：&nbsp;操作1，&nbsp;选择第二个字符串前三个字符，修改为c&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;操作2，&nbsp;选择第二个字符串前两个字符，修改为a数据范围：0<&nbsp;s.length&nbsp;=&nbsp;t.length&nbsp;<&nbsp;10^5

第三题解法：树形dfs，用1表示B，2表示R，对树自下而上取或，那么节点为3表示子树同时有1和2。也可用集合，从下往上更新集合，找集合中有1和2的，但集合常数比位运算大，推荐使用位运算。C++和Python代码见截图，Python需要加sys.setrecursionlimit(100000)，防止递归深度过大。&nbsp;#include&nbsp;&lt;bits/stdc++.h&gt;&nbsp;using&nbsp;namespace&nbsp;std;&nbsp;int&nbsp;main()&nbsp;{&nbsp;int&nbsp;n;&nbsp;cin&gt;&gt;n;&nbsp;string&nbsp;s;&nbsp;cin&gt;&gt;s;&nbsp;vector&lt;ve...