华为OD算法

【华为OD机考 统一考试机试C卷】开源项目热度榜单

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

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

H = (Wwatch * #watch) + (Wstar * #star) + (Wfork * #fork) + (Wissue * #issue) + (Wmr * #mr)

H表示热度值

Wwatch、Wstar、Wfork、Wissue、Wmr分别表示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 为开源项目的名字，由英文字母组成，长度 ≤ 50，其余 5 个整型值分别为该开源项目关注、收藏、fork、issue、MR的数量，数量取值 0 < nr ≤ 1000。

输出描述
按照热度降序，输出开源项目的名字，对于热度值相等的，按照项目名字转换为全小写后的字典序排序（‘a’ > ‘b’ > ‘c’ > … > ‘x’ > ‘y’ > ‘z’）。

字符串序列判定/最后一个有效字符

题目描述：字符串序列判定/最后一个有效字符
输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。判定S是否是L的有效子串。

判定规则：

S中的每个字符在L中都能找到（可以不连续），

且S在Ｌ中字符的前后顺序与S中顺序要保持一致。

（例如，S=”ace”是L=”abcde”的一个子序列且有效字符是a、c、e，而”aec”不是有效子序列，且有效字符只有a、e）

输入描述
输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。

先输入S，再输入L，每个字符串占一行。

输出描述
输出S串最后一个有效字符在L中的位置。（首位从0开始计算，无有效字符返回-1）

山脉的个数(本题分值100)

题目描述：注意：本题为Lettcode模式，不需要处理输入。本题为已经考过的同学回忆版，题目描述可能与真实机考不一定，但本意和原题一直，且通过率为100%。

给一个数组，判断山峰的个数。数据每个元素的值代表海拔高度。0表示平地。数值越高，海拔越高。数组的起始和末尾如果符合条件，也算山峰。

输入描述
输入为一个整型数组

输出描述
输出山峰的个数

构成指定长度字符串的个数 (本题分值100)

题目描述:
输入一个字符串 和 一个数字。求输出用字符串里字符构成指定长度字符串的个数，构成的字符串不同，且每个字符串相邻字符串不能相同

输入描述
输入一行，字符串 长度

输出描述
指定长度字符串的个数

题目描述：用连续自然数之和来表达整数 （本题分值100）

一个整数可以由连续的自然数之和来表示。 给定一个整数，计算该整数有几种连续自然数之和的表达式，且打印出每种表达式

输入描述
一个目标整数T (1 <=T<= 1000)

输出描述
该整数的所有表达式和表达式的个数。如果有多种表达式，输出要求为： 自然数个数最少的表达式优先输出 每个表达式中按自然数递增的顺序输出，具体的格式参见样例。 在每个测试数据结束时，输出一行”Result:X”，其中X是最终的表达式个数。

密码输入检测

题目描述：密码输入检测（本题分值100）
给定用户密码输入流input，输入流中字符’<'表示退格，可以清除前一个输入的字符，请你编写程序，输出最终得到的密码字符，并判断密码是否满足如下的密码安全要求。

密码安全要求如下：

1.密码长度>=8; 2.密码至少需要包含1个大写字母; 3.密码至少需要包含1个小写字母; 4.密码至少需要包含1个数字; 5.密码至少需要包含1个字母和数字以外的非空白特殊字符 注意空串退格后仍然为空串，且用户输入的字符串不包含‘<’字符和空白字符。

输入描述
用一行字符串表示输入的用户数据，输入的字符串中‘<’字符标识退格，用户输入的字符串不包含空白字符，例如：ABC<c89%000<

输出描述
输出经过程序处理后，输出的实际密码字符串，并输出改密码字符串是否满足密码安全要求。两者间由‘,’分隔， 例如：ABc89%00,true

查找众数及中位数

题目描述：查找众数及中位数（本题分值100）
众数是指一组数据中出现次数量多的那个数，众数可以是多个。 中位数是指把一组数据从小到大排列，最中间的那个数，如果这组数据的个数是奇数，那最中间那个就是中位数，如果这组数据的个数为偶数，那就把中间的两个数之和除以2，所得的结果就是中位数。 查找整型数组中元素的众数并组成一个新的数组，求新数组的中位数。

输入描述
输入一个一维整型数组，数组大小取值范围 0<N<1000，数组中每个元素取值范围 0<E<1000

输出描述
输出众数组成的新数组的中位数

用例
输入

10 11 21 19 21 17 21 16 21 18 15

输出21

输入2 1 5 4 3 3 9 2 7 4 6 2 15 4 2 4

输出3

输入5 1 5 3 5 2 5 5 7 6 7 3 7 11 7 55 7 9 98 9 17 9 15 9 9 1 39

输出7

最长的指定瑕疵度的元音子串

题目描述
开头和结尾都是元音字母（aeiouAEIOU）的字符串为元音字符串，其中混杂的非元音字母数量为其瑕疵度。比如:

“a” 、 “aa”是元音字符串，其瑕疵度都为0

“aiur”不是元音字符串（结尾不是元音字符）

“abira”是元音字符串，其瑕疵度为2

给定一个字符串，请找出指定瑕疵度的最长元音字符子串，并输出其长度，如果找不到满足条件的元音字符子串，输出0。

子串：字符串中任意个连续的字符组成的子序列称为该字符串的子串。

输入描述
首行输入是一个整数，表示预期的瑕疵度flaw，取值范围[0, 65535]。

接下来一行是一个仅由字符a-z和A-Z组成的字符串，字符串长度(0, 65535]。

输出描述
输出为一个整数，代表满足条件的元音字符子串的长度。

整数对最小和

题目描述：整数对最小和（分值100）
给定两个整数数组array1、array2，数组元素按升序排列。

假设从array1、array2中分别取出一个元素可构成一对元素，现在需要取出k对元素，

并对取出的所有元素求和，计算和的最小值。

注意：

两对元素如果对应于array1、array2中的两个下标均相同，则视为同一对元素。

输入描述
输入两行数组array1、array2，每行首个数字为数组大小size(0 < size <= 100);

0 < array1[i] <= 1000

0 < array2[i] <= 1000

接下来一行为正整数k

0 < k <= array1.size() * array2.size()

输出描述
满足要求的最小和

找出作弊的人

题目描述:
公司组织了一次考试,现在考试结果出来了，想看一下有没人存在作弊行为,但是员工太多了,需要先对员工进行一次过滤,再进一步确定是否存在作弊行为。

过滤的规则为:找到分差最小的员工ID对(p1,p2)列表,要求p1<p2

员工个数取值范国:O<n<100000

员工ID为整数,取值范围:0<=n<=100000

考试成绩为整数,取值范围:0<=score<=300
输入描述
员工的ID及考试分数
输出描述
分差最小的员工ID对(p1,p2)列表,要求p1<p2。每一行代表一个集合,每个集合内的员工ID按顺序排列,多行结果也以员工对中p1值大小升序排列(如果p1相同则p2升序)。

环中最长子串/字符成环找偶数O

题目描述
在一个大型体育场内举办了一场大型活动，由于疫情防控的需要，要求每位观众的必须间隔至少一个空位才允许落座。

现在给出一排观众座位分布图，座位中存在已落座的观众，请计算出，在不移动现有观众座位的情况下，最多还能坐下多少名观众。

输入描述
一个数组，用来标识某一排座位中，每个座位是否已经坐人。0表示该座位没有坐人，1表示该座位已经坐人。

1 ≤ 数组长度 ≤ 10000

输出描述
整数，在不移动现有观众座位的情况下，最多还能坐下多少名观众。

转盘寿司

题目描述
寿司店周年庆，正在举办优惠活动回馈新老客户。
寿司转盘上总共有 n 盘寿司，prices[i] 是第 i 盘寿司的价格，
如果客户选择了第 i 盘寿司，寿司店免费赠送客户距离第 i 盘寿司最近的下一盘寿司 j，前提是 prices[j] < prices[i]，如果没有满足条件的 j，则不赠送寿司。
每个价格的寿司都可无限供应。
输入描述
输入的每一个数字代表每盘寿司的价格，每盘寿司的价格之间使用空格分隔，例如:
3 15 6 14
表示：
第 0 盘寿司价格 prices[0] 为 3
第 1 盘寿司价格 prices[1] 为 15
第 2 盘寿司价格 prices[2] 为 6
第 3 盘寿司价格 prices[3] 为 14
寿司的盘数 n 范围为：1 ≤ n ≤ 500

每盘寿司的价格 price 范围为：1 ≤ price ≤ 1000
输出描述
输出享受优惠后的一组数据，每个值表示客户选择第 i 盘寿司时实际得到的寿司的总价格。使用空格进行分隔，例如：

3 21 9 17

找朋友

题目描述
在学校中，N个小朋友站成一队， 第i个小朋友的身高为height[i]，

第i个小朋友可以看到的第一个比自己身高更高的小朋友j，那么j是i的好朋友(要求j > i)。

请重新生成一个列表，对应位置的输出是每个小朋友的好朋友位置，如果没有看到好朋友，请在该位置用0代替。

小朋友人数范围是 [0, 40000]。

输入描述
第一行输入N，N表示有N个小朋友

第二行输入N个小朋友的身高height[i]，都是整数

输出描述
输出N个小朋友的好朋友的位置

爱吃蟠桃的孙悟空 / 猴子吃桃

题目描述
孙悟空爱吃蟠桃，有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有 N 棵桃树，每颗树上都有桃子，守卫将在 H 小时后回来。

孙悟空可以决定他吃蟠桃的速度K（个/小时），每个小时选一颗桃树，并从树上吃掉 K 个，如果树上的桃子少于 K 个，则全部吃掉，并且这一小时剩余的时间里不再吃桃。

孙悟空喜欢慢慢吃，但又想在守卫回来前吃完桃子。

请返回孙悟空可以在 H 小时内吃掉所有桃子的最小速度 K（K为整数）。如果以任何速度都吃不完所有桃子，则返回0。

输入描述
第一行输入为 N 个数字，N 表示桃树的数量，这 N 个数字表示每颗桃树上蟠桃的数量。

第二行输入为一个数字，表示守卫离开的时间 H。

其中数字通过空格分割，N、H为正整数，每颗树上都有蟠桃，且 0 < N < 10000，0 < H < 10000。

输出描述
吃掉所有蟠桃的最小速度 K，无解或输入异常时输出 0。

求满足条件的最长子串的长度

题目描述
给定一个字符串，只包含字母和数字，按要求找出字符串中的最长（连续）子串的长度，字符串本身是其最长的子串，子串要求： 1、 只包含1个字母(a~z, A~Z)，其余必须是数字； 2、 字母可以在子串中的任意位置； 如果找不到满足要求的子串，如全是字母或全是数字，则返回-1。

输入描述
字符串(只包含字母和数字)

输出描述
子串的长度

用例
输入abC124ACb输出4说明满足条件的最长子串是C124或者124A，长度都是4输入a5输出2说明字符串自身就是满足条件的子串，长度为2输入aBB9输出2说明满足条件的子串为B9，长度为2输入abcdef输出-1说明没有满足要求的子串，返回-1

机器人仓库搬砖

题目描述
机器人搬砖，一共有N堆砖存放在N个不同的仓库中，第i堆砖中有bricks[i]块砖头，要求在8小时内搬完。机器人每小时能搬砖的数量取决于有多少能量格，机器人一个小时中只能在一个仓库中搬砖，机器人的能量格每小时补充一次且能量格只在这一个小时有效，为使得机器人损耗最小化尽量减小每次补充的能量格数 为了保障在8小时内能完成搬砖任务，请计算每小时给机器人充能的最小能量格数。

1、无需考虑机器人补充能量格的耗时， 2、无需考虑机器人搬砖的耗时; 3、机器人每小时补充能量格只在这一个小时中有效;

输入描述
第一行为一行数字，空格分隔

输出描述
机器人每小时最少需要充的能量格，若无法完成任务，输出 -1

示例1
输入30 12 25 8 19输出15

示例2
输入10 12 25 8 19 8 6 4 17 19 20 30输出-1

出租车计费 、靠谱的车

题目描述：出租车计费 、靠谱的车
程序员小明打了一辆出租车去上班。出于职业敏感，他注意到这辆出租车的计费表有点问题，总是偏大。

出租车司机解释说他不喜欢数字4，所以改装了计费表，任何数字位置遇到数字4就直接跳过，其余功能都正常。

比如：

23再多一块钱就变为25；

39再多一块钱变为50；

399再多一块钱变为500；

小明识破了司机的伎俩，准备利用自己的学识打败司机的阴谋。

给出计费表的表面读数，返回实际产生的费用。

输入描述
只有一行，数字N，表示里程表的读数。

(1<=N<=888888888)。

输出描述
一个数字，表示实际产生的费用。以回车结束。

用例
输入5输出4说明5表示计费表的表面读数。4表示实际产生的费用其实只有4块钱。输入17输出15说明17表示计费表的表面读数。15表示实际产生的费用其实只有15块钱。输入100输出81说明100表示计费表的表面读数。81表示实际产生的费用其实只有81块钱。

游戏分组/英雄联盟

题目描述
2020年题：

英雄联盟是一款十分火热的对战类游戏。每一场对战有10位玩家参与，分为两组，每组5人。每位玩家都有一个战斗力，代表着这位玩家的厉害程度。为了对战尽可能精彩，我们需要把玩家们分为实力尽量相等的两组。一组的实力可以表示为这一组5位玩家的战斗力和。现在，给你10位玩家的战斗力，请你把他们分为实力尽量相等的两组。请你输出这两组的实力差。

2023年题：
部门准备举办一场王者荣耀表演赛，有10名游戏爱好者参与，分5为两队，每队5人。每位参与者都有一个评分，代表着他的游戏水平。为了表演赛尽可能精彩，我们需要把10名参赛者分为实力尽量相近的两队。一队的实力可以表示为这一队5名队员的评分总和。 现在给你10名参与者的游戏水平评分，请你根据上述要求分队最后输出这两组的实力差绝对值。 例: 10名参赛者的评分分别为5 1 8 3 4 6 710 9 2，分组为 (135 8 10) (24 679)，两组实力差最小，差值为1。有多种分法，但实力差的绝对值最小为1。
输入描述
10个整数，表示10名参与者的游戏水平评分。范围在[1,10000]之间
输出描述
1个整数，表示分组后两组实力差绝对值的最小值.

分割均衡字符串

题目描述
均衡串定义: 字符串只包含两种字符，且两种字符的个数相同。

给定一个均衡字符串，请给出可分割成新的均衡子串的最大个数。

约定字符串中只包含大写的X和Y两种字符。

输入描述
均衡串: XXYYXY 字符串的长度[2,100001]。给定的字符串均为均衡串

输出描述
可分割为两个子串: XXYY XY

备注 分割后的子串，是原字符串的连续子串。

用例
输入XXYYXY输出2说明无