算法题记录 14

2502.设计内存分配器（1746）

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。

请你设计一个具备以下功能的内存分配器：

分配 一块大小为 size 的连续空闲内存单元并赋 id mID 。
释放 给定 id mID 对应的所有内存单元。
注意：

多个块可以被分配到同一个 mID 。
你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。
实现 Allocator 类：

Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。
int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于 最左侧 的块，分配并赋 id mID 。返回块的第一个下标。如果不存在这样的块，返回 -1 。
int freeMemory(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。

涉及知识点

模拟

解决思路

秒答题，看图说话即可，如果要简化运算，可以尝试使用“跳棋”的思想，但是比较复杂，优化效率不大，没意义。

class Allocator:
    def __init__(self, n: int):
        self.memory = [0] * n

    def allocate(self, size: int, mID: int) -> int:
        free = 0
        for i, id in enumerate(self.memory):
            if id > 0:  # 已分配
                free = 0  # 重新计数
                continue
            free += 1
            if free == size:  # 找到了
                self.memory[i - size + 1: i + 1] = [mID] * size
                return i - size + 1
        return -1  # 无法分配内存

    def freeMemory(self, mID: int) -> int:
        ans = 0
        for i, id in enumerate(self.memory):
            if id == mID:
                ans += 1
                self.memory[i] = 0  # 标记为空闲内存
        return ans

3040.相同分数的最大操作数目2（1709）

给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个：

选择 nums 中最前面两个元素并且删除它们。
选择 nums 中最后两个元素并且删除它们。
选择 nums 中第一个和最后一个元素并且删除它们。
一次操作的 分数 是被删除元素的和。

在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。

请你返回按照上述要求 最多 可以进行的操作次数。

涉及知识点

DFS

解决思路

秒答题，常规的DFS搜索。

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int, target: int) -> int:
            if i >= j:
                return 0
            res = 0
            if nums[i] + nums[i + 1] == target:  # 删除前两个数
                res = max(res, dfs(i + 2, j, target) + 1)
            if nums[j - 1] + nums[j] == target:  # 删除后两个数
                res = max(res, dfs(i, j - 2, target) + 1)
            if nums[i] + nums[j] == target:  # 删除第一个和最后一个数
                res = max(res, dfs(i + 1, j - 1, target) + 1)
            return res

        n = len(nums)
        res1 = dfs(2, n - 1, nums[0] + nums[1])  # 删除前两个数
        res2 = dfs(0, n - 3, nums[-2] + nums[-1])  # 删除后两个数
        res3 = dfs(1, n - 2, nums[0] + nums[-1])  # 删除第一个和最后一个数
        return max(res1, res2, res3) + 1  # 加上第一次操作

LCR 181.字符串中的单词反转（简单）

你在与一位习惯从右往左阅读的朋友发消息，他发出的文字顺序都与正常相反但单词内容正确，为了和他顺利交流你决定写一个转换程序，把他所发的消息 message 转换为正常语序。

注意：输入字符串 message 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

涉及知识点

字符串

解决思路

秒答题，对于python来说考察的是库函数的使用，包括列表反转、正则表达式、字符串分割、字符串前后去空格。

class Solution:
    def reverseMessage(self,message: str) -> str:
        message=message.strip()
        message=re.split("\s+",message)
        message.reverse()
        return " ".join(message)

2434.使用机器人打印字典序最小的字符串（1953）

给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：

删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
请你返回纸上能写出的字典序最小的字符串。

涉及知识点

贪心、栈

解决思路

秒答题，题意为在s从左到右遍历字符，对于每个字符可以入栈也可以写纸上，入栈的字符会以出栈顺序写纸上。用一个栈辅助，并且每次判断后续有没有字母小于栈顶字母即可，如果没有，那么栈顶的出栈写纸上，如果有，那么遍历到那个最小的字母写纸上。

class Solution:
    def robotWithString(self, s: str) -> str:
        ans=[]
        cnt=Counter(s)
        min=0
        st=[]
        for c in s:
            cnt[c]-=1
            while min <25 and cnt[ascii_lowercase[min]]==0:
                min+=1
            st.append(c)
            while st and st[-1]<=ascii_lowercase[min]:
                ans.append(st.pop())
        return ''.join(ans)

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。