题目 思路 接的雨水总量为每个柱子能够接的雨水之和，而每个柱子的接水量计算公式为： $$ 接水量=\min(左右两边最高柱子)−当前柱子的高度 $$ 那么直接新建两个数组 left_max 和 right_max 来存储每个柱子左右两侧的最大高度， left_max[i] 和 right_max[i] 分别表示柱子i左右两侧的最高柱子高度( left_max[i] 从左往右计算， right_max[i] 从右往左计算)，然后再通过遍历计算每个柱子的接水量累加起来即可。 上面的方法时间复杂度和空间复杂度均为$O(n)$。时间已经是最快了，那么空间上还能不能进行优化呢？上面的方法空间耗费主要来自于新建的两个存储数组。由于数组left_max是从左往右计算，数组right_max是从右往左计算，因此可以使用双指针和两个变量代替两个数组。 对于左指针left来说，其左右两侧的最大高度分别为left_left_max和 left_right_max；同理右指针有right_left_max和 right_right_max。由于$right > left$，故$right\_left\_max \ge left\_left\_max$ 且 $left\_right\_max \ge right\_right\_max$，这两个不等式画个图便可直接看出。 由上面的不等式可知： 若$right\_right\_max > left\_left\_max$，则必有$left\_right\_max > left\_left\_max$，又left_left_max是可知的， 那么就可以计算left指向的柱子的接水量。 若$right\_right\_max < left\_left\_max$，则必有$right\_left\_max > right\_right\_max$，又right_right_max是可知的， 那么就可以计算right指向的柱子的接水量。 在处理了left指向的柱子后，++left向右移; 在处理了right指向的柱子后，--right向左移，直到全部柱子都被处理。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public: int trap(vector<int>& height) { int ans, left, left_max; int right, right_max; ans = left = 0; right = height.

题目 思路 题目中要求找到所有 「不重复」且和为0的三元组，这个「不重复」的要求使得无法直接使用三重循环枚举所有的三元组找到答案。当然，可以直接用三重循环枚举每个答案，再使用哈希表进行去重(即先对得到的答案进行排序，比如从小到大，再转化成string后存放进unordered_set)，得到最终答案。这种做法时间复杂度和空间复杂度都很高，因此需要换一种思路来考虑这个问题。 重复的答案形式为：$(a, b, c)、(a, c, b)、(b, a, c)$…… 假设$a \le b \le c$，如果能保证只有$(a, b, c)$这种形式的答案会被枚举，就能够直接去除掉重复的答案，而不必再使用哈希表来进行去重了。 要实现这一点，就可以通过将数组中的元素从小达到进行排序，随后使用三重循环进行遍历，且 「每重循环相邻两次枚举的元素不能相同」，否则也会造成重复。例如：一个排完序后的数组为$[-1, 0, 1, 1, 2, 3]$，第一次枚举到的三元组为$(-1, 0, 1)$ ，如果第三重循环继续枚举下一个相邻元素，那么仍然为 $(-1, 0, 1)$，这就产生了重复，因此就需要将第三重的循环跳到下一个不相同的元素，即数组中的最后一个元素3，枚举三元组$(-1, 0, 3)$。 至此，我们已经对初始版本进行了空间上的优化，下面给出伪代码： 1 2 3 4 5 6 7 8 9 10 nums.sort() for first = 0 .. n-1 // 只有和上一次枚举的元素不相同，我们才会进行枚举 if first == 0 or nums[first] != nums[first-1] then for second = first+1 .. n-1 if second == first+1 or nums[second] !

题目描述： 思路 时间复杂度为 $O(n^2)$ 的算法思路很简单，直接采用暴力法使用两层循环遍历每一种可能，判断是否存在答案。 这里详细说明一下时间复杂度为 $O(n)$ 的算法，暴力法之所以慢是因为寻找 target - x 的时间复杂度过高。那有没有什么方法可以加速寻找元素 target - x 是否存在且存在时可以知道其索引呢？有的，那就是使用哈希表来做，以target - x 为key，以索引为value。这样，寻找target - x的时间复杂度就变为了 $O(1)$，极大地提高了效率。 具体来说，对于遍历的每个元素，先判断其target - x是否存在，若存在，则直接返回对应的下标；若不存在，则将x存入哈希表，方便后续的查找。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 // 暴力法 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for (int i = 0; i < nums.

前言 最近在看的一篇布局论文，发现其将 Mean Shift 算法扩展来进行聚类操作，而想要读懂文章就必须先理解此算法，故此文章记录的就是我对该算法的理解，若有理解错误的地方，欢迎留言指正。 简介 Mean Shift 是一种「基于密度」的聚类算法，它是一种非参数聚类方法（无需开始前指定簇数），可以自动从数据点的分布中推断出簇的数量。该算法会让数据点朝着密度更高的地方进行快速移动，直到达到该数据点所在区域的局部密度峰值地（即簇中心）。 通俗来说，将密度峰值比作山顶，数据点视为登山者，该算法就是让每个登山者沿着最快的路径登上离自己最近的山顶，登上同一个山顶的登山者就属于同一个簇。 带宽 带宽(bandwidth)是Mean Shift 算法唯一需要指定的参数，它用于确定每个点的邻域。以当前点为圆心，带宽为半径画圆，所画出的圆就是该点的邻域，在邻域内的点就是该点的邻居。 带宽非常重要，它会影响簇的大小： 小带宽。这会形成许多小簇，因为只有近距离的点才会形成一个群集。 大带宽。这会形成较少的大簇，因为距离远的点也可以形成一个群集。 核函数 在 Mean Shift 算法中，核函数的作用就是用来衡量当前移动点的邻居对该移动点的下一个位置的影响程度(由于该点是不断移动的，所以其邻居也会不断变化)。 为什么使用核函数？ 核函数有助于平滑数据并确保远离中心的点不会过度影响结果。它使得 Mean Shift 算法关注数据中的局部情况而不是全局，有助于进行分类。 核函数类型 核函数有非常多的类型，比如Uniform Kernel、Epanechnikov Kernel等，其中最常用的的是高斯核函数(Gaussian Kernel)： $$ K\left(\frac{x - x_i}{h}\right) = \exp\left(-\frac{||x - x_i||^2}{2h^2}\right) $$ $x$: 当前点坐标 $x_i$: 当前点的邻居坐标 $h$: 带宽 物理意义: 距离$x$越近的$x_i$，权重越大；超过带宽$h$的点权重为0 核密度估计(Kernel Density Estimation, KDE) 在Mean Shift算法中，KDE 的作用是用来估算数据点的局部密度分布。它通过核函数将每个点的邻域内的其他点进行加权，提供一个平滑的、连续的密度估计，帮助识别局部密度峰值(即告诉我们山顶在哪)，确定点的移动方向。KDE具体公式如下: $$ f(x) = \frac{1}{nh^d} \sum_{i=1}^{n} K\left(\frac{x - x_i}{h}\right) $$ $n$: 数据集中的点数 $h$: 带宽 $d$: 数据的维度 $K\left(\frac{x - x_i}{h}\right)$: 核函数，加权每个点 $x_i$ 对当前点的密度贡献 均值漂移向量(Mean Shift Vector) 在使用KDE确定了移动方向后，就需要使用均值漂移向量来将该数据点移动到当前的山顶。

问题发现

最近在使用 git push 命令时发现连接超时，因为我使用的是用公钥走ssh协议进行连接，输入命令 ssh -T git@github.com 发现果然是ssh连接超时。在网上搜索了一圈，找到问题是主域名 github.com 的 IP 被彻底墙了。

解决办法

通过Google大法，找到供 ssh 连接的子域名 ssh.github.com IP 还活着。因此，解决办法就是往 ~/.ssh/config 文件 中添加下面的配置：

至此，问题成功解决。

参考资料

1. https://docs.github.com/en/authentication/troubleshooting-ssh/using-ssh-over-the-https-port
2. https://ww-rm.top/posts/2024/01/17/githubssh-timeout/

环境搭建 我是在WSL2下的Ubuntu进行Python开发的，所以本笔记的环境搭建仅适用于Liunx开发环境，Windows下搭建环境请自行Google。 miniconda 首先，先安装 miniconda，直接按照官方教程即可安装。 不同的项目可能需要不同版本的库或包，而直接在系统中安装多个版本可能会导致冲突和不可预见的问题。为了解决这个问题，conda虚拟环境应运而生。 conda虚拟环境允许你在同一台机器上创建多个 「独立」 的环境，每个环境都有自己的Python解释器和依赖库，从而实现了项目之间的隔离。这样，你可以在一个环境中安装特定版本的库，而不影响其他环境。 miniconda 的常用命令有： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 # 创建一个名为 myenv 的环境并指定在该环境中安装 3.7版本的Python conda create --name myenv python=3.7 # 激活或切换到名称为 myenc 的环境 conda activate myenv # 在当前环境下安装 numpy 包 conda install numpy # 在当前环境下安装指定版本的 numpy 包 conda install numpy=1.

A星算法简介 A*（A星）算法是一种基于格子（Grid）的寻路算法，用于从众多路径中，寻找一条从起点到终点代价最小的路径。基于格子也就是说会把地图看作是由 w*h 个格子组成的，因此寻得的路径也就是由一连串相邻的格子所组成的路径。 既然是要寻找代价最小的路径，那么遍历节点时，就不能盲目地遍历，而是挑那些 「最有可能代价很小」 的节点来运算。如何获得这种代价很小的节点呢？这就需要使用启发函数来计算每个节点的代价了（在A*中启发函数也被称为 估价函数 ）。 一条路径的代价无非就是路径长度（不带权重时），可是当寻找路径时，该如何计算代价呢？那就是将代价分为两个方面： 已知代价。 即从起点到当前节点的路径长度。 未来可能会有的代价。 用 “猜” 的，假设当前节点到终点之间没有障碍，代价是多少。 那么我们就可以得到估价函数为：f(n) = g(n) + h(n)，其中g(n)表示起点到格子n的代价，h(n)表示格子n到终点的代价，f(n)表示格子n的代价。 由于在EDA中，是使用曼哈顿距离来表示两点之间的距离，所以本文采用曼哈顿距离来计算代价。 知道启发函数是怎么回事之后我们就可以开始遍历节点了。从起点开始，计算其四周节点的代价，并把那些节点放到一个 「池子」 里面去，之后每次都从池子里面捞出来代价最小的节点，继续计算其周围节点的代价。 如果遍历到目标节点，或者池子空了之后，寻路就结束了。那么如何获得路径呢？我们从遍历的过程可以看出，节点加入到池子之前，我们知道这些加入到池子中的节点是来自于当前节点的，所以在加入池子之前将那些节点的父节点设为当前节点，等寻路到目标节点之后我们逐个节点遍历其父节点，就可以遍历完最短路径。 对于算法，有以下几点需要注意： 计算当前节点的周围节点的代价值时，如果需计算的节点原先就已经算过代价值，且当前算出来的代价值比原先的小，说明这个节点从当前节点过去路径会更短一些，应更新其父节点和代价值。 我们每次都是从「池子」中捞出代价最小的节点，所以用小根堆来实现「池子」是十分高效的。 综上所述，可以画出 A* 算法流程图： A星算法的实现 作者采用 C++ 来实现 A* 算法，代码已上传至此仓库