【华为笔试题汇总】2024-04-10-华为春招笔试题(第二套)-三语言题解(CPP/Python/Java)

2024-04-12 16:36

本文主要是介绍【华为笔试题汇总】2024-04-10-华为春招笔试题(第二套)-三语言题解(CPP/Python/Java),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

🍭 大家好这里是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{n+1}{2} 2n+1

样例输入

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 来记录每个朋友出现的次数,然后遍历这个数组,判断是否存在出现次数超过总出现次数一半的朋友。

具体步骤如下:

  1. 初始化一个长度为 100001 100001 100001 的数组 c n t cnt cnt,用于记录每个朋友出现的次数。
  2. 读入朋友编号序列,对于每个编号 x x x,将 c n t [ x ] cnt[x] cnt[x] 的值加 1 1 1,同时累加朋友总数 t o t a l total total
  3. 计算出现次数的临界值 h a l f half half,即 ⌊ t o t a l 2 ⌋ \lfloor \frac{total}{2} \rfloor 2total
  4. 遍历数组 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 1n,m1000
  • 1 ≤ 1 \leq 1 部门编号 ≤ 50 \leq 50 50
  • 0 ≤ x < n 0 \leq x < n 0x<n
  • 0 ≤ y < m 0 \leq y < m 0y<m
  • 1 ≤ 1 \leq 1 允许传递的部门数量 ≤ 50 \leq 50 50

题解

本题可以使用 BFS 算法求解。从 LYA 的工位开始,将邀请函传递给周围的同事,如果这些同事所在的部门允许传递邀请函,就将他们加入队列中,并标记为已访问。不断从队列中取出同事,重复上述过程,直到队列为空。最终访问过的同事数量就是收到邀请函的人数。

具体步骤如下:

  1. 使用二维数组 g r i d grid grid 存储办公室的布局, g r i d [ i ] [ j ] grid[i][j] grid[i][j] 表示位置 ( i , j ) (i, j) (i,j) 上同事所在的部门编号。
  2. 使用集合 a l l o w e d allowed allowed 存储允许传递邀请函的部门列表。
  3. 使用二维数组 v i s vis vis 标记每个位置是否被访问过,初始时除了 LYA 的工位外,其余位置都未被访问。
  4. 创建一个队列 q q q,将 LYA 的工位坐标 ( x , y ) (x, y) (x,y) 加入队列,并标记为已访问。
  5. 初始化答案 a n s = 0 ans = 0 ans=0,表示收到邀请函的人数。
  6. 当队列不为空时,重复以下步骤:
    • 从队列中取出一个位置 ( 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
  7. 返回答案 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 [(i+1, j), (i-1, j), (i, j+1), (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();Set<Integer> allowed = new HashSet<>();while (sc.hasNextInt()) {allowed.add(sc.nextInt());}boolean[][] vis = new boolean[n][m];vis[x][y] = true;Queue<int[]> 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;vector<vector<int>> grid(n, vector<int>(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_set<int> allowed;int dept;while (cin >> dept) {allowed.insert(dept);}vector<vector<bool>> vis(n, vector<bool>(m, false));vis[x][y] = true;queue<pair<int, 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 有多少种选择方案?

注意:

  1. 每种口味的蛋糕可以选择任意多个。
  2. 不同口味的蛋糕卡路里各不相同。

输入格式

第一行包含两个整数 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 1low1000
  • 1 ≤ h i g h ≤ 1000 1 \leq high \leq 1000 1high1000
  • 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 dp=1,表示不选任何蛋糕的方案数为 1 1 1

对于每种蛋糕,我们可以选择任意多个。因此,对于第 j j j 种蛋糕,我们可以从 i = c a l [ j ] i=cal[j] i=cal[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[ical[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:high+1]))
  • 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;vector<int> cal;int c;while (cin >> c) {cal.push_back(c);}vector<long 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领取,会在飞书进行同步的跟新。

在这里插入图片描述

这篇关于【华为笔试题汇总】2024-04-10-华为春招笔试题(第二套)-三语言题解(CPP/Python/Java)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/897665

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技