题目描述： 思路 时间复杂度为 $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* 算法，代码已上传至此仓库

软件安装与更新 在Linux下，一般用包管理器来安装软件，它能自动化地完成软件的安装、更新、配置和移除功能，优雅而快速。 软件包管理器的一个重要组成部分是软件仓库。软件仓库是收藏了互联网上可用软件包（应用程序）的图书馆，里面往往包含了数万个可供下载 和安装的可用软件包。 有了软件仓库，我们不需要手动下载大量的软件包再通过包管理器安装。只需要知道软件在软件仓库中的名称，即可让包管理器从网络中抓取到相应的软件包到本地，自动进行安装。 但是与应用商店相比，使用包管理器安装需要预先知道所需软件在软件仓库中的对应包名，和应用商店相比无法进行模糊搜索（不过你也可以在包管理器官网上进行查找包名，再通过包管理器安装）。 作者使用的是Ubuntu系统，Ubuntu下默认的包管理器为apt，所有后面的讲解以apt为例。 使用包管理器系统安装 搜索 安装前，先在浏览器中搜索所需的软件，查找包名，再使用 apt search package_name 命令搜索软件仓库，查看对应的包名是否在软件仓库中(这步可跳过，只要知道要安装的软件包名即可)。 安装 找到要安装的软件的包名后，使用命令 apt install package_name 进行安装。 PS： 如果提示当前用户无安装软件权限，则在命令前加上 sudo，即 sudo apt install package_name，输入此命令后会要求用户输入密码(输入的密码不会在终端显示)。 官方软件源镜像 通过 apt 安装的软件都来源于相对应的软件源，每个 Linux 发行版一般都带有官方的软件源，在官方的软件源中已经包含了丰富的软件，apt 的软件源列表在 /etc/apt/sources.list 下。 Ubuntu 官方源位于国外，往往会有速度与延迟上的限制，可以通过修改官方源为其镜像实现更快的下载速度。镜像缓存了官方源中的软件列表，与官方源基本一致。 修改官方源为镜像步骤 本例以修改官方源为 USTC Mirror 为例。注意：在操作前请做好备份。 一般情况下，/etc/apt/sources.list 下的官方源地址为 http://archive.ubuntu.com/ ，我们只需要将其替换为 http://mirrors.ustc.edu.cn 即可。 如果你使用 Ubuntu 图形安装器安装，默认的源地址通常不是 http://archive.ubuntu.com/ ， 而是 http://<country-code>.archive.ubuntu.com/ubuntu/ ，如 http://cn.archive.ubuntu.com/ubuntu/，同样也将其替换为 http://mirrors.ustc.edu.cn 即可。 可以使用如下命令： $ sudo sed -i 's|//.*archive.ubuntu.com|//mirrors.ustc.edu.cn|g' /etc/apt/sources.list 当然也可以直接使用 vim、nano 等文本编辑器进行修改。

Better C++ Syntax 该插件主要作用是提供 C++ 语法高亮 Bookmarks 该插件主要作用是允许用户在代码中添加书签，以便快速跳转到这些特定位置。这个插件对于需要在大型项目中导航和跟踪重要代码段的开发者来说非常有用。 该插件常用快捷键为： 添加书签：Ctrl+Alt+K 删除书签：将光标放在带有书签的行上，然后使用 Ctrl+Alt+J 切换书签：Ctrl+Alt+Q可以在书签之间切换，如果当前行有书签，则会删除它。 跳转到下一书签：Ctrl+Alt+L 跳转到上一书签：Shift+Ctrl+Alt+L C/C++ 该插件主要作用是提供了一系列的工具和功能，例如代码分析功能、代码格式化功能、代码提示等。 CMake 该插件主要作用是CMake语法高亮、CMake代码自动补全。 CMake Tools 该插件主要作用是提供各种CMake编译相关的小工具，包括在底部状态栏显示一些快捷工具。 cmake-format 该插件的主要作用是格式化 CMakeLists.txt 文件，使其保持一致和可读性。安装此插件前，需要先安装cmake-format工具。 Code Runner 该插件的主要作用是运行选定的代码片段。 该插件常用快捷键为： 运行选定代码 Ctrl+Alt+N 或 直接点击右上角的三角形 或 点击右键菜单中的 Run Code 停止正在运行的代码 Ctrl+Alt+M 或 点击右键菜单中的 Stop Run Code 插件详细说明地址 Diff 该插件的主要作用是比较两个文件的不同之处，直接在资源管理窗口中选择两个要比较的文件，将会直接显示比较结果。 Error Lens 该插件的主要作用是将代码中存在的问题突出显示(包括错误、警告和语法问题)，它不仅在代码行尾显示问题，而且会在整行进行高亮，使得诊断信息更加明显。 GitLens 该插件的主要作用是可以更方便地在VsCode中进行Git相关操作，该插件的使用可看此视频了解。 PS: 建议能够熟练使用Git命令后再使用此插件，Git的学习可看此教程。 GitHub Copilot 该插件的主要作用是辅助编码。该插件是GitHub的AI编码工具，能根据注释、函数名、函数参数编写代码。该插件的详细介绍可看此文章。 PS: 该插件需要进行GitHub学生认证才能免费使用，可参考此教程。 Include Autocomplete 该插件的主要作用是提供编写 C++ #include 语句时自动补全功能 Markdown All in One 和 Markdown Preview Enhanced 这两个插件都是用于帮助编写Markdown文件