2024年华为9月4日秋招笔试真题题解

2024年华为0904秋招笔试真题

    • 二叉树消消乐
    • 好友推荐系统
    • 维修工
      • 力扣上类似的题--K站中转内最便宜的航班

二叉树消消乐

题目描述

给定原始二叉树和参照二叉树(输入的二叉树均为满二叉树,二叉树节点的值范围为[1,1000],二叉树的深度不超过1000),现对原始二叉树和参照二叉树中相同层级目值相同的节点进行消除、消除规则为原始叉树和参照二叉树中存在多个值相同的节点只能消除等数量的、消除后的节点变为无效节点,请按节点值出现频率从高到低输出消除后原始二叉树中有效节点的值(如果原始二叉树消除后没有有效节点返回0)。

输入描述

原始二叉树中的节点个数
原始二叉树
参照二叉树中的节点个数
参照二叉树

输出描述

原始二叉树中有效节点的值,按出现频率从高到低排序(相同频率的值按大小排序),相同频率的值按降序排列。

用例输入

7
1 3 3 3 4 5 6
3
2 3 4

用例输出

36541

样例1解释:
原始二叉树A消除参照二叉树B中的重复元素后,有效节点剩余2个3,1个6,1个5,1个4,1个1,3出现的频率2,6、5、4、1出现的频率为1,按值从大到小排序、所以排序结果为36541。

求解思路

注意审题,题目明确指出这是一个满二叉树,因此我们不需要真的去构建一个二叉树,只需要利用满二叉树的性质去进行模拟求解就行。

需要注意的是,华为的命题人在写题面时候不够严谨,题面说二叉树的深度不超过1000,这显然是不现实的,毕竟这是满二叉树,如果深度达到几十上百的话,二叉树的节点数直接2的几百次方,显然这么大的数据哪怕O(n)的时间复杂度也过不了。因此只需要按照节点数为1e5的规模来设计算法即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100001;
int n, m;
int origin[maxn], refer[maxn];
vector<int>sum(maxn, 0);void dfs(int depth) {int start = pow(2, depth - 1), end = start + pow(2, depth - 1);if(start > n || start > m) return;map<int, int>mp1, mp2;for(int i = start; i < end; i++) {mp1[origin[i]]++;mp2[refer[i]]++;}for(auto i : mp1) {if(mp2[i.first] > i.second) sum[i.first] -= i.second;else sum[i.first] -= mp2[i.first];// cout << i.first << " " << sum[i.first] << endl;}dfs(depth + 1);
}bool cmp(pair<int, int>a, pair<int, int> b) {if(a.second != b.second) return a.second > b.second;return a.first > b.first;
}int main() {scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%d", &origin[i]);sum[origin[i]]++;}scanf("%d", &m);for(int i = 1; i <= m; i++) scanf("%d", &refer[i]);dfs(1);// for(int i = 1; i <= n; i++) cout << sum[origin[i]] << " ";// cout << endl;vector<pair<int, int>>v;set<int>s;for(int i = 1; i <= n; i++) s.insert(origin[i]);for(auto i : s) v.push_back(make_pair(i, sum[i]));// for(auto i : s) cout << i << " " << sum[i] << " " << endl;sort(v.begin(), v.end(), cmp);bool flag = false;for(auto i : v) {if(i.second != 0) {flag = true;printf("%d", i.first);} else break;}if(!flag) printf("0");return 0;
}
/*
15
5 8 8 8 7 7 7 6 6 9 9 7 7 5 6
7
5 6 6 7 7 8 8
*/

好友推荐系统

题目描述

你正在为一个社交网络平台开发好友推荐功能。

平台上有N个用户(每个用户使用1到N的整数编号),同时系统中维护了用户之间的好友关系。

为了推荐新朋友,平台决定采用“共同好友数量"作为衡量两个用户之间相似度的标准。

系统根据输入用户编号K,输出与此用户K相似度最高的前L个用户ID来推荐给用户K。

相似度定义:两个用户非好友,两个用户的相似度为拥有的共同好友数(例如用户A和用户B,只有共同好友C和D,相似度=2)

输入描述

第一行包含四个整数 N,M 、K和L,分别表示用户的数量(N),好友记录条数(M)、查询的用户编号(K)和推荐的好友数量(L)。接下来 M 行,每行包含两个整数编号X和Y,表示编号为X和Y用户是好友。

  1. 输入格式都是标准的,无需考虑输出异常场景(不会包含用户和自己是好友的输入,例如11)

  2. 用户数不超过1024,用户编码最大1024

  3. 好友记录数不超过10240

输出描述

根据输入K和L,输出和用户K相似度最高的L个用户编码。

  1. 输出相似度最高的前L个用户编码,按照相似度从高到低排序

  2. 如果有相似度相同的可能好友,按照用户编号从小到大排序

  3. 如果推荐的好友个效不足L个,则推荐与用户K无无共同好友关系的用户(陌生人)作为可能好友,如果推荐仍不满足L个用户,剩余推荐用户编码使用0来占位

用例输入

6 7 3 2
1 2
1 3
2 3
3 4
3 5
4 5
5 6

用例输出

6 0

输入包含了6个用户,7条好友记录,给用户ID编号为3的用户推荐2个好友。

输出只有编号为6的用户可能是编号3用户的可能好友;

尝试推荐与编号3用户无共同好友的其他用户,由于除编号为6的用户之外,其他用户和编号3用户都是好友,所以找不到陌生人作为推荐的第二个用户;

推荐结果不足2个用户,所以推荐的第二个用户编码使用0来占位补足。

求解思路

我们首先可以利用哈希表构建用户之间的好友关系,方便在O(1)的时间复杂度内查找两个用户之间是否是好友关系

然后排序遍历就可以得到推荐列表了

#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b) {if(a.second != b.second) return a.second > b.second;return a.first < b.first;
}
int main() {int N, M, K, L;scanf("%d %d %d %d", &N, &M, &K, &L);int x, y;int isf[1025][1025] = {0};for(int i = 0; i < M; i++) {scanf("%d%d", &x, &y);isf[x][y] = isf[y][x] = 1;}vector < pair<int, int> > sim;for(int i = 1; i <= N; i++) {if(i == K) continue;if(isf[K][i] != 1) {int cnt = 0;for(int j = 1; j <= N; j++) {if(i == j) continue;if(isf[K][j] == 1 && isf[i][j] == 1) cnt++;}sim.push_back(make_pair(i, cnt));}}sort(sim.begin(), sim.end(), cmp);int sum = 0;for(auto i : sim) {printf("%d ", i.first);sum++;}if(sum < L) {for(int i = sum; i < L; i++) printf("0 ");}return 0;
}

维修工

题目描述

维修工要给n个客户更换设备,为每个用户更换一个设备。维修工背包内最多装k个设备,如果背包里有设备可以直接前往下一个客户更换或回公司补充设备,没有则需要回公司取设备。这些客户有优先级,维修工需要按照优先级给客户更换设备,优先级level用数字表示,数字小的优先级高。维修工从公司出发,给n个客户更换设备,最后再返回公司。请计算维修工完成这项工作所需要经历的最短总距离是多少。维修工可以走斜线。

输入描述

第一行两个正整数 n,k(1≤k≤n≤2000),表示客户数和维修工背包容量。
第二行两个正整数 x,y ,用空格分隔(1 ≤ x , y ≤ 10^6),表示公司的坐标
接下来n行每行三个正整数 x i x_i xi, y i y_i yi, l e v e l i level_i leveli,用空格分隔(1≤ x i x_i xi, y i y_i yi≤10^6,1≤ l e v e l i level_i leveli<=n)。
( x i x_i xi, y i y_i yi)表示第i个客户的位置坐标, l e v e l i level_i leveli表示第 i i i个客户的优先级,保证所有客户优先级不同,客户和公司坐标不会重叠。

输出描述

输出最短总距离,结果四舍五入并保留一位小数,例如:9.0。

用例输入

3 2
1 1
3 1 1
1 2 2
3 2 3

用例输出

9.2

样例1解释:

从(1,1)->(3,1)->(1,1)->(1,2)->(3,2)->(1,1) = 2+2+1+2+√5 = 9.236

求解思路

题目的意思是维修工在维修完一家客户后,就会废掉背包内的一个设备(题面没讲清楚,一开始理解了好久背包内有设备为什么需要回公司取)。

因为本题规定了客户的优先级,因此我们首先将客户按照优先级进行排序。

接下来,我们可以按照记忆化搜索的方法,决定维修完当前客户后,到底回公司取设备再前往下一家客户还是直接去下一家客户维修。

我们采用memo数组记录每次的结果

memo[i + 1][k - 1] 表示回公司取完设备再前往下一家客户维修

memo[i + 1][j - 1] 表示背包内还有设备,直接前往下一家客户维修

#include<bits/stdc++.h>
using namespace std;double cal_dis(int x1, int y1, int x2, int y2) {return (double)sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}const int maxn = 2001;
int n, k, cx, cy;struct customer
{int x, y, level;bool operator < (const customer& other) const { return level < other.level; }
}p[maxn];/*
记忆化搜索,假设memo[i][j]表示维修完第i个客户,并且背包中还剩下j个设备。
*/
vector <vector<double>> memo(maxn, vector<double>(maxn, 0)); double dfs(int i, int j) {if(memo[i][j] > 0) return memo[i][j];double dis = cal_dis(p[i].x, p[i].y, cx, cy);double ans = 99999999999.0;if(i < n - 1) {ans = min(ans, dfs(i + 1, k - 1) + dis + cal_dis(p[i + 1]. x, p[i + 1].y, cx, cy));// cout << dis + cal_dis(p[i + 1]. x, p[i + 1].y, cx, cy) << endl;if(j > 0) {ans = min(ans, dfs(i + 1, j - 1) + cal_dis(p[i + 1].x, p[i + 1].y, p[i].x, p[i].y));// cout <<  cal_dis(p[i + 1].x, p[i + 1].y, p[i].x, p[i].y) << endl;}} else { // 如果是最后一家,则修完直接回公司ans = dis;}return memo[i][j] = ans;
}int main() {scanf("%d%d", &n, &k);scanf("%d%d", &cx, &cy);for(int i = 0; i < n; i++) scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].level);sort(p, p + n);dfs(0, k);double ans = dfs(0, k - 1) + cal_dis(p[0].x, p[0].y, cx, cy);printf("%.1f", ans);return 0;
}

维修工这个题是通过记忆化搜索求解最短路径的问题,想起之前在力扣上面刷到一个类似的题目,K站中转内最便宜的航班

题目链接

力扣上类似的题–K站中转内最便宜的航班

题目描述

n 个城市通过一些航班连接。给你一个数组 flights ,其中 flights[i] = [fromi, toi, pricei] ,表示该航班都从城市 fromi 开始,以价格 pricei 抵达 toi

现在给定所有的城市和航班,以及出发城市 src 和目的地 dst,你的任务是找到出一条最多经过 k 站中转的路线,使得从 srcdst价格最便宜 ,并返回该价格。 如果不存在这样的路线,则输出 -1

image-20240912141710328

image-20240912141914144

求解思路

和维修工一样,我们只需要利用记忆化搜索去寻找到第k个城市所需要的最少花费即可,注意k次中转的限制。

class Solution {
public:const int INF = 99999999;/*dp[i][j] 表示起点到城市i到达第j个城市的最少花费*/int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {vector <int> G[n]; // 构建邻接矩阵vector <vector<int>> price(n, vector<int>(n, INF));for(auto flight : flights) {G[flight[0]].push_back(flight[1]); price[flight[0]][flight[1]] = flight[2];}vector <vector<int>> dp(n, vector<int>(k + 2, 0));function<int(int, int)> dfs = [&](int i, int j) {if(dp[i][j] > 0) return dp[i][j];if(i == dst) {if(j <= k + 1) return dp[i][j];return INF;}int ans = INF;for(auto v : G[i]) {if(j < k + 1)ans = min(ans, dfs(v, j + 1) + price[i][v]);}return dp[i][j] = ans;};int ans = dfs(src, 0);return ans == INF ? -1 : ans;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/424775.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【信创】Linux上图形化多ping工具--gping的编译安装与打包 _ 统信 _ 麒麟 _ 方德

原文链接&#xff1a;【信创】图形化多ping工具gping的编译安装与打包 | 统信 | 麒麟 | 方德 Hello&#xff0c;大家好啊&#xff01;今天给大家带来一篇关于在Linux操作系统上使用gping的文章。gping是一款非常实用的命令行工具&#xff0c;它将传统的ping命令进行了可视化改进…

『功能项目』切换职业面板【48】

我们打开上一篇47技能冷却蒙版的项目&#xff0c; 本章要做的事情是切换职业UI面板的功能 首先双击打开Canvas预制体在左上主角面板信息中新建一个button按钮 重命名&#xff08;父物体是按钮Button&#xff0c;子物体Image即可&#xff09; 创建一个Image 设计一下布局 复制三…

窗口嵌入桌面背景层(vb.net,高考倒计时特供版)

开发思路 根据系统生成高考倒计时的具体时间&#xff0c;附加江苏省省统考的时间生成算法&#xff0c;并且用户可以根据实际情况调整前后30天&#xff0c;具有丰富多彩的图片库和强大的自定义功能&#xff0c;效果图见P3 目前程序处于正式版的1.4版本&#xff0c;本程序由本作…

supermap Iclient3d for cesium加载地形并夸大地形

先看效果图 这是没有夸张之前的都江堰 这是夸大五倍后的都江堰 下面展示代码 主要就是加载supermaponline的skt地形然后夸大 <template><div class"PartOneBox"><div id"cesiumContainer"></div></div> </template>…

个人随想-向量数据库,你到底应该选择谁?

随着大模型的新起&#xff0c;vectorstore这1、2年也非常的火。从以前只能用chroma到现在几十种向量数据库&#xff0c;选都选不过来。 以我接触过的很多公司来说&#xff0c;他们去选择向量数据库的时候&#xff0c;很多都和迷茫&#xff0c;不知道应该选择哪个向量数据库&am…

自动驾驶自动泊车场景应用总结

自动泊车技术是当前智能驾驶技术的一个重要分支,其目标是通过车辆自身的感知、决策和控制系统,实现车辆在有限空间内的自主泊车操作。目前自动泊车可分为半自动泊车、全自动泊车、记忆泊车、自主代客泊车四种产品形态,其中, 根据搭载传感器和使用场景的不同,全自动泊车又可…

文本到3D生成

文本到3D生成是一种通过文本描述直接创建三维数字模型的技术。这种技术能够将语言描述转换成可视化的三维模型&#xff0c;使得内容创作者和设计师可以直接从概念阶段跳转到三维可视化&#xff0c;大大加快创作流程并提供更直观的设计和修改过程。 该技术的核心应用之一是基于…

无人直播好帮手,视频指定词语消音,消除违禁词,直播视频录制,音视频分离,分段

1.视频消音功能 一键删除或者静音视频中的词语 2.直播视频录制功能 可同时录制多个平台,多个主播,没有数量限制 3.音视频转码 支持多种音视频格式转换 4.视频频分离 分离视频中的音频和视频 5.视频合并分割 合并和按时间分割视屏 目前正在测试中…如有需要可以先使…

Netty笔记07-粘包与半包(上)

文章目录 前言1. 粘包造成粘包的原因解决粘包的方法 2. 半包造成半包的原因解决半包的方法 粘包现象服务端代码示例客户端代码示例 半包现象现象分析粘包半包滑动窗口MSS 限制Nagle 算法 前言 粘包和半包问题是网络编程中常见的问题&#xff0c;特别是在TCP协议中。通过合理的设…

[Postman]接口自动化测试入门

文章大多用作个人学习分享&#xff0c;如果大家觉得有不足或错漏的地方欢迎评论指出或补充 此文章将完整的走一遍一个web页面的接口测试流程 大致路径为&#xff1a; 创建集合->调用接口登录获取token->保存token->带着token去完成其他接口的自动化测试->断言-&g…

✔2848. 与车相交的点

代码实现&#xff1a; 方法一&#xff1a;哈希表 #define fmax(a, b) ((a) > (b) ? (a) : (b))int numberOfPoints(int **nums, int numsSize, int *numsColSize) {int hash[101] {0};int max 0;for (int i 0; i < numsSize; i) {max fmax(max, nums[i][1]);for …

【人工智能】AI创业的前沿思考 | 从垂直领域到通用智能模型AGI的崛起

写在前面&#xff1a; &#x1f31f; 欢迎光临 清流君 的博客小天地&#xff0c;这里是我分享技术与心得的温馨角落。&#x1f4dd; 个人主页&#xff1a;清流君_CSDN博客&#xff0c;期待与您一同探索 移动机器人 领域的无限可能。 &#x1f50d; 本文系 清流君 原创之作&…

Golang协程泄漏定位和排查

Golang协程泄漏定位和排查 1 场景&#xff1a;无缓冲channel写阻塞2 排查和定位思路2.1 Golang pprof2.2 协程数监控2.3 操作系统内存泄漏 参考 1 场景&#xff1a;无缓冲channel写阻塞 package mainimport ("log""net/http"_ "net/http/pprof"…

PPT中的图形与图片:插入、调整与格式设置技术详解

目录 引言 一、图形与图片的插入 1. 插入图形 2. 插入图片 二、图形与图片的调整 1. 调整大小与位置 2. 裁剪与旋转 3. 图形与图片的合并与组合 三、图片格式与布局设置 1. 图片格式设置 2. 图片布局设置 示例案例&#xff1a;制作产品展示PPT 四、结论 引言 在现…

【OJ刷题】双指针问题4

这里是阿川的博客&#xff0c;祝您变得更强 ✨ 个人主页&#xff1a;在线OJ的阿川 &#x1f496;文章专栏&#xff1a;OJ刷题入门到进阶 &#x1f30f;代码仓库&#xff1a; 写在开头 现在您看到的是我的结论或想法&#xff0c;但在这背后凝结了大量的思考、经验和讨论 目录 1…

(CVPR-2022)感知优先的扩散模型训练

感知优先的扩散模型训练 Paper Title&#xff1a;Perception Prioritized Training of Diffusion Models Paper是首尔国立大学数据科学与人工智能实验室发表在CVPR 2022的工作 论文地址 Code地址 Abstract 扩散模型通过优化相应损失项的加权和&#xff08;即去噪得分匹配损失&…

IEEE 754浮点数表示

浮点数组成 以单精度浮点数(32位)为例说明&#xff1a; 十进制浮点数组成&#xff1a; 十进制基数(base)为10 二进制浮点数组成&#xff1a; 二进制基数(base)为2 以IEEE 754标准表示十进制数&#xff1a; ( 7.625 ) 10 (7.625)_{10} (7.625)10​&#xff0c;先将其转成…

一,掌心里的智慧:我的 TinyML 学习之旅

从云端到掌心&#xff1a;TinyML 的故事 想象一下&#xff0c;有一天你起床&#xff0c;伸手去关闭窗边的小闹钟&#xff0c;却发现这个小家伙已经提前预判到你的醒来时间——因为它能够“听到”你昨晚的呼吸变化&#xff0c;分析出你什么时候会醒。这个场景可能听起来像科幻小…

网络编程基础概述

文章目录 协议网络协议栈(osi)局域网IPIP和Mac地址端口号TCP和UDP网络字节序 协议 (网络协议的)意义:为了让计算机传输之间将信息正确传输给目标机器 不同系统之间能接入网络是因为定制了一套通用的协议以便支持不同系统间的网络通信 1.网络通信的问题: 将数据可靠的从A传给B a…

什么是 SMB 服务器以及它如何工作?

在本文中&#xff0c;您将了解 SMB 服务器以及它们如何促进网络文件共享。 我们将介绍它们的基本功能、主要特性以及如何安全地设置它们。无论您是新手还是需要复习&#xff0c;本指南都将帮助您更好地了解 SMB 服务器。 什么是 SMB 服务器&#xff1f; SMB&#xff08;服务器…