算法题--华为od机试考试(开源项目热度榜单、API集群负载统计、分月饼)

本文主要是介绍算法题--华为od机试考试(开源项目热度榜单、API集群负载统计、分月饼),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

开源项目热度榜单

题目描述

输入描述

输出描述

示例1

输入

输出

解析

答案

API集群负载统计

题目描述

输入描述

输出描述

示例1

输入

输出

解析

答案

分月饼

题目描述

输入描述

输出描述

示例1

输入

输出

说明

示例2

输入

输出

说明

示例3

输入

输出

说明

解析

答案


开源项目热度榜单

考察排序

题目描述

某个开源社区希望将最近热度比较高的开源项目出一个榜单,推荐给社区里面的开发者对于每个开源项目,开发者可以进行关注 (watch) 、收藏(star) 、fork、提issue、提交合并请求 (MR)等。

数据库里面统计了每个开源项目关注、收藏、fork、issue、MR的数量,开源项目的热度根据这5个维度的加权求和进行排序。

H = W(watch) x #watch + W(star) x #star + W(fork) x #fork + W(issue) x #issue + W(mr) x #mr

H 表示热度值 W(watch)、W(star)、W(fork)、W(issue)、W(mr) 分别表示5个统计维度的权重。#watch、#star、#fork、#issue、#mr 分别表示5个统计维度的统计值.

榜单按照热度值降序排序,对于热度值相等的,按照项目名字转换为全小写字母后的字典序排序(a,b,c...x,y,z)。

输入描述

第一行输入为N,表示开源项目的个数,0 < N <100。

第二行输入为权重值列表,一共 5 个整型值,分别对应关注、收藏、fork、issue、MR的权重,权重取值 0< W<= 50。

第三行开始接下来的N行为开源项目的统计维度,每一行的格式为: name nr_watch nr_start nr_fork nr_issue nr_mr。其中name为开源项目的名字,由英文字。

输出描述

排序后的项目名字。

示例1

输入

4

8 6 2 8 6

camila 66 70 46 158 80

victoria 94 76 86 189 211

anthony 29 17 83 21 48

emily 53 97 1 19 218

输出

victoria camila emily anthony

解析

先让每个项目通过字母排序,然后再通过热度值排序即可。

字母排序可以通过将比较的两个单词补全到相同长度,然后将每一位对应的权重设置为>24,然后计算单词对应的数值进行相减即可。这样可以避免每一位依次比较。

答案

function sortTopProj(str) {let arr = str.split('\n')arr.shift()let [watch, star, fork, issue, mr] = arr.shift().split(' ').map(Number)arr = arr.map(v => {v = v.split(' ')let res = {}res.value = v.shift()res.num = v[0] * watch + v[1] * star + v[2] * fork + v[3] * issue + v[4] * mrreturn res})arr.sort(compareWord)arr.sort((a, b) => b.num - a.num)return arr.map(v => v.value).join(' ')
}
function compareWord({ value: a }, { value: b }) {let len = Math.max(a.length, b.length)a = a.padEnd(len, 'a')b = b.padEnd(len, 'a')// 将每一位对应的权重设置为100,然后计算补全后的单词对应的数值,例如abc=》1*100**2+2*100**1+3*100**0a = a.split('').reverse().reduce((t, v, i) => t = t + (v.charCodeAt() - 96) * 100 ** i, 0)b = b.split('').reverse().reduce((t, v, i) => t = t + (v.charCodeAt() - 96) * 100 ** i, 0)return a - b
}
console.log(sortTopProj(`4
8 6 2 8 6
camila 66 70 46 158 80
victoria 94 76 86 189 211
anthony 29 17 83 21 48
emily 53 97 1 19 218`))

 

API集群负载统计

考察数组操作

题目描述

某个产品的RESTful API集合部署在服务器集群的多个节点上,近期对客户端访问日志进行了采集,需要统计各个API的访问频次,

根据热点信息在服务器节点之间做负载均衡,现在需要实现热点信息统计查询功能。

RESTful API是由多个层级构成,层级之间使用 / 连接,如 /A/B/C/D 这个地址,A属于第一级,B属于第二级,C属于第三级,D属于第四级。

现在负载均衡模块需要知道给定层级上某个名字出现的频次,未出现过用0表示,实现这个功能。

输入描述

第一行为N,表示访问历史日志的条数,0 < N ≤ 100。

接下来N行,每一行为一个RESTful API的URL地址,约束地址中仅包含英文字母和连接符 / ,最大层级为10,每层级字符串最大长度为10。

最后一行为层级L和要查询的关键字。

输出描述

输出给定层级上,关键字出现的频次,使用完全匹配方式(大小写敏感)。

示例1

输入

5

/com/cheese/no/pop

/lai/cheese

/apple

/cat/cloud/no/one

/la/apple/no/hot

2 cheese

输出

2

解析

通过/分割每个url地址,取出每一个的目标层级位,进行判断是否和关键字相等。

答案

function getWordNum(str) {let arr = str.split('\n')arr.shift()let [n, word] = arr.pop().split(' ')arr = arr.map(v => v.split('/'))let sum = 0arr.forEach(v => {if (v?.[n] === word) {sum++}})return sum
}
console.log(getWordNum(`5
/com/cheese/no/pop
/lai/cheese
/apple
/cat/cloud/no/one
/la/apple/no/hot
2 cheese`))

分月饼

考察深度遍历、递归。

题目描述

中秋节,公司分月饼,m个员工,买了n个月饼,m<=n,每个员工至少分1个月饼,但可以分多个,单人分到最多月饼的个数是Max1,

单人分到第二多月饼个数是Max2,Max1-Max2 <= 3,单人分到第n-1多月饼个数是Max(n-1),

单人分到第n多月饼个数是Max(n),Max(n-1) – Max(n) <= 3, 问有多少种分月饼的方法?

输入描述

每一行输入m n,表示m个员工,n个月饼,m<=n

输出描述

输出有多少种月饼分法

示例1

输入

2 4

输出

2

说明

分法有2种

4=1+3

4=2+2

注意:1+3和3+1算一种分法

示例2

输入

3 5

输出

2

说明

5=1+1+3

5=1+2+2

示例3

输入

3 12

输出

6

说明

满足要求的有6种分法:

12=1+1+10(Max1=10,Max2=1,不满足要求)

12=1+2+9(Max1=9, Max2=2, 不满足要求)

12=1+3+8(Max1=8, Max2=3, 不满足要求)

12=1+4+7(Max1=7, Max2=4, Max3=1,满足要求)

12=1+5+6(Max1=6, Max2=5, Max3=1,不满足要求)

12=2+2+8(Max1=8, Max2=2, 不满足要求)

12=2+3+7(Max1=7, Max2=3, 不满足要求)

12=2+4+6(Max1=6, Max2=4, Max3=2, 满足要求)

12=2+5+5(Max1=5, Max2=2,满足要求)

12=3+3+6(Max1=6, Max2=3, 满足要求)

12=3+4+5(Max1=5, Max2=4, Max3=3,满足要求)

12=4+4+4(Max1=4, 满足要求)

解析

首先我们需要从第一个员工开始分配,由于示例1中1+3和3+1算一种分法,所以我们可以假设从序号0到序号m-1个员工拿到的月饼为一个递增的序列。

然后相邻的每个员工有一个限制条件,拿到月饼的范围,故可以得出函数的参数f(index,sum,down,up)表示序号为index的员工,sum为剩余的月饼数,

down和up表示当前员工可以拿月饼的范围。

找到f(index,sum,down,up)=f(index+1,sum-i,i,Math.min(i+3,sum-i)),其中i从down到up循环,表示为index员工拿到的月饼数。

找终点。

    1.当index和m相等时,表示已经分配完了所有元,如果不剩月饼,此时应该把符合条件的分法加一。

    2. 剩余的月饼不足以分配||无剩余月饼||月饼的下限大于上限

答案

function getDispatchWay(m, n) {let res = 0; dfs(0, n, 1, n);  // u表示当前员工的索引,sum表示剩余的月饼数,down和up表示当前员工分到的月饼数量的下限和上线function dfs(index, sum, down, up) {  if (index === m) {  // 如果u等于mif (sum === 0) {  // 如果sum等于0res++;  // 结果加一}return;  }// 剩余的月饼不足以分配||无剩余月饼||月饼的下限大于上限if (down > sum || sum < 0 || down > up) { return;  }// 当前序号的员工发放了i个月饼for (let i = down; i <= up; i++) {  // 下一个员工分到月饼的上限不能大于剩余的月饼数或当前员工的月饼数量+3取最小值dfs(index + 1, sum - i, i, Math.min(sum - i, i + 3));  }}return res
}
console.log(getDispatchWay(2, 4))
console.log(getDispatchWay(3, 5))
console.log(getDispatchWay(3, 12))

这篇关于算法题--华为od机试考试(开源项目热度榜单、API集群负载统计、分月饼)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

如何在Spring Boot项目中集成MQTT协议

《如何在SpringBoot项目中集成MQTT协议》本文介绍在SpringBoot中集成MQTT的步骤,包括安装Broker、添加EclipsePaho依赖、配置连接参数、实现消息发布订阅、测试接口... 目录1. 准备工作2. 引入依赖3. 配置MQTT连接4. 创建MQTT配置类5. 实现消息发布与订阅

在Linux终端中统计非二进制文件行数的实现方法

《在Linux终端中统计非二进制文件行数的实现方法》在Linux系统中,有时需要统计非二进制文件(如CSV、TXT文件)的行数,而不希望手动打开文件进行查看,例如,在处理大型日志文件、数据文件时,了解... 目录在linux终端中统计非二进制文件的行数技术背景实现步骤1. 使用wc命令2. 使用grep命令

springboot项目打jar制作成镜像并指定配置文件位置方式

《springboot项目打jar制作成镜像并指定配置文件位置方式》:本文主要介绍springboot项目打jar制作成镜像并指定配置文件位置方式,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录一、上传jar到服务器二、编写dockerfile三、新建对应配置文件所存放的数据卷目录四、将配置文

怎么用idea创建一个SpringBoot项目

《怎么用idea创建一个SpringBoot项目》本文介绍了在IDEA中创建SpringBoot项目的步骤,包括环境准备(JDK1.8+、Maven3.2.5+)、使用SpringInitializr... 目录如何在idea中创建一个SpringBoot项目环境准备1.1打开IDEA,点击New新建一个项

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题?(与哨兵模

SpringBoot连接Redis集群教程

《SpringBoot连接Redis集群教程》:本文主要介绍SpringBoot连接Redis集群教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 依赖2. 修改配置文件3. 创建RedisClusterConfig4. 测试总结1. 依赖 <de

HTML5 getUserMedia API网页录音实现指南示例小结

《HTML5getUserMediaAPI网页录音实现指南示例小结》本教程将指导你如何利用这一API,结合WebAudioAPI,实现网页录音功能,从获取音频流到处理和保存录音,整个过程将逐步... 目录1. html5 getUserMedia API简介1.1 API概念与历史1.2 功能与优势1.3

springboot项目中整合高德地图的实践

《springboot项目中整合高德地图的实践》:本文主要介绍springboot项目中整合高德地图的实践,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一:高德开放平台的使用二:创建数据库(我是用的是mysql)三:Springboot所需的依赖(根据你的需求再