【2022

【2022

恭喜发现宝藏！搜索公众号【TechGuide】回复公司名，解锁更多新鲜好文和互联网大厂的笔经面经，目前已更新至美团、微软…
作者@TechGuide【全网同名】
点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝

第一题：找出赝品

题目描述

小红拿到了n个物品，每个物品的品质为ai。这n个物品中至少有一个真品。

已知所有真品的品质都是相同的，但赝品的品质比真品低。小红想知道，这n个物品中最多有多少赝品。

输入描述

第一行输入一个正整数n，代表小红拿到的物品数量。
第二行输入n个正整数ai，代表每个物品的品质。n≤1e5, ai ≤ 1e9

1
5

输出描述

一个整数，代表赝品的数量。

0

解释：只有一个物品，显然是真品

思路

排个序统计一下就可以了。

代码

Python版本

from collections import Countern = int(input())
a = list(map(int, input().split()))
print(len(a) - Counter(a)[sorted(a)[-1]])
# vx公众号关注TechGuide 实时题库 闪电速递

CPP版本

#include<iostream>
using namespace std;int main(){int n,q;cin>>n;int big=0,tn=0,nn=n;while(nn--){cin>>q;if(big<q){big=q;tn=1;}else if(big==q)tn++;}cout<<n-tn;return 0;
}
// vx公众号关注TechGuide 实时题库 闪电速递

Java版本

// vx公众号关注TechGuide 实时题库 闪电速递

第二题：小红的元素分裂

题目描述

小红拿到了一个数组，她每次可以进行如下操作之一：

选择一个元素x，将其分裂为1和x-1。

·选择一个元素x，将其分裂为a和b，需要保证a*b=x

小红希望用最少的操作次数，将所有数组的所有元素全部变成1。你能帮帮她吗？

输入描述

第一行输入一个正整数n，代表数组的长度。
第二行输入n个正整数ai，代表小红拿到的数组。1 ≤ n, ai ≤ 1e5

2
2 6

输出描述

一个整数，代表最小的操作次数。

5

思路

预处理所有因数，然后记忆化搜索即可，不想写递归也可以写数组格式dp。

代码

Python版本

from functools import lru_cachen = int(input())
a = list(map(int, (input().split())))
v = int(1e5) + 1
fs = [[] for _ in range(v)]
for i in range(2, v):for j in range(2 * i, v, i):fs[j].append(i)@lru_cache(None)
def solve(n):if n == 1:return 0ans = 1 + solve(n - 1)for f in fs[n]:ans = min(ans, 1 + solve(f) + solve(n // f))return ansprint(sum(map(solve, a)))
# vx公众号关注TechGuide 实时题库 闪电速递

CPP版本

// 100%*20' 9min
// 小红的元素分裂
// 从数组里选择一个元素x
// x分裂为1和x-1
// x分裂为a和b，a*b=x
// 最少次数使所有数组元素变成1// 2
// 2 6// 输出5
// 116
// 1123
// 11113
// 111121
// 111111// 1<=n,ai<=1e5#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;int main(){int n,q;cin>>n;vector<int> a(n);for(int i=0;i<n;i++)cin>>a[i];int big=*max_element(a.begin(),a.end());vector<int> d(big+1,0);d[2]=1;for(int i=3;i<=big;i++){d[i]=d[i-1];for(int x=2;x<=sqrt(i);x++){if(i%x==0)d[i]=min(d[i],d[i/x]+d[x]);}d[i]+=1;}int ans=0;for(int i=0;i<n;i++){ans+=d[a[i]];}cout<<ans;return 0;
}
// vx公众号关注TechGuide 实时题库 闪电速递

第三题：子串必须连续

题目描述

定义一个括号串的权值为，它的最长合法括号子序列的长度。

例如，“())())的权值是4，它的最长合法括号子序列为”()()”

现在求一个给定括号串的所有子串权值之和。

输入描述

一个仅包含’(‘和’)'的字符串，长度不超过2e5。

(()())

输出描述

所有子串的权值和。

26

解释

权值为2的子串有2个

权值为4的子串有2个

思路

考虑不同子串太麻烦，可以反向考虑，考虑每一对可以匹配的括号对答案的贡献。考虑这样一个子串：xx()x，x表示任意字符。如何计算中间这对括号的贡献呢？其实可以看出来，带有这对括号的子串的数量只和它左右侧的字符数量有关，根据上面这个字符串，可以得到的带有这个括号的子串：

• xx()x
• xx()
• x()x
• x()
• ()x
• ()

也就是6个。如何得到这个数字呢？实际上就是（括号左侧的字符数+1）*（括号右侧的字符数+1）。为什么这样是正确的呢？因为我们要考虑这对括号的贡献，那么我们就要考虑所有包含该括号的子串。假设左括号左边有n个数字，那么左边其实有(n+1)种选择——什么都不选、选1个、选2个、选3个…因为要求是连续子串，所以只能有(n+1)种选择，右侧同理。两边选择的方案数需要乘起来。

那么只需要遍历一下字符串，查到每一个右括号对应的左括号位置，(左括号左侧的字符数+1)*(右括号右侧的字符数+1)则为这个括号的贡献，总复杂度O(n)

代码

Python版本

s = input()
ans = 0
n = len(s)
l = []
for i, v in enumerate(s):if v == '(': l.append(i)elif l: ans += 2 * (l.pop() + 1) * (n - i)
print(ans)
# vx公众号关注TechGuide 实时题库 闪电速递