wolverine12138

题解

/ 注册

全部文章 / 题解（共6篇）

题解 | #旅行Ⅰ#

拓扑排序拓扑排序的核心在于维护每个节点的入度，每个节点会指向其他的节点，记录释放当前节点能减少入度的节点列表，同时维护一个优先队列，用结构体自定义排序算法。需要注意的是下标有时从1开始，有时从0开始，我的想法是做题前统一转化成从0开始，避免混乱。 * struct Point { * int ...

C++

2022-03-22

0 346

题解 | #长度为 K 的重复字符子串#

滑动窗口滑动窗口的思路是很容易想到的，但是在移动窗口的过程中，如果每次都判断当前是否存在重复元素显得效率低下。此时一种优化的思路是：窗口中数字变化无非来自左边元素的删除和右边元素的增加，只有删除了正好出现两次的元素，或者增加了正好出现一次的元素，才会导致窗口内重复元素种类的变化。显然重复元素种类大...

C++

2022-01-19

0 457

题解 | #朋友圈#

并查集涉及集合之间的关系，核心是每个元素最终都将唯一指向某个自旋元素，统计这样的元素数目以及它们出现的次数，即可得到每个集合的大小。需要注意的是初始时每个元素并非自旋，可以在查找其父节点而不可得的时候将其设置为自旋，当使用秩时，只有自旋节点的秩是有价值的，也可以在第一次查找到自旋节点时设置。 #i...

C++

2022-01-08

0 366

题解 | #牛牛们吃糖果#

01背包问题动态规划中的核心在构建动态规划的矩阵和更新的方法。 1、矩阵行（i）:表示仅考虑[0, 1, ..., i]元素。 2、矩阵列（j）:表示最大容量为j。此时dp[i][j]即表示相应的奖励，在选择i元素后，可选元素和最大容量都收缩。更新策略是外层累加i，内层增加最大容量j。可以采用滚...

C++

2022-01-06

1 491

题解 | #合法连续子段#

滑动窗口滑动窗口的核心在于维护窗口的左指针和右指针的移动条件，有时可以一次移动多位，有时只能移动一位。移动多位的条件要求跳过的情况已经被覆盖，本例左指针一次移动多位。 #include<iostream> #include<vector> #include<unord...

C++

2022-01-05

0 527

题解 | #对称飞行器#

从一个节点出发，搜索最短路径，选择广度优先搜索，核心在维护一个移动步数（深度）不减的队列；过程中每个节点只会入队列一次，入队列后将其标记，避免重复无效的入队操作。 #include<iostream> #include<vector> #include<queue>...

C++

2021-12-29

3 535