Losita's Blog - 算法
type: channel
link: https://blog.lecspace.com/index.php/category/problem_solving/
items: 算法笔记-动态规划 11月25日更新
items: 算法笔记-二分算法 已完结
items: [偏自用]算法笔记系列——滑动窗口 已完结
items: [偏自用]竞赛算法速成日记（CCF CSP、蓝桥杯）(6/13更新）

算法笔记-动态规划 11月25日更新
type: item
date: 2025-11-07T17:27:00+08:00
description: 前言本笔记是我挑战灵神的dp题单的算法笔记，可能是我最后一个关于题单的算法笔记了。做完这个题单的所有会做的基础题后，我将会转战hot100，挑战解析hot100的每一道题。灵神说的好：掌握动态规划（DP）是没有捷径的，咱们唯一能做的，就是投入时间猛猛刷题。好比学数学，只看书看视频而不做习题，是不能说学会的。我能做的，是帮你节省找题的时间，并把这些题分类整理好。有着相同套路的题，一起做效率会更高，也更能领悟到 DP 的精髓。所以推荐按照专题刷。题目已按照难度分排序（右侧数字为难度分）。如果遇到难度很大，题解都看不懂的题目，建议直接跳过，二刷的时候再来尝试。好的，话不多说，我们开始解析题目！至于为啥不解析dp算法本身？因为这玩意一种题目一个样，如果硬要概括啥是dp：动态规划的核心思想是：将复杂问题分解成简单子问题，通过“记住”并复用子问题的答案，来避免重复计算，最终高效解决整个问题。1 入门 DP1.1 爬楼梯问题1.1.1 简介到底是入门题，难度从开局的及其简单到最后的中等难度，基本都可以接受。老样子，咱们给题目分分类：1.基础题(我能较快做出来)(讲解)70. 爬楼梯 note:最最经典的dp题目，必须掌握(讲解)746. 使用最小花费爬楼梯 约 1500 note:换汤不换药，只是将dp的主体从种类数量换成了花费，并需要引入最小值函数来保证每一步dp都是花费最小的2.进阶题(我需要思考一下才能做出来)3693. 爬楼梯 II 1560 note:是746的进阶版本2466. 统计构造好字符串的方案数 1694 note:和下面的377做法一样3.困难题(大体思路正确，但是需要纠正一些细节后才能做对)(讲解)377. 组合总和 Ⅳ 约 1600 note:这类题目的本质就是爬楼梯，是2466的启蒙导师(对我来说)(讲解)2266. 统计打字方案数 1857 note:非常新颖，第一眼可能看不出它是爬楼梯类型的4.78题(题解里面需要用到我目前没掌握的，且难以快速掌握的知识解决题目，所以看了题解也无法做出)无故事的开头总是极其温柔的。作为dp章节的开头，这次的题目难度并不怎么高，但是下面的题目难度会变成咋样，就需要交给时间去验证了。1.1.2 开始讲解！我们先来看第一题：70. 爬楼梯，先看题。下面我讲的是DP的核心概念，必须掌握。首先，我们需要讲问题的规模缩小。如果直接套多层循环暴力枚举每一步爬几步，既不好写(很难确定循环层数)，也很慢(时间复杂度会达到O(n的好几次方))。这里，我们需要掌握一个基本概念：假设我一次可以爬1格或者2格楼梯，设第n层的爬楼梯方式种数为f(n)，那么，它一定满足如下式子：$$ f(n)=f(n-1)+f(n-2) (n>=2) $$因为，我可以从第n-2格跳2格上来，也可以从第n-1格跳一格上来，我只需要将这两格的可能性相加，就是我抵达第n格的爬楼梯方式的种数。看到这个，你是不是会想到递归？当然可以，但是递归(纯递归，不带记忆化搜索)有很多缺点：指数级的时间复杂度与重复计算这是最致命、最核心的缺点。DP问题的本质是问题可以分解为重叠子问题。纯递归会盲目地、反复地计算这些完全相同的子问题。栈溢出风险。每一次递归调用都会在程序的调用栈上分配一个栈帧，用于保存局部变量、返回地址等信息。递归深度过深会耗尽栈空间，导致 StackOverflowError。低效的函数调用开销。函数调用本身涉及参数压栈、上下文保存、跳转等操作，这些操作比简单的循环和数组访问要慢。难以进行空间优化。自底向上的迭代DP，我们可以清晰地看到整个状态转移的过程，从而很容易进行空间优化（例如“滚动数组”技术）。将纯递归排除掉后，我们剩下两种方式：第一种就是将上面缺点的第一点给优化掉：引入记忆模块，使其摇身一变，成为记忆化搜索。第二种就是抛弃递归，使用数组进行dp。我们先来讲第一种。1.记忆化搜索何为记忆模块？上面的缺点说到：“纯递归会盲目地、反复地计算这些完全相同的子问题。”，那我不是将这些已经计算好的子问题的结果存储起来就好了？这样我下次要用的时候直接调用算好的，能省下指数级别的时间。所以，选择哪种数据类型作为我们的记忆模块，就至关重要了。我们希望它存取快。毫无疑问，在大多数情况下，哈希表支撑的映射是最佳选择。因为它们存取的时间复杂度在大多数情况都是O(1)，非常快速。映射在常用竞赛语言中的对应如下：语言主要实现平均时间复杂度最坏情况线程安全JavaHashMapO(1)O(n)否PythondictO(1)O(n)全局解释器锁C++unordered_map (不是map哦)O(1)O(n)否C#DictionaryO(1)O(n)否JavaScriptMapO(1)O(n)否GomapO(1)O(n)并发不安全RustHashM…

算法笔记-二分算法 已完结
type: item
date: 2025-08-05T11:31:00+08:00
description: 前言在这篇文章中，我们将会一起学习二分算法，比上一章的滑动窗口要难上许多（对我来说）。话不多说，我们直接开始。1.二分算法的基本定义一句话概括本质：通过判断左右边界所围成区域的中点的值和目标值的关系，来决定下一步要在该区域的哪半边继续进行同样的操作，直到触发循环的退出条件。讲一讲流程就是(以左右闭区间为例)：假设我们拿到一个升序的序列nums和要查找的目标值target，那么我们开局将左边界left和右边界right都设立在这个序列的两头(举个例子，0和len(nums)-1)，进入循环后先取它的中点mid，判断nums[mid]的值：如果nums[mid]≥target，那就选择左半边进行下一步，使right=mid-1；反之，选择右半边进行下一步，使left=mid+1。周而复始，直到触发循环的退出条件(此处是left>right退出)。2.如何进一步理解二分算法-红蓝染色法可以先去看这个视频：【算法入门】用红蓝染色法学爆二分查找在红蓝染色法中，我们将一个升序数组分成蓝区(<目标值的区域)，空白区和红区(>=目标值的区域)。我们二分就是把对应的元素染色到对应的区域。在这个视频中，博主介绍了三种二分类型，分别是左右开区间、左右闭区间以及左闭右开区间。为了方便，本文章统一使用左右闭区间，即[l,r]。在这个视频中，左右闭区间类型的二分算法在循环结束后，有一件事情是永远不变的，无论红蓝区的标准如何调整：l在红区的最左边，r在蓝区的最右边。如下图所示：并且，按照我上面的分区设定，l会正好指在target上面(如果有)，如果没有target，会指在大于它的第一个数上面。所以如果你要找target或者大于它的第一个数，直接输出nums[l]就行了。那么遇到其他类型又怎么办呢？假设题目就是想让我找>target的第一个数，并且nums中有可能本身就有target，如果还是按照上面的标准划定红蓝区，那么就有可能直接输出target了，这咋整呢？先记住上面永远不变的事情，然后我们再去调整蓝区和红区的标准，就能做到这件事：把红区调整成>target的数全都在这里面，把蓝区调整成≤target的数全都在这里面。再看看上面永远不变的事情，是不是l自然而然就指到了比target大的第一个数上，并且即使有target，也不会指到target上。那么反映到代码上，又会变成咋样呢？先看看最上面情况的代码(蓝区是<目标值的区域，红区是>=目标值的区域)： int lower_bound(vector<int>& nums,int target){ int l=0,r=nums.size()-1; while (l<=r){ int mid=(l+r)/2; //下面这一行代码是最关键的，是决定红蓝区域性质的核心代码 if (nums[mid]<target){ //由于l左边(不包含它自己)是蓝区，如果nums[mid]<target， l=mid+1; //那么将其收入蓝区； }else{ //如果nums[mid]≥target， r=mid-1; //将其收入红区 } } return l;//输出红区的最左边的元素 }结合注释看，你现在一定有所体会了吧？所以，如果我们要求大于target的第一个数，那就按照上面的标准来更改红蓝区：把红区调整成>target的数全都在这里面，把蓝区调整成≤target的数全都在这里面。 int lower_bound(vector<int>& nums,int target){ int l=0,r=nums.size()-1; while (l<=r){ int mid=(l+r)/2; if (nums[mid]<=target){ //由于l左边(不包含它自己)是蓝区，如果nums[mid]<=target， l=mid+1; //那么将其收入蓝区； }else{ //如果nums[mid]>target， r=mid-1; //将其收入红区 } } return l;//输出红区的最左边的元素 }这样一讲，是不是小于target的第一个数等等情况，你也能解决了？如果要找小于target的第一个数，就直接将蓝区改成<target，红区改成≥target，最后l-1就是答案的位置(如果算出来是-1，说明不存在，target就是最小的数)。其他情况就不讲了，举一反三即可。3.题目实战——二分查找型 0809更新做了4天的题目(当然也只限于白天的时间做，晚上或者接近晚上时我要三角洲启动)，属于是要给我燃尽了。这个难度真的比滑动窗口难多了。滑动窗口是这样的：简单题直接秒，中等题有的能秒有的得稍微想想，hard题目有点难度，有的能想出来，没想出来的看题解后也能豁然开朗；二分呢？简单题我得想想到底哪里能用到二分，中等题我绞尽…

[偏自用]算法笔记系列——滑动窗口 已完结
type: item
date: 2025-07-04T16:40:00+08:00
description: 专栏简介上一个专栏，《竞赛算法速成日记》是我为了应对大一下所到来的蓝桥杯国赛和CSP认证所临时准备所学习的算法思想，只能说是提高了广度，并没有学到精髓，在竞赛中发挥的作用并不大（蓝桥杯PyB组喜提国三，CSP认证喜提前60%）。所以，我认为确实有必要系统的，多投入一些时间去学习算法的一整套体系，来应对后面更重要的工作面试。总体学习路线，我是参照灵茶山艾府大神的这篇文章：分享｜如何科学刷题？我从文章中扒了一张图，大体就是这样：算法的知识面是非常广的，我也不奢求完美完成每一个模块，力求在1年内把所有基础的题目都做完，并且每做完一个板块，就来这里更新我自认为这一块知识点的精髓内容(如果我半个月没有更新，欢迎催更~)。当然这最主要的是为了加深我自己的理解，如果能顺带帮到你，那就更好了。所以，总结一下，这个专栏，《算法笔记》，就是我为了总结消化我所学习到的算法知识，顺带还能帮助到你一点的一个专栏。下面开始正文内容。PS:由于算法笔记的内容比较多，所以我打算每个大模块都发一篇文章，各自之间分开，不然一篇文章肯定装不下。1.定长滑动窗口最初的样子滑动窗口这个算法，算是我第一次打开leetcode刷题时就有接触到的算法了，当时也是把我狠狠震撼到了。我之前学习到的滑动窗口是这样的：给定一个字符串和一个子串，求该子串在该字符串中出现的次数(重叠也算)，如果不存在请输出-1。当时反正是拿双指针折腾了半天，结果最后还超时了，整了个O(n^2)的复杂度。其实正确的做法是，只需要一个指针，然后不断的按照该子串的长度，在字符串中从前到后切片，不断对比这个切片和给定子串，如果相等，则次数加一。这就像我在字符串中画了一片固定大小的区域，把它慢慢往后移动，就像滑动的窗户一样。这样就能以O(n)的时间复杂度完成这道题目。这是它最初的样子，让人看到恍然大悟，且一秒钟就能理解。但是现在，它又不一样了。现在的版本先看题：定长子串中元音的最大数目我的第一版本的做法就和上面一致：直接滑窗，然后傻傻的又开了一个循环数里面元音的个数。毫无意外，O(n^2)的复杂度，超时了。百思不得其解，我去看题解，发现我已经落后于时代。现在的做法是这样的：将滑动的窗户看成一个队列，当窗户向后滑一格时，把出去的那一格元素认为是出队；相反，滑进来的那一格元素认为是入队。如果出队的那一格元素是元音，那就将窗户当前的元音数量减一；如果进来的那一格元素是元音，那就把窗户当前的元音数量加一。因为窗户在滑动的过程中，除了出去的元素和进来的元素，其他元素都待在窗户里面，和上一次一样，都属于这个窗户，所以不需要去管它们的状态。当然，第一次进入循环的时候，还是得老老实实数元音的个数，不过就这一次，窗户向后滑之后，就只需要用上面的方法，管进来的和出去的就行了。最后时间复杂度O(n)，轻松解决。这个做法是非常通用的，如果具备一定的应变能力(到底啥是应变能力，你下面就知道了)，它能解决90%的定长滑窗题目(计数或者求和等)。奉上我的AC代码(最近在重温go语言，所以用go写的，当C语言看就行了，一样的)：func isYuan(b byte) bool {//判断是否是元音的函数 return b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u' } func maxVowels(s string, k int) int { maxCnt := 0//维护一个最大元音个数的计数器 cnt := 0//维护一个当前元音个数的计数器 for i := 0; i <= len(s)-k; i++ { ns := s[i : i+k]//切片，切出窗户 if i == 0 { //计算第一个窗口的元音个数 cnt = 0 for j := 0; j < k; j++ { if isYuan(ns[j]) { cnt++ } } } else { if isYuan(s[i-1]) { //如果出去的是元音 cnt-- //当前元音个数减一 } if isYuan(s[i+k-1]) { //如果进来的是元音 cnt++ //当前元音个数加一 } } maxCnt = max(maxCnt, cnt)//维护一个最大元音个数 } return maxCnt }还能配合哈希使用先看题：几乎唯一子数组的最大和我先说人话翻译一下这个题目：滑窗，如果这个窗户内的元素种类>=m，那就求它的和，然后找所有满足这个条件的窗户内的和的最大值。有什么东西能够自动去重，并且能够快速查询想要的元素？那就是哈希。在各类编程语言中，都有相对应的使用了哈希的容器。Python是字典(dict)和集合(set)，cpp和go中是映射(map)。将数据以哈希的形式存放，查询它是否存在、查询它对应键值对…

[偏自用]竞赛算法速成日记（CCF CSP、蓝桥杯）(6/13更新）
type: item
date: 2025-05-08T20:02:00+08:00
description: 前言此博文用于记录我学习到的一些算法思想，语言是c++或者python。cpp竞赛模板第一行的万能头大部分情况下是能用的，如果不能用，那就手动导入iostream等等的库。#include <bits/stdc++.h> using namespace std; int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); // code here }py和cpp时间复杂度对比复杂度C++ 每秒数据量估算Python 每秒数据量估算O(1)无限无限O(log n)~1e8~1e7O(n)~1e8~1e7O(n log n)~2e7~1e6O(n^2)~1e4~1e3O(n^3)~300~50这是单机、单核、主流在线评测平台（如LeetCode、Codeforces、牛客、洛谷等）上1秒内大致能承受的数据规模。C++ 由于编译型、无解释器开销，所以通常比 Python 快 5~10 倍，甚至更高。复杂度上升一档，数据规模要大幅缩小！c++一些需要注意的地方1.快速输入输出c++默认的cin cout在数据量很大时输入输出很慢，可以在main函数的开头加上如下两行（此时输入输出只能是cin cout，不能再用scanf和printf了）：ios::sync_with_stdio(false); cin.tie(nullptr);尤其是在处理矩阵时，差两行这个可能会让你从ac到超时。2.unsigned数据类型的溢出反倒可以自动取模举个例子，unsigned long long正好到2^64-1的大小，所以如果此时输入2^64或者更大的数，相当于自动对2的64次方取模(mod)，实现了啥都不干自动就取模了。c++主要数据类型的范围和取模的关系：数据类型位数有符号/无符号自动对 2^k 取模最大可自动取模的 k备注unsigned char8无符号是82^8=256unsigned short16无符号是162^16=65536unsigned int32无符号是322^32unsigned long32/64无符号是32/64（平台相关） unsigned long long64无符号是642^643.set的使用用途在需要不断维护一个有序列表，并且需要经常插入、寻找、删除、修改的，用set这个数据结构是十分高效且合适的。时间复杂度平均为O(logn)使用方法操作说明示例代码定义声明一个 setset<int> s;插入元素插入元素，自动排序s.insert(5);删除元素删除指定元素s.erase(5);查找元素查找元素是否存在auto it = s.find(5);大小返回元素个数s.size();清空清空所有元素s.clear();遍历从小到大遍历所有元素for(auto x : s) ...lower_bound找到第一个不小于某值的元素迭代器s.lower_bound(5);upper_bound找到第一个大于某值的元素迭代器s.upper_bound(5);相关题目https://www.luogu.com.cn/problem/P5250Python一些需要注意的地方1.浅拷贝问题——如何正确创建矩阵在Python中，创建一维列表有两种创建方式：list1=[0]*length list2=[0 for _ in range(length)]随意选择即可。但是创建二维列表就不一样了，虽然也有两种方式：matrix1=[[0 for _ in range(length1)] for _ in range(length2)] matrix2=[[0]*length1 for _ in range(length2)]我知道你肯定想写这种：matrix3=[[0]*length1]*length2那你猜会发生什么？正如标题所言，浅拷贝：假设你使得matrix[0][2]=1，那么matrix[1][2] matrix[2][2] matrix[3][2]...全都会等于1。也就是相当于你这样生成矩阵，python相当于复制了一堆引用，也算是一个特性吧，所以不要这么写。2.append中暴露的引用问题看下面的代码：def a(lis,cnt): global result if cnt>=5: return lis.append(1) result.append(lis) a(lis,cnt+1) result=[] a([],1) print(result)你肯定会认为，最后的结果是这样：[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1]]实际是这样的：[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], …