4.9美团笔试五题解析
1.已知当前星期，时，分，求指定分钟前的星期，时，分
日期通常有两种解决思路：
- 找到一个起点，将时分全部转换为一个整数，计算完差值再转回时分的格式
- 统一格式化为时分，然后从最小单位开始做模拟减法
2.有编号1-n的选手，给定出发排列顺序和到达排列顺序，只要存在一个人X，出发时X在Y前，到达时X在Y后，那么Y会受到嘉奖。求能受到嘉奖的总人数。
本题再难点可出成逆序对问题，即每超过一个人就计数一次。
简单可用暴力求解，对于每个到达排列中的的选手，看看此时它后面有没人在出发时在他前面，时间复杂度为O(n^2)
优化可用哈希表，给出发排列按顺序进行编号，然后给到达排列写上对应的出发位置，问题就转换为是否存在逆序对问题。时间复杂度O(n)。
#include <iostream>
using namespace std;
#include <algorithm>
const int maxn=100010;
int n, t, Rank[2][maxn], m[maxn];
int main() { // 类似逆序对
cin >>n;
for (int i=0; i < n; i ++) {
cin >>t;
Rank[0][t] = i; // 按顺序编号
}
for (int i=0; i < n; i ++) {
cin >>t;
Rank[1][i] = Rank[0][t]; // 到达序列对应的出发位置
}
m[n-1] = Rank[1][n-1];
for (int i=n-2; i >= 0; i --) {
m[i] = min(m[i+1], Rank[1][i]); // 计算区间最小值
}
int ans=0;
for (int i=0; i < n-1; i ++) {
if (Rank[1][i] > m[i+1]) ans ++; // 统计总数
}
cout <<ans <<endl;
return 0;
} 3. f(x)=累加[x/(k^(i-1)]（i=1...n,[]表示向下取整，括号内值为0停止累加），问令f(x)>=n满足的最小x
x取值范围在[1,n]，暴力也行，不够优雅
二分查找找到第一个f(x)>=n的值(功能与STL里的upper_bound一样)
#include <iostream>
using namespace std;
#include <algorithm>
int n,k;
int cal(int x) { // 计算以x开头所能找到的最多bug
int ans = x;
do {
x /= k;
ans += x;
} while (x != 0);
return ans;
}
int lowerbound(int l, int r) { // 找到第一个>=n的值
if (l == r) return l;
int mid = l + (r-l)/2;
int mval = cal(mid);
if (mval == n) return mid;
else if (mval < n) return lowerbound(mid+1,r);
else return lowerbound(l,mid);
}
int main() {
cin >>n >>k;
cout <<lowerbound(1,n);
return 0;
} 4.给定4个顶点S,A,B,C，任何两个顶点均有一条连线（本质为4点完全图），从S点出发，经过K步，有多少种走法能最终到达S
暴力搜索时间复杂度过高，只能优雅一点，用动态规划解决，动规就是带着记事本的暴力搜索- 动态规划
状态定义：dp(i,v)表示从S点出发经过i步到达顶点v的走法数
状态转移：dp(i,S)=dp(i-1,A)+dp(i-1,B)+dp(i-1,C)，dp(i,A)=dp(i-1,S)+dp(i-1,B)+dp(i-1,C),还有两个不写了，都是从另外三个相邻点转移过来
空间优化：可以用滚动数组
- 矩阵相乘
ps:感谢大佬gfyyyyy在评论区指出该经典解法（图论好像学过，但早忘了捂脸🙃🙃🙃）
在图论中有一个经典问题：如何找出图中两点间长度为K的路径数？该问题和其实就是本题，只不过指定了起点和终点都为S，规定走K步指明路径长度为K。
问题是清楚了，那怎么求解呢？聪明的前哲发明了一种算法，利用矩阵完成计算（全源最短路算法Floyd也是类似思想）
定义矩阵M如下，其实就是图的邻接矩阵表示，1表示两点可达，0表示不可达（可达即有通路的意思）。
S A B C S 0 1 1 1 A 1 0 1 1 B 1 1 0 1 C 1 1 1 0那有了这个矩阵有啥用呢？先说结论：M^K（矩阵M进行K次相乘）第一个元素（M^K[0][0]）即为最终答案
若是初次相见，必定满腹狐疑，why？
看下去前保证你了解矩阵的乘法规则，即A=BC,那么A[i][j]=B的第i行与C的第j列对应元素相乘求和。
此时，假设B=C=M，
那么矩阵B中第一行的实际含义为点S->S,S->A,S->B,S->C的连通性
同理，矩阵C中第一列实际含义为点S->S,A->S,B->S,C->S的连通性
矩阵BC相乘时，即可完成类似S->A->S是否连通的判断，其余点与上面相同计算
因此，最终可以累计出结果
编码实现策略选择
根据以上分析，我们可用必须要计算出M^K，若是暴力求解，两个矩阵相乘需三重循环，K个相乘，则时间复杂度为O(kN^3)
可以用矩阵快速幂优化到O(logK*N^3)，（这些算法网络资料超多）
个人感悟
矩阵相乘其实本质上是一种剪枝策略完美的暴力搜索，暴力搜索每个节点都有3个选择，导致状态空间爆炸，而矩阵相乘每次乘完都是16个元素，有一个剪枝收缩的过程，这也是矩阵运算的魅力所在叭~
5.给定一组字符串，三种操作：插入/删除编号为x的字符串，求指定文本串S和输入的字符串集合的匹配总次数
模拟题，直接用哈希表/map存储字符串，然后依次实现三种操作即可。
注意点：
- 输入的字符串有重复，放入集合时需去重
- 一个字符串和文本串可能有多次匹配点，如文本串“ababa”和模式串“a”，就存在3个匹配点
#include <iostream>
using namespace std;
#include <algorithm>
#include <unordered_map>
#include <vector>
int n,k;
unordered_map<string, int> mp;
vector<string> vec;
void add(int idx) {
if (mp[vec[idx-1]] == 0) { // 不存在就插入
mp[vec[idx-1]] = 1;
}
}
void del(int idx) {
// if (mp[vec[idx-1]] != 0) mp[vec[idx-1]] --; // 删除一个？？还是全删
if (mp[vec[idx-1]] != 0) mp[vec[idx-1]] = 0; // 删除一个？？还是全删
}
void query(string s) {
int sum=0;
for (auto& p : mp) { // 遍历所有字符串
if (p.second != 0) { // 存在
int cnt=0;
auto it = s.find(p.first);
while (it != string::npos) {
cnt ++;
it = s.find(p.first, it+1);
}
// sum += cnt * p.second; // 存在多个相同字符串
sum += cnt; // 坑人，多个相同字符串只算一个
}
}
cout <<sum <<endl;
}
int main() {
cin >>n >>k;
string s;
for (int i=0; i < k; i ++) {
cin >>s;
vec.push_back(s);
mp[s] ++;
}
char op; int idx;
for (int i=0; i < n; i ++) {
cin >>op;
if (op == '?') {
cin >>s;
query(s);
}
else {
cin >>idx;
if (op == '+') add(idx);
else if (op == '-') del(idx);
}
}
return 0;
} 
查看8道真题和解析
投递牛客等公司10个岗位 >
