Corn 的自留地

1. 滑动窗口的本质

首先是近半个月 leetcode 的每日一题基本都是滑动窗口的题，做多了也有自己的思考，写一篇总结。

滑动窗口，顾名思义，就是通过维护子数组的左右边界，来枚举子数组，因为这个左右边界都只会向右移动，所以就叫做滑动窗口。

首先，比较一下滑动窗口的做法和暴力枚举子数组的做法有何不同。

暴力枚举子数组，需要在右边界移动一次后，重新枚举左边界，直到左边界移动到右边界之前的位置。
滑动窗口，在右边界移动一次后，只需要从左边界之前的位置开始枚举，直到左边界移动到右边界之前的位置。

暴力枚举子数组的复杂度是 O(n^2)，而滑动窗口的复杂度是 O(n)。

这么看来，滑动窗口本质上就是对子数组枚举的剪枝。

那什么题可以这样做呢？为什么可以这样剪呢？

做法和例题

一个我听说的滑动窗口的口诀是“越长越合法”的子数组问题使用滑动窗口。

先来严格定义一下“越长越合法”：

即，当一个数组满足某个条件时，如果这个条件是“越长越合法”的，那么包含这个数组作为子数组的数组也一定满足这个条件。

对于这种问题，使用滑动窗口的解法如下：

初始化窗口的左边界和右边界为0，记录变量 cnt 和 ans，初始化为0.
移动窗口的右边界，同时遍历数组的元素，然后直到当前窗口代表的子数组满足条件。
移动窗口的左边界，直到窗口代表的子数组不再满足条件，然后更新 cnt 为 cnt + 左边界移动的次数。
更新答案为 ans = ans + cnt。
重复步骤2-4，直到遍历完整个数组。

这样，我们就能得到一个“越长越合法”的子数组的数量为 ans 。例题见 LeetCode 2799. 统计完全子数组的数目。

为什么可以这样做

上面已经举例回答了第一个问题：什么题可以这样做。

下面我继续回答第二个问题：为什么可以这样剪。也就是说，为什么这么做可以得到合法子数组的数量，不用从0开始枚举左边界。

这种做法，除了可以看作是暴力枚举的剪枝之外，还可以看作是分类讨论。

枚举右边界的过程，可以看作是分别计数以右边界为元素之一的子数组集合中合法子数组的数量。

那么，对于每一个原数组元素（若一共有n个元素）作为的右边界，我们可以彼此独立地划分出n个不重不漏的类。而每一个类拥有的特殊条件是所有子数组拥有同样的右边界。

这样分类之后，对于每一个类，我们只需要知道左边界的可能性有几种，就知道这个类的合法子数组有多少种了。

那有没有什么办法可以让我们不用枚举左边界，而是可以直接知道左边界的范围呢？

答案是有的。

首先根据“越长越合法”的原则，假设以左边界为 l 的子数组和右边界为 r 的子数组是合法的，那么以 i （i < l）为左边界的子数组也一定是合法的（注意一个类的右边界是不变的，都是同一个）。

因此，我们只需要找到最右边的合法左边界 l（即 l 配上 r 是合法的但 l+1 不合法），就可以直接知道这个类的合法子数组数量为 l+1（l 从0开始）。

再次回看之前的做法，不难发现，第二步实际上就是分右边界的类的过程。第三步实际上就是在找最右边的左边界的右边一个元素的过程。

不过，为什么不从0开始枚举左边界寻找最右边的左边界仍然是一个不太显然的问题。下面进行证明解释。

命题：以r作为右边界的类的合法子数组的左边界范围在以r+1作为右边界的类中也是合法的。

证明：假设以r作为右边界的类的合法子数组的左边界范围为[0,i]（0 <=i <= r），组成的子数组为[i,r]。

那么以r+1作为右边界的类中，以同样的左边界范围[0,i]（0 <= i <= r）组成的子数组是[i,r+1]。

又因为“越长越合法”的原则，[i, r+1] 包含 [i, r] ，所以[i, r+1]的左边界范围[0,i]仍然是合法的。

这样我们就清楚地知道了为什么左边界不用从0开始了。

思路推广+例题

进一步推广，在我们理解了滑动窗口的本质的本质是分类讨论之后，即使面对的是不满足“越长越合法”的子数组问题，只要我们能够通过某种方式在知道右边界的情况下，以O(1)的时间复杂度得到左边界的范围，同样可以使用滑动窗口。

可见，其中体现的最重要的思想是“分类讨论”。

具体例题见 LeetCode 2444. 统计定界子数组的数目

2. 集合与二进制

主要是参照的这一篇文章分享｜从集合论到位运算，常见位运算技巧分类总结！

3. 最近做到的一道很舒服的动规

题目是 LeetCode 486. 预测赢家

这里整理一下我之前做这道题的思路

首先是看到分数最大化和这种分阶段的回合制游戏，我就想到用动态规划来解决。

于是先套一下相关概念

阶段 k：不同的回合（每个玩家动一次表示一个回合）
状态 Sk：当前用于进行游戏的数组，做决策的人是先手还是后手
决策 xk：选择最左边的数还是最右边的数，还是等待对手的决策

由于每个阶段只能拿处于边界的数字，所以当前用于游戏的数组一定是原数组的某个子数组。于是我们可以使用l，r两个指针来表示当前子数组的左右边界，以此来表示当前用于进行游戏的数组。
再用 is_first 表示是先手还是后手
xk = 0 表示选择最左边的数, xk = 1 表示选择最右边的数

状态转移方程：
初始状态为 Sk = (l, r)

pythondef Sk_1(l, r, xk): # xk 为当前先手的人的决策
    if xk == 0:
        Sk_1 = (l+1, r, is_first=0)
    else:
        Sk_1 = (l, r-1, is_first=0)
    return Sk_1

评价函数：

plaintextdef value(l, r, xk):
    if xk == 0:
        return arr[l]
    else:
        return arr[r]

发现概念都能套的进去，不过还是要先论证下其是否有动态规划的性质才能用动态规划来解。

首先是最优子结构性质：

问题的最优解包含子问题的最优解。

这个题目，我们定义子问题为经过了若干个回合之后，使用当前数组重新开始的游戏。

假设子问题的最优解（决策）不被包含于问题的最优解中，而是存在一个更有的解记为更优解，那么我们可以将原问题最优解在子问题的状态之后的解用更优解代替，得到原问题一个更优的解。

这与原问题的解是一个最优解矛盾。因此，问题的最优解包含子问题的最优解。

其实上面的证明就是想说无后效性，即当前状态的最优解只由当前的状态影响，而不受之前的决策影响。

其次是重叠子问题性质：

子问题的最优解可以重复使用。

不太明显，不过不影响我们使用动态规划。

开始写目标函数的递推公式

a 为原数组， n 为数组长度

定义 m[k][i][j] 表示当前状态下该玩家能获得的最大分数

其中（0 <= i <= j < n）：

k表示是否是先手，0表示后手，1表示先手

i表示当前用于游戏的子数组的左边界

j表示当前用于游戏的子数组的右边界

m[k][i][j]的计算公式如下：

当 k == 1 时，表示当前玩家是先手，则：

plaintextm[k][i][j] = max(
    a[i] + m[0][i+1][j], # 选择左边界
    a[j] + m[0][i][j-1]  # 选择右边界
)

当 i == j 时，表示当前子数组只有一个元素，则：
    m[k][i][j] = a[i]

当 k == 0 时，表示当前玩家是后手，则：

plaintextm[k][i][j] = 
    # 对手会选择左边界
    if m[0][i+1][j] + a[i] > m[0][i][j-1] + a[j]:
        m[1][i+1][j]
    else:
        m[1][i][j-1]

当 i == j 时，表示当前子数组只有一个元素，则：
    m[k][i][j] = a[i]

时间复杂度： $O(n^2)$ 因为 k 只有 2 种取值

代码实现

pythonclass Solution:
    def predictTheWinner(self, nums) -> bool:
        n = len(nums)

        m = [[[nums[i] if k == 1 and i == j else 0 for j in range(n)] for i in range(n)] for k in range(2)]

        for i in range(n-2, -1, -1):
            for j in range(i+1, n):
                for k in range(2):
                    if k == 1:
                        m[k][i][j] = max(m[0][i+1][j] + nums[i], m[0][i][j-1] + nums[j])
                    else:
                        if m[0][i+1][j] + nums[i] >= m[0][i][j-1] + nums[j]: # 对手拿 nums[i]
                            m[k][i][j] = m[1][i+1][j]
                        else:
                            m[k][i][j] = m[1][i][j-1]

        return m[1][0][n-1] >= m[0][0][n-1]

pythonsol = Solution()

nums = [1,5,233,7]
print(sol.predictTheWinner(nums))

True

一、概要设计

下面，我将介绍本系统的概要设计。
整个软件系统采用经典的MVC架构，实现各个功能模块的解耦。
其中，用户界面 views 负责各个界面组件的布局和样式实现，负责接受用户交互事件后转发给其绑定的controller进行处理
然后，控制器 controllers 负责处理各个组件的操作事件，通过调用数据模型提供的数据处理接口获取用户当前需要的数据，最后通过调用与其绑定的视图组件提供的信息展示接口将处理完成的数据再通过视图展现给用户。
然后，对应涉及到复杂算法的数据处理操作，我们将核心算法逻辑封装在算法服务 Service 模块中，供数据模型模块调用，实现核心算法和简单数据模型的进一步解耦。
总之，在这样的架构下，软件系统的任何功能都遵循着这样一套统一的交互流程。

用户通过界面上的组件触发操作事件。
系统的控制器模块会捕捉到这些操作并解析用户的输入，生成相应的数据请求。
数据请求会传递到模型层，模型层根据请求调用核心算法进行数据处理，最终生成用户所需的结果。
控制器层会将这些结果通过视图层展示给用户。

整个流程各个模块职责清晰独立。
在架构层面上极大地增强了软件的可修改性，为后续的迭代升级工作打下了良好的基础。

二、详细设计

在界面设计方面，对于不同的功能需求，系统分为了相应的各个的界面
包括文件上传窗格、波形展示窗格、震源检测窗格和设置窗格。
每个窗格对应不同的功能模块，用户可以在这些模块之间方便地切换使用他们目前需要的功能。

右图展示了这些窗格的布局，确保用户能够清晰地查看地震波形、检波器位置和震源检测结果。
整体设计简洁直观，便于操作。

在各个模块的详细设计上，
左图展示了本项目的类图，其详细描述了构成各个模块的的类的属性和方法的定义。
可以看到，Views模块就分为了文件上传，波形展示，震源检测和设置四个类，分别对应之前展示的四个界面。

Models 模块定义的有 TraceFile 和 Config 两个类，其中最为关键的是 TraceFile 类，其被定义为对地震波数据文件的抽象，包括基本信息，波形数据，检波器位置数据等属性。
同时实现了加载波形数据文件，查询指定到号的波形数据，获取震源位置等方法，涵盖了本软件系统的核心功能。

最后 Services 模块定义了计算震源位置和估计地震发生大致区间的核心算法函数，为核心功能实现提供底层支撑。

4.1 接下来，我将简要介绍本软件实现震源检测的核心算法叫做 SSA，对应中文名叫做源扫描算法。其核心思想为：
在我们获取到了当前3维区域中各个采样点在一定时间段的波形数据后，此时我们想要知道当前这个时间段的哪一刻和哪个位置发生了地震。
首先我们知道
最直接的想法便是，对于这个时间段的每一刻时间，这个区域中的每一个点，我们都先假设其为震源，然后计算出所有波形在这一刻这个点为震源的情况下，叠加后的平均振幅有多大，我们把这个平均振幅叫做亮度。亮度越高，意味着如果这个点是震源，其引发的造成整个区域中检波器的震动越强。当遍历完各个时刻下各个区域位置的亮度后，选取亮度最高的点作为检测结果。

不过很明显的，这个算法本质上是一个暴力搜索算法，其时间复杂度为O(XYZT)，其中XYZ分别是区域中三个维度的采样点数，T是时间刻的采样点数。导致了它计算效率低下，而且对于更高精度的检测计算量更是成倍增加

为了解决原始SSA算法的计算瓶颈，我们采用了启发式搜索算法——遗传算法替换原算法中搜索的过程。
通过将震源参数（x,y,z,t）作为种群的的染色体编码，对应的亮度作为评价标准。在若干轮迭代进化之后，便能得到相对精确的结果

4.2 我们的算法避免了传统的人工拾取震相方法，通过直接利用波形振幅和时差信息，从而提升了地震事件定位的准确性。首先，算法会对波形数据进行归一化处理。
然后，基于三维速度模型，系统构建走时表并进行空间扫描。接下来，我们通过亮度函数计算，对时间窗附近的波形振幅进行加权求和，从而提高抗噪能力。最后，系统通过并行扫描和亮度阈值筛选，提取出最有可能的震源位置，并生成震源的时空分布热力图，输出震源的三维坐标和发震时刻。

近期算法做题总结