网站中微信公众号链接怎么做,wordpress的背景图片,湘潭市高新建设局施工报建网站,wordpress的标签是什么#x1f36d; 大家好这里是清隆学长 #xff0c;一枚热爱算法的程序员 ✨ 本系计划跟新各公司春秋招的笔试题 #x1f4bb; ACM银牌#x1f948;| 多次AK大厂笔试 #xff5c; 编程一对一辅导 #x1f44f; 感谢大家的订阅➕ 和 喜欢#x1f497; #x1f4e7; 清隆这边… 大家好这里是清隆学长 一枚热爱算法的程序员 ✨ 本系计划跟新各公司春秋招的笔试题 ACM银牌| 多次AK大厂笔试 编程一对一辅导 感谢大家的订阅➕ 和 喜欢 清隆这边最近正在收集近一年互联网各厂的笔试题汇总如果有需要的小伙伴可以关注CSDN同名公主号领取会在飞书进行同步的跟新。 文章目录 写在前面夏天要来了 秋招还会远吗 01.K小姐的字符串问题问题描述输入格式输出格式样例输入样例输出数据范围题解参考代码 02.珍惜美食问题描述输入格式输出格式样例输入样例输出数据范围题解参考代码 03.收藏家LAY小姐问题描述输入格式输出格式样例输入样例输出数据范围题解参考代码 写在最后 这里介绍一下咱们的笔试打卡小屋 打卡奖励 每日学习安排 打卡小屋涉及题型基础算法基础数据结构搜索动态规划 贪心 数论 写在前面
夏天要来了 秋招还会远吗
前不久春招也算是圆满结束咯大家有拿到心仪的 offer吗 接下来互联网的秋招也快来啦小伙伴们有开始准备了吗 本次给大家带来24届秋招 小红书 的笔试题目三语言解析(Java/Python/Cpp) 文末有清隆学长的笔试陪伴打卡小屋活动介绍: ✨丰富的打卡奖励等你来领哦大厂笔试题汇总笔试面试经验贴算法笔试模版… 有兴趣的小伙伴们也可以了解一下不要错过啦~ 01.K小姐的字符串问题
问题描述
K小姐最近在研究一个有趣的字符串问题。给定两个仅由小写字母组成的字符串 S S S 和 T T TK小姐想知道在 S S S 中最多有多少个 不重叠 的子串使得每个子串都是 T T T 的 异位词。这里两个字符串是 异位词 当且仅当两个字符串长度相同且每个字母出现的次数都相同。
例如当 S S S “abcbac” T T T “abc” 时在 S S S 中最多有 2 个不重叠的子串 “abc” 和 “bac”它们都是 T T T 的异位词。
输入格式
第一行包含一个字符串 S S S。
第二行包含一个字符串 T T T。
输出格式
输出一个整数表示在 S S S 中最多有多少个不重叠的 T T T 的异位词子串。
样例输入
abcbac
abc样例输出
1数据范围 1 ≤ ∣ S ∣ , ∣ T ∣ ≤ 1 0 5 1 \le |S|, |T| \le 10^5 1≤∣S∣,∣T∣≤105
题解
本题可以用滑动窗口的思想来解决。我们可以维护一个长度为 ∣ T ∣ |T| ∣T∣ 的滑动窗口统计窗口内每个字母出现的次数并与 T T T 中每个字母出现的次数进行比较。如果窗口内的字母出现次数与 T T T 完全相同则找到了一个异位词子串答案加 1并将窗口向右移动 ∣ T ∣ |T| ∣T∣ 个位置继续查找下一个异位词子串。如果字母出现次数不同就将窗口向右移动一个位置继续进行比较。
具体实现时我们可以用两个数组 c n t s cnt_s cnts 和 c n t t cnt_t cntt 分别存储窗口内和 T T T 中每个字母出现的次数。初始时将 T T T 中每个字母出现的次数记录在 c n t t cnt_t cntt 中。然后枚举滑动窗口的起始位置 i i i统计窗口内每个字母出现的次数存入 c n t s cnt_s cnts 中。如果 c n t s cnt_s cnts 和 c n t t cnt_t cntt 完全相同就将答案加 1并将窗口向右移动 ∣ T ∣ |T| ∣T∣ 个位置否则将窗口向右移动一个位置。
时间复杂度 O ( ∣ S ∣ ) O(|S|) O(∣S∣)空间复杂度 O ( ∣ Σ ∣ ) O(|\Sigma|) O(∣Σ∣)其中 Σ \Sigma Σ 为字符集大小。
参考代码
Python
def count_anagrams(s: str, t: str) - int:n, m len(s), len(t)if n m:return 0cnt_t [0] * 26for c in t:cnt_t[ord(c) - ord(a)] 1cnt_s [0] * 26ans 0for i in range(n):cnt_s[ord(s[i]) - ord(a)] 1if i m:cnt_s[ord(s[i - m]) - ord(a)] - 1if cnt_s cnt_t:ans 1for j in range(m):cnt_s[ord(s[i - j]) - ord(a)] - 1return anss 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));}
}Cpp
#include iostream
#include string
#include vectorusing namespace std;int countAnagrams(string s, string t) {int n s.size(), m t.size();if (n m) {return 0;}vectorint cntT(26, 0);for (char c : t) {cntT[c - a];}vectorint 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 n n 家店铺坐落在同一条街道上第 i i i 家店铺提供 a i a_i ai 份第 i i i 种美食。K小姐希望品尝尽可能多的美食但由于时间和胃容量有限她最多只能光顾 k k k 次店铺。每次光顾可以选择一段连续的店铺并品尝这些店铺提供的所有美食。
为了不错过任何一种美味K小姐希望在光顾店铺后剩下的美食种类数量仍然大于 0 0 0并且剩余美食中数量最少的那一种尽可能多。
请问K小姐最多能让剩余美食中数量最少的那一种有多少份呢
输入格式
第一行包含两个正整数 n n n 和 k k k分别表示店铺数量和最多光顾次数。
第二行包含 n n n 个正整数其中第 i i i 个数为 a i a_i ai表示第 i i i 种美食的份数。
输出格式
输出一个整数表示剩余美食中数量最少的那一种的最大可能份数。
样例输入
5 1
45 39 90 65 15样例输出
45数据范围 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105 0 ≤ k ≤ 1 0 5 0 \le k \le 10^5 0≤k≤105 1 ≤ a i ≤ 1 0 6 1 \le a_i \le 10^6 1≤ai≤106
题解
这道题可以使用贪心的思想来解决。我们可以分情况讨论
当 k 0 k0 k0 时不能光顾任何店铺因此剩余美食中数量最少的就是所有美食中最少的那一种。当 k 1 k1 k1 时可以选择光顾街道的左端或右端剩余美食中数量最少的就是左右两端美食数量的较大值。当 k ≥ 2 k \ge 2 k≥2 时可以先光顾左右两端然后剩下的美食可以任意选择。此时剩余美食中数量最少的就是所有美食中最多的那一种。
因此我们可以根据 k k k 的值直接求出答案。
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) 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;}
}Cpp
#include iostream
#include vector
#include algorithm
using namespace std;int solve(int n, int k, vectorint 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;vectorint 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 3 3 个条件那么她就能获得一个成就奖励
每个宝箱里不会有两颗相同的宝石。每一种类型的宝石只出现在一个宝箱中或者出现在所有宝箱中。每个宝箱的容量大小一样。
LYA 非常想要这个成就奖励现在她想知道她的这些宝箱是否同时满足上述 3 3 3 个条件能否获得成就奖励。
输入格式
第一行包含一个正整数 T T T表示测试数据组数。
对于每组测试数据第一行包含一个正整数 n n n表示 LYA 的宝箱数量。
接下来的 n n n 行每行描述一个宝箱。每行的第一个数为正整数 t t t表示这个宝箱的容量大小后面跟着 t t t 个正整数 a i a_i ai分别表示这个宝箱中每颗宝石的类型。
输出格式
对于每组测试数据如果 LYA 的这些宝箱满足全部三个条件则在一行中先输出 Yes然后按编号从小到大输出所有宝箱中都有的宝石类型。如果没有任何一种类型的宝石为所有宝箱共有则仅需要输出 Yes。
如果 LYA 的这些宝箱不满足以上的所有条件则输出 NO。
样例输入
3
1
1 39
3
2 49 50
3 58 49 50
1 49
5
3 90 89 63
2 89 63
2 63 89
3 89 32 63
3 86 63 89样例输出
Yes 39
NO
NO数据范围 1 ≤ T ≤ 10 1 \leq T \leq 10 1≤T≤10 2 ≤ n ≤ 100 2 \leq n \leq 100 2≤n≤100 1 ≤ t ≤ 100 1 \leq t \leq 100 1≤t≤100 0 a i 2147483647 0 a_i 2147483647 0ai2147483647
题解
这道题需要我们判断给定的宝箱是否满足以下三个条件
每个宝箱里不会有两颗相同的宝石。每一种类型的宝石只出现在一个宝箱中或者出现在所有宝箱中。每个宝箱的容量大小一样。
我们可以逐个检查每个条件是否满足。
对于条件 1 1 1我们可以对每个宝箱内的宝石类型进行去重如果去重后的宝石类型数量与原来不同则说明该宝箱内有重复的宝石不满足条件 1 1 1。
对于条件 2 2 2我们可以用一个哈希表 c n t cnt cnt 统计每种宝石类型出现的宝箱数量。遍历完所有宝箱后检查哈希表中每个宝石类型的出现次数如果不是 1 1 1 次或 n n n 次则不满足条件 2 2 2。同时我们可以把出现在所有宝箱中的宝石类型记录下来。
对于条件 3 3 3我们只需要记录第一个宝箱的容量大小然后检查后面每个宝箱的容量大小是否与第一个宝箱相同即可。
如果所有条件都满足则输出 Yes 以及所有宝箱中都有的宝石类型如果有的话否则输出 NO。
时间复杂度为 O ( n × t ) O(n \times t) O(n×t)其中 n n n 为宝箱数量 t t t 为每个宝箱的容量大小。空间复杂度为 O ( n × t ) O(n \times t) O(n×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 Truegem_cnt {}cap len(boxes[0])for box in boxes:if len(box) ! cap:is_valid Falsebreakif len(set(box)) ! len(box):is_valid Falsebreakfor gem in box:gem_cnt[gem] gem_cnt.get(gem, 0) 1common_gems []for gem, cnt in gem_cnt.items():if cnt 1 or cnt n:if cnt n:common_gems.append(gem)else:is_valid Falsebreakif 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();ListSetInteger boxes new ArrayList();for (int i 0; i n; i) {int t sc.nextInt();SetInteger box new HashSet();for (int j 0; j t; j) {box.add(sc.nextInt());}boxes.add(box);}boolean isValid true;MapInteger, Integer gemCnt new HashMap();int cap boxes.get(0).size();for (SetInteger box : boxes) {if (box.size() ! cap) {isValid false;break;}for (int gem : box) {gemCnt.put(gem, gemCnt.getOrDefault(gem, 0) 1);}}ListInteger commonGems new ArrayList();for (Map.EntryInteger, 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);}}}
}Cpp
#include iostream
#include vector
#include unordered_map
#include unordered_set
#include algorithm
using namespace std;int main() {int T;cin T;while (T--) {int n;cin n;vectorvectorint 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_mapint, int gemCnt;int cap boxes[0].size();for (const auto box : boxes) {if (box.size() ! cap) {isValid false;break;}unordered_setint uniqueGems(box.begin(), box.end());if (uniqueGems.size() ! box.size()) {isValid false;break;}for (int gem : box) {gemCnt[gem];}}vectorint 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;
}写在最后 这里介绍一下咱们的笔试打卡小屋 ✨ 打卡小屋旨在陪伴大家养成每日学习的好习惯。在这里你可以 与备战笔试的小伙伴相识找到志同道合的学习小组 通过写题解巩固做题思路养成良好的记录习惯 系统掌握常考算法和数据结构了解互联网笔试难度 坚持打卡获得丰厚奖励激励自己持之以恒 打卡奖励
打卡时长奖励内容7天任选一家最新互联网笔试真题 x 1 (价值29.9r)14天任选一家最新互联网笔试真题 x 3 笔试面试经验贴21天任选一家最新互联网笔试真题 x 5 清隆三语言算法模版28天最新互联网大厂笔试真题汇总(价值199r) 华为OD机试训练营 (价值89r)
7天打卡即可值回票价心动不如行动 每日学习安排
小屋将在每日上午发放打卡题目包括
一道算法模版题帮助大家掌握常用算法套路根据算法模版精选一道对应的大厂笔试真题巩固算法应用
让我们一起直击笔试重点攻克常考题型 打卡小屋涉及题型
小屋从零基础出发涵盖笔试常考知识点
基础算法
自定义排序二分前缀和差分双指针
基础数据结构
栈 单调栈队列 单调队列并查集优先队列(堆)
搜索
DFS BFS 基础应用树的遍历基础图论
动态规划 贪心 数论
快速幂组合数质数 因数位运算基础动态规划常见贪心
