华为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)

仅供参考！如有错误，欢迎指正！