恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】
点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝
第一道：小美的AI学习（100%）
参考代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const ll mod = 1e9 + 7;
vector<int> color, weight;
vector<vector<int>> v;
void dfs(int i, int fa)
{
if (v[i].size() == 1 && v[i][0] == fa)
return;
map<int, int> mp;
int Max = 0, sum = weight[i];
for (auto j : v[i])
{
if (j == fa)
continue;
dfs(j, i);
Max = max(Max, mp[color[j]] += weight[j] + 1);
}
weight[i] = Max;
}
int main()
{
int n, k;
cin >> n >> k;
color.resize(n);
weight.resize(n);
v.resize(n);
for (int i = 0; i < n; ++i)
{
int c;
cin >> c;
color[i] = c;
}
for (int i = 1; i < n; ++i)
{
int p;
cin >> p;
v[i].push_back(p - 1);
***bsp;- 1].push_back(i);
}
for (int i = 0; i < n; ++i)
{
cin >> weight[i];
}
dfs(0, -1);
for (int i = 0; i < n; ++i)
{
printf("%d%c", weight[i], (i == n - 1 ? '
' : ' '));
}
}
第二道：小美的数学题（100%）
题目描述
输入一个括号序列(())()。
单独成对的括号()则表示为整数2。
(())则表示（2），如果外层还有一个括号则将内部的数字加一，所以（2） 得到3。
如果两个标准括号相连，例如()()， 则表示2*2 = 4。
输入'(())()' --> （2+1）*2 = 6
输入 '(()())(())' -->（1+2*2）*（2+1） = 15
思路解析
假设测试用例为：（）（（）（））（（））
第一步：找到最外层的括号对，可以看到最外层的括号有三对：（）、（（）（））、（（））
第二步：取出最外层的括号对里面的序列，分别为：空、（）（）、（）
第三步：递推公式:
f( “（）（（）（））（（））” ) = ( f( “空” ) +1 ) * ( f( “（）（）” ) +1 ) * ( f( “（）” ) +1 )
再例如s = ‘(()))()’，n = len(s)
步骤为 检测stk后面是否有连续的两个正数，如果有，这两个正数应该“相碰”（相乘）， 因为两个正数挨着，说明这两个完整的括号部分挨着，因此必为相乘操作；
stk.size()-2 , stk.size()-1，就是后两位的idx， 相乘之后存在stk.size()-2的位置，因为最后一位需要被pop掉。
此时stk [-1, 4]，如果 ")"进入， 由于最后一位不是‘-1’，说明这个右括号“）”肯定有前面未匹配的左括号“（”在等待。
规律：前面未匹配的左括号比为倒数第二位。因为后面可以匹配的正整数已经相互碰撞成了一个新的整数，所以stk最右侧最多只能连续存在一个正整数。
参考代码
CPP版本
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
int main()
{
string s;
cin >> s;
int n = s.size();
vector<ll> stk;
for (int i = 0; i < n; ++i)
{
if (s[i] == '(')
stk.push_back(-1);
else
{
if (stk.back() == -1)
{
stk[stk.size() - 1] = 2;
if (stk.size() >= 2 && stk[stk.size() - 2] > 0)
{
stk[stk.size() - 2] = (stk[stk.size() - 2] * stk[stk.size() - 1]) % mod;
stk.pop_back();
}
}
else
{
stk[stk.size() - 2] = (1 + stk[stk.size() - 1]) % mod;
stk.pop_back();
if (stk.size() >= 2 && stk[stk.size() - 2] > 0)
{
stk[stk.size() - 2] = (stk[stk.size() - 2] * stk[stk.size() - 1]) % mod;
stk.pop_back();
}
}
}
}
cout << stk.back() << "
";
}
第三道：小美当会计
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
int n, T;
cin >> n;
vector<ll> v(n), Max(n), Sum(n + 1), Square(n + 1);
for (int i = 0; i < n; ++i)
scanf("%lld", &v[i]);
for (int i = 1; i <= n; ++i)
{
Sum[i] += Sum[i - 1] + v[i - 1];
Square[i] += Square[i - 1] + v[i - 1] * v[i - 1];
}
cin >> T;
while (T--)
{
int op, L, R;
scanf("%d%d%d", &op, &L, &R);
--L;
if (op == 1)
{
cout << Sum[R] - Sum[L] << "
";
}
else if (op == 2)
{
ll A = Sum[R] - Sum[L];
ll B = Square[R] - Square[L];
cout << (R - L) * A * A + B - 2 * A * A << "
";
}
else
{
cout << *max_element(v.begin() + L, v.begin() + R) << "
";
}
}
}
第四道：小美写作文（100%）
参考代码
Java版本
大致思路就是将每个字母的出现的下标全存下来，然后再去找前一个和后一个下标
import java.util.*;
public class Main2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder(sc.nextLine());
Map<Character, List<Integer>> map = new HashMap<>();
int i=0;
for(;i<sb.length();i++){
map.computeIfAbsent(sb.charAt(i),k->new ArrayList<>()).add(i);
}
int n =sc.nextInt();
sc.nextLine();
while (n-->0){
String[] s = sc.nextLine().split("\\s+");
int type = Integer.parseInt(s[0]);
if(type==1){
sb.append(s[1]);
map.computeIfAbsent(s[1].charAt(0),k->new ArrayList<>()).add(i++);
}else{
int pos = Integer.parseInt(s[1])-1;
char c = sb.charAt(pos);
List<Integer> list = map.get(c);
int idx = list.indexOf(pos);
int min = Integer.MAX_VALUE;
if(idx-1>=0){
min=Math.min(min,pos-list.get(idx-1));
}
if(idx+1<list.si***=Math.min(min,list.get(idx+1)-pos);
}
if(min==Integer.MAX_VALUE){
System.out.println(-1);
}else{
System.out.println(min);
}
}
}
}
}
CPP版本
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
int n;
cin >> s >> n;
vector<set<int>> mp(26);
for (int i = 0; i < s.size(); ++i)
{
mp[s[i] - 'a'].insert(i);
}
while (n--)
{
int op;
scanf("%d ", &op);
if (op == 1)
{
char c;
cin >> c;
mp[c - 'a'].insert(s.size());
s += string(1, c);
}
else
{
int c;
cin >> c;
int pos = c - 1;
auto &t = mp[s[c - 1] - 'a'];
auto it = t.lower_bound(pos);
int res = INT_MAX;
if (next(it) != t.end())
res = min(res, *next(it) - pos);
if (it != t.begin())
res = min(res, pos - *prev(it));
cout << (res == INT_MAX ? -1 : res) << "
";
}
}
}
第五道：小美的数字卡片（100%）
参考代码
Java版本
package Meituan.Exam;
import java.util.Scanner;
import java.util.Stack;
public class MeituanThree {
static int M = 1000000007;
public static long solve(String str,int L,int R){
if(R-L==1){
return 2;
}
int left = 0;
int right = 0;
int index = L;
while (index<=R){
if(str.charAt(index)=='('){
left++;
}
if(str.charAt(index)==')'){
right++;
}
if(left==right){
if(index-L>2){
if(index==R){
long res = 1+(solve(str,L+1,index-1)%M);
return res;
}else{
long res =((1+solve(str,L+1,index-1)%M)*(solve(str,index+1,R)%M))%M;
return res;
}
}
if(index-L==1){
long res = (2*solve(str,index+1,R)%M)%M;
return res;
}
}
index++;
}
return 0;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
if (str.length()==1||str==null){
System.out.println(1);
}
long ans = solve(str, 0, str.length() - 1);
System.out.println(ans%M);
}
}
CPP版本
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; ++i) cin >> v[i];
sort(v.begin(), v.end());
vector<vector<int>> res;
do {
res.push_back(v);
} while (next_permutation(v.begin(), v.end()));
cout << res.size() << "
";
for (auto &v : res) {
for (int i = 0; i< n; ++i) {
printf("%d%c", v[i], (i == n-1 ? '
' : ' '));
}
}
}
恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。
|