做网站一条龙,网页升级访问站,服饰网站建设目的,网站建设规划论文#x1f36d; 大家好这里是KK爱Coding #xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为近期的春秋招笔试题汇总#xff5e; #x1f4bb; ACM银牌#x1f948;| 多次AK大厂笔试 #xff5c; 编程一对一辅导 #x1f44f; 感谢大家的订阅➕ 和 喜欢#x1f… 大家好这里是KK爱Coding 一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为近期的春秋招笔试题汇总 ACM银牌| 多次AK大厂笔试 编程一对一辅导 感谢大家的订阅➕ 和 喜欢 KK这边最近正在收集近一年互联网各厂的笔试题汇总如果有需要的小伙伴可以关注后私信一下 KK领取会在飞书进行同步的跟新。 文章目录 01.K小姐的生日派对问题描述输入格式输出格式样例输入样例输出数据范围题解参考代码 02.LYA 的生日派对邀请函传递问题描述输入格式输出格式样例输入样例输出数据范围题解参考代码 03.LYA 的生日蛋糕订购问题描述输入格式输出格式样例输入样例输出数据范围题解参考代码 写在最后 KK这边最近正在收集近一年互联网各厂的笔试题汇总如果有需要的小伙伴可以关注后私信一下 KK领取会在飞书进行同步的跟新。 01.K小姐的生日派对
问题描述
K小姐即将迎来自己的生日,为了庆祝这一天,她邀请了许多朋友来参加生日派对。派对结束后,K小姐发现有一位朋友在派对上出现的次数超过了所有朋友总出现次数的一半。K小姐很想知道这位朋友是谁,你能帮助她找出这位神秘朋友吗?
输入格式
输入包含一行,为一个以逗号分隔的正整数列表,表示每位朋友的编号。编号范围为 1 1 1 到 100000 100000 100000,朋友总数不超过 1000 1000 1000。
输出格式
输出一个整数,表示出现次数超过总出现次数一半的朋友编号。如果不存在这样的朋友,则输出 0 0 0。
当朋友总数为偶数 n n n 时,超过总数一半意味着出现次数大于 n 2 \frac{n}{2} 2n;当朋友总数为奇数 n n n 时,超过总数一半意味着出现次数大于 n 1 2 \frac{n1}{2} 2n1。
样例输入
1,2,3,2,2样例输出
2数据范围 1 ≤ 1 \leq 1≤ 朋友编号 ≤ 100000 \leq 100000 ≤100000 1 1 1 朋友总数 1000 1000 1000
题解
本题可以使用模拟的方法求解。我们可以用一个数组 c n t cnt cnt 来记录每个朋友出现的次数,然后遍历这个数组,判断是否存在出现次数超过总出现次数一半的朋友。
具体步骤如下:
初始化一个长度为 100001 100001 100001 的数组 c n t cnt cnt,用于记录每个朋友出现的次数。读入朋友编号序列,对于每个编号 x x x,将 c n t [ x ] cnt[x] cnt[x] 的值加 1 1 1,同时累加朋友总数 t o t a l total total。计算出现次数的临界值 h a l f half half,即 ⌊ t o t a l 2 ⌋ \lfloor \frac{total}{2} \rfloor ⌊2total⌋。遍历数组 c n t cnt cnt,判断是否存在某个元素的值大于 h a l f half half,如果存在则输出对应的朋友编号,否则输出 0 0 0。
时间复杂度为 O ( n ) O(n) O(n),其中 n n n 为朋友总数。空间复杂度为 O ( m ) O(m) O(m),其中 m m m 为朋友编号的范围。
参考代码
Python
friends list(map(int, input().split(,)))
cnt [0] * 100001
total 0for x in friends:cnt[x] 1total 1half total // 2for i in range(1, 100001):if cnt[i] half:print(i)exit(0)print(0)Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);String[] input sc.nextLine().split(,);int[] cnt new int[100001];int total 0;for (String x : input) {int num Integer.parseInt(x);cnt[num];total;}int half total / 2;for (int i 1; i 100000; i) {if (cnt[i] half) {System.out.println(i);return;}}System.out.println(0);}
}Cpp
#include iostream
using namespace std;const int MAXN 100001;int main() {int cnt[MAXN] {0};int total 0;string input;getline(cin, input);int pos 0;while (pos input.size()) {int num 0;while (pos input.size() input[pos] ! ,) {num num * 10 (input[pos] - 0);pos;}cnt[num];total;pos;}int half total / 2;for (int i 1; i MAXN; i) {if (cnt[i] half) {cout i endl;return 0;}}cout 0 endl;return 0;
}02.LYA 的生日派对邀请函传递
问题描述
LYA 正在筹备自己的生日派对,她邀请了公司里的许多同事。为了方便传递邀请函,LYA 决定采用一种特殊的方式:当一位同事收到邀请函后,如果 TA 所在的部门在允许传递的部门列表中,就将邀请函传递给周围(上、下、左、右)的同事;否则,就不再传递。
公司的办公室可以看作一个 n × m n \times m n×m 的网格,每个格子代表一个工位。LYA 的工位位于 ( x , y ) (x, y) (x,y),她会在这里开始传递邀请函。
给定办公室的布局、LYA 的工位坐标以及允许传递邀请函的部门列表,请问最终会有多少人收到邀请函?
输入格式
第一行包含两个整数 n n n 和 m m m,表示办公室的行数和列数。
接下来 n n n 行,每行包含 m m m 个整数,表示办公室的布局。每个整数代表该位置上同事所在的部门编号。
再接下来一行包含两个整数 x x x 和 y y y,表示 LYA 的工位坐标。
最后一行包含若干个整数,表示允许传递邀请函的部门列表,整数之间用空格隔开。
输出格式
输出一个整数,表示最终收到邀请函的人数。
样例输入
5 5
1 3 5 2 3
2 2 1 3 5
2 2 1 3 3
4 4 1 1 1
1 1 5 1 2
2 2
1样例输出
5数据范围 1 ≤ n , m ≤ 1000 1 \leq n, m \leq 1000 1≤n,m≤1000 1 ≤ 1 \leq 1≤ 部门编号 ≤ 50 \leq 50 ≤50 0 ≤ x n 0 \leq x n 0≤xn 0 ≤ y m 0 \leq y m 0≤ym 1 ≤ 1 \leq 1≤ 允许传递的部门数量 ≤ 50 \leq 50 ≤50
题解
本题可以使用 BFS 算法求解。从 LYA 的工位开始,将邀请函传递给周围的同事,如果这些同事所在的部门允许传递邀请函,就将他们加入队列中,并标记为已访问。不断从队列中取出同事,重复上述过程,直到队列为空。最终访问过的同事数量就是收到邀请函的人数。
具体步骤如下:
使用二维数组 g r i d grid grid 存储办公室的布局, g r i d [ i ] [ j ] grid[i][j] grid[i][j] 表示位置 ( i , j ) (i, j) (i,j) 上同事所在的部门编号。使用集合 a l l o w e d allowed allowed 存储允许传递邀请函的部门列表。使用二维数组 v i s vis vis 标记每个位置是否被访问过,初始时除了 LYA 的工位外,其余位置都未被访问。创建一个队列 q q q,将 LYA 的工位坐标 ( x , y ) (x, y) (x,y) 加入队列,并标记为已访问。初始化答案 a n s 0 ans 0 ans0,表示收到邀请函的人数。当队列不为空时,重复以下步骤: 从队列中取出一个位置 ( i , j ) (i, j) (i,j)。枚举 ( i , j ) (i, j) (i,j) 的四个相邻位置 ( n i , n j ) (ni, nj) (ni,nj): 如果 ( n i , n j ) (ni, nj) (ni,nj) 在网格范围内,且未被访问过,且 g r i d [ n i ] [ n j ] grid[ni][nj] grid[ni][nj] 在 a l l o w e d allowed allowed 中,则将 ( n i , n j ) (ni, nj) (ni,nj) 加入队列,标记为已访问,并将 a n s ans ans 加 1 1 1。 返回答案 a n s ans ans。
时间复杂度 O ( n m ) O(nm) O(nm),空间复杂度 O ( n m ) O(nm) O(nm)。其中 n n n 和 m m m 分别为办公室的行数和列数。
参考代码
Python
from collections import dequen int(input())
m int(input())
grid [list(map(int, input().split())) for _ in range(n)]
x, y map(int, input().split())
allowed set(map(int, input().split()))vis [[False] * m for _ in range(n)]
vis[x][y] Trueq deque([(x, y)])
ans 0while q:i, j q.popleft()for ni, nj in [(i1, j), (i-1, j), (i, j1), (i, j-1)]:if 0 ni n and 0 nj m and not vis[ni][nj] and grid[ni][nj] in allowed:vis[ni][nj] Trueq.append((ni, nj))ans 1print(ans)Java
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt(), m sc.nextInt();int[][] grid new int[n][m];for (int i 0; i n; i) {for (int j 0; j m; j) {grid[i][j] sc.nextInt();}}int x sc.nextInt(), y sc.nextInt();SetInteger allowed new HashSet();while (sc.hasNextInt()) {allowed.add(sc.nextInt());}boolean[][] vis new boolean[n][m];vis[x][y] true;Queueint[] q new LinkedList();q.offer(new int[]{x, y});int ans 0;int[][] dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};while (!q.isEmpty()) {int[] pos q.poll();int i pos[0], j pos[1];for (int[] dir : dirs) {int ni i dir[0], nj j dir[1];if (ni 0 ni n nj 0 nj m !vis[ni][nj] allowed.contains(grid[ni][nj])) {vis[ni][nj] true;q.offer(new int[]{ni, nj});ans;}}}System.out.println(ans);}
}Cpp
#include iostream
#include vector
#include queue
#include unordered_set
using namespace std;int main() {int n, m;cin n m;vectorvectorint grid(n, vectorint(m));for (int i 0; i n; i) {for (int j 0; j m; j) {cin grid[i][j];}}int x, y;cin x y;unordered_setint allowed;int dept;while (cin dept) {allowed.insert(dept);}vectorvectorbool vis(n, vectorbool(m, false));vis[x][y] true;queuepairint, int q;q.push({x, y});int ans 0;int dx[4] {1, -1, 0, 0};int dy[4] {0, 0, 1, -1};while (!q.empty()) {auto [i, j] q.front();q.pop();for (int k 0; k 4; k) {int ni i dx[k], nj j dy[k];if (ni 0 ni n nj 0 nj m !vis[ni][nj] allowed.count(grid[ni][nj])) {vis[ni][nj] true;q.push({ni, nj});ans;}}}cout ans endl;return 0;
}03.LYA 的生日蛋糕订购
问题描述
LYA 的生日快到了,她打算订购一个特别的生日蛋糕。蛋糕店提供了若干种口味的蛋糕,每种口味的蛋糕都有对应的卡路里。为了保持身材,LYA 希望蛋糕的总卡路里在一定范围内。
现在给定蛋糕店提供的各种口味蛋糕的卡路里,以及 LYA 希望的总卡路里范围,请问 LYA 有多少种选择方案?
注意:
每种口味的蛋糕可以选择任意多个。不同口味的蛋糕卡路里各不相同。
输入格式
第一行包含两个整数 l o w low low 和 h i g h high high,表示 LYA 希望的蛋糕总卡路里的下限和上限。
第二行包含若干个整数,表示蛋糕店提供的各种口味蛋糕的卡路里,整数之间用空格隔开。
输出格式
输出一个整数,表示 LYA 的选择方案数。
样例输入
350 500
100 200 500样例输出
7数据范围 1 ≤ l o w ≤ 1000 1 \leq low \leq 1000 1≤low≤1000 1 ≤ h i g h ≤ 1000 1 \leq high \leq 1000 1≤high≤1000 1 ≤ 1 \leq 1≤ 蛋糕种类数 ≤ 100 \leq 100 ≤100 100 ≤ 100 \leq 100≤ 每种蛋糕的卡路里 ≤ 1000 \leq 1000 ≤1000
题解
本题可以转化为一个完全背包问题。我们可以将蛋糕店提供的各种口味蛋糕看作物品,每种蛋糕的卡路里看作物品的重量,LYA 希望的总卡路里范围看作背包的容量范围。
定义 d p [ i ] dp[i] dp[i] 表示总卡路里恰好为 i i i 的方案数。初始时 d p 1 dp 1 dp1,表示不选任何蛋糕的方案数为 1 1 1。
对于每种蛋糕,我们可以选择任意多个。因此,对于第 j j j 种蛋糕,我们可以从 i c a l [ j ] ical[j] ical[j] 开始更新 d p dp dp 数组: d p [ i ] d p [ i ] d p [ i − c a l [ j ] ] dp[i] dp[i] dp[i-cal[j]] dp[i]dp[i]dp[i−cal[j]]
其中 c a l [ j ] cal[j] cal[j] 表示第 j j j 种蛋糕的卡路里。
最后,将 d p [ l o w ] dp[low] dp[low] 到 d p [ h i g h ] dp[high] dp[high] 的值累加起来,就得到了 LYA 的选择方案数。
时间复杂度 O ( n × h i g h ) O(n \times high) O(n×high),空间复杂度 O ( h i g h ) O(high) O(high)。其中 n n n 为蛋糕种类数, h i g h high high 为总卡路里上限。
参考代码
Python
low, high map(int, input().split())
cal list(map(int, input().split()))dp [0] * (high 1)
dp[0] 1for c in cal:for i in range(c, high 1):dp[i] dp[i - c]print(sum(dp[low:high1]))Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int low sc.nextInt();int high sc.nextInt();int n 0;while (sc.hasNextInt()) {n;sc.nextInt();}int[] cal new int[n];for (int i 0; i n; i) {cal[i] sc.nextInt();}long[] dp new long[high 1];dp[0] 1;for (int c : cal) {for (int i c; i high; i) {dp[i] dp[i - c];}}long ans 0;for (int i low; i high; i) {ans dp[i];}System.out.println(ans);}
}Cpp
#include iostream
#include vector
using namespace std;int main() {int low, high;cin low high;vectorint cal;int c;while (cin c) {cal.push_back(c);}vectorlong long dp(high 1, 0);dp[0] 1;for (int c : cal) {for (int i c; i high; i) {dp[i] dp[i - c];}}long long ans 0;for (int i low; i high; i) {ans dp[i];}cout ans endl;return 0;
}写在最后 KK这边最近正在收集近一年互联网各厂的笔试题汇总如果有需要的小伙伴可以关注后私信一下 KK领取会在飞书进行同步的跟新。
