算法题记录 18

131.分割回文串（1782）

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

涉及知识点

字符串，dfs

解决思路

很简单能想到深搜，枚举各种情况即可。

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        ans = []
        path = []

        def dfs(i: int) -> None:
            if i == n:
                ans.append(path.copy())  # 复制 path
                return
            for j in range(i, n):  # 枚举子串的结束位置
                t = s[i: j + 1]
                if t == t[::-1]:  # 判断是否回文
                    path.append(t)
                    dfs(j + 1)
                    path.pop()  # 恢复现场

        dfs(0)
        return ans

732.我的日程安排表3（困难）

当 k 个日程存在一些非空交集时（即, k 个日程包含了一些相同时间），就会产生 k 次预订。

给你一些日程安排 [startTime, endTime) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

MyCalendarThree() 初始化对象。
int book(int startTime, int endTime) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

涉及知识点

差分、线段树

解决思路

直接做会发现非常复杂，要对重复区间进行各种判断相加。但是，有算法基础的话能很快反应出这道题是道非常标准的差分题。
差分算法的核心是记录每个时间段的变化量，而不是直接记录每个时间段的状态。通过这个方法，我们只需要记录增减操作，而不是每个时间点的值。通过这些变化量，我们可以在后续的时间段中计算出真实的预定数。
假设我们有以下两个预定：

预定 1: [10, 15)
预定 2: [12, 20)
我们使用差分算法来记录这些预定的变化。每个预定的起始时间和结束时间都会对活跃预定数产生影响。具体操作如下：

步骤 1: 初始化
我们先定义一个空的字典 self.delta = SortedDict() 来存储时间点上的变化量。

步骤 2: 第一个预定 [10, 15)
对于第一个预定 [10, 15)，我们记录以下变化：

在 startTime = 10 时，预定数增加 1。即：self.delta[10] = 1。
在 endTime = 15 时，预定数减少 1。即：self.delta[15] = -1。

对于第二个预定 [12, 20)，我们记录以下变化：

在 startTime = 12 时，预定数增加 1。即：self.delta[12] = 1。
在 endTime = 20 时，预定数减少 1。即：self.delta[20] = -1。

现在我们已经记录了所有预定的变化，接下来我们可以遍历 self.delta 来计算每个时间点的活跃预定数。

从最小时间点开始（即 10），我们初始化一个变量 active 来表示当前活跃的预定数。初始时 active = 0。
遇到时间点 10 时，self.delta[10] = 1，所以 active 增加 1，变成 active = 1。
遇到时间点 12 时，self.delta[12] = 1，所以 active 增加 1，变成 active = 2。
遇到时间点 15 时，self.delta[15] = -1，所以 active 减少 1，变成 active = 1。
遇到时间点 20 时，self.delta[20] = -1，所以 active 减少 1，变成 active = 0。
通过遍历所有的时间点，我们可以看到活跃预定数的最大值是 2，即在时间段 [12, 15) 内有两个预定重合，达到了最大活跃预定数。

另外，如果有竞赛基础，还应意识到差分能替换为线段树。

from sortedcontainers import SortedDict

class MyCalendarThree:
    def __init__(self):
        # 按键排序，也即根据时间顺序
        self.delta = SortedDict()

    def book(self, startTime: int, endTime: int) -> bool:
        # 在 startTime 时刻增加一个预定，end 时刻减少一个预定
        self.delta[startTime] = self.delta.get(startTime, 0) + 1
        self.delta[endTime] = self.delta.get(endTime, 0) - 1
        
        # 统计当前最大活跃预定数
        ans, active = 0, 0
        for freq in self.delta.values():
            active += freq  # 更新活跃预定数
            if active > ans:  # 手动比较替代max
                ans = active
        
        return ans

1706.球会落何处（1765）

用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。

箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。

将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。
在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 “V” 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。

返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。

涉及知识点

模拟

解决思路

有两种想法，第一种模拟，模拟小球的运动即可。第二种是从下往上先把走到网格的每个格子的结果算出来，遍历到最上方的一行我们就知道小球的出口在哪了，不过这种方法比模拟要复杂很多，没看见几个人在用。

class Solution:
    def findBall(self, grid: List[List[int]]) -> List[int]:
        n = len(grid[0])
        ans = [-1] * n
        for j in range(n):
            # 模拟第 j 列球的移动
            cur_col = j  # 当前列号
            for row in grid:
                d = row[cur_col]  # -1 或 1，表示左/右
                cur_col += d  # 左/右走一步
                # 如果球出界或者卡在 V 形，退出循环，否则继续循环（垂直落入下一排）
                # V 形就是 -1 的左边是 1，1 的右边是 -1，即 row[cur_col] != d
                if cur_col < 0 or cur_col == n or row[cur_col] != d:
                    break
            else:  # 没有中途 break，说明球成功到达底部
                ans[j] = cur_col
        return ans

声明

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