华为OD机试分享20220622
考试时间：2022-06-22
总分：136分
第一题：字符串分割-水仙花数（用例通过率：11.1%）
第二题：内存资源分配（用例通过率：95.8%）
第三题：模拟内存分配（用例通过率：15%）
之前在网上也看了很多分享，虽然机考没通过，不过也分享一下遇到的考题。
说明：
1.试题是考后在网上找的原题或比较类似的题。
2.部分代码是考试时候写的，可能写的有点乱。考试时候只管用例通过率，不讲究格式或有没有冗余代码。
题目描述用代码块的原因：牛客这编辑器不知现在咱回事，竟然显示不换行。
第一题 字符串分割-水仙花数
题目描述
给定非空字符串s，将该字符串分割成一些子串，使每个子串的ASCII码值的和均为水仙花数。
1、若分割不成功，则返回0
2、若分割成功且分割结果不唯一，则返回-1
3、若分割成功且分割结果唯一，则返回分割后子串的数目
输入描述
输入字符串的最大长度为200
输出描述
根据题目描述的情况，返回相应的结果
示例1
输入
abc
输出
0
说明
分割不成功
示例2
输入
f3@d5a8
输出
-1
说明
分割成功但分割结果不唯一，可以分割为两组，一组'f3'和'@d5a8'，另外一组'f3@d5'和'a8'
示例3
输入
AXdddF
输出
2
说明
分割成功且分割结果唯一，可以分割成'AX'和'dddF'(370)两个子串
备注
“水仙花数”是指一个三位数，每位上数字的立方和等于该数字本身，如371是'水仙花数'，因371=3^3+7^3+1^3
#以下代码用例通过率为：11.1%
s = input()
l = []
tem = []
c = []
for i in s:
l.append(ord(i))
for i in range(len(s)):
for j in range(i,len(s)+1):
if l[i:j] not in tem and len(str(sum(l[i:j]))) == 3:
tem.append(str(sum(l[i:j])))
for i in tem:
if int(i[0])**3+int(i[1])**3+int(i[2])**3 == int(i):
c.append(int(i))
if len(c) == 0:
print(0)
else:
if sum(l) == sum(c):
print(len(c))
else:
print(-1)
说明：本题我在考试的时候理解成只要能分出水仙花数就算分割成功。其实应该是分割的每个子串都是水仙花数才能算分割成功。不过这题在分组上确实也有难点，因为即使子串已经是水仙花数了，再加字符可能仍然是水仙花数。一个字符串可以分割出很多个水仙花数，也存在多个分组。这样应该用到回溯来解此题。 考后结合评论区兰夜的提示和想到力扣93题复原IP地址用到的回溯方法，重新解此题： 首先：咋们以s = "f3@d5a8"为例，利用回溯方法找一下可能的具体分组
代码实现
# 1.提取字符及其ASCII码
s = "f3@d5a8"
ls =list(s)
nums = []
for i in s:
nums.append(ord(i))
# 2.列出所有三位数的水仙花数
narcissus_nums = []
for i in range(100,1000):
i = str(i)
if int(i[0])**3+int(i[1])**3+int(i[2])**3 == int(i):
narcissus_nums.append(int(i))
# 3.回溯
def backtrack(ls,nums,stk):
if sum(nums) in narcissus_nums:
stk.append("".join(ls))
res.append(stk[:])
stk.pop()
return
for i in range(1,len(nums)):
if sum(nums[:i]) in narcissus_nums:
stk.append("".join(ls[:i]))
backtrack(ls[i:],nums[i:],stk)
stk.pop()
res = []
backtrack(ls,nums,[])
# 4.输出
print(res)
输出结果：
[['f3', '@d5a8'], ['f3@d5', 'a8']]
其次：按输出要求，修改为如下代码：
# 1.提取字符及其ASCII码
s = input()
ls =list(s)
nums = []
for i in s:
nums.append(ord(i))
# 2.列出所有三位数的水仙花数
narcissus_nums = []
for i in range(100,1000):
i = str(i)
if int(i[0])**3+int(i[1])**3+int(i[2])**3 == int(i):
narcissus_nums.append(int(i))
# 3.回溯
def backtrack(ls,nums,stk):
if sum(nums) in narcissus_nums:
stk.append("".join(ls))
res.append(stk[:])
stk.pop()
return
for i in range(1,len(nums)):
if sum(nums[:i]) in narcissus_nums:
stk.append("".join(ls[:i]))
backtrack(ls[i:],nums[i:],stk)
stk.pop()
res = [] # 只有满足条件的分组才会存入res
backtrack(ls,nums,[])
# 4.输出
if len(res) == 0: # 分割不成功，res为空
print(0)
elif len(res) == 1: # 分割唯一，输出子串数
print(len(res[0]))
else: # 分割不唯一，事实上 len(res) > 1
print(-1)
方法二：本题与力扣131题分割回文串类似
def check(sec):
"""检查水仙花数的片段"""
tem = [ord(i) for i in sec]
total = sum(tem)
if not 99 < total < 1000:
return False
ts = str(total)
return int(ts[0]) ** 3 + int(ts[1]) ** 3 + int(ts[2]) ** 3 == total
def backtrack(s):
"""回溯"""
if len(s) == 0:
res.append(path[:])
return
for i in range(1, len(s)+1):
if check(s[:i]):
path.append(s[:i])
backtrack(s[i:])
path.pop()
s = input()
res = []
path = []
backtrack(s)
# 格式输出
if len(res) == 0:
print(0)
elif len(res) == 1:
print(len(res[0]))
else:
print(-1)
仅供参考！如有错误，欢迎指正！
第二题：内存资源分配
题目描述
有一个简易内存池，内存按照大小粒度分类，每个粒度有若干个可用内存资源，用户会进行一系列内存申请，需要按需分配内存池中的资源，返回申请结果成功失败列表。
分配规则如下：
1.分配的内存要大于等于内存申请量，存在满足需求的内存就必须分配，优先分配粒度小的，但内存不能拆分使用。
2.需要按申请顺序分配，先申请的先分配。
3.有可用内存分配则申请结果为true，没有可用内存分配则返回false。
注：不考虑内存释放。
输入描述
第一行为内存池资源列表，包含内存粒度数据信息，粒度数据间用逗号分割，一个粒度信息内部用冒号分割，冒号前为内存粒度大小，冒号后为数量。资源列表不大于1024，每个粒度的数量不大于4096。
第二行为申请列表，申请的内存大小间用逗号分隔。申请列表不大于100000。
输出描述
输出为内存池分配结果。
示例
输入：
64:2,128:1,32:4,1:128
50,36,64,128,127
输出：
true,true,true,false,false
说明：
内存池资源包含：64K共2个、128K共1个、32K共4个、1K共128个的内存资源；
针对50,36,64,128,127的内存申请序列，分配的内存依次是：64,64,128,NULL,NULL,
第三次申请内存时已经将128分配出去，因此输出结果是：true,true,true,false,false
代码实现
# 以下代码用例通过率为：95.8%
s = input().split(",")
a = list(map(int,input().split(",")))
ds = {}
ls = ""
for i in s:
size,n = map(int,i.split(":"))
ls += n * (" "+str(size))
ds[size] = n # 注意！这里应分情况讨论，如果字典已有指定大小的内存，应进行累加（ds[size] += n）
tls = sorted(list(map(int,ls.split())))
res = []
def check(i):
for j,v in enumerate(tls):
if v >= i:
tls.pop(j)
return "true"
return "false"
for i in a:
res.append(check(i))
print(",".join(res))
代码优化
def check(apply):
"""检查池里是否有可分配的内存"""
for memery in pool:
if memery >= apply: # 若有，分配后返回true
pool.remove(memery) # 从池里剔除
return "true"
return "false" # 找一圈了都没有，则最后返回false
# 1.输入
source = list(input().split(","))
applies = list(map(int,input().split(",")))
# 2.内存资源池
pool = []
for mem in source:
size, n = map(int, mem.split(":"))
pool.extend([size] * n)
pool.sort() # 从小到大排序
# 3.申请内存的结果
res = []
for apply in applies:
res.append(check(apply))
print(",".join(res))
进一步利用字典来进行空间优化
def check(apply):
"""检查池里是否有可分配的内存"""
for mem in sorted(pool.keys()):
if mem >= apply and pool[mem] > 0: # 若有，分配后返回true
pool[mem] -= 1 # 池里该类内存数减1
return "true"
return "false" # 找一圈了都没有，则最后返回false
# 1.输入
source = list(input().split(","))
applies = list(map(int,input().split(",")))
# 2.内存资源
pool = {}
for mem_info in source:
size, n = map(int, mem_info.split(":"))
if size not in pool:
pool[size] = n
else:
pool[size] += n
print(pool)
# 3.申请内存的结果
res = []
for apply in applies:
res.append(check(apply))
print(",".join(res))
仅供参考！如有错误，欢迎指正！
第三题：模拟内存分配
请实现一个简易内存池，根据请求命令完成内存分配和释放。
内存池支持两种操作命令，REQUEST和RELEASE，其格式为：
REQUEST=请求的内存大小 表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error。
RELEASE=释放的内存首地址 表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。
注意：
1.内存池总大小为100字节。
2.内存池地址分配必须是连续内存，并优先从低地址分配。
3.内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放。
4.不会释放已申请的内存块的中间地址。
5.释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其它内存块。
解答要求
时间限制: 1000ms, 内存限制: 256MB
首行为整数 N , 表示操作命令的个数，取值范围：0 < N <= 100。
接下来的N行, 每行将给出一个操作命令，操作命令和参数之间用 “=”分割。
输入样例1
2
REQUEST=10
REQUEST=20
输出样例1
0
10
输入样例2
5
REQUEST=10
REQUEST=20
RELEASE=0
REQUEST=20
REQUEST=10
输出样例2
0
10
30
0
提示说明
第一条指令，申请地址0~9的10个字节内存，返回地址0
第二条指令，申请地址10~29的20字节内存，返回首地址10
第三条指令，释放首地址为0的内存申请，0~9地址内存被释放，变为空闲，释放成功，无需输出
第四条指令，申请20字节内存，09地址内存连续空间不足20字节，往后查找到3049地址，返回首地址30
第五条指令，申请10字节，0~9地址内存空间足够，返回首地址0
# 以下代码用例通过率：15% 哈哈！所有不会也不要留空白哦
N = int(input())
print("error")
这道题好像不难，之前一直没咋细看，被长长的文字吓住了。
解题思路
开辟一个长度为100的一维数组模拟内存池，未使用或已释放位置用0标记，使用了用1标记
代码实现
def allocation(handle):
"""分配内存"""
if handle[0] == "REQUEST":
k = int(handle[1])
for i in range(len(pool) - k + 1): # i只需要遍历到len(men)-k
if pool[i:i + k] == [0] * k:
pool[i:i + k] = [1] * k # 标记为1：表示已使用
d[i] = k
print(i)
return
print("error")
elif handle[0] == "RELEASE":
id = int(handle[1])
if id in d.keys():
pool[id:id + d[id]] = [0] * d[id] # 标记为0：释放内存
d.pop(id)
else:
print("error")
else: # 其它操作
print("error")
# 0.用数组虚拟开辟内存空间
pool = [0 for i in range(100)] # 初始化全为0:表示内存所有地址未被使用
# 1.输入（操作按元组格式存入数组handles）
N= int(input())
handles = [(input().split("=")) for _ in range(N)]
d = {} # 用字典存入已分配地址及大小
for handle in handles:
allocation(handle)
仅供参考！如有错误，欢迎指正！
华为工作强度 810人发布
查看5道真题和解析