杭州富阳小码王集训营知识梳理
2025-08-05 11:55:34
发布于：浙江
DAY 01 ~ DAY 02 —— 贪心算法
贪心算法的定义
贪心算法（Greedy Algorithm）是一种在每一步决策中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的解题策略。它不追求整体最优，而是通过一系列局部最优的选择，逐步构建最终解决方案，最终期望得到全局最优解。
贪心排序
在数据之间没有相互的联系时，可以通过对数组（或其他类型的变量，例如string类型）的排序来取得最优解。
这里顺便复习一下sort()排序。
普通数组：
sort(a,a+n); //此为升序排列，格式sort(数组名+第一个开始要排序的下标,数组名+最后一个要排序的下标+1);
sort(a,a+n,greater<int>); //此为升序排列，格式sort(数组名+第一个开始要排序的下标,数组名+最后一个要排序的下标+1,greater<数组元素的类型>());
其他类型（vector，string）：
sort(s.begin(),s.end());
//这里与普通数组的区别仅仅只有下标的区别
例题
题目描述
在一个神秘的魔法王国里，两个强大的巫师，
吉娜 和 安度因，他们在打一起打副本的时候遇到了一个难题。
现在每个巫师手里都有一个装满魔法符文的袋子，这些符文由小写英文字母分别表示为字符串 s和 t。他们可以通过重新排列各自字符串中的字符来获得一个新的符文组合。
如果两位巫师可以在重新排列字符串 s和 t 后让 s的字典序 < t 的字典序输出YES，否则输出NO。
参考代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
string t,s;
while(T--){
cin >> s >> t;
sort(s.begin(),s.end());
sort(t.begin(),t.end(),greater<char>());
s >= t ? cout << "NO\n" : cout << "YES\n";
}
return 0;
}
这道题让我们求字符串 和 重新排序后能否让 的字典序小于 的字典序。
所以贪心思想就是将 按字典序按最小的情况排序，将 按字典序最大的情况排序，如果这样都不行的话，那就说明 的字典序绝对大于 的字典序。
贪心 - 优先队列
优先队列是什么？
优先队列是一种特殊队列，元素按优先级排序，出队时优先取出最高优先级元素，常用于调度、任务处理等场景，实现方式有堆、二叉搜索树等。
优先队列分为两种：升序与降序。
//优先队列的创建
priority_queue<int, vector<int>, greater<int>> q;
/*
priority_queue的第三个参数greater<int>指定了比较方式，使用该比较器时，
队列会以升序（从小到大）排列元素，即最小的元素会被优先取出。
*/
priority_queue<int，vector<int>> q;
//priority_queue中只有两个参数，未指定第三个参数，默认为降序（从大到小）。
为什么要使用优先队列
请看这道题：
题目描述
在一个果园里，超级阿拉已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。超级阿拉决定把所有的果子合成一堆。
每一次合并，超级阿拉可以把两堆果子合并到一起（不一定是相邻的两堆果子），消耗的体力等于两堆果子的重量之和。可以看出，所有的果子合并到最后就只剩下一堆了。超级阿拉在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以超级阿拉在合并果子时要尽可能节省体力。你的任务是使超级阿拉消耗的体力最少，并输出这个最小的体力消耗值
数据范围： 。
为什么这道题要用优先队列，问题就出在数据范围。
sort排序在此代码中时间复杂度为O(n² log n)，在会TLE，然而优先队列能在O(1)时间获取到最小（最大）值，用O(log n)的时间完成插入和删除。
反悔贪心
请看题目：
题目链接
这道题第一反应是前面先用砖块搭上去，后面再用梯子。
但如果你先用了砖头，用完了后遇到了更小的差值，不就反悔了吗？
先用了梯子，用完了后又遇到了更大的差值，不就又反悔了吗？
这道题就是典型的反悔贪心。
#include<bits/stdc++.h>
using namespace std;
int ans;
int main(){
int n,bricks,ladders;
cin >> n;
int a[1145141];
for(int i=0;i<n;i++){
cin >> a[i];
}
cin >> bricks >> ladders;
priority_queue<int,vector<int>,greater<int>>q;
int sum=0;
int ans=n-1;
for(int i=1;i<n;i++){
int H = a[i]-a[i-1];
if(H>0){
q.push(H);
if(q.size() > ladders){
sum+=q.top();
q.pop();
}
}
if(sum>bricks){
ans = i-1;
break;
}
}
cout << ans;
}
前面我们先无脑用梯子，后面遇到差值比较此次差值与前面的差值的最小值用砖头填充就好了。
如果此时砖头不够了，那就说明无法到达更远的建筑，记录下当前坐标-1即可
DAY 03 —— 前缀和数组
前缀和数组的定义：
- 前缀和数组：对于数组
a，其前缀和数组prefix满足prefix[i] = a[0] + a[1] + ... + a[i]，即从数组起始位置到第 个元素的累加和。
前缀和数组用于快速计算数组中某段连续元素的和，关注 "从开头到当前"。
前缀和数组的应用
题目描述
在一个遥远的科技王国里，有一位年轻的数学天才，名叫艾伦。艾伦非常擅长解决数学难题，并且从小就对数据结构和算法充满兴趣。某一天，王国的国王遇到了一道难题，他需要根据给定的数列和多个区间，快速计算每个区间内的元素和。
国王找到了艾伦，希望她能帮助解决这个问题。艾伦看着国王给出的数据和区间，发现这正是一道典型的区间和问题。
给定 个正整数组成的数列 和 个区间 ，分别求 个区间之和。
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,q,a[N],pre[N];
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
pre[i]=a[i]+pre[i-1];
}
cin >> q;
for(int i=1;i<=q;i++){
int l,r;
cin >> l >> r;
int sum=pre[r]-pre[l-1];
cout << sum << endl;
}
return 0;
}
这道题用暴力的方法是可以的一部分分的，但是数据范围：
，会超时，所以要用前缀和数组。
前缀和数组的公式一定要记牢：pre[i]=pre[i-1]+a[i]。
推导过程
由于前缀和数组用于求和，所以：
pre[0]=a[0]
pre[1]=a[0]+a[1]
pre[2]=a[0]+a[1]+a[2]
pre[3]=a[0]+a[1]+a[2]+a[3]
pre[4]=a[0]+a[1]+a[2]+ … +a[4]
…
pre[i-1]=a[0]+a[1]+a[2]+ … +a[i-1]+a[i]
pre[i]表示原数组中从第 0 个元素到第 i 个元素的总和，即：
pre[i] = a[0] + a[1] + ... + a[i-1] + a[i]- 而 pre[i-1] 表示从第 0 个元素到第 i-1 个元素的总和，即：
pre[i-1] = a[0] + a[1] + ... + a[i-1]
将两式对比可见，pre[i] 比 pre[i-1] 多了一个a[i]，因此自然有：
pre[i] = pre[i-1] + a[i]
总结
这个公式是优化计算效率的关键 —— 它将重复累加的过程转化为单次加法，体现了「用空间换时间」的算法思想。
之前写空间换时间被 复仇者_某某 喷，这次就解释一下
用pre数组的空间换取O(n*n)的时间复杂度。
异或前缀和
什么是异或？
异或（XOR，Exclusive OR）是一种逻辑运算，也是计算机科学中常用的位运算，其运算规则可以概括为：两个操作数的对应位相同则结果为 0，不同则结果为 1。
//具体运算如下：
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
多位数的异或运算
当对两个多位数（如整数）进行异或时，需按二进制位逐位运算，即对两个数的每个对应二进制位分别执行异或，最终组合成结果。
实例：5 ^ 3 = ?
101
^ 011
-----------
110
所以5 ^ 3 =6。
其实说白了，
异或前缀和不能被当做一个新的知识点
它只是前缀和的变种而已
将前缀和数组的加号改成异或 ^ 就好了
所以异或前缀和的知识点不在前缀和，而在异或。
DAY04 —— 二维前缀和
二维数组
在C++中，普通的数组都是一维的：
int a[5]={1,3,5,7,9};
有一维，当然也有二维。
二维数组与一维数组不同的是，你需要给定它两个参数：行和列
int a[3][3]={{1,2,3},{4,5,6},{7,8,9}};
那么如何快速获取某一区间之和呢？
第一反应：暴力枚举
int n; //此处的n表示的是二维数组a的行数和列数
cin >> n;
int sum=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sum+=a[i][j];
}
}
此时我们就得到了整个二维数组 各项元素之和。
但如果 可以达到 又是这个恶心人的10^5
那么此代码的时间复杂度O(n*n)在n最大时必然会TLE
所以的用老朋友前缀和。
这次的公式略有不同：
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + a[i][j]
解释：
prefix[i-1][j]：上方矩形的前缀和（包含a[1][1]到a[i-1][j]）。prefix[i][j-1]：左方矩形的前缀和（包含a[1][1]到a[i][j-1]）。- 两者相加时，
prefix[i-1][j-1]被重复计算，因此需要减去。 - 最后加上当前元素
a[i][j]，得到prefix[i][j]。
原数组array
一 二 三
a 1 2 3
b 4 5 6
c 7 8 9
pre前缀和数组
一 二 三
a 1 3 6
b 5 12 21
c 12 27 45
question：如何求出数组a指定范围内的所有元素之和？
既然pre数组都列出来了，找一下不就好了吗？
套入公式：
i=b,j=二
pre[b][二]=pre[a][二]+pre[b][一]-pre[a][一]+array[b][二]
∵12 = 3+5-1+5
∴所以公式成立。
DAY05 —— 双指针
一、什么是双指针？
简单来说，双指针就是在数据结构（如数组、链表）中定义两个指针，通过指针的移动和配合，完成遍历、查找、修改等操作。
它的核心优势是：降低时间复杂度（通常能把O(n²)优化到O(n)），或简化代码逻辑（避免嵌套循环）。
二、双指针的常见类型
根据指针的移动方向和功能，双指针主要分为以下几类：
1. 同向双指针（快慢指针）
- 特点：两个指针朝同一个方向移动，通常分为"快指针"和"慢指针"，分工不同。
- 核心逻辑：
- 快指针（fast）：负责遍历整个数据结构，探索新元素或判断条件；
- 慢指针（slow）：负责记录有效位置或需要更新的位置，仅在满足特定条件时移动。
- 适用场景：
- 原地修改数组（如删除元素、去重、筛选符合条件的元素）；
- 链表中的环检测、中间节点查找等；
- 需要在遍历过程中同步维护某种状态的场景。
2. 相向双指针（左右指针）
- 特点：两个指针分别从数据结构的两端出发，向中间移动，直到相遇或满足特定条件。
- 核心逻辑：
- 左指针（left）：从起始位置（如数组的0索引）开始，向右移动；
- 右指针（right）：从结束位置（如数组的n-1索引）开始，向左移动；
- 通过比较两个指针指向的元素，决定哪一个指针移动（或同时移动）。
- 适用场景：
- 有序数组中的查找问题（如两数之和、三数之和）；
- 对称结构的判断（如回文串、对称数组）；
- 需要利用数据有序性优化查找效率的场景。
3. 其他变种
除了上述两种基础类型，双指针还有一些灵活的变种：
- 滑动窗口：本质是同向双指针的扩展，通过左右指针维护一个"窗口"区间，动态调整窗口大小以满足条件（如最长子串、子数组问题）；
- 固定间距指针：两个指针保持固定距离移动，用于查找特定长度的区间（如链表中倒数第k个节点）。
三、双指针的核心优势
- 时间效率优化：
避免了暴力解法中的嵌套循环（O(n²)），通过一次遍历（O(n)）完成操作，大幅提升效率。 - 空间效率优化：
支持原地操作（如修改数组、链表），无需额外开辟与原数据结构同规模的空间，空间复杂度可降至O(1)。 - 逻辑简化：
用清晰的指针移动规则替代复杂的嵌套判断，代码更易读、易维护。
四、使用双指针的关键思路
- 明确指针分工：
先确定两个指针的角色（如谁负责遍历、谁负责记录，谁从左出发、谁从右出发）。 - 制定移动规则：
根据问题场景定义指针移动的条件（如满足什么条件时快指针/慢指针移动，左指针/右指针移动）。 - 利用数据特性：
若数据是有序的（如排序数组），优先考虑相向双指针；若需要原地修改，优先考虑同向双指针。
总结
双指针是一种"以空间换时间"或"简化逻辑"的编程思想，核心在于通过两个指针的协同移动，将复杂问题转化为线性遍历问题。它在数组、链表、字符串等数据结构的处理中应用广泛，掌握后能显著提升解题效率。
题目描述
今天英语老师讲了一个新单词 ，小A由于上课走神，被老师点起来提问了。
英语老师给小A写了一串字母 ，并让小A从这串字母中找出刚刚讲解的单词，说出单词 的每一个字母在 中第一次出现的位置。
这里的位置指的是当前字母在上一个字母出现后第一次出现的位置，例如样例组 4中，字母 b 在 的第一个位置就出现了，但此时字母 a 还没出现，因此字母 b 第一次出现的位置是 3。
输入#4
abc
babbc
输出#4
2 3 5
数据范围：
同样的话，暴力能拿分，但不是全部。
所以用双指针会更快。
#include<bits/stdc++.h>
int main(){
std::string s;
std::string t;
std::cin >> s >> t;
int i=0,j=i;
while(i<s.length() && j<t.length()){
if(s[i]==t[j]){
std::cout << j+1 << " ";
i++;
}
j++;
}
}
其中的i就是慢指针，负责进行判断，成立则更新位置，否则不变，j就是快指针，用于遍历每个元素。
如果s[i]等于t[j]，那么输出当前下标加1，更新i的位置，j则继续遍历。
有帮助，赞一个