【秋招突围】2024届秋招笔试-小红书笔试题-第一套-三语言题解(Java/Cpp/Python)-个人在线分享

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员
✨ 本系计划跟新各公司春秋招的笔试题
💻 ACM银牌🥈| 多次AK大厂笔试｜编程一对一辅导
👏 感谢大家的订阅➕ 和喜欢💗
📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注CSDN同名公主号领取，会在飞书进行同步的跟新。

文章目录

- 📖 写在前面
- - 夏天要来了秋招还会远吗？
- 🌲 01.K小姐的字符串问题
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 🍄 02.珍惜美食
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 🍇 03.收藏家LAY小姐
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 🎀 写在最后
- 🛖 这里介绍一下咱们的笔试打卡小屋
- - 🥰 打卡奖励
  - 🕰 每日学习安排
  - 📖 打卡小屋涉及题型
  - - 基础算法
    - 基础数据结构
    - 搜索
    - 动态规划 & 贪心 & 数论

📖 写在前面

夏天要来了秋招还会远吗？

前不久春招也算是圆满结束咯，大家有拿到心仪的 offer吗？
接下来互联网的秋招也快来啦，小伙伴们有开始准备了吗？
本次给大家带来24届秋招 小红书 的笔试题目三语言解析(Java/Python/Cpp)

文末有清隆学长的笔试陪伴打卡小屋活动介绍:
✨丰富的打卡奖励等你来领哦，大厂笔试题汇总，笔试面试经验贴，算法笔试模版…
💽 有兴趣的小伙伴们也可以了解一下，不要错过啦~

🌲 01.K小姐的字符串问题

问题描述

K小姐最近在研究一个有趣的字符串问题。给定两个仅由小写字母组成的字符串

$S$ 和

$T$ ，K小姐想知道在

$S$ 中最多有多少个 不重叠 的子串，使得每个子串都是

$T$ 的 异位词。这里两个字符串是 异位词 当且仅当两个字符串长度相同且每个字母出现的次数都相同。

例如，当

$S$ = “abcbac”，

$T$ = “abc” 时，在

$S$ 中最多有 2 个不重叠的子串 “abc” 和 “bac”，它们都是

$T$ 的异位词。

输入格式

第一行包含一个字符串

$S$ 。

第二行包含一个字符串

$T$ 。

输出格式

输出一个整数，表示在

$S$ 中最多有多少个不重叠的

$T$ 的异位词子串。

样例输入

abcbac
abc

样例输出

数据范围

≤

∣

≤

1 \le |S|, |T| \le 10^5

$1 \leq ∣ S ∣, ∣ T ∣ \leq 1 0^{5}$

题解

本题可以用滑动窗口的思想来解决。我们可以维护一个长度为

∣

|T|

$∣ T ∣$ 的滑动窗口，统计窗口内每个字母出现的次数，并与

$T$ 中每个字母出现的次数进行比较。如果窗口内的字母出现次数与

$T$ 完全相同，则找到了一个异位词子串，答案加 1，并将窗口向右移动

∣

|T|

$∣ T ∣$ 个位置，继续查找下一个异位词子串。如果字母出现次数不同，就将窗口向右移动一个位置，继续进行比较。

具体实现时，我们可以用两个数组

cnt_s

$c n t_{s}$ 和

cnt_t

$c n t_{t}$ 分别存储窗口内和

$T$ 中每个字母出现的次数。初始时，将

$T$ 中每个字母出现的次数记录在

cnt_t

$c n t_{t}$ 中。然后枚举滑动窗口的起始位置

$i$ ，统计窗口内每个字母出现的次数，存入

cnt_s

$c n t_{s}$ 中。如果

cnt_s

$c n t_{s}$ 和

cnt_t

$c n t_{t}$ 完全相同，就将答案加 1，并将窗口向右移动

∣

|T|

$∣ T ∣$ 个位置；否则将窗口向右移动一个位置。

时间复杂度

(

∣

)

O(|S|)

$O (∣ S ∣)$ ，空间复杂度

(

∣

)

O(|\Sigma|)

$O (∣Σ∣)$ ，其中

\Sigma

$Σ$ 为字符集大小。

参考代码

Python

def count_anagrams(s: str, t: str) -> int:
    n, m = len(s), len(t)
    if n < m:
        return 0
    
    cnt_t = [0] * 26
    for c in t:
        cnt_t[ord(c) - ord('a')] += 1
    
    cnt_s = [0] * 26
    ans = 0
    for i in range(n):
        cnt_s[ord(s[i]) - ord('a')] += 1
        if i >= m:
            cnt_s[ord(s[i - m]) - ord('a')] -= 1
        if cnt_s == cnt_t:
            ans += 1
            for j in range(m):
                cnt_s[ord(s[i - j]) - ord('a')] -= 1
    
    return ans

s = input()
t = input()
print(count_anagrams(s, t))

Java

import java.util.Scanner;
public class Solution {
public static int countAnagrams(String s, String t) {
int n = s.length(), m = t.length();
if (n < m) {
return 0;
}
int[] cntT = new int[26];
for (char c : t.toCharArray()) {
cntT[c - 'a']++;
}
int[] cntS = new int[26];
int ans = 0;
for (int i = 0; i < n; i++) {
cntS[s.charAt(i) - 'a']++;
if (i >= m) {
cntS[s.charAt(i - m) - 'a']--;
}
if (Arrays.equals(cntS, cntT)) {
ans++;
for (int j = 0; j < m; j++) {
cntS[s.charAt(i - j) - 'a']--;
}
}
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String t = sc.nextLine();
System.out.println(countAnagrams(s, t));
}
}

#include 
#include 
#include 
using namespace std;
int countAnagrams(string s, string t) {
int n = s.size(), m = t.size();
if (n < m) {
return 0;
}
vector<int> cntT(26, 0);
for (char c : t) {
cntT[c - 'a']++;
}
vector<int> cntS(26, 0);
int ans = 0;
for (int i = 0; i < n; i++) {
cntS[s[i] - 'a']++;
if (i >= m) {
cntS[s[i - m] - 'a']--;
}
if (cntS == cntT) {
ans++;
for (int j = 0; j < m; j++) {
cntS[s[i - j] - 'a']--;
}
}
}
return ans;
}
int main() {
string s, t;
getline(cin, s);
getline(cin, t);
cout << countAnagrams(s, t) << endl;
return 0;
}

🍄 02.珍惜美食

问题描述

K小姐是一位美食家，她最近来到了一个美食之都。这个城市以街边小吃和特色餐厅闻名于世，每条街道上都有许多独特的美食店铺。

$n$ 家店铺坐落在同一条街道上，第

$i$ 家店铺提供

a_i

$a_{i}$ 份第

$i$ 种美食。K小姐希望品尝尽可能多的美食，但由于时间和胃容量有限，她最多只能光顾

$k$ 次店铺。每次光顾可以选择一段连续的店铺，并品尝这些店铺提供的所有美食。

为了不错过任何一种美味，K小姐希望在光顾店铺后，剩下的美食种类数量仍然大于

$0$ ，并且剩余美食中数量最少的那一种尽可能多。

请问，K小姐最多能让剩余美食中数量最少的那一种有多少份呢？

输入格式

第一行包含两个正整数

$n$ 和

$k$ ，分别表示店铺数量和最多光顾次数。

第二行包含

$n$ 个正整数，其中第

$i$ 个数为

a_i

$a_{i}$ ，表示第

$i$ 种美食的份数。

输出格式

输出一个整数，表示剩余美食中数量最少的那一种的最大可能份数。

样例输入

5 1
45 39 90 65 15

样例输出

数据范围

≤

1 \le n \le 10^5

$1 \leq n \leq 1 0^{5}$

≤

0 \le k \le 10^5

$0 \leq k \leq 1 0^{5}$

≤

1 \le a_i \le 10^6

$1 \leq a_{i} \leq 1 0^{6}$

题解

这道题可以使用贪心的思想来解决。我们可以分情况讨论：

当
当
当 $\ge 2 k≥2 时，可以先光顾左右两端，然后剩下的美食可以任意选择。此时剩余美食中数量最少的就是所有美食中最多的那一种。$

因此，我们可以根据

$k$ 的值，直接求出答案。

时间复杂度：

(

)

O(n)

$O (n)$ ，空间复杂度：

(

)

O(1)

$O (1)$ 。

参考代码

Python

n, k = map(int, input().split())
a = list(map(int, input().split()))
def solve(n, k, a):
if k == 0:
return min(a)
if k == 1:
return max(a[0], a[-1])
return max(a)
res = solve(n, k, a)
print(res)

Java

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int res = solve(n, k, a);
System.out.println(res);
}
public static int solve(int n, int k, int[] a) {
if (k == 0) {
return min(a);
}
if (k == 1) {
return Math.max(a[0], a[n - 1]);
}
return max(a);
}
public static int min(int[] a) {
int min = a[0];
for (int i = 1; i < a.length; i++) {
min = Math.min(min, a[i]);
}
return min;
}
public static int max(int[] a) {
int max = a[0];
for (int i = 1; i < a.length; i++) {
max = Math.max(max, a[i]);
}
return max;
}
}

#include 
#include 
#include 
using namespace std;
int solve(int n, int k, vector<int>& a) {
if (k == 0) {
return *min_element(a.begin(), a.end());
}
if (k == 1) {
return max(a[0], a[n - 1]);
}
return *max_element(a.begin(), a.end());
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int res = solve(n, k, a);
cout << res << endl;
return 0;
}

🍇 03.收藏家LAY小姐

问题描述

LYA 是一位喜欢收藏的玩家，她最近在玩一款叫做”动物之森”的游戏。在游戏中，LYA 拥有很多个宝箱，每个宝箱里都装着一些她收集的宝石。每一种类型的宝石都有不同的作用。

有一天，LYA 在游戏中遇到了另一位玩家 A 先生。A 先生告诉 LYA，如果她的宝箱满足以下

$3$ 个条件，那么她就能获得一个成就奖励：

每个宝箱里不会有两颗相同的宝石。
每一种类型的宝石，只出现在一个宝箱中或者出现在所有宝箱中。
每个宝箱的容量大小一样。

LYA 非常想要这个成就奖励，现在她想知道她的这些宝箱是否同时满足上述

$3$ 个条件，能否获得成就奖励。

输入格式

第一行包含一个正整数

$T$ ，表示测试数据组数。

对于每组测试数据，第一行包含一个正整数

$n$ ，表示 LYA 的宝箱数量。

接下来的

$n$ 行，每行描述一个宝箱。每行的第一个数为正整数

$t$ ，表示这个宝箱的容量大小，后面跟着

$t$ 个正整数

a_i

$a_{i}$ ，分别表示这个宝箱中每颗宝石的类型。

输出格式

对于每组测试数据，如果 LYA 的这些宝箱满足全部三个条件，则在一行中先输出 Yes，然后按编号从小到大输出所有宝箱中都有的宝石类型。如果没有任何一种类型的宝石为所有宝箱共有，则仅需要输出 Yes。

如果 LYA 的这些宝箱不满足以上的所有条件，则输出 NO。

样例输入

样例输出

Yes 39
NO
NO

数据范围

$\leq T \leq 10 1≤T≤10$
$\leq n \leq 100 2≤n≤100$
$\leq t \leq 100 1≤t≤100$
$a_i < 2147483647 0<ai<2147483647$

题解

这道题需要我们判断给定的宝箱是否满足以下三个条件：

每个宝箱里不会有两颗相同的宝石。
每一种类型的宝石，只出现在一个宝箱中或者出现在所有宝箱中。
每个宝箱的容量大小一样。

我们可以逐个检查每个条件是否满足。

对于条件

$1$ ，我们可以对每个宝箱内的宝石类型进行去重，如果去重后的宝石类型数量与原来不同，则说明该宝箱内有重复的宝石，不满足条件

$1$ 。

对于条件

$2$ ，我们可以用一个哈希表

cnt

$c n t$ 统计每种宝石类型出现的宝箱数量。遍历完所有宝箱后，检查哈希表中每个宝石类型的出现次数，如果不是

$1$ 次或

$n$ 次，则不满足条件

$2$ 。同时，我们可以把出现在所有宝箱中的宝石类型记录下来。

对于条件

$3$ ，我们只需要记录第一个宝箱的容量大小，然后检查后面每个宝箱的容量大小是否与第一个宝箱相同即可。

如果所有条件都满足，则输出 Yes 以及所有宝箱中都有的宝石类型（如果有的话）；否则，输出 NO。

时间复杂度为

(

)

O(n imes t)

$O (n \times t)$ ，其中

$n$ 为宝箱数量，

$t$ 为每个宝箱的容量大小。空间复杂度为

(

)

O(n imes t)

$O (n \times t)$ 。

参考代码

Python

T = int(input())
for _ in range(T):
n = int(input())
boxes = []
for _ in range(n):
box = list(map(int, input().split()))
boxes.append(box[1:])
is_valid = True
gem_cnt = {}
cap = len(boxes[0])
for box in boxes:
if len(box) != cap:
is_valid = False
break
if len(set(box)) != len(box):
is_valid = False
break
for gem in box:
gem_cnt[gem] = gem_cnt.get(gem, 0) + 1
common_gems = []
for gem, cnt in gem_cnt.items():
if cnt == 1 or cnt == n:
if cnt == n:
common_gems.append(gem)
else:
is_valid = False
break
if is_valid:
print("Yes", end="")
if common_gems:
print(" " + " ".join(map(str, sorted(common_gems))))
else:
print()
else:
print("NO")

Java

import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int n = sc.nextInt();
List<Set<Integer>> boxes = new ArrayList<>();
for (int i = 0; i < n; i++) {
int t = sc.nextInt();
Set<Integer> box = new HashSet<>();
for (int j = 0; j < t; j++) {
box.add(sc.nextInt());
}
boxes.add(box);
}
boolean isValid = true;
Map<Integer, Integer> gemCnt = new HashMap<>();
int cap = boxes.get(0).size();
for (Set<Integer> box : boxes) {
if (box.size() != cap) {
isValid = false;
break;
}
for (int gem : box) {
gemCnt.put(gem, gemCnt.getOrDefault(gem, 0) + 1);
}
}
List<Integer> commonGems = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : gemCnt.entrySet()) {
int cnt = entry.getValue();
if (cnt == 1 || cnt == n) {
if (cnt == n) {
commonGems.add(entry.getKey());
}
} else {
isValid = false;
break;
}
}
if (isValid) {
System.out.print("Yes");
if (!commonGems.isEmpty()) {
Collections.sort(commonGems);
for (int gem : commonGems) {
System.out.print(" " + gem);
}
}
System.out.println();
} else {
System.out.println("NO");
}
}
}
}

#include 
#include 
#include 
#include 
#include 
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<vector<int>> boxes(n);
for (int i = 0; i < n; i++) {
int t;
cin >> t;
boxes[i].resize(t);
for (int j = 0; j < t; j++) {
cin >> boxes[i][j];
}
}
bool isValid = true;
unordered_map<int, int> gemCnt;
int cap = boxes[0].size();
for (const auto& box : boxes) {
if (box.size() != cap) {
isValid = false;
break;
}
unordered_set<int> uniqueGems(box.begin(), box.end());
if (uniqueGems.size() != box.size()) {
isValid = false;
break;
}
for (int gem : box) {
gemCnt[gem]++;
}
}
vector<int> commonGems;
for (const auto& entry : gemCnt) {
int cnt = entry.second;
if (cnt == 1 || cnt == n) {
if (cnt == n) {
commonGems.push_back(entry.first);
}
} else {
isValid = false;
break;
}
}
if (isValid) {
cout << "Yes";
if (!commonGems.empty()) {
sort(commonGems.begin(), commonGems.end());
for (int gem : commonGems) {
cout << " " << gem;
}
}
cout << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}

🎀 写在最后

🛖 这里介绍一下咱们的笔试打卡小屋

【秋招突围】2024届秋招笔试-小红书笔试题-第一套-三语言题解(Java/Cpp/Python)插图

✨ 打卡小屋旨在陪伴大家，养成每日学习的好习惯。在这里，你可以：

🤝 与备战笔试的小伙伴相识，找到志同道合的学习小组
📝 通过写题解，巩固做题思路，养成良好的记录习惯
💡 系统掌握常考算法和数据结构，了解互联网笔试难度
🎁 坚持打卡，获得丰厚奖励，激励自己持之以恒

🥰 打卡奖励

打卡时长	奖励内容
7天	任选一家最新互联网笔试真题 x 1 (价值29.9r)
14天	任选一家最新互联网笔试真题 x 3 + 笔试面试经验贴
21天	任选一家最新互联网笔试真题 x 5 + 清隆三语言算法模版
28天	最新互联网大厂笔试真题汇总(价值199r) + 华为OD机试训练营 (价值89r)

7天打卡即可值回票价，心动不如行动！

🕰 每日学习安排

小屋将在每日上午发放打卡题目，包括：

一道算法模版题，帮助大家掌握常用算法套路
根据算法模版，精选一道对应的大厂笔试真题，巩固算法应用

让我们一起直击笔试重点，攻克常考题型！

📖 打卡小屋涉及题型

小屋从零基础出发，涵盖笔试常考知识点：

基础算法

自定义排序
二分
前缀和
差分
双指针

基础数据结构

栈 & 单调栈
队列 & 单调队列
并查集
优先队列(堆)

搜索

DFS & BFS 基础应用
树的遍历
基础图论

动态规划 & 贪心 & 数论

快速幂
组合数
质数 & 因数
位运算
基础动态规划
常见贪心

【秋招突围】2024届秋招笔试-小红书笔试题-第一套-三语言题解(Java/Cpp/Python)插图(1)

2024年七月
一	二	三	四	五	六	日
						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

文章目录

📖 写在前面

夏天要来了 秋招还会远吗？

🌲 01.K小姐的字符串问题

问题描述

输入格式

输出格式

样例输入

样例输出

数据范围

题解

参考代码

🍄 02.珍惜美食

问题描述

输入格式

输出格式

样例输入

样例输出

数据范围

题解

参考代码

🍇 03.收藏家LAY小姐

问题描述

输入格式

输出格式

样例输入

样例输出

数据范围

题解

参考代码

🎀 写在最后

🛖 这里介绍一下咱们的笔试打卡小屋

🥰 打卡奖励

🕰 每日学习安排

📖 打卡小屋涉及题型

基础算法

基础数据结构

搜索

动态规划 & 贪心 & 数论

admin 钻石

相关推荐

夏天要来了秋招还会远吗？