实习-2024春招笔试汇总

学习笔记 评论

2024大厂笔试真题B站讲解
2024大厂笔试笔记

3.9美团第一次

题目链接

4.小美的朋友关系

小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。
现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？
事件共有 2 种：
1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。
2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。

注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。

输入描述：

第一行两个整数 n,m，表示人数和事件数(1≤n,m≤105)(1\leq n,m\leq 10^5)。
接下来 m 行，每行有三个整数 t,u,v，表示事件类型和两个人的编号(1≤t≤2,1≤u,v≤n)(1\leq t\leq 2,1\leq u,v\leq n)。
接下来一行一个整数 q，表示小美的查询次数(1≤q≤105)(1\leq q\leq 10^5)。
接下来 q 行，每行有两个整数 u,v，表示小美的查询(1≤u,v≤n)(1\leq u,v\leq n)。
保证没有重复的事件。

输出描述：

对于每个查询，如果 u 和 v 可以通过朋友介绍互相认识，输出 “Yes”，否则输出 “No”。

示例：
输入例子：
5 3 5
1 2
2 3
4 5
1 1 5
2 1 3
2 1 4
1 1 2
2 1 3
输出例子：
Yes
No
No
例子说明：
第一次事件，1 号和 5 号本来就不是朋友，所以无事发生。
第二次事件是询问，1 号和 3 号可以通过 2 号的介绍认识。
第三次事件是询问，显然 1 号和 4 号无法互相认识。
第四次事件，1 号和 2 号淡忘了。
第五次事件，此时 1 号无法再经过 2 号和 3 号互相认识了。

思路：
并查集，但是对于查询反着来，相当于时光倒流，站在后面看之前。

  1. 根据初始条件，构建朋友关系边
  2. 根据查询条件1，构建淡忘的关系边
  3. 然后将初始条件中的并且不在淡忘条件中的边，构建并查集
  4. 现在构建的，是最后所有关系淡忘完的朋友圈
  5. 此时，对于所有查询逆序。
  6. 如果查询的两个人在同一个朋友圈（所有关系都断开了还能相通），输出Yes，否则输出No
  7. 如果遇到了淡忘条件，将淡忘条件加入并查集，恢复关系

参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
n, m, q = map(int, input().split())
initial_relationship = [list(map(int, input().split())) for _ in range(m)]
events = [list(map(int, input().split())) for _ in range(q)]

class UnionFind:
    def __init__(self, n: int) -> None:
        self.parent = [i for i in range(n)]  # 位置i的元素记录其父节点下标
  
    # 查找根节点
    def find(self, i: int) -> int:
        if self.parent[i] == i: return i
        # 递归查找父节点
        self.parent[i] = self.find(self.parent[i])  # 完全压缩
        return self.parent[i]
  
    def merge(self, i: int, j: int):
        root_i = self.find(i)
        root_j = self.find(j)

        self.parent[root_i] = root_j

    def query(self, i: int, j: int) -> bool:
        return self.find(i) == self.find(j)


unionFind = UnionFind(n+1)
relationship = set()
for relation in initial_relationship:
    relationship.add(tuple(sorted(relation)))  # 排序元素，保证关系不重复
for event in events:
    if event[0] == 1:
        relationship.discard(tuple(sorted(event[1:])))

# 将所有未被淡忘的关系加入并查集
for relation in relationship:
    unionFind.merge(*relation)

# 倒推事件，出现淡忘关系，将该关系加入并查集
ans = []
for event in events[::-1]:
    if event[0] == 1:
        unionFind.merge(event[1], event[2])
    else:
        ans.append('Yes' if unionFind.query(event[1], event[2]) else 'No')

# 逆序输出结果
print(ans[::-1])

5.小美的区间删除

小美拿到了一个大小为nn的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有kk个00。小美想知道，一共有多少种不同的删除方案？

输入描述：

第一行两个整数n,kn,k，表示数组大小和末尾00的个数(1≤n≤105,0≤k≤18)(1\leq n\leq 10^5,0\leq k\leq 18)。
第二行nn个整数，表示数组中的元素(1≤ai≤109)(1\leq a_i\leq 10^9)。

输出描述：

一个整数，表示答案。

示例：

输入例子：
5 2
2 5 3 4 20
输出例子：
4
例子说明：
第一个方案，删除[3]。
第二个方案，删除[4]。
第三个方案，删除[3,4]。
第四个方案，删除[2]。

参考1
参考2

思路：
乘积末尾有k个0意味着乘积可以被 10k10^k 整除，又 10k=2k∗5k10^k=2^k*5^k。因此，问题转化为找到删除区间后，剩余所有元素的乘积中2和5的因子数量都至少有k个。

  1. 预处理每个元素的2和5的因子数量，记录前缀和，分别存储在cnt2和cnt5数组中。
  2. 用双指针l和r维护一个区间，使得去除区间内的元素因子数量之外，剩下的至少有k个，那么这个区间就是可以被删除的区间。
  3. 每一次，固定l，r向右移动，此时计算剩余的2和5的因子数量，并判断min(remain2,remain5)min(remain2,remain5)是否小于k，如果小于k，表示剩余的元素不满足条件，那么l向右移动，重新找一个起点区间。如果大于k，表示剩余的元素满足条件，那么r向右移动，查看下一个区间，是否满足条件。
  4. 每次移动，都用ans记录所有的区间数（如果大区间删掉没问题，那么小区间也没问题），最后输出ans。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

n,k=map(int,input().split())

nums=list(map(int,input().split()))

def countn(n,factor):
    ans=0
    while n:
        if n%factor==0:
            ans+=1
            n//=factor
        else:
            break
    return ans
cnt2=[0]*(n+1)
cnt5=[0]*(n+1)
for i in range(n):
    cnt2[i+1]=cnt2[i]+countn(nums[i],2)
    cnt5[i+1]=cnt5[i]+countn(nums[i],5)
ans=0
l=1
r=1
while l<=n:
    while r<=n:
        range2=cnt2[r]-cnt2[l-1]
        range5=cnt5[r]-cnt5[l-1]
        remain2=cnt2[n]-range2
        remain5=cnt5[n]-range5
        if min(remain2,remain5)<k:
            break
        r+=1
    ans+=max(r-l,0)
    l+=1
print(ans)

3.16美团第二次

树状数组补充

4.小美的众数

小明要求出一个数组的所有子数组的众数之和，定义子数组的众数为出现次数最多的那个数。如果有多个数出现次数最多，那么众数是其中最小的那个数。

输入描述

第一行输入一个正整数n，代表数组的大小。
第二行输入n个正整数aia_i，代表数组的元素(1≤n≤2∗105,1≤ai≤2)(1\leq n\leq 2*10^5,1\leq a_i\leq 2)。

输出描述

一个正整数，代表所有区间的众数之和。

示例：

输入
3
2 1 2
输出
9
说明
[2],[2,1,2],[2]的众数是 2。
[2,1],[1],[1,2]的众数是 1。
因此答案是 9。

思路：
我整个子数组的数量为n∗(n+1)2\frac{n*(n+1)}{2}，因此我们只需要统计众数2的个数，即可知道众数1的个数，反之亦然
对于这题，我们可以将1视为-1，2视为1，那么区间 [l, r]的和就相当于区间中2的数量减去1的数量，如果该区间的和>0，则说明对于区间 [l, r]而言，区间的众数为2，否则为1。
为了区间和的计算方便，这里采用前缀和来进行处理:
-记s[i]为前i个数的和，那么区间 [l, r]的和可以表示为: s[r]-s[l-1]
将本题转换为，对于每个位置r，找到其左侧所有满足 s[r]-s[l]>0. l∈[1,r一1]l \in [1,r一1]的数量其中查询左侧满足的数量个数可以用树状数组来维护查询。
值得注意的是:由于这里将所有的1都变成-1了，那么所有的前缀和的范围为[一n, n]，因此在使数状数组的时候要加上偏移量n+1

1
2


5.小美的逆序对

小明拿到了一个排列，他定义 f(i) 为：将第 i 个元素取反后，形成的数组的逆序对数量。小明希望你求出 f(1) 到 f(n) 的值。（排列是指一个长度为n的数组，1到 n每个元素恰好出现了一次）

输入描述

第一行输入一个正整数n，代表排列的大小。
第二行输入n个正整数aia_i，代表排列的元素。
1≤n≤2∗1051 \le n \le 2 * 10^5
1≤ai≤n1 \le a_i \le n

输出描述

输出n整数，第i整数是 f(i) 的值。

示例：

输入
3
1 2 3
输出
0 1 2
说明
第一个元素取反，数组将变成[-1,2,3]，逆序对数量为 0。
第二个元素取反，数组将变成[1,-2,3]，逆序对数量为 1。
第三个元素取反，数组将变成[1,2,-3]，逆序对数量为 2。

思路：

  1. 首先要求出来原来数组的逆序对数量（记为ans），常见的方法是树状数组或者归并排序, 统计逆序对有两种遍历方法，一种是看前面的元素有几个比当前元素大（记为 pre[i]），或者是看后面的元素有几个比当前元素小(记为 suf[i])。
  2. 在遍历每个元素求 f(i) 的时候，要分别求出当前元素取反之后，对前面元素和后面元素的影响，f(i) = ans + 对前面的影响 + 对后面的影响
    • 对后面元素：取负之后，后面的元素一定比当前元素大，相比原来少了suf[i]个逆序对，所以ans要减去suf[i]；
    • 对前面元素：取负之后，前面的元素一定比当前元素小，所以现在一定形成了i-1个逆序对，再减去pre[i]，就求出变化量了。
  3. 所以 f ( i ) f(i)f(i) = ans + ((i - 1) - pre[i]) + (-suf[i])
  4. 求pre[i]和suf[i]的过程要用到树状数组

3.24拼多多第一次

×3.超级快递点

多多快递站共有n个快递点，n个快递点之间通过m条单向车道连接。快递员从任何一个快递站点出发，都无法通过单向车道回到该站点。也就是说，n个快递点组成一张有向无环图。对于快递点u，如果对于所有的快递点 v(v!=u)， 快递员都可以从u走到v，或者从v走到u，那么则评定站点u为超级快递点。请你帮忙算一算，一共有多少个超级快递点。

输入描述：

第一行 2个数字n(2<=n<=310^5) , m(1<=m<=310^5) , n为快递点个数，m为单向车道个数。
接下来的m行每行两个数字 u,v(1<=u,v<=n, v!=u)，表示有一条站点u指向v的单向车道。

输出描述：

请输出个数字，表示超级快递点的个数。

示例：

输入示例
7 7
1 2
2 3
3 4
4 7
2 5
5 4
6 4
输出示例
2
说明
快递点 4 可以到达 4，7，可以从1，2，3，5，6 到达， 评为超级快递点 快递点 7 可以到达 7，可以从 1，2，3，4，5，6到达，评为超级快递点

思路：
有点像图中的求关键节点

4.多多的回文修建

多多有一个长度为 n 的字符串, 这个字符串由26个小写字母组成.
多多可以对这个字符串进行多次操作, 每次操作可以把该字符串中一段连续的回文子串删除(单个字符也属于回文串), 删除后剩下的串会拼在一起.
请问最少需要多少次操作可以将这个字符串删光.

输入描述：

第一行, 包含一个正整数 T(1<=T<=20) 代表测试数据的组数.
对于每组测试数据, 仅有一行, 代表这个字符串.
(1<=n<=500)
保证 Σn 不超过 3000

输出描述：

对于每组数据输出一行整数, 代表多多在进行最少多少次操作后, 可以将这个字符串删光.

示例：

输入示例
3
mwapd
tvuvv
yxxmi
输出示例
5
3
4
说明
对于 tvuvv
第一步: 删除u, 此时剩下tvvv
第二步: 删除vvv, 此时剩下t
第三步: 删除t

思路：

【LeetCode - 1246】删除回文子数组(会员题)

f[i][j]表示将区间 [i,j]删除的最小次数. 转移时枚举k将区间分为[i,k]和[k+1,j]两部分, 如果 a[i]==a[j]则可以选择从 f[i+1][j-1]转移,因为可以选择再删除 a[i+1][j-1]之后,把i和j作为回文串删掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def min_insertions(st):
    n = len(st)
    f = [[0 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        f[i][i] = 1

    for i in range(n - 1):
        if st[i] == st[i + 1]:
            f[i][i + 1] = 1
        else:
            f[i][i + 1] = 2
    # i代表的枚举长度
    for i in range(2, n):
        for j in range(n - i):
            if st[j] == st[j + i]:
                f[j][j + i] = f[j + 1][j + i - 1]
            else:
                f[j][j + i] = min(f[j][k] + f[k + 1][j + i] for k in range(j, j + i))

    return f[0][n - 1]

T = int(input())
for _ in range(T):
    st = input().strip()
    print(min_insertions(st))

# 自己的错误代码

def count(s,n):
    dp=[[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            dp[i][j]=j-i+1
    for i in range(n):
        dp[i][i]=1
        if i<n-1 and s[i]==s[i+1]:
            dp[i][i+1]=1

    for i in range(n):
        for j in range(n):
            if s[i:j+1]==s[i:j+1][::-1]:
                dp[i][j]=1
            for k in range(i,j):
                if s[i:k+1]==s[i:k+1][::-1]:
                    dp[i][k]=1
                if s[k+1:j+1]==s[k+1:j+1][::-1]:
                    dp[k+1][j]=1
                dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j])
    return dp[0][n-1]


inp=[
    'astgd',
    'tvuvv',
    'sfghhgtyujss',
    'sftyujss',
    'sdddsdgykkkjginfhsdkkkoiituiuiuiusdtmzptr',
]
for i in range(len(inp)):
    a=inp[i]
    if a==a[::-1]:
        print(1)
    else:
        n=len(a)
        print(count(a,n))

3.27饿了么第一次

1.K小姐的魔法仓库

K小姐是一位魔法师，她拥有三种魔法材料：火焰水晶、海洋之心和风之精灵，分别有 a个、b个和
c个。为了方便使用，她需要将这些材料存放在魔法仓库中，但由于材料的特性，存放时必须遵守以下规则：

每个仓库中的火焰水晶数量不能超过 2个。
每个仓库中的海洋之心数量不能少于 3个。
风之精灵没有特殊要求，可以任意存放。K小姐想知道，最少需要准备多少个仓库，才能将所有材料妥善存放？同时，如果她想尽可能多地使用仓库，最多可以使用多少个？

输入格式
第一行输入一个正整数 g，表示询问的次数。
接下来的 g 行，每行输入三个正整数 a、b、c，分别表示火焰水晶、海洋之心和风之精灵的数量。
1≤g≤1051 \le g \le 10^5
0≤a,b,c≤1090 \le a,b,c \le 10^9
输出格式
对于每组询问，输出一行结果。

如果不存在合法的存放方案，则输出 -1。

否则，输出两个正整数，分别表示最少和最多需要的仓库数量，用空格隔开。

示例

输入
2
3 3 3
1 1 1
输出
3 7
-1

思路：
要求最少需要的仓库数量，我们可以这样考虑：

  1. 先计算出存放火焰水晶所需的最少仓库数，即 [a2\frac{a}{2}]。
  2. 然后看剩余的海洋之心和风之精灵的总数是否不小于 3，如果小于3,则无解。
  3. 如果剩余材料总数不小于 3，那么可以将它们都放入一个仓库中，此时仓库总数就是最少需要的仓库数。

要求最多可以使用的仓库数量，我们可以这样考虑：

  1. 先将海洋之心平均分配到若干个仓库中，每个仓库恰好 3个，计算出需要的仓库数。
  2. 然后将剩余的海洋之心、火焰水晶和风之精灵各自单独放入一个仓库中。
  3. 所有仓库的总数就是最多可以使用的仓库数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solve():
    a, b, c = map(int, input().split())
    if b + c < 3:
        print(-1)
        return
    min_num = 1 + (a + 1) // 2
    while b < 3 and c > 0:
        b += 1
        c -= 1
    max_num = b // 3 + c + a
    print(min_num, max_num)

g = int(input())
for _ in range(g):
    solve()

3.K小姐的密码锁

K小姐在研究一个有趣的密码锁问题。这个密码锁由一排按钮组成，每个按钮要么是未知状态（用 ? 表示），要么是已解锁状态（用 * 表示）。对于每个未知状态的按钮，它旁边会标记一个数字（
0到 2），表示其左右两侧已解锁按钮的总数。

现在 K小姐想要知道，一共有多少种可能的解锁方案满足所有按钮旁边的数字条件。由于方案数可能很大，你只需要输出结果除以109+710^9+7 的余数即可。

输入格式
输入一行，包含一个只由 *、? 和 0 到 2 组成的字符串，表示密码锁的初始状态。字符串长度不超过
10510^5。

输出格式
输出一个整数，表示可能的解锁方案数除以
109+710^9+7的余数。

示例

输入
??**2?11??
输出
8

思路
dp,看不会

1
2


3.28携程第一次

😁第一次ak,两题用的双指针,练就有用!

3.游游的区间除2

游游拿到了一个数组，她可以进行最多一次操作:选择一个元素全是偶数的区间，使这个区间所有元素除以2.
游游希望最终所有元素之和尽可能大，你能帮帮她吗?

输入描述

第一行输入一个正整数n，代表数组的大小。
第二行输入n个正整数aia_i，代表数组的元素。
1≤n≤1051 ≤ n ≤ 10^5
−109≤ai≤109-10^9 ≤a_i≤ 10^9

输出描述

一个整数，代表最终所有元素之和的最大值。

示例

输入
5
8 -4 2 -6 5
输出
-1
说明
[-4,2,-6]是一个全是偶数的区间，将其除以2后得到[-2,1,-3]，最终所有元素之和为-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys
n=int(input())
nums=list(map(int,sys.stdin.readline().split()))
ans_left=0
ans_right=0
ans=0
left,right=0,0
temp=0
while left<n and right<n:
    if nums[right]%2==1:
        right+=1
        left=right
        temp=0
        continue
    temp+=nums[right]
    if temp<ans:
        ans_left=left
        ans_right=right
        ans=temp
    if temp<0:
        right+=1
    else:
        right+=1
        left=right
        temp=0
total=sum(nums)
total-=ans
total+=(ans//2)
print(total)

4.SQL题

cities表

city_id: 城市id
city_name: 城市名
country: 国家

city_id city_name country
1 巴黎 法国
2 罗马 意大利
3 东京 日本

tour_packages表

package_id: 旅游线路id
city_id: 城市id
package_name: 旅游线路名
start_date: 开始日期
end_date: 结束日期
price: 价格

package_id city_id package_name start_date end_date price
1 1 巴黎之旅 2023-01-01 2023-01-10 1000
2 1 巴黎之旅 2023-01-11 2023-01-20 1100
3 1 巴黎之旅 2023-01-21 2023-01-30 1200
4 2 罗马之旅 2023-01-01 2023-01-10 1000
5 2 罗马之旅 2023-01-11 2023-01-20 1100
6 2 罗马之旅 2023-01-21 2023-01-30 1200
7 3 东京之旅 2023-01-01 2023-01-10 1000 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
select
    a.name_ as city_name,
    a.year_ as year,
    a.month_ as month,
    t.package_name as package_name ,
    a.price_ as price
from (
    select 
        c.city_name as  name_,
        c.city_id as id_, 
        YEAR(t.start_date) as  year_,
        MONTH(t.start_date) as  month_,
        min(price) as  price_
    from 
            tour_packages t
    left join cities c 
    on c.city_id = t.city_id
    group by c.city_id,c.city_name, YEAR(t.start_date),MONTH(t.start_date)
) as a
right join tour_packages t
on t.city_id = a.id_ and YEAR(t.start_date)=year_ and MONTH(start_date)=month_ and t.price=a.price_ 
where a.id_ is not null
order by a.year_,a.month_,a.price_,a.id_

3.30腾讯第一次

没参加

GladdduckKB Master

我写的个人简介。