华为OD机试，集牛友之分享，持续刷新

2星题目 题目都没咋读懂，大意是一个城市规划问题，一个地图有很多城市，两个城市之间只有一种路径，切断通往一个城市i的所有路径之后，其他的城市形成了独立的城市群，这些城市群里最大的城市数量，就是聚集度DPi，现在给出一个地图上各个城市的路径，输出聚集度最小的城市，如果有多个结果，按照编号从小到大 第一行输入 城市节点数目N 后面N-1输入城市之间的路径 栗子： 输入 5 1 2 2 3 3 4 4 5 输出 3 将通往3的所有路径切断，最大城市群数量是2，其他任意城市切断后，最大城市群数量都比2大，所以输出3 输入 6 1 2 2 3 2 4 3 5 3 6 输出 2 3

3.仿lisp运算 题目描述： LISP 语言唯一的语法就是括号要配对。 形如(OP P1 P2 …)，括号内元素由单个空格分割。 其中第一个 元素 OP 为操作符，后续元素均为其参数，参数个数取决于操作符类型 注意：参数 P1, P2 也有可能是另外 一个嵌套的(OP P1 P2 …) 当前 OP 类型为 add / sub / mul / div（全小写），分别代表整数的加减乘除法 简单起见，所有 OP 参数个数均为 2 举例: 输入：(mul 3 -7) 输出： -21 输入：(add 1 2) 输出：3 输入：(sub(mul 2 4) (div 9 3)) 输出：5 输入：(div 1 0) 输出：error 题目涉及数字均为整数，可能为负； 不考虑 32 位溢出翻转，计算过程中也不会发生 32 位溢出翻转 除零错误时， 输出 “error”，除法遇除不尽，向下取整，即 3 / 2 = 1 输入描述： 输入为长度不超过 512 的字符串，用例保证了无语法错误 输出描述： 输出计算结果或者“error” 示例 1 输入：(div 12 (sub 45 45)) 输出： error

第一题，按照身高体重给学生排队，矮的排前面，高的排后面，一样高的比体重，重的排后面，身高体重都一样的按照输入顺序排。第一行输入学生数，第二行输入学生身高，第三行输入学生体重，要求按照排队顺序输出学生编号。 第二题，括号的最大深度，输入字符串由（）｛｝【】组成，求括号的最大深度。每种类型的左右括号数都相等，否则返回0；每种类型括号都需要按照正确顺序关闭，否则返回0。 第三题，两兄弟分积木，每块积木都标有重量，两堆积木重量“相等”的情况下（以弟弟的加法方式判断，弟弟每次都是把数字转为二进制数进行加法运算，并且每次都忘记进位），由哥哥负责分配，弟弟如果认为没有平均分配积木就会哭，求不让弟弟哭的情况下，哥哥能分到积木的最大总重量，如果不能分配就返回0。

1.题目描述： 为了充分发挥GPU算力，需要尽可能多的将任务交给GPU执行。 现在有一个任务数组，数组元素表示在这1s内新增的任务个数，且每秒都有新增任务。 假设GPU最多一次执行n个任务，一次执行耗时1s，在保证GPU不空闲的情况下，最少需要多长时间执行完成。 输入描述： 第一个参数为GPU最多执行的任务个数，取值范围1-10000 第二个参数为任务数组的长度，取值范围1-10000 第三个参数为任务数组，数字范围1-10000 输出描述： 执行完所有任务需要多少秒 示例 输入： 3 5 1 2 3 4 5 输出： 6 说明： 一次最多执行3个任务 最少耗时6s 输入： 4 5 5 4 1 1 1 输出： 5 说明： 一次最多执行4个任务 最少耗时5s (easy,从第一个数往后迭代即可,记录一下每次剩余的量留给下次,最后做一次剩余的处理) 2.题目描述： 现在有一队小朋友，他们高矮不同，，我们以正整数数组表示这一队小朋友的身高，如数组{5,3,1,2,3}。 我们现在希望小朋友排队，以“高”“矮”“高”“矮”顺序排列，每一个“高”位置的小朋友要比相邻的位置高或者相等；每一个“矮”位置的小朋友要比相邻的位置矮或者相等；要求小朋友们移动的距离和最小，第一个从“高”位开始排，输出最小移动距离即可。 移动距离的定义如下所示：第二位小朋友移到第三位小朋友后面，移动距离为1，若移动到第四位小朋友后面，移动距离为2。 输入描述： 排序前的小朋友，以英文空格的正整数：4 3 5 7 8 小朋友<100个 输出描述： 排序后的小朋友，以英文空格分割的正整数：4 3 7 5 8 输出结果为最小移动距离，只有5和7交换了位置，移动距离都是1 示例： 输入： 4 1 3 5 2 输出： 4 1 5 2 3 输入： 1 1 1 1 1 输出： 1 1 1 1 1 说明： 相邻位置可以相等 输入： xxx 输出： [] 说明： 出现非法参数情况，返回空数组

3、给你几个服务器（忘了叫啥了），几个之间可以内部通信，给你多行字符串（样例见下），dp[i][j]的值如果为1，表示可以直接通信，为0则不通信，问你需要连接几个服务器，能使得所有服务器可以直接通信。 思路呢，就是并查集，模板题，啥也没变，返回不连通的一共有几堆即可。    AC了，代码仅供参考 1 0 0 0 1 0 0 0 1 输出 3

1.翻牌求最大分 给出n个牌数，在-100到100之间，求最大得分。规则如下：连续翻牌，如果选当前牌，则总得分等于上一次翻牌总得分加上当前牌的数字，如果当前总得分小于它前三次的总得分的话，那此次不翻牌，并且总得分就等于它前三次的得分。1到3次翻牌数如果小于0的话就取0。 例子：1，-5，-6，4，7，2，-2 （1）1大于零 翻牌 （2）-5 加上1 小于0      不翻 结果为0 （3）-6 加上0 小于0     不翻 结果为0 （4）4 加上0 大于0（1）翻牌 结果为4 （5）7 加上4 大于0（2）    翻牌 结果为11 （6）2 加上11 大于0（3） 翻牌 结果为13 （7）-2 加上14 大于4（4）翻牌 结果为11 2.求N个最大，最小数之和 输入数组，排序 找到最大N个数和最小N个数 然后相加，返回相加结果。 如果N个数中有重复，返回-1。 输入 5 2,3,2,4,3 2 输出 -1 因为排序后最小n个数有重复 3.病毒扩散 一个输入N个数满足n*n，1表示中病毒，0表示健康。每天有病毒的会感染它的上下左右的格子。求共需多少天所有格子全部感染。当输入全0或者全一的话输出-1，否则输出所需天数。

1 停车位问题 有一横排车位，有至少一个车位停了车，也至少有一个车位没停车。一个车位有车用1表示，无车用0表示。为了避免剐蹭，请为司机规划停在哪个车位，距离其他车中间间隔的车位最远。输入：一组数据，代表目前车位的状态。 输出：当前车辆停车距离其他车辆的最大间距 栗子： 输入 1 0 0 0 0 1 0 1 0 输出 3 这个题比较简单，用1分割输入的数据，再考虑首尾为0的情况，取最大值，但是最后只通过95%，不知道漏了哪种情况 2 URL问题 输入两个URL，如/abc,/asd 输出拼接后的URL，/abc/asd 就是考虑两个字符串首尾是不是’/‘的问题，我用暴力解发，判断3个位置，共8种情况，最后还是只通过85%

题目一： 2-35进制的两个数进行相减，大于10进制的用a-z（小写字母）补齐 输入： 2   11    1 解释：2  为2进制， 11 为被减数   1 为减数 输出： 0 10 解释：①0为正数，1为负数  ②11-1 =10 ------------------------------ 题目二 求三个矩形的相交面积 输入： 1 6 4 4 2 5 3 3 0 3 5 5 解释：三行为三个矩形，第一二列为左上角 横纵坐标，第三四列分别为矩形长宽 输出： 2 解释：矩形面积（具体数字记不太清了，大神们脑部画面） ------------------ 题目三 m个员工分n个月饼(n>m)，每人最少分1个，max(n-1) -max(n) <= 3，求有多少种分法？ （真题描述比我这个更详细，这个算是大概意思，大佬们脑补思路即可） 输入： 2 4 输出 2 解释：1+3=4（1+3和3+1相同只记一种） 2+2=4

第一题： 计算字符串中整数和的最小值。 输入字符包含：a-z A-Z 0-9和负号"-" 思路： 字符串中包含需要跳过的大小写字母，正整数和负整数。 要想和最小， 当遇到正整数时，分别当做个位数处理相加。 当遇到负号"-"时，要把 负号"-"和后面数字当做整体，这样和最小。 ps： 负号"-"遇到字母和其他负号"-"时，负整数结束。 通过率100% 第二题： 给出3组点坐标(x, y, w, h)，-1000<x,y<1000，w,h为正整数。 (x, y, w, h)表示平面直角坐标系中的一个矩形： x, y为矩形左上角坐标点，w, h向右w，向下h。 (x, y, w, h)表示x轴(x, x+w)和y轴(y, y-h)围城的矩形区域 (0, 0, 2, 2)表示 x轴(0, 2)和y 轴(0, -2)围城的矩形区域 (3, 5, 4, 6)表示x轴(3, 7)和y轴(5, -1)围城的矩形区域 求3组坐标构成的矩形区域重合部分的面积。 思路： 通过观察分析得出结论： 设x1, x2, y1, y2围城的矩形区域就是 重合部分， 则x1为三组点坐标中max(x) 则x2为三组点坐标中min(x+w) 则y1为三组点坐标中min(y) 则y2为三组点坐标中max(y-h) 重合部分的面积为(x2-x1)*(y1-y2) ps：x1>=x2或者y2>=y1，无重合部分，面积为0 通过率100%

第二道：给出一个数组n[ ]，其中n[0]=0，从n[0]开始向后走，第一步可走的距离len满足1<=len<=n.length/2，之后的每一步距离等于该位置的值n[index]，问能否走到数组的最后一个位置，如果能，返回最小的步数； 这题也是一道比较简单的动态规划，dp[ ]全部初始化为Integer.MAX_VALUE，走第一步时能到的位置赋值为1，然后dp[i+n[i]]=Math.min(dp[i]+1,dp[i+n[i]])遍历即可； 第三道：一个树状结构，每个节点有且仅有一个父节点，可能有多个子节点，根节点没有父节点， 给出一个二维数组test[ ][ ]用来表示这样的一棵树，tes[i]={a,b}，表示a的父节点为b。保证test数据合法。再给出一个节点数值k，从该树种删去节点k及其所有子节点，升序输出剩下的节点数值。 这题我的思路是新建一个哈希集合sets，遍历test，保存所有元素；然后新建集合del，再次遍历test，找到k的子节点，重复这个过程，使del保存所有k的子节点，最后从sets中remove掉del中的元素。

第三题 为了提升数据传输的效率，会对传输的报文进行压缩处理。输入一个压缩后的报文，请返回它解压后的原始报文。 压缩规则：n[str]，表示方括号内部的 str 正好重复 n 次。注意 n 为正整数（0 < n <= 100），str只包含小写英文字母，不考虑异常情况。 " “输入描述: 输入压缩后的报文： 1）不考虑无效的输入，报文没有额外的空格，方括号总是符合格式要求的； 2）原始报文不包含数字，所有的数字只表示重复的次数 n ，例如不会出现像 5b 或 3[8] 的输入； 输出描述: 解压后的原始报文 注： 1）原始报文长度不会超过1000，不考虑异常的情况 示例1 输入 3[k]2[mn] 输出 kkkmnmn 说明 k 重复3次，mn 重复2次，最终得到 kkkmnmn 示例2 输入 3[m2[c]] 输出 mccmccmcc 说明 m2[c] 解压缩后为 mcc，重复三次为 mccmccmcc”

题目1描述： 幼儿园两个班的小朋友在排队时混在了一起，每位小朋友都知道自己是否与前面一位小朋友同班，请你帮忙把同班的小朋友找出来。 小朋友的编号是整数，与前一位小朋友同班用Y表示，不同班用N表示。 输入描述： 输入为空格分开的小朋友编号和是否同班标志。 输出描述： 输出为两行，每一行记录一个班小朋友的编号，编号用空格分开，且： 1.编号需按照升序排列。 2.若只有一个班的小朋友，第二行为空行。 比如： 输入 1/N 2/Y 3/N 4/Y 输出 1 2 3 4 题目2描述： 大概意思：100个人报数，报到M的删除，输出最后剩下的m-1个人 题目3描述： 破解保险箱密码 小明拥有一个保险箱，但是忘记了密码。已知密码在范围在0~9中，且每位数字仅出现一次。现小明只记得密码是由序列s[]里的数字组成(s[i] ∈ [0, 9], s.length ∈ [1, 10]s[i]∈[0,9],s.length∈[1,10]),密码最少为N位(N ∈ [0, 10]N∈[0,10])，且密码各位上的数字，是从左到右依次递增的。 已知密码不会为空，请输出所有可能出现的密码。 输出结果要求: 输出结果需要按位数数字从小到大排列(即字典序)。 1、给你两个字符串 t 和 p ，t.length() >= p.length()，让你找到 t 中是否包含p,如果包含找到p在t中的第一个位置,否则输出No 一般三种做法    1）调库，2）KMP 3）字符串HASH我怕麻烦就调库的，数据量很大，暴力肯定过不了 t的长度100W,p的长度最大1W

【敏感字段加密】给定个由多个命令字组成的命令字符串： 1.字符串长度小于等于127字节，只包含大小写字母，数字，下划线和偶数个双引号; 2、命令字之间以个或多个下划线——进行分割; 3、 可以通过两个双引号""来标识包含下划线——的命今字或空命今字(仅包含两个双引号的命令字),双引号不会在命令字内部出现; 请对指定索的敏感字段进行加密，替换为******(6个)，并删除命令字前后多余的下划线——。如果无法找到指定索引的命今字,输出字符串ERROR. 输入描述: 输入为两行,第一行为命令字索引K（从0开始),第一行为命令字符串s.   2.补种未成活胡杨树 //某沙漠新种植N颗胡杨（编号1~N），一个月后，有M颗未能成活。现可补种K颗（只可补种，不可新种），请问怎样补种，可以得到最多的连续胡杨树？ 输入  N 总种植数量          M  未成活数量          M个空格分割的数，按编号从小到大排列          K 最多可以补种的数量 其中 1<=N<1000 1<=M<N 0<=K<=M 实例 输入        10        3        2 4 7        1        输出        6 说明 补种第7颗 可得到5，6，7,8，9，10连续胡杨树

第二题：最大括号深度 先判断一下输入的括号是不是合法的，再把所有的[]和{}都替换成(),再来判断深度，还挺简单的，但是得注意不要超时了。 第三题：x*y的迷宫 机器人走一个迷宫,给出迷宫的x和y(x*y的迷宫)并且迷宫中有障碍物,输入k表示障碍物有k个,并且会将障碍物的坐标挨个输入. 机器人从0,0的位置走到x,y的位置并且只能向x,y增加的方向走,不能回退. 其中会有不可达方格和陷阱方格.不可达方格为是该机器人在行走路径上不可能走到的方格,陷阱方格走进之后则不能抵达终点. 要求: 输出陷阱和不可达方格方格数量 这题很懵，题目记得也不是很清楚，可能得用动态规划做，我没做出来，过了16%。 1、约瑟夫环，判断剩下的K个人的编号； 2、字符串的输出，主要是考查循环、缩进； 3、DFS，查找字符矩阵中的特定单词，并返回起点的坐标。、

第一题： 用数组代表每个人的权重，现在要进行组队权重大于等于 N，每个队可以由 1人或 2人组队，且 1个人只能参加 1个队， 计算可以派出最多的符合要求的团队 输入三行 第一行：代表数组长度 第二行：数组的元素 第三行：最小权重 示例： 5 3 1 5 7 9 8 输出： 3 解释： [ 3 5 ] [ 1 7 ] [ 9 ] 这题应该先对数组排序，再利用双指针应该可以做出来，当时我没想到，用暴力过了75%。

1.求最大子矩阵和 2.给一个首尾相连的仅包含小写字母的循环字符串，求包含字母o且字母o为偶数的最长子串 3.手搓一个内存池（大模拟题。。。） 要求实现个100字节的内存池，支持申请内存块，支持释放任意存在的内存块，每次申请都先利用内存块最靠前的地址，内存块连续，申请失败需要输出error，申请成功返回内存块头节点，不可释放不存在的内存块

第一题：给一组数和一个数据，求该数据包含数组里的数的最多个数 输入：2 11 5 3 10            20 输出：4 我的解法很简单，先对数组排序，然后从小到大一个一个去试 第二题：给定三个长方形的左上角坐标以及长宽，求公共部分面积 例子数据忘了 我的解法是先求两个长方形的公共部分，然后再与第三个相交，求出坐标与长宽 第三题：给定一组书的长宽，并且只有当一本书的长宽同时小于另一本书的长宽时，两书才能叠放在一起，求改组书中最多能有多少本书叠放在一起 输入：[[20,16],[15,11],[10,10],[9,10]] 输出：3，前三本可叠放在一起 我的解法：利用第一题中的排序按招书本的长进行排序，然后依次计算以每本书为底最多能放多少书，然后输出最大的那个数

第一题 因式分解：求素数乘积 输入一个数，求该数的素数乘积 输入：21 输出：3 7 第二题 括号的最大嵌套深度 输入一个仅由 "()[]{}" 组成的字符串，计算出有效的括号最大嵌套深度 输入：([]{()}) 输出：3 第三题 第一行输入一个非负整数字符串，第二行输入一个整数n 输出从该字符串中取出n个字符后剩下的字符组成的最小的数（不改变字符顺序） 输入 ： 2615371 4 输出：131

3.题目描述 积木宽高相等，长度不等，每层只能放一个或拼接多个积木，每层长度相等，求最大层数，最少2层。 输入 给定积木的长度，以空格分隔，例如:3 6 6 3。 输出 如果可以搭建，返回最大层数，如果不可以返回-1。 样例输入 3 6 6 3 样例输出 3 样例输入 3 5 样例输出 -1

1.翻牌求最大分 给出n个牌数，在-100到100之间，求最大得分。规则如下：连续翻牌，如果选当前牌，则总得分等于上一次翻牌总得分加上当前牌的数字，如果当前总得分小于它前三次的总得分的话，那此次不翻牌，并且总得分就等于它前三次的得分。1到3次翻牌数如果小于0的话就取0。 例子：1，-5，-6，4，7，2，-2 （1）1大于零 翻牌 （2）-5 加上1 小于0      不翻 结果为0 （3）-6 加上0 小于0     不翻 结果为0 （4）4 加上0 大于0（1）翻牌 结果为4 （5）7 加上4 大于0（2）    翻牌 结果为11 （6）2 加上11 大于0（3） 翻牌 结果为13 （7）-2 加上14 大于4（4）翻牌 结果为11 2.求N个最大，最小数之和 输入数组，排序 找到最大N个数和最小N个数 然后相加，返回相加结果。 如果N个数中有重复，返回-1。 输入 5 2,3,2,4,3 2 输出 -1 因为排序后最小n个数有重复 3.病毒扩散 一个输入N个数满足n*n，1表示中病毒，0表示健康。每天有病毒的会感染它的上下左右的格子。求共需多少天所有格子全部感染。当输入全0或者全一的话输出-1，否则输出所需天数。