在通过网上一些资料稍微系统学习了一下DFS相关的内容，还有初步接触了一些DP的基础知识之后，我开这篇blog用来记录我刷相关的练习题的思路 打家劫舍 Ⅱ leetcode213第一版代码是错误的。 我的思路是，现在房屋形成了一个环，我可以任意枚举一个位置入手，把环剪开，此时还原成房屋是一排的情况，然后套用Ⅰ的dp模板就可以了。 这样做的问题在于，dp模板在新的一排房屋上，相当于状态树是从i+1的位置开始的，但是dp模板是套用在从0开始的。也就是说状态树结点上前后结点的值有严格的依赖，任意剪切环，形成的数组，从前往后的dp并不对应原始数据的状态树。 以下是...

这篇blog用来整理一些常见的可以使用深度优先搜索的问题模板 写在最前面在这篇blog中会高频地出现三个词汇，DFS、递归、回溯，实际上DFS与后二者的关联是十分密切的。 狭义上来说，DFS是在图上面做搜索的一种算法，它使用深度优先，依次处理各个结点。可以用递归函数的形式实现，也可以用循环+栈的形式实现。 但是从广义上来说，对于可以枚举状态的问题，问题的状态转移的过程本就可以抽象成一棵树，而树本质上就是一个特殊的图。当我们使用递归函数，搜索问题的各个状态的时候，就可以看作，我们是在一张“特殊的”图上，做DFS。 关于回溯与它们的联系，后面再进行补充。 基...

这篇blog用来整理图有关的数据结构与算法的知识 图的存储结构邻接矩阵邻接矩阵本质上就是一个二维数组，分为两种情况 无权图，m[i][j] == 1代表vi有到vj的边；否则为0，代表不存在这样的边 有权图，元素为inf代表两点间不存在边，否则存在，且对应元素值为权重 从数据结构上来说，有向无向图没有区别，都是二维数组，且均适用于上面描述的两种情况。只是无向图有m[i][j] == m[j][i]恒成立的性质 链式前向星本质上是数组实现的静态邻接表 掌握的关键在于记住三个点 使用到的数据结构即其含义 初始化的方式 ...

在平常练习算法题的过程中，有的题目常常涉及到使用一些基本的小算法作为整个解决方案中的一部分，例如gcd、进制转换，乃至KMP等等，我用这篇blog对这些小算法。我在这篇blog中对它们做一个综合的整理。 gcdint gcd(int x,int y){ if(x%y == 0)return y; else return gcd(y,x%y); } 辗转相除法求最大公约数 进制转换lcmint lcm(int x,int y) { return x*y/gcd(x,y); } 利用最大公约数求最小公倍数 Fibona...

在过去的算法竞赛中，我常常接触到一些库中的工具，例如函数、容器、类等等，但是总是零零散散的，记忆也不是很牢，每次都是用到了现查。于是我用这篇blog做一个简单的整理 头文件algorithmmax()函数在 C++ 中，max 函数是一个非常实用的函数，用于比较两个或更多数值并返回其中的最大值。这个函数定义在 algorithm 头文件中。 #include <iostream> #include <algorithm> // 引入algorithm头文件以使用max函数 int main() { int a = 10;...

之前零零散散地接触过一些动态规划的问题，用这篇blog来稍微系统性的记录一下 动态规划的基本步骤 定义数组的基本含义（模板或是灵感） 找到数组元素间的关系（dp的递推式，模板或是灵感） 找到边界的初始值（基本含义定义好了这个通常不难） 递推填表得到需要的元素（结合初始值以及递推式，考虑应该如何进行递推填表，确保新填一个元素需要用到其它元素的时候，其它元素的值已经被填过了） 背包问题01背包（二维解法）问题描述：有n种物品，每种物品只有一个。每个物品有自己的重量和价值。有一个给定容量的背包，问这个背包最多能装的最大价值是多少。 step1定义数组元素的含义...

我正在学习一个用来跑PFL算法的代码框架，读代码的同时用这篇blog记录一些有关联邦学习的基础知识；以及一些python、pytorch的知识 数据集划分的平衡与不平衡含义在联邦学习中，平衡和不平衡主要指数据量上的分布情况： 平衡数据（Balanced Data）：每个客户端拥有的数据量大致相同。例如，如果有10个客户端和1000个数据样本，那么每个客户端分配到的数据约为100条。 不平衡数据（Unbalanced Data）：不同客户端拥有的数据量差别很大。例如，10个客户端中，某些客户端可能分配到300条数据，而另一些可能只有10条。这种情况在实际场...

一些有意思的东西

这篇blog用来记录我读的第二篇有关联邦学习的文献，其中也使用了nash bargaining game 基本概念Representation Collapse Entanglement表示崩塌纠缠：这是指在联邦无监督学习（FUSL）过程中，由于某个本地模型的表示崩塌（即该模型的特征表示不再具有区分度），会影响到全局模型和其他本地模型的表示能力。这种崩塌会导致整个系统的表示能力下降，使得模型在处理非独立同分布（non-IID）数据时效果不佳。 Flexible Uniform RegularizerFUR：灵活均匀正则化器，这是FedU2方法中的一个组件...

这篇blog用于记录我阅读论文《 Improve global generalization for personalized federated learning within a Stackelberg game》过程中学习到的一些基础知识。 基本概念PFL个性化联邦学习：在联邦学习(FL)的基础上， PFL的目标是为每个客户端训练一个个性化模型，适应每个客户端的特定数据分布和需求。PFL适用于各客户端数据分布差异较大，且每个客户端需要一个定制化模型的场景。不同于FL训练一个全局共享的模型，希望是该模型在所有客户端上表现良好。 PFL分类“Towar...