- 博客(90)
- 收藏
- 关注
RSS订阅原创 KMP真的比暴力匹配更快吗？这真不一定
但很神奇的是，暴力的平均比较次数始终略高于KMP，（虽然高的不多，甚至纯随机的测试数据中两者的差别只在个位数），但暴力花的时间就是要小一些。每一本教KMP的书都会告诉你KMP的时间复杂度是O(m+n)，而暴力匹配的最坏情况下会达到O(mn)。暴力匹配的时间复杂度和KMP的时间复杂度都是O(n)（虽然KMP还有个O(m)的建立next时间，但由于m一般远小于n，所以对实际的运行时间没什么影响），但KMP的常数因子更小，所以在比较次数上，KMP的平均比较次数始终小于暴力匹配，但因为是同级的，所以差距不大。
2025-02-15 17:03:29
570
原创 windows资源管理器无限重启
事情的起因是这样的，我电脑上原本有一个老的IDM，但我又下了一个新的IDM，然后直接双击运行了，然后就发现电脑资源管理器无限重启，表现为电脑下方的任务栏不见，整个桌面在间断性刷新，还伴随着黑屏。不过我感觉还是有点奇怪，因为我习惯性是关掉开机自启动的，就算新的IDM默认有开机自启，我把新的IDM全删了应该也不会影响了。措施一、用任务管理器的新建任务打开cmd，然后taskkill /f /im explorer.exe强行杀掉资源管理器，虽然没用，整个屏幕背景全黑了，但至少它不闪了。我是执行的bat卸载的。
2024-12-27 00:30:22
2451
原创 Multi-attentional Deepfake Detection 阅读笔记
论文提出“现在”大多数深度伪造检测的方法是将其视为一种简单的二元分类问题，基本步骤就是先利用骨干网络(backbone network)提取出图像的全局特征，然后把它喂给二元分类器(binary classifier)就可以得到一个真或假的结果。所以作者提出了区域独立的损失(regional independence loss)减少每个注意力图关注的区域的重叠并且对不同的输入保持关注的语义区域的一致性。终于力扣的每日一题打卡完成了，以后应该只会偶尔写题解了，力扣的大概率应该不会再写了，以后还是专心读论文。
2024-11-14 23:16:14
439
原创 力扣每日一题 3261. 统计满足 K 约束的子字符串数量 II
3. 因为左端点为 l 的最长的合法子串是[l,r1],所以[l,r1+1]一定是不合法的，以r1+1为右端点的最长的合法子串的左端点一定在 l 的右边。2. 区间[l,r]的所有合法子串的右端点一定在[l,r]之间，而我们计算了所有右端点在[l,r1]的合法子串和所有右端点在[r1+1,r]的合法子串，刚好把整个区间[l,r]覆盖了，所以也不会有遗漏。那么，如果对于左端点 l ，最长的合法子串的右端点r1，那么对于区间[l,r]，如果r<=r1，那显然[l,r]的合法子串的数量就是[l,r]的所有子串。
2024-11-13 15:19:11
544
原创 力扣每日一题 3258. 统计满足 K 约束的子字符串数量 I
如果数据范围大的话，这题目还真有点难度。但是它的数据太小了，直接暴力就行，只能算简单中的简单了。思路没啥可说的，就按题目要求的做，找到所有的子串，然后检查是否满足0和1的数量最多为k。时间复杂度应该算O(n^3),n表示字符串的长度，空间复杂度应该是O(n*n)满足以下任一条件，则认为该字符串满足。
2024-11-12 22:22:03
304
原创 力扣每日一题 1547. 切棍子的最小成本
每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。dfs的方法就是以整段为递归入口，枚举每个可切割点尝试切割，递归求解。至于我的贪心思想，就是参考哈夫曼树，每次选择花费最小的两块合并，其实就是切分的逆过程。这个题目的正解应该是动态规划，区间dp。但这个题的数据范围太水了，直接dfs递归暴力求解就可以过，完全够不上困难。因为记忆化了，所以时间复杂度应该是O(m^3)，m是cuts的长度。
2024-11-11 14:18:07
278
原创 力扣每日一题 540. 有序数组中的单一元素
因为数据是有序的，所以假设只出现一次的元素位于下标x，那么对于x左边的偶数下标y，一定有nums[y]=nums[y+1]。而对于x右边的奇数下标y，一定有nums[y]=nums[y+1]。如果不考虑时间复杂度要求的话，最简单的就是以步长为2进行遍历，也可以用点位运算把整个数组全异或一边，最后的结果就是答案了。所以我们根据nums[y]=nums[y+1]的y是奇数还是偶数就可以知道x是在y的左边还是右边了。给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
2024-11-10 02:03:56
306
原创 力扣每日一题 3242. 设计相邻元素求和服务
也可以直接把构造函数的参数存起来，然后在查询的函数里找元素位置再计算。要省时间的话，还可以再开个哈希表把元素值和位置做个映射，虽然以这个题来说完全没有必要。不过我选择了把数据进行预处理，开了一个数组存每个元素的相邻和与对角和。在构造函数里就遍历一遍把答案算出来，后面两个查询函数就直接返回答案就可以了。今天这题目确实简单，因为数据范围极小，所以只要按照题目要求去模拟就可以了。构造函数的时间复杂度O(n*n),两个查询的函数的时间复杂度O(1)。空间复杂度O(n*n)。
2024-11-09 00:32:02
310
原创 力扣每日一题 3235. 判断矩形的两个角落是否可达
方法是这样的，把整个n个圆和矩形的4条边都抽象成图里的点，如果他们有相交，就把图里的点进行连线，那么要判断矩形的两个角落是否可达就可以简单的变成判断图里的四条矩形边任意两条是否联通，如果联通了，那么说明存在一些圆横跨了矩形的左右或者上下或者堵住了一个角落，也就是说不可达，否则就意味这可达。今天的困难题是真的困难，以前的虽然也难，但至少我知道我是能写出来的，而今天的题目，一看就知道是个数学几何，而且看数据范围就知道还得套其他方法，只能说完全没有思路。如果存在这样的路径，请你返回。圆的内部和边界，同时。
2024-11-08 23:54:57
300
原创 力扣每日一题 3255. 长度为 K 的子数组的能量值 II
把数组分成一段一段连续上升的子数组，用pre记录当前这段连续上升的子数组的起点，然后用当前位置减去起点位置就是连续上升的长度，大于k时就可以记录下来。如果遇到不满足连续上升的，就更新一下pre的位置。今天的数据范围就用昨天那个O(n)复杂度的解法就可以了。
2024-11-07 22:30:03
137
原创 力扣每日一题 3254. 长度为 K 的子数组的能量值 I
怎么做呢，我们没必要枚举每个子数组，因为要求连续上升，所以我们可以把数组分成一段一段连续上升的子数组，用pre记录当前这段连续上升的子数组的起点，然后用当前位置减去起点位置就是连续上升的长度，大于k时就可以记录下来。如果遇到不满足连续上升的，就更新一下pre的位置。外层遍历数组，内层往前找k个，检查这k个数是否满足连续上升的条件。如果满足，那最大值肯定就是最后一个了。不过其实我们可以再优化一下，把两个循环降到一个循环。因为只有一个循环，时间复杂度降到了O(n)时间复杂度O(n*k)。
2024-11-06 10:57:56
244
原创 个人对Numpy中transpose()函数的理解
如果新轴顺序是 `(1, 2, 0)`，则 `transpose` 会按顺序排列新步长 `(16, 4, 48)` 和新形状 `(3, 4, 2)`。简单来说，轴重新排列就是把原来的轴的读取顺序换成了新的轴的读取顺序，然后又改回了原来(0,1,2,3)顺序的表现。同理，三维的填充顺序就是先填完一层二维的，然后从前往后填充，所以前后方向是0号轴，每一层的填充顺序与二维一致，所以二维的轴的编号加个一就是三维里的编号了。所以答案是(3,2,1,0)。更高维的也是一样的道理，新的方向是0轴，原来的轴就依次加一。
2024-11-04 19:21:32
1353
原创 力扣每日一题 633. 平方数之和
不过后来意识到这是单次查询，完全没必要打表浪费空间。最简单的还是暴力枚举 i ，然后计算c-i**2是不是一个平方数就可以了。我的第一反应其实是打表暴力计算。先把所有i**2打表计算出来，然后遍历枚举，判断c-i**2是否在表中。一个非负整数 c 如果能够表示为两个整数的平方和，当且仅当 c 的所有形如 4k+3 的。虽然这应该是一个数学题，但可惜我确实不会判断。只不过我不会，就不放代码了，直接贴。，你要判断是否存在两个整数。正解应该是费马平方和定理。
2024-11-04 15:31:48
286
原创 力扣每日一题 638. 大礼包
我们先计算一下不使用任何礼包所需要的价格，然后对每个礼包遍历一下尝试使用，再递归下去找对剩余所需要的清单购买需要的价格，取个最小值就是答案了。为了省点时间，做了一个记忆化，如果当前的清单是已经计算过一次的就直接返回答案。可以试一下去掉记忆化，不知道会不会超时。满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。（也就是数组中的最后一个整数）为第。
2024-11-03 22:21:56
242
原创 力扣每日一题 3226. 使两个整数相等的位更改次数
已经保证了所有k为1时n都为1，那么统计一下n和k有多少位不同就可以了。我们可以计算n^k中1的个数。幸好即使是C/C++也有办法可以快速统计1的个数，那就是__builtin_popcount。与是两个同为1则1否则为0，那么就应该是n&k=k。C语言的高光时刻，一行解决问题。同样的，C++也可以用。又是一个简单题，直接n和k转换成二进制然后算就可以了。如果无法实现，返回 -1。中任意一个值为 1 的位，并将其改为 0。不过我们可以用位运算再提一下速度。再贴个python的。
2024-11-02 00:40:35
323
原创 力扣每日一题 3259. 超级饮料的最大强化能量
然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。可以得到状态转换方程 dpA[i] = max(dpA[i - 1], dpB[i - 2]) + energyDrinkA[i])将dpA[i]定义为最后第i个小时喝能量A的最大能量提升，如果我们只考虑前i+1个小时，那么在最后一个小时，我们喝能量饮料A。那么，我们要的答案就是max(dpA[n - 1], dpB[n - 1])。时间复杂度不变，还是O(n), 但空间复杂度O(1)。
2024-11-01 23:52:17
196
原创 力扣每日一题 3165. 不包含相邻元素的子序列的最大和
最后我每个node保存了4个元素，cc,co,oc,oo，分别表示该节点对应区间在左右闭区间，左闭右开，左开右闭和左右开区间的情况下的最大和。我们以cc的情况为例。同时，因为要求没有连续元素，所以左节点右闭和右节点左闭最多只能有一个存在，所以父节点的cc值应该是max(L.cc+R.oc, L.co+R.oc, L.co+R.cc)。本来我是想保存node节点对应区间的最大和的起始和结束位置的，但发现不行，因为这样存的话，node的父节点的答案还是需要一次O(n)遍历才能出结果。返回所有查询的答案之和。
2024-10-31 20:28:43
456
原创 力扣每日一题 3216. 交换后字典序最小的字符串
这个题目非常简单，就直接从前往后遍历找到相邻的可以交换且前面比后面大的数字就可以了。因为要字典序最小，而字典序是从前往后进行大小比较，所以先交换的肯定是字段序最小的。如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。的数字后，返回可以得到的字典序最小的字符串。时间复杂度O(n)，空间复杂度O(1)。给你一个仅由数字组成的字符串。
2024-10-30 00:39:33
207
原创 力扣每日一题 3211. 生成不含相邻零的二进制字符串
我们知道 x & (x >> 1) 的结果可以判断x是否有连续的1，那么我们只要稍微改一下，把x取反，就可以判断有没有连续的0了。计算 x ^ mask，由于 0 和 1 异或后变成了 1，1 和 1 异或后变成了 0，所以 x 的低 n 位都取反了。第二种方法：直接枚举所有二进制长度为n的整数，判断是否满足条件，满足就把数字的二进制填进数组即可。创建一个低 n 位全为 1 的二进制数 mask = (1 << n) - 1。如果前一个位置是1，那这个位置不管是0还是1都可以。字符串，可以以任意顺序排列。
2024-10-29 17:32:40
298
原创 力扣每日一题 685. 冗余连接 II
第一种情况，新增的边连接了根节点，不存在入度为0的根节点了。第二种情况，新增的边连接的两个非根节点，出现了一个入度为2的节点。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。对于第一种情况，和昨天的做法是一样的，一条条加边，找到一条连接的两个点在同一个联通分量的边就可以返回了。但对于第二种情况，我们需要找到那两条指向了同一个节点的边，然后尝试删除一条边，判断是否构成树。简单来说就是有n个节点n条边的有向图，需要找到最后加入的一条删除后可以构成有向树的边。个节点（节点值不重复，从。
2024-10-28 20:54:16
546
原创 力扣每日一题打卡 684. 冗余连接
可以认为优化后的并查集几乎是常数时间复杂度，也就是说这题如果用优化后的并查集，时间复杂度可以看成是接近O(n)的，虽然严格来说是O(n*α(n))思路是一条条尝试加边，判断两个点是否在同一个连通分量里面，如果在就可以直接返回这条边了，如果不在就把这条边加进去。因为题目保证只有n条边，所以这个方法找到的那条边一定是最后那条。因为没有进行任何优化，就连路径压缩都没做，所以这个并查集的查找时间复杂度在最坏情况下是O(n)。本来我还想着超时之后就改成用邻接表去存的，按这个题的数据范围，邻接表应该是不会超时的。
2024-10-27 22:07:35
350
原创 力扣每日一题 3181. 执行操作可获得的最大总奖励 II
不过今天翻题解区的时候，发现竟然还可以用母函数解题，这种思路确实是我从没想到过的，这里就不班门弄斧了，就直接贴他的链接了。顺便吐槽一句，本来以为去重只能省少量时间，甚至可能还会增加时间，但没想到面对今天的数据，居然能省这么多时间。思路完全一致，只不过最开始的解法会超时，必须要用最终的优化版的代码，就是bitset位运算的。今天的内容确实没啥好写的，就看昨天的题解就可以了。
2024-10-26 00:11:27
263
原创 力扣每日一题打卡 3180. 执行操作可获得的最大总奖励 I
那么，最后要求的就是dp[n-1]那一行最大的满足dp[n-1][j]=1的 j。这题目其实是个非常明显的背包问题，只不过是稍微改了一下的0-1背包问题，所以很明显是个动态规划(dp)题，但可惜我太久没写题目了，已经不会dp了。然后，因为每次选择的奖励值必须大于你手上的奖励值，所以我们绝对不可能选择两个奖励值一样的物品，所以我们可以对输入数据进行一次去重。首先，因为这个题只需要求最大的总奖励，对具体选的物品编号没有要求，所以我们完全可以先排个序，而且排序之后也可以更方便进行选择。为 0，所有下标都是。
2024-10-26 00:06:41
217
原创 力扣每日一题打卡 3180. 执行操作可获得的最大总奖励 I
如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。那么，最后要求的就是dp[n-1]那一行最大的满足dp[n-1][j]=1的 j。顺便，我们假设奖励的最大值为m，那么如果我们要选择m，则我们前面的所有操作的总奖励一定是小于m的。的值小的时候，我们才可以选择，在这种情况下，dp[i][j] = dp[i-1][j- rewardValues[i] ]。
2024-10-25 20:47:41
514
原创 力扣每日一题3175. 找到连续赢 K 场比赛的第一位玩家
但我们看，在k比n大情况下，一轮循环下来肯定是没有赢家的，需要多轮。如果你要把最前面的数字移到最后面，还保持其他数据的顺序不变，那只能一个个的把元素往前挪，时间复杂度O(n)，在最坏情况下，你需要将n个数都这样移动，时间复杂度O(n^2)。实际上我们可以直接一次循环查找它能不能连续赢k场，因为如果它输了一次比赛，那它就被移到了队伍末尾，已经在x之后了，在它下一次出场之前，x已经先出场了。根据前面的分析，我们可以知道，如果其他玩家想要能连续赢k场，那这个玩家的所有比赛一定是在遇到这位x之前就赢了k场比赛了。
2024-10-24 01:12:13
309
原创 力扣每日一题3185. 构成整天的下标对数目 II
今天的题目没啥好说的，就是昨天的题目的进阶版，用昨天题解的最终版就可以直接过了。今天的就不写思路了，有需要就看昨天的就好了。
2024-10-23 18:31:24
274
原创 ioccc代码分析(2)
与运算之后值要么是0要么是1，而这里或运算还是起一个加法的作用，所以运算的结果为32或者33。那么 7[__TIME__ - _/8%8] = __TIME__ - _/8%8[7] = __TIME__[7 - _/8%8]。所以这实际上是取出来字符串里的某个字符，取值范围是'0'-'9'和 :。1:8)%8的计算结果了。*2 的结果在二进制上就是左移一位，而&8 的结果就是第四位为1时结果为8，否则为0。而_ 的取值范围是限定在 [0, 447] 的，所以 _/64 的结果是 [0, 6]。
2024-10-23 16:49:04
596
1
原创 c++ 读取MNIST数据集实现softmax回归
代码太长了就没整理了，也暂时没有运行效果截图。超长代码警告，757行。同样没有本文也没有实现反向自动求导。
2024-05-23 11:35:14
269
1
原创 if和switch效率比较及分析
经常听说switch的效率比if-else要高。可是到底高多少呢？又为什么会高呢？我写了两个简单的测试程序进行了比较。if-else测试代码int main(int argc, char** argv){ int rounds = atoi(argv[1]); int target = atoi(argv[2]); clock_t st=clock(); for(int i=0; i<rounds; i++) { if (target == 0) continue; el
2021-07-07 17:40:35
7856
2
原创 STL sort源码分析
先大概介绍一下sort的实现吧。sort的底层实际上算是两种甚至三种排序的混合。当对大量数据采用快速排序，当数据基本有序时改用插入排序，并且在发现时间复杂度有向O(n*n)发展时，改用堆排序。以下代码均来自于devc++ 5.11版本。我们从sort函数看起//stl_algo.h, line 4703 template<typename _RandomAccessIterator, typename _Compare> inline void sort(_Ra
2021-05-11 14:35:10
761
1
原创 二分模板
#include <bits/stdc++.h>using namespace std;const int maxn=1e5+5;void binary(int a[], int n, int x){ int l=0, r=n;//左闭右开区间 while(l<=r) { int mid=(l+r)/2; if(a[mid] < x) l=mid+1;//找到第一个大于等于的元素，如果要找大于就加个等于号 else r=mid-1;//return l.
2020-10-10 10:36:54
130
原创 通过cmd命令获取文件的行数
偶尔，我们会需要快速获得某一文本的行数，但如果自己手动写程序可能会发现程序运行所用的时间会比想象中要长得多。这时，我们可以考虑使用调用cmd命令实现该功能，速度会比自己实现快得多。测试环境：win7 32bit 4G内存测试结果：0.5G的txt文件只要3秒左右可以获取测试截图：cmd命令： find /V /C "" test.txt命令解释：查询所有不包含空串的行的行数/V显示所有不包含某字符串的行/C仅显示包含某字符串的行数...
2020-09-28 16:16:15
5537
原创 【2020CCPC网络赛】1002 Graph Theory Class（HDU6889）
题目链接题意：给你一个n个结点的完全图，结点从1~n标号，结点i和j之间的边权为lcm(i+1,j+1)，问你这个图的最小生成树的边权和是多少思路：为了方便起见，我们将节点从2~n+1编号，可以知道，当新加入的节点是个质数时，最小生成树的权值之和增加的是两倍的质数值，因为把这个点和2连起来是加的值最小的，当新加入节点的值不是质数时，权值之和增加的是这个数的值，因为前面一定会存在一个数是这个数的因子，只要把这个数和它的因子连起来，增加的值就只是这个数本身的值了。我们可以把所有质数提一个出来，则增加
2020-09-21 18:08:36
286
原创 【2020CCPC网络赛】1005 Lunch（HDU6892）
题目链接题意：有n块巧克力，每块长度为Li，两个人轮流选某一块，将其均分为x(x!=1)块，每块长度为整数。无法进行操作者输。思路：首先我们知道如果只有一块，则一定是先手必胜状态。因为先手可以把这一块分成L块长度为1的。但如果先手不是一次性分成长度为1的，那么先手是不是一定会变成必败态呢？当然不是。考虑长度为4的情况，如果将4分成2个2，最后还是先手必胜。其实，只要分成的是偶数块，都不会导致状态交换。那如果是分成奇数块呢？那就会了。比如将6分成3个2，最后先手由必胜变成了必败态。所以我们可以知道
2020-09-21 16:11:05
199
原创 hdu 6747 rotate 【数学期望】
http://acm.hdu.edu.cn/showproblem.php?pid=6747Problem Description我们有一个圈，从内到外一共被分成了 n 个环，中间是空的。我们把从外到内第 i 层环平分成 a[i] 份，其中 a[i] 是偶数，我们把这 a[i] 份黑白染色，第奇数个染成黑色，第偶数个染成白色。现在我们旋转每一层，每一层都会等概率随机到一个中止位置。问黑色的联通块数目的期望。两块黑色的区域有交点即算联通。层之间的旋转是相互独立的。Input第一行一个正整
2020-07-31 21:50:24
249
原创 Hybrid Crystals（思维，水题）
题目链接：Hybrid Crystals题意：有三种能量石，分别是L，D，N。每颗能量石含有ai的能量。能量石可以融合，融合规则：L类型的合并可以增加ai点能量，D类型的减少，N类型的可加可减（加还是减随你自己）。并且保证第一颗能量石的能量是1，且类型是N。并且每颗能量石符合题目所给的那个公式。给你一些能量石，你需要融合其中一部分，让融合后的能量是k。思路：看懂那个式子，这就是一个彻底的水题了。我直接解释式子的意义了：第一颗L的取值最大是1，第二颗最大是2，第三颗最大是4，第四颗是8。D类型的同
2020-06-13 18:23:42
172
原创 HDU6143 Killer Names（排列组合）
题目链接：Killer Names题意：每个人的姓和名都是长度为n的字符串，现在你有m个字符可用，要求姓和名不能出现相同的字符，问最多有多少种方案。思路：因为不要求m个字符全部用完，所以我们可以考虑共使用x个字符分配给姓和名，可选方案数是C(m,x)，显然2<=x<=m。然后我们考虑从x个字符中选 i 个字符给姓，则剩下x-i个字符可以给名，可选方案数是C(x,i)。我们记 A[n][i] 是用 i 个字符填n个位置的方法数，可得状态转移方程 a[n][i]=( a[n-1][i-1]
2020-06-13 17:48:36
168
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人