算法题记录 3

1760.扰乱字符串（1940）

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。
你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

涉及知识点

最优化、二分

解决思路

首先观察题意，可知是一个最小化最大值的问题。我们设最后的最大值为m，于是对于有x个球的袋子，需要执行「x/m次，对所有袋子进行计算求和，只要小于maxOperations就是合法分法，在这个限制下找到最小值即可，采用0到max（nums）的二分开区间查找。

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        def check (m:int)->bool:
            cnt=0
            for x in nums:
                cnt+=(x-1)//m
            return cnt<=maxOperations
        
        left=0
        right=max(nums)
        while left+1<right:
            mid=(left+right)//2
            if check(mid):
                right=mid
            else:
                left=mid
        return right 

1845.座位预约管理系统（1429）

请你设计一个管理 n 个座位预约的系统，座位编号从 1 到 n 。

请你实现 SeatManager 类：

SeatManager(int n) 初始化一个 SeatManager 对象，它管理从 1 到 n 编号的 n 个座位。所有座位初始都是可预约的。
int reserve() 返回可以预约座位的 最小编号 ，此座位变为不可预约。
void unreserve(int seatNumber) 将给定编号 seatNumber 对应的座位变成可以预约。

涉及知识点

类，最小堆

解决思路

首先意识到这样的落座逻辑与最小堆的入堆、出堆一致，但如果直接运用最小堆效率不理想。针对这一现象进行优化，不必要的地方尽量减少最小堆的使用，比如没人离开，后续来到者不需“插队”，只需通过一个seats进行计数返回座位编号即可。当有人离开座位（出堆），再对来到者使用最小堆的入堆策略。

class SeatManager:

    def __init__(self, n: int):
        self.seats=0
        self.available=[]

    def reserve(self) -> int:
        if self.available:
            return heappop(self.available)
        self.seats+=1
        return self.seats

    def unreserve(self, seatNumber: int) -> None:
        heappush(self.available,seatNumber)

3254.长度为K的子数组的能量值1（1267）

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个数组的 能量值 定义为：

如果 所有 元素都是依次 连续 且 上升 的，那么能量值为 最大 的元素。
否则为 -1 。
你需要求出 nums 中所有长度为 k 的
子数组
的能量值。

请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i..(i + k - 1)] 的能量值。

涉及知识点

数组的操作

解决思路

题目思路非常简单，在遍历过程中判断是否连续上升即可，如果截止目前i的连续上升数已经大于等于k，那么这段的能量就是目前的nums[i]。

class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]:
        ans=[-1]*(len(nums)-k+1)
        cnt=0
        for i,x in enumerate(nums):
            cnt=cnt+1 if i==0 or x==nums[i-1]+1 else 1
            if cnt>=k:
                ans[i-k+1]=x
        return ans

1847.最近的房间（2082）

一个酒店里有 n 个房间，这些房间用二维整数数组 rooms 表示，其中 rooms[i] = [roomIdi, sizei] 表示有一个房间号为 roomIdi 的房间且它的面积为 sizei 。每一个房间号 roomIdi 保证是 独一无二 的。

同时给你 k 个查询，用二维数组 queries 表示，其中 queries[j] = [preferredj, minSizej] 。第 j 个查询的答案是满足如下条件的房间 id ：

房间的面积 至少 为 minSizej ，且
abs(id - preferredj) 的值 最小 ，其中 abs(x) 是 x 的绝对值。
如果差的绝对值有 相等 的，选择 最小 的 id 。如果 没有满足条件的房间 ，答案为 -1 。

请你返回长度为 k 的数组 answer ，其中 answer[j] 为第 j 个查询的结果。

涉及知识点

双指针，二分

解决思路

题目核心：为了简化计算步骤，先把query的minsize从大到小排序，rooms按size排序，双指针依query查询room中满足条件者依房间号为序放入新数组room_ids对preferred_id进行二分查找，判断左边更好还是右边更好，得到该query的答案，遍历所有query即可。注意：因为输出要求按query先后顺序进行，不能直接对query进行排序改变输入顺序，新建序号数组q，对q按query的minsize进行排序，把答案放在以q为序号的ans[]中即可。

class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        rooms.sort(key=lambda r:r[1])
        q=len(queries)
        ans=[-1]*q
        room_ids=SortedList()
        j=len(rooms)-1
        for i in sorted(range(q),key=lambda i:-queries[i][1]):
            preferred_id,min_size=queries[i]
            while j>=0 and rooms[j][1]>=min_size:
                room_ids.add(rooms[j][0])
                j-=1
            
            diff=inf
            k=room_ids.bisect_left(preferred_id)
            if k:
                diff=preferred_id-room_ids[k-1]
                ans[i]=room_ids[k-1]
            if k<len(room_ids) and room_ids[k]-preferred_id<diff:
                ans[i]=room_ids[k]
        return ans
        

3235.判断矩形的两个角落是否可达（3774）

给你两个正整数 xCorner 和 yCorner 和一个二维整数数组 circles ，其中 circles[i] = [xi, yi, ri] 表示一个圆心在 (xi, yi) 半径为 ri 的圆。

坐标平面内有一个左下角在原点，右上角在 (xCorner, yCorner) 的矩形。你需要判断是否存在一条从左下角到右上角的路径满足：路径 完全 在矩形内部，不会 触碰或者经过 任何 圆的内部和边界，同时 只 在起点和终点接触到矩形。

如果存在这样的路径，请你返回 true ，否则返回 false 。

涉及知识点

dfs

解决思路

数学题，没啥好说的。先判断是否包含左下和右上两点，包含就错误。然后遍历与左边上边相交、相切的圆，并挨个对其它圆进行dfs，如果两圆相交且交点在内部、进一步判断第二个圆是否与右边下边相交相切，如果相交相切就错误。完成循环和dfs就能得到最终答案。判断条件由数学公式推导得来，高中解析几何难度。

class Solution:
    def canReachCorner(self, xCorner: int, yCorner: int, circles: List[List[int]]) -> bool:
        # 判断点 (x,y) 是否在圆 (ox,oy,r) 内
        def in_circle(x: int, y: int, ox: int, oy: int, r: int) -> int:
            return (x - ox) ** 2 + (y - oy) ** 2 <= r**2

        # 判断圆 (ox,oy,r) 是否与矩形的上边界/左边界相交
        def cross_left_top(ox: int, oy: int, r: int) -> bool:
            a = abs(ox) <= r and 0 <= oy <= yCorner
            b = abs(oy - yCorner) <= r and 0 <= ox <= xCorner
            return a or b

        # 判断圆 (ox,oy,r) 是否与矩形的右边界/下边界相交
        def cross_right_bottom(ox: int, oy: int, r: int) -> bool:
            a = abs(ox - xCorner) <= r and 0 <= oy <= yCorner
            b = abs(oy) <= r and 0 <= ox <= xCorner
            return a or b

        # 定义 dfs(i) 表示从第 i 个圆开始搜索
        def dfs(i: int) -> bool:
            x1, y1, r1 = circles[i]
            # 说明到达右下，能够切分这个矩形
            if cross_right_bottom(x1, y1, r1):
                return True
            vis[i] = True
            for j, (x2, y2, r2) in enumerate(circles):
                if vis[j] or not ((x1 - x2) ** 2 + (y1 - y2) ** 2 <= (r1 + r2) ** 2):
                    continue
                # 两圆相交，且点A严格在矩形内，继续递归
                if ((x1 * r2 + x2 * r1 < (r1 + r2) * xCorner)
                    and (y1 * r2 + y2 * r1 < (r1 + r2) * yCorner)
                    and dfs(j)):
                    return True
            return False

        # 判断每个圆
        vis = [False] * len(circles)
        for i, (x, y, r) in enumerate(circles):
            # 圆包含矩形左下角，或右上角
            if in_circle(0, 0, x, y, r) or in_circle(xCorner, yCorner, x, y, r):
                return False
            # 从左上角的圆开始递归，它能到达右下角
            if (not vis[i]) and cross_left_top(x, y, r) and dfs(i):
                return False
        # 没有连通，可行
        return True
        

声明

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