讲解七道蓝桥杯省/国赛真题（第三弹）
234 大胖子走迷宫
题目介绍
开始挑战：234 大胖子走迷宫
方法一：
#include <iostream>
#include <queue>
#include <cstring> // 用于 memset
using namespace std;
int t, n, k; // t: 当前体型大小, n: 地图大小, k: 变瘦时间
char grid[1001][1001]; // 存地图
int visited[1001][1001]; // 访问标记数组
//顺时针方向搜索：右、下、左、上
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
// 定义节点结构体
struct Node
{
int x, y, steps; // (x, y) 和步数 steps
Node(int x_val = 0, int y_val = 0, int steps_val = 0) : x(x_val), y(y_val), steps(steps_val) {}
};
// 检查当前位置是否可以通过（没有障碍物）
bool canPass(int x, int y)
{
for (int i = x - t / 2; i <= x + t / 2; i++)
{
for (int j = y - t / 2; j <= y + t / 2; j++)
{
if (grid[i][j] == '*')
{
return false; // 有障碍物
}
}
}
return true; // 可以通过
}
// BFS 搜索最短路径
void bfs()
{
queue<Node> q;
struct Node start(3, 3, 0); // 起点 (3, 3)，步数为 0
visited[3][3] = 1; // 标记起点为已访问
q.push(start);
while (!q.empty())
{
struct Node current = q.front();
q.pop();
// 到达终点
if (current.x == n - 2 && current.y == n - 2)
{
cout << current.steps;
return;
}
// 根据步数更新体型
if (current.steps < k)
{
t = 5; // 大胖子
}
else if (current.steps >= k && current.steps < 2 * k)
{
t = 3; // 胖子
}
else if (current.steps >= 2 * k)
{
t = 1; // 瘦子
}
//小明可以有五种选择
// 如果体型不是瘦子，可以原地等待变瘦
if (t != 1)
{
q.push(Node(current.x, current.y, current.steps + 1));
}
// 尝试向四个方向移动
for (int i = 0; i < 4; i++)
{
int nx = current.x + dx[i];
int ny = current.y + dy[i];
// 剔除掉新位置：“已越界 + 未越界但是该位置因为体重的原因小明并不可以在那个位置上”
if (nx - t / 2 < 1 || nx + t / 2 > n || ny - t / 2 < 1 || ny + t / 2 > n)
{
continue; // 在地图范围外
}
// 剔除掉新位置：“已访问”
if (visited[nx][ny])
{
continue; // 该位置已经访问过
}
// 检查新位置是否合法：独属于本题的特殊要求“小明一次所占的位置不是1*1的格子，而是3*3或5*5的面积，所以如果在该面积里有障碍物的话，那该位置也不合法”
if (canPass(nx, ny)) //本题特殊要求有点复杂，所以在bfs函数外部用canPass函数完成该部分的功能
{
visited[nx][ny] = 1; // 标记为已访问
int newSteps = current.steps + 1;
struct Node next(nx, ny, newSteps);
q.push(next);
}
}
}
}
int main()
{
cin >> n >> k;
memset(visited, 0, sizeof(visited));
for (int i = 1; i <= n; i++)
{
//第一种方法：
//for(int j=1;j<=n;j++)
//{
//cin >> grid[i][j];
//}
//第二种方法：
cin >> (grid[i] + 1); // 从 grid[i][1] 开始存储数据
}
bfs();
return 0;
}
代码片段解释
片段一：
// 定义节点结构体
struct Node
{
int x, y, steps; // (x, y) 和步数 steps
Node(int x_val = 0, int y_val = 0, int steps_val = 0) : x(x_val), y(y_val), steps(steps_val) {}
};
1. 结构体定义：
struct Node定义了一个名为Node的结构体。- 结构体包含三个成员变量：
int x：表示节点的横坐标。int y：表示节点的纵坐标。int steps：表示从起点到该节点的步数。2. 构造函数：
结构体的构造函数：Node(int x_val = 0, int y_val = 0, int steps_val = 0) : x(x_val), y(y_val), steps(steps_val)
- 构造函数是一种特殊的成员函数，用于在创建结构体对象时对其成员变量进行初始化。
参数列表：(int x_val = 0, int y_val = 0, int steps_val = 0)
x的默认值为0y的默认值为0steps的默认值为0初始化列表：: x(x_val), y(y_val), steps(steps_val)
- 将传入的参数
x_val赋值给成员变量x- 将传入的参数
y_val赋值给成员变量y- 将传入的参数
steps_val赋值给成员变量steps构造函数体：{}
- 表示构造函数体，这里为空，因为所有的初始化工作已经在初始化列表中完成。
片段二：
for (int i = 1; i <= n; i++)
{
//都一种方法：
//for(int j=1;j<=n;j++)
//{
//cin >> grid[i][j];
//}
//第二种方法：
cin >> (grid[i] + 1); // 从 grid[i][1] 开始存储数据
}
循环变量
i从1开始，到n结束，之所以从1开始，是因为代码的逻辑是想让数组下标从1开始使用（虽然 C 和 C++ 中数组默认下标从0开始），这样做是为了与问题的实际场景相匹配。cin >> (grid[i] + 1); // 从 grid[i][1] 开始存储数据
grid[i]：是一个指向grid[i][0]的指针。（即：grid数组的第i行的首地址）
- 因为
grid是二维字符数组，grid[i]可以看作是一个一维字符数组（即：第i行）的名称。
grid[i] + 1：是grid[i][1]的地址，也可以认为是指向grid[i][1]的指针。
grid[i] + 1是指针的算术运算，表示将指针grid[i]向后移动一个字符的位置，指向grid[i][1]
cin >> (grid[i] + 1);：是从标准输入读取一行字符数据，并将其存储到从grid[i][1]开始的位置。
cin是 C++ 标准输入流对象。
>>是输入流提取运算符。这样：用户输入的每一行字符就会依次存储到
grid数组的相应行中，且从每个行的第二个元素（下标为1）开始存储。
片段三：
struct Node start(3, 3, 0); // 起点 (3, 3)，步数为 0
q.push(Node(current.x, current.y, current.steps + 1));
struct Node start(3, 3, 0);：这行代码的作用是定义一个Node类型的变量start，并通过构造函数初始化它的成员变量x为3，y为3，steps为0
- 这个变量在后续代码中可以被多次引用和操作，通常用于表示某个特定的起始节点。
Node(current.x, current.y, current.steps + 1)：这行代码只是临时创建了一个Node类型的对象，它没有定义新的变量名。
- 创建该对象的目的一般是为了传递给其他函数（如：
q.push），或者用于某种临时的计算或操作。
精彩代码片段
为二维字符数组从下标为1的位置开始进行赋值
char grid[1001][1001]; //存储地图
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
//第一种方法：
//for(int j=1;j<=n;j++)
//{
//cin >> grid[i][j];
//}
//第二种方法：
cin >> (grid[i] + 1); // 从 grid[i][1] 开始存储数据
}
解题思路分析
准备进行广度优先搜索的数据
- 迷宫的边长信息 —>
一个int的变量- 迷宫的数据信息 —>
一个二维数组- 迷宫的访问信息 —>
一个二维数组- 进行搜索的方向增量 —>
两个二维数组- 准备包含位置信息的
结构体- 准备存储要访问的位置的
队列- 开始广搜的起始位置的横纵坐标 —>
一个int的变量（也可以不准备，广搜函数中可以不传参）实现广度优先搜索
第一步：创建一个初始位置的结构体
第二步：标记该位置已被访问
第三步：将该位置的结构体入队
第四步：使用while循环判断队列何时为空
第五步：再创建一个在队首存放的结构体（相当于改名），同时将该结构体出队列
第六步：使用if分支语句书写正常结束的条件，并输出题目想要得到的数据
第七步：完成题目的要求 （通常是特殊的要求）
第八步：使用for循环4个方向增量
第九步：更新新位置的横坐标和纵坐标
第十步：使用if条件语句剔除“已访问 + 越界”的新位置
第十一步：使用if条件语句排除掉“由于本题特殊要求导致不合法的一些位置”（若是比较复杂的排除情况应当在bfs函数的外部使用函数实现，这里只负责调用）
- 第十二步：标记该位置已被访问
- 第十三步：完成题目的要求在（通常是步数+1）
- 第十四步：为该新位置创建一个结构体，并将该结构体添加到队列中去
调用广度优先搜索函数
118 机器人塔
题目介绍
开始挑战：118 机器人塔
方法一：
#include <iostream>
#include <bitset>
#include <cmath>
using namespace std;
int numA, numB; // A 和 B 的人数
// 检查当前塔的排列是否满足条件
bool isValidTower(int currentLayer, int layerCount)
{
int countA = 0, countB = 0; //按当前最底层机器人的排列情况，统计出整个机器人塔中机器人A和B的数量各是多少
for (int i = layerCount; i >= 1; i--) // i 是当前层数，也是机器人数量
{
bitset<32> layerBits = currentLayer; // 将当前层的排列转换为二进制
countB += layerBits.count(); // 统计当前层 B 的数量 ---> 二进制位上的1代表的是：B
countA += i - layerBits.count(); // 统计当前层 A 的数量 ---> 当前层机器人的总数量 - 当前层B机器人的数量
// 计算上一层的排列
currentLayer ^= currentLayer >> 1;
currentLayer &= (1 << (i - 1) - 1);
}
return countA == numA && countB == numB;
}
int main01()
{
cin >> numA >> numB;
// 计算塔的层数
int layerCount = sqrt((numA + numB) * 2);
int validTowers = 0;
// 遍历所有可能的排列
for (int i = 0; i < (1 << layerCount); i++)
{
if (isValidTower(i, layerCount))
{
validTowers++;
}
}
cout << validTowers << endl;
return 0;
}
代码片段解释
片段一：
// 计算塔的层数
int layerCount = sqrt((numA + numB) * 2);
这行代码的作用是通过数学公式计算出塔的层数，它的原理基于
塔的层数与机器人总数之间的关系。
1. 塔的结构
- 塔的每一层的机器人数量与层数相关。
- 第 1 层有 1 个机器人，第 2 层有 2 个机器人，第 3 层有 3 个机器人，依此类推。
- 总机器人数量为： 1 + 2 + 3 + ⋯ + layerCount = layerCount × ( layerCount + 1 ) 2 1 + 2 + 3 + \dots + \text{layerCount} = \frac{\text{layerCount} \times (\text{layerCount} + 1)}{2} 1+2+3+⋯+layerCount=2layerCount×(layerCount+1)
2. 机器人总数
- 题目中给定 A 和 B 的数量分别为
numA和numB- 总机器人数量为： numA + numB \text{numA} + \text{numB} numA+numB
3. 建立方程
根据塔的结构和机器人总数，可以建立以下方程： layerCount × ( layerCount + 1 ) 2 = numA + numB \frac{\text{layerCount} \times (\text{layerCount} + 1)}{2} = \text{numA} + \text{numB} 2layerCount×(layerCount+1)=numA+numB
4. 解方程
为了求解
layerCount，我们可以对方程进行变形：layerCount × ( layerCount + 1 ) = 2 × ( numA + numB ) \text{layerCount} \times (\text{layerCount} + 1) = 2 \times (\text{numA} + \text{numB}) layerCount×(layerCount+1)=2×(numA+numB)
这是一个二次方程，可以近似求解：
layerCount 2 + layerCount − 2 × ( numA + numB ) = 0 \text{layerCount}^2 + \text{layerCount} - 2 \times (\text{numA} + \text{numB}) = 0 layerCount2+layerCount−2×(numA+numB)=0
对于较大的
layerCount，layerCount + 1近似等于layerCount
因此： 方程可以简化为： layerCount 2 ≈ 2 × ( numA + numB ) \text{layerCount}^2 \approx 2 \times (\text{numA} + \text{numB}) layerCount2≈2×(numA+numB)于是： layerCount ≈ 2 × ( numA + numB ) \text{layerCount} \approx \sqrt{2 \times (\text{numA} + \text{numB})} layerCount≈2×(numA+numB)
片段二：
// 遍历所有可能的排列
for (int i = 0; i < (1 << layerCount); i++)
1. 二进制枚举
- 每一层的机器人排列可以用二进制表示：
0表示 A 类型的机器人。1表示 B 类型的机器人。- 对于
layerCount层的塔，最底层有layerCount个机器人，因此最底层的排列有2^layerCount种可能性。
2.
1 << layerCount的含义
<<：是 C++ 中的左移运算符。1 << layerCount：是将数字1左移layerCount位。
- 如果
layerCount = 2，则1 << 2 = 4（二进制100）- 如果
layerCount = 3，则1 << 3 = 8（二进制1000）因此：
1 << layerCount的值是2^layerCount，表示最底层的排列总数。
3. 循环范围
i < (1 << layerCount)表示循环变量i的取值范围是：0到2^layerCount - 1
- 如果
layerCount = 2，则i的取值范围是0到3（二进制00、01、10、11）- 如果
layerCount = 3，则i的取值范围是0到7（二进制000、001、010、011、100、101、110、111）
疑问：为什么这样写？
可以使用二进制来枚举一层机器人的所有排列：
- 每一层的排列可以用二进制表示，
0表示 A，1表示 B- 通过遍历
i的所有可能值，可以枚举最底层的所有排列。
- 例如：
layerCount = 2时，i的取值为0、1、2、3，分别对应最底层的排列00、01、10、11
示例：假设
layerCount = 2
1 << 2 = 4，因此循环范围是i = 0到i = 3i的二进制表示：
0：00（A A）1：01（A B）2：10（B A）3：11（B B）通过遍历
i，可以枚举最底层的所有排列。
片段三：
bitset<32> layerBits = currentLayer; // 将当前层的排列转换为二进制
countB += layerBits.count();
这段代码的作用是将当前层的机器人排列转换为二进制形式，并统计当前层中 B 类型机器人的数量。
1.
bitset<32> layerBits = currentLayer;
bitset<32>：
bitset是 C++ 标准库中的一个类，用于表示固定长度的二进制位序列<32>表示bitset的长度为 32 位（即：32 个二进制位）layerBits = currentLayer;：
- 将整数
currentLayer转换为一个 32 位的二进制表示，并存储在layerBits中
- 例如：如果
currentLayer = 5，则layerBits的二进制表示为000...00 101（前面补零到 32 位）2.
countB += layerBits.count();
layerBits.count()：
count()：是bitset类的成员函数，用于统计二进制表示中1的个数。
- 例如：如果
layerBits = 000...00 101，则layerBits.count()返回2（因为有两个1）countB += layerBits.count();
- 将当前层中 B 类型的机器人数量累加到
countB中。- 因为
1表示 B 类型的机器人，所以layerBits.count()就是当前层中 B 的数量。
片段四：
// 计算上一层的排列
currentLayer ^= currentLayer >> 1;
currentLayer &= (1 << (i - 1)) - 1;
这段代码的作用是 计算上一层的机器人排列，基于当前层的排列和塔的规则，它的核心思想是通过 位运算 来推导上一层的排列。
1. 塔的规则
- A 只能站在 AA 或 BB 的肩上。
- B 只能站在 AB 或 BA 的肩上。
这意味着：
- 如果当前层的某个位置是 A，那么它的下方必须是 AA 或 BB
- 如果当前层的某个位置是 B，那么它的下方必须是 AB 或 BA
2. 位运算的作用
计算上一层的排列：
currentLayer ^= currentLayer >> 1;：通过异或运算，根据当前层的排列推导出上一层的排列。
异或运算的规则：相同为0，不同为1- 通过将当前层的排列
currentLayer和其右移一位的结果currentLayer >> 1进行异或运算，可以推导出上一层的排列。
- 如果当前层为
101，则currentLayer >> 1为010101 ^ 010 = 111，表示上一层的排列确保排列的有效性：
currentLayer &= (1 << (i - 1)) - 1;：通过掩码运算，确保上一层的排列不超过当前层的范围。
(1 << (i - 1)) - 1：生成一个低i - 1位全为1的掩码，用于截取有效的二进制位。
- 如果
i = 3，则(1 << 2) - 1 = 4 - 1 = 3（二进制011）- 如果
i = 4，则(1 << 3) - 1 = 8 - 1 = 7（二进制0111）通过
currentLayer &= mask，保留currentLayer的低i - 1位，其余位清零。
如果
currentLayer = 111（二进制），mask = 011（二进制）111 & 011 = 011 111 \& 011 = 011 111&011=011
上一层的排列为
011（二进制）
3. 示例：假设当前层
i = 3，currentLayer = 5（二进制101）
- 计算上一层的排列：
currentLayer >> 1为010currentLayer ^= currentLayer >> 1： 101 ⊕ 010 = 111 101 \oplus 010 = 111 101⊕010=111- 上一层的排列为
111（二进制）- 确保排列的有效性：
(1 << (i - 1)) - 1 = (1 << 2) - 1 = 3（二进制011）currentLayer &= 3： 111 & 011 = 011 111 \& 011 = 011 111&011=011- 上一层的排列为
011（二进制）
疑问：为什么异或运算可以推导出上一层的排列？
- 根据塔的规则：
- 如果当前层的某个位置是 A（
0），那么它的下方必须是 AA 或 BB- 如果当前层的某个位置是 B（
1），那么它的下方必须是 AB 或 BA- 异或运算的结果正好符合这一规则：
- 如果当前层的两个相邻位置相同，则上一层为
0（A）- 如果当前层的两个相邻位置不同，则上一层为
1（B）
疑问：在对currentLayer进行异或运算时为什么要先将currentLayer进行右移1位？
右移 1 位的作用：比较相邻位
- 右移 1 位（
currentLayer >> 1）可以将当前层的排列向右移动一位。- 右移 1 位后，
currentLayer和currentLayer >> 1的每一位分别对应当前层的相邻位。- 这样做的目的是将当前层的每一位与其相邻的下一位进行比较，从而根据塔的规则推导出上一层的排列。
示例：假设当前层的排列为
101（二进制）
- 右移 1 位后：
currentLayer >> 1 = 010- 异或运算： 101 ⊕ 010 = 111 101 \oplus 010 = 111 101⊕010=111
注意：可能有人会有疑问就是不是说：将当前层的每一位与其相邻的下一位进行比较吗？
- 当前层的排列是010—> 即当前层的机器人的排列为：ABA
- 而进行右移的操作后是001 —> 即当前层的机器人的相邻的下一位的机器人排列为：BBA
- 二进制序列中开头的数字：
不一定会和相邻的下一位的机器人进行异或- 二进制序列中中间的数字：
一定会和相邻的下一位的机器人进行异或- 二进制序列中末尾的数字：
一定会和相邻的上一位的机器人进行异或- 所以：不用担心二进制序列中末尾的数字，同时也不需要担心二进制序列中开头的数字因为后面要确保排列的有效性，会生成一个低
i - 1位全为1的掩码，保留currentLayer的低i - 1位，其余位清零。- 之后进行异或操作后是011 ----> 即上一层的机器人的排列为：ABB
- 经过确保排列的有效性的操作后 ----> 即上一层的机器人的排列为：BB
精彩代码片段
第i行有i个元素的三角塔的总元素已知求该塔的总层数
// 计算塔的层数
int layerCount = sqrt((numA + numB) * 2);
将一个4字节的整数转换为32位二进制
bitset<32> layerBits = currentLayer;
统计一个32位二进制中1的数量
countB += layerBits.count();
将一个4字节的整数的每一位与其相邻的下一位进行异或操作
currentLayer ^= currentLayer >> 1;
保留一个4字节的整数的低i - 1位，其余位清零
currentLayer &= (1 << (i - 1) - 1);
解题思路分析
1. 准备阶段
第一步：获取到A、B机器人的数量 —> 定义两个变量
第二步：找到该机器人塔的总层数 —> 根据机器人的数量和塔的层数的关系
第三步：使用for循环遍历塔的最后一层的所有可能的情况
- 第四步：使用if选择语句判断这些情况中合格的情况，并记录合格的数量
2. 实现isValidTower函数来判断在给定一种塔的最底层的排列情况下，其上面的层在满足题意要求创建好后，对机器人A、B的数量的要求是否和输入的一样
第五步：定义两个变量用于统计塔种机器人A、B的数量
- 第六步：使用for循环从塔的最后一层遍历到第一层
- 将当前要处理的层数转换为二进制 —>
最一层当中A、B 机器人的数量蕴藏在传入函数的参数currentLayer的二进制数中- 统计出机器人B的数量
- 统计出机器人A的数量
- 使用异或操作得到上一层的机器人排列的二进制序列
- 使用掩码操作保留低上一层的机器人排列的二进制序列i - 1位，以保证上一层机器人的数量比这一层的少一个
170 次数差
题目介绍
开始挑战：170 次数差
方法一：
#include <iostream>
#include <string>
#include <vector>
#include <climits>
using namespace std;
int main()
{
string s;
cin >> s;
vector<int>num(26, 0);
//直白思路：获取字符串中出现次数最多的字符出现的次数 - 字符串中出现次数最少的字符出现的次数
//所以任务：1.统计字符串中每个字符出现次数 2.找到出现次数最多和最少的情况
//解决1.将字符串中字符出现的次数用一个包含26个元素的一维数组存储了起来
for (char ch : s)
{
num[ch - 'a']++;
}
//解决2.
int maxx = INT_MIN;
int minn = INT_MAX;
for (int n : num)
{
if (n > 0)
{
maxx = max(maxx, n);
minn = min(minn, n);
}
}
cout << maxx - minn << endl;
return 0;
}
精彩代码片段
将一个字符串中字符出现的次数用一个包含26个元素的一维数组存储了起来
//将字符串中字符出现的次数用一个包含26个元素的一维数组存储了起来
for (char ch : s)
{
num[ch - 'a']++;
}
附加条件下找一维数组中的最大值和最小值
int maxx = INT_MIN;
int minn = INT_MAX;
for (int n : num)
{
if (n > 0)
{
maxx = max(maxx, n);
minn = min(minn, n);
}
}
解题思路分析
统计一个字符串中字符出现的次数的最大值和最小值 == 将一个字符串中字符出现的次数用一个包含26个元素的一维整数数组存储了起来 + 获取整数数组中的最大值和最小值
方法二：
#include <iostream>
#include <algorithm> // 用于 sort 函数
#include <string> // 用于 string 类型
using namespace std;
int main()
{
string inputString;
cin >> inputString;
int letterCount[26] = { 0 }; // 用于统计每个字母出现的次数
// 统计每个字母出现的次数
for (int i = 0; i < inputString.size(); i++)
{
letterCount[inputString[i] - 'a']++;
}
// 对字母出现次数进行排序
sort(letterCount, letterCount + 26);
// 找到第一个非零的字母出现次数，并计算最大次数与最小次数的差
for (int i = 0; i < 26; i++)
{
if (letterCount[i] != 0)
{
cout << letterCount[25] - letterCount[i] << endl;
break;
}
}
return 0;
}
代码片段解释
// 对字母出现次数进行排序
sort(letterCount, letterCount + 26);
sort函数的原型如下：template <class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last);
first：是指向排序范围的起始位置last：是指向排序范围的结束位置（不包含在排序范围内）
为什么可以这样写？
letterCount：是一个指针，指向数组的第一个元素
letterCount + 26： 是数组的结束位置（即：第 26 个元素的下一个位置）
- 在 C++ 中，数组的索引从
0开始，因此letterCount + 26指向数组的末尾
244 最长子序列
题目介绍
开始挑战：244 最长子序列
方法一：
#include <stdio.h>
#include <string.h>
int main()
{
char sourceString[1000], targetString[1000];// 定义源字符串和目标字符串
int matchedLength = 0; // 记录匹配的长度
// 获取输入字符串
fgets(sourceString, sizeof(sourceString), stdin); //fgets会读取空格，并且可以连我们结束输入字符串的换行符\n都能读取到
fgets(targetString, sizeof(targetString), stdin);
// 去掉 fgets 读取的换行符
int sourceLength = strlen(sourceString);
if (sourceString[sourceLength - 1] == '\n') //sourceLength - 1这是字符串sourceString中最后一个字符的下标，
{ //这个字符可能是\n也可能不是：1.正常输入完---> 是\n ; 2.被截断 ---> 不是\n
sourceString[sourceLength - 1] = '\0';
}
int targetLength = strlen(targetString);
if (targetString[targetLength - 1] == '\n')
{
targetString[targetLength - 1] = '\0';
}
// 重新计算字符串的长度
sourceLength = strlen(sourceString);
targetLength = strlen(targetString);
// 使用双指针（快慢指针：一个指针不停的走，而一个指针只有满足条件才走）
// 目标是：从左到右在源字符串中找到尽可能多的目标字符串的字符
for (int sourceIndex = 0, targetIndex = 0; sourceIndex < sourceLength && targetIndex < targetLength; sourceIndex++)
{
// 如果当前字符匹配
if (targetString[targetIndex] == sourceString[sourceIndex])
{
matchedLength++; // 匹配长度加1
targetIndex++; // 移动到目标字符串的下一个字符
}
}
printf("%d\n", matchedLength); // 输出匹配的长度
return 0;
}
代码片段解释
片段一：
// 获取输入字符串
fgets(sourceString, sizeof(sourceString), stdin);
fgets(targetString, sizeof(targetString), stdin);
函数介绍：
fgets()：用于从文件或标准输入中读取一行字符串。
fgets会从标准输入中读取一行字符（直到遇到换行符\n或文件结束符EOF），并将其存储到sourceString中- 如果读取的字符数超过
sizeof(sourceString) - 1，fgets会自动截断，并在末尾添加空字符\0
- 如果读取成功，
fgets会返回sourceString的地址- 如果读取失败（如：遇到文件结束符），则返回
NULL
函数原型：char *fgets(char *str, int n, FILE *stream);
str：是一个指向字符数组的指针，用于存储读取到的字符串的缓冲区n：是最多读取的字符数（包含字符串末尾用于表示结束的空字符\0）
- 比如
n为 10，那么最多读取 9 个字符，剩下一个字节留给\0stream：是文件或输入流的指针
- 若从
标准输入（键盘）读取，该参数为stdin- 若从
文件读取，则是通过fopen函数打开文件后返回的文件指针
片段二：
// 去掉 fgets 读取的换行符
int sourceLength = strlen(sourceString);
if (sourceString[sourceLength - 1] == '\n') //sourceLength - 1这是字符串sourceString中最后一个字符的下标，
{ //这个字符可能是\n也可能不是：1.正常输入完---> 是\n ; 2.被截断 ---> 不是\n
sourceString[sourceLength - 1] = '\0';
}
int targetLength = strlen(targetString);
if (targetString[targetLength - 1] == '\n')
{
targetString[targetLength - 1] = '\0';
}
这段代码的作用是使用
fgets从标准输入读取字符串，并去掉字符串末尾的换行符\n（
只有在输入的字符数量+1 还不大于fgets函数的第二个参数的值-1时 字符串末尾的字符才是\n）
为什么要去掉换行符
\n？
fgets会从输入中读取一行字符，直到遇到换行符\n或文件结束符EOF如果读取到换行符
\n，fgets会将其包含在读取的字符串中
- 例如：如果输入是
Hello，fgets读取的字符串实际上是"Hello\n\0"去掉换行符后，字符串只包含用户实际输入的内容，便于后续处理。
- 例如：输入
Hello，去掉换行符后，字符串变为"Hello\0"，更符合预期
精彩代码模块
使用fgets函数从键盘获取字符串并求出字符串的长度
// 获取输入字符串
fgets(sourceString, sizeof(sourceString), stdin); //fgets会读取空格，并且可以连我们结束输入字符串的换行符\n都能读取到
fgets(targetString, sizeof(targetString), stdin);
// 去掉 fgets 读取的换行符
int sourceLength = strlen(sourceString);
if (sourceString[sourceLength - 1] == '\n') //sourceLength - 1这是字符串sourceString中最后一个字符的下标，
{ //这个字符可能是\n也可能不是：1.正常输入完---> 是\n ; 2.被截断 ---> 不是\n
sourceString[sourceLength - 1] = '\0';
}
int targetLength = strlen(targetString);
if (targetString[targetLength - 1] == '\n')
{
targetString[targetLength - 1] = '\0';
}
// 重新计算字符串的长度
sourceLength = strlen(sourceString);
targetLength = strlen(targetString);
解题思路分析
题目的大意是：
按照目标字符串中字符出现的顺序，从源字符串中从前往后挑选出与之对应的若干个字符，输出无法挑出对应的字符时已经挑出的字符的数量
使用一个for循环：（下面所说的指针是广义上的指针，其实是字符数组的下标）
- 两个指针同时从各自字符串下标为0的地方开始向后遍历
- 一个指针经过一次if判断（无论是否满足条件）就 ++ 一次
- 另一指针只有满足条件时才 ++ 一次
- 两个指针中任意一个指针到达自己字符串的尾部 —> 循环结束
239 最优包含
题目介绍
开始挑战：239 最优包含
方法一：
#include <iostream>
#include <string>
#include <algorithm> // 用于 min 函数
using namespace std;
int minEditDistance[1010][1010]; // minEditDistance[i][j] 表示 s 的前 i 个字符和 t 的前 j 个字符的最小编辑距离
int main()
{
string source, target; // source 是源字符串，target 是目标字符串
cin >> source >> target;
// 初始化：当 source 为空字符串时，需要插入 target 的所有字符
for (int j = 1; j <= target.size(); j++)
{
minEditDistance[0][j] = 0x3f3f; // 设置为一个较大的值，表示不可达
}
// 动态规划计算最小编辑距离
for (int i = 0; i < source.size(); i++)
{
for (int j = 0; j < target.size(); j++)
{
if (source[i] == target[j])
{
// 如果字符相等，则不需要修改，直接继承之前的编辑距离 ---> 在二维数组的该位置左上角的位置的值
minEditDistance[i + 1][j + 1] = minEditDistance[i][j];
}
else
{
// 如果字符不相等，则选择替换或删除操作中的最小值 ---> 选择 在二维数组的该位置左上角的位置的值+1 与 该位置正上方的位置的值 的最小值
minEditDistance[i + 1][j + 1] = min(minEditDistance[i][j] + 1, minEditDistance[i][j + 1]);
}
}
}
// 输出最小编辑距离
cout << minEditDistance[source.size()][target.size()] << endl;
return 0;
}
程序执行流程
精彩代码模块
动态规划计算最小编辑距离dp数组的初始化
// 初始化：当 source 为空字符串时，需要插入 target 的所有字符
for (int j = 1; j <= target.size(); j++)
{
minEditDistance[0][j] = 0x3f3f; // 设置为一个较大的值，表示不可达
}
动态规划计算最小编辑距离的递推公式
// 动态规划计算最小编辑距离
for (int i = 0; i < source.size(); i++)
{
for (int j = 0; j < target.size(); j++)
{
if (source[i] == target[j])
{
// 如果字符相等，则不需要修改，直接继承之前的编辑距离 ---> 在二维数组的该位置左上角的位置的值
minEditDistance[i + 1][j + 1] = minEditDistance[i][j];
}
else
{
// 如果字符不相等，则选择替换或删除操作中的最小值 ---> 选择 在二维数组的该位置左上角的位置的值+1 与 该位置正上方的位置的值 的最小值
minEditDistance[i + 1][j + 1] = min(minEditDistance[i][j] + 1, minEditDistance[i][j + 1]);
}
}
}
解题思路分析
题目的主要意思：给定两个字符串，输出源串最少修改多少个字符可以使得“源串包含目标串”
针对本题有一些误区：
源串只可以对自己进行：替换和删除 ，不可以在源串中添加任何字符（正确理解
修改源串中的字符的意思）并不是要把源串修改成和目标串一样，而只是说将源串修改成从源串中从左到右挑选出的字符可以按从左到右的顺序拼接成和目标串一样的字符串即可（正确理解
包含目标串的意思）
第一步：先定义一个二维的dp数组（一定要对于自己定义的dp数组的含义非常理解）
- dp数组的含义：
minEditDistance[i][j]：表示 s 的前 i 个字符和 t 的前 j 个字符的最小编辑距离第二步：对dp数组的进行初始化
minEditDistance[0][j] = 0x3f3f;将数组的第一行初始化为一个较大的值，表示不可达
- 初始化含义：如果源串是一个空串那么它不可以通过修改而包含目标字符串（这里的修改包含：
替换，删除，但是不包含添加）第三步：使用双重for循环遍历两个字符串，并根据递推公式不断的完善dp数组
- 使用if分支语句根据源串和目标串对应的字符是否相等，进行不同的操作
- 对应的字符相等：则不需要修改，直接继承之前的编辑距离 —> 在二维数组的该位置左上角的位置的值
- 对应的字符不相等：则选择替换或删除操作中的最小值 —> 选择 在二维数组的该位置左上角的位置的值+1 与 该位置正上方的位置的值 的最小值
继承操作：
minEditDistance[i + 1][j + 1] = minEditDistance[i][j];
- 源串与目标串中都又添加的新字符是相等， 所以源串没有必要修改什么
替换操作：
minEditDistance[i + 1][j + 1] = minEditDistance[i][j] + 1;
- 源串和目标串中都又添加了一个新字符，只不过这两个字符不一样，那就在之前的所有操作基础上再添加一步操作即可
删除操作：
minEditDistance[i + 1][j + 1] = minEditDistance[i][j + 1];
- 这不是真正意义上的删除了一个字符串中的一个字符，而是说忽略掉了源串中新添加的那个字符。
minEditDistance[i][j + 1]这个位置在minEditDistance[i + 1][j + 1]这个位置的正上方所以两者相比较就像是现在的源字符串比之前的源字符串多了一个字符，但是我们要知道：我们现在要研究的问题是“源串包含目标串”，所以源串中多一个字符并不会影响我们修改的次数，所以我们选择忽略掉它，这也即使所谓的删除操作。注意：遍历两个字符串我们是我们是从0<= 下标 <source.size()/0<= 下标 <target.size()，但是dp数组中使用的下标范围是：1<= 下标 <=source.size()
504 单词分析
题目介绍
开始挑战：504 单词分析
方法一：
#include <iostream>
#include <string>
#include <vector>
#include <climits>
using namespace std;
int main()
{
string inputString;
cin >> inputString;
// 处理数据：要求
// 1. 获取出现次数最多的字符
// 2. 若出现次数最多的字符有多个，则输出字典序最小的那个字符
// 使用一个数组来统计每个小写字母的出现次数
vector<int> letterCount(26, 0); // 初始化为0
// 遍历字符串，统计每个字符的出现次数
for (char currentChar : inputString)
{
letterCount[currentChar - 'a']++; // 对应字母的计数加1
}
// 找到出现次数最多的字符及其次数
int maxCount = INT_MIN; // 记录出现次数的最大值
char mostFrequentChar; // 记录出现次数最多的字符
for (int i = 0; i < letterCount.size(); i++)
{
if (letterCount[i] > maxCount)
{
mostFrequentChar = (char)(i + 'a'); // 转换为对应的字符
maxCount = letterCount[i]; // 更新最大次数
}
}
// 输出结果：出现次数最多的字符及其出现次数
cout << mostFrequentChar << endl << maxCount;
return 0;
}
精彩代码片段
输出一个字符串中出现次数最多的字符和其出现的次数，如果有多个出现次数最多的字符输出字典序最小的那个
//遍历字符串并使用一个一维数组来存放每个字符出现的次数
//遍历一维数组并找出所有数中的最大的数
for (char currentChar : inputString)
{
letterCount[currentChar - 'a']++; // 对应字母的计数加1
}
int maxCount = INT_MIN; // 记录出现次数的最大值
char mostFrequentChar; // 记录出现次数最多的字符
for (int i = 0; i < letterCount.size(); i++)
{
if (letterCount[i] > maxCount)
{
mostFrequentChar = (char)(i + 'a'); // 转换为对应的字符
maxCount = letterCount[i]; // 更新最大次数
}
}
解题思路分析
疑问：从上面代码中我们好像并没有看出有单独处理输入的字符串中出现次数最多的字符不止一个的情况的代码啊？
但是其实我们在无形中已经处理了上面的情况，若最大出现次数的字符有多个时，当我们通过遍历一维数组找最大的出现次数的时候，我们其实找的是第一个最大的出现次数，而第一个最大的出现次数的索引对应的字符也即是字典序最小的字符。
97 K倍区间
题目介绍
开始挑战：97 K倍区间
方法一：
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> num(n);
for (int i = 0; i < n; i++)
{
cin >> num[i];
}
// 使用前缀和和哈希表优化
unordered_map<int, int> remainderCount; // 记录前缀和余数的出现次数
long long prefixSum; //这里注意我们使用的类型是：long long
//n与k的范围都是在1e5内，int类型足以，但是prefixSum是1e5个int的和，int的容量已经不够使用
prefixSum = 0;
remainderCount[0] = 1; // 初始化：前缀和为 0 的情况
long long result = 0;
for (int i = 0; i < n; i++)
{
prefixSum += num[i]; // 计算前缀和
int remainder = (prefixSum % k + k) % k; // 处理负数情况，确保余数为正
// 如果当前余数已经出现过，则累加对应的区间数量
if (remainderCount.find(remainder) != remainderCount.end())
{
result += remainderCount[remainder];
}
// 更新当前余数的出现次数
remainderCount[remainder]++;
}
// 输出结果
cout << result << endl;
return 0;
}
代码片段解释
片段一：
unordered_map<int, int> remainderCount; // 记录前缀和余数的出现次数
remainderCount[0] = 1; // 初始化：前缀和为 0 的情况
unordered_map：是 C++ 标准库中的一个关联容器。
- 用于存储键值对，能实现快速的查找、插入和删除操作。
unordered_map<int, int>：表示创建一个无序映射。
- 其中键（key）和值（value）的数据类型都是
intremainderCount：是这个无序映射容器的名称。
- 本题中用来记录前缀和除以某个数（这里是题目中的
k）得到的余数的出现次数。- 键为余数，值为该余数出现的次数 。
- 比如：键
3对应的值为2，表示前缀和除以指定数余数为3的情况出现了2次
remainderCount[0]：表示访问remainderCount这个无序映射中键为0的元素。
- 如果该键不存在，
unordered_map会自动创建它，并将对应的值初始化为默认值（对于int类型默认值是0）remainderCount[0] = 1：是将键为0的元素的值设为1，这是一种初始化操作。- 因为前缀和为
0的情况默认出现了1次（可以理解为还没有开始计算任何数的前缀和时，也就是空序列的前缀和为0，出现了一次 ），在计算K倍区间数量时，这个初始化能正确处理相关逻辑。
片段二：
prefixSum += num[i]; // 计算前缀和
int remainder = (prefixSum % k + k) % k; // 处理负数情况，确保余数为正
这行代码的作用是计算前缀和 (prefixSum) 除以 (k) 的余数，并确保余数为非负数。
1. 为什么需要这行代码？
在 C++ 中，取模运算
%的结果可能是负数，而在哈希表remainderCount中，余数作为键（Key），必须是唯一的且非负的。
- 如果 prefixSum = -1，k = 3，那么
-1 % 3的结果是-1- 但我们希望余数始终是非负数（即： 0 ≤ 余数 < k 0 \leq \text{余数} < k 0≤余数<k），因此需要对负数情况进行处理
2. 代码解析
步骤 1：
计算 prefixSum % k
- 如果 prefixSum 是正数，结果是一个非负余数（ 0 ≤ 余数 < k 0 \leq \text{余数} < k 0≤余数<k）
- 如果 prefixSum 是负数，结果是一个负余数（ − k < 余数 < 0 -k < \text{余数} < 0 −k<余数<0）
步骤 2：
加上 k（如果前缀和是负数，这一步骤很重要）
- 如果
prefixSum % k是负数，加上 k 可以将其转换为正数。
- 如果
prefixSum % k = -1，那么-1 + k = 2（假设： k = 3 k = 3 k=3）- 如果
prefixSum % k = 2，那么2 + k = 5（假设： k = 3 k = 3 k=3）步骤 3：
再次取模 % k（如果前缀和是正数，这一步骤很重要）
- 对上一步的结果再次取模，确保余数在 ( 0 ≤ 余数 < k 0 \leq \text{余数} < k 0≤余数<k )的范围内。
- 如果上一步的结果是
5，那么5 % 3 = 2- 如果上一步的结果是
2，那么2 % 3 = 2
片段三：
// 如果当前余数已经出现过，则累加对应的区间数量
if (remainderCount.find(remainder) != remainderCount.end())
{
result += remainderCount[remainder];
}
// 更新当前余数的出现次数
remainderCount[remainder]++;
1.
if (remainderCount.find(remainder) != remainderCount.end())
这行代码的作用是检查当前前缀和对
k的余数remainder是否已经在哈希表remainderCount中出现过。
remainderCount.find(remainder)会在哈希表中查找键remainder
- 如果找到了，返回指向该键值对的迭代器
- 如果没找到，返回
remainderCount.end()因此：
remainderCount.find(remainder) != remainderCount.end()的含义是：如果余数remainder之前已经出现过，则进入if语句。
2.
result += remainderCount[remainder];
- 如果余数
remainder之前已经出现过，说明当前前缀和可以和之前所有出现过相同余数的前缀和配对，形成新的K倍区间。remainderCount[remainder]表示余数remainder之前出现的次数。因此：
result += remainderCount[remainder]的含义是：将之前出现过该余数的次数累加到结果result中。示例：
- 假设余数
remainder = 2，且之前出现过 3 次（即：remainderCount[2] = 3）- 当前前缀和可以与之前 3 个前缀和配对，形成 3 个新的
K倍区间。- 因此：
result增加 3
3.
remainderCount[remainder]++;
- 这行代码的作用是更新当前余数
remainder的出现次数- 无论当前余数是否之前出现过，都需要将当前余数的出现次数加 1
- 这样做的目的是为了在后续遍历中，如果再次遇到相同的余数，可以正确统计新增的
K倍区间数量示例：
- 假设当前余数
remainder = 2，且之前出现过 3 次（即：remainderCount[2] = 3）- 执行
remainderCount[2]++后，remainderCount[2]变为 4- 这样，如果后续再次遇到余数
2，就可以知道之前已经出现过 4 次
精彩代码片段
求一个有符号整数的非负余数
int remainder = (prefixSum % k + k) % k; // 处理负数情况，确保余数为正
解题思路分析
问题描述：
给定一个整数数组
nums和一个整数k，要求计算有多少个子数组的和可以被k整除。疑问：为什么使用前缀和？
前缀和：用于快速计算数组中任意子数组的和。前缀和数组 prefixSum 的定义：
prefixSum[i] = nums[0] + nums[1] + ... + nums[i-1]
通过前缀和，我们可以快速计算任意子数组
nums[i..j]的和：sum(i, j) = prefixSum[j+1] - prefixSum[i]
为什么要计算余数？
我们需要找到那些子数组的和可以被
k整除，即：sum(i, j) % k == 0（这里的i，j是数组的下标哦~）根据前缀和的性质，我们可以将上述条件转化为：
(prefixSum[j] - prefixSum[i-1]) % k == 0这等价于：
prefixSum[j] % k == prefixSum[i-1] % k结论：
如果两个前缀和对 k 取余的结果相同，那么这两个前缀和之间的子数组和一定可以被 k 整除或者记忆为：
余数相同的两个前缀和之间的子数组和一定是 k 的倍数
疑问：什么统计余数出现的次数？
或者这样问：为什么当前缀和除以 k 的余数之前出现过时，K倍区间的数量会直接增加之前出现过该余数的数量个？（本题的核心问题）
核心思想：余数相同的两个前缀和之间的子数组和一定是
k的倍数
假设我们有两个前缀和
prefixSum[i]和prefixSum[j]（其中i < j），它们对k取余的结果相同：prefixSum[i] % k == prefixSum[j] % k根据前缀和的性质，两个前缀和之间的子数组
nums[i+1..j]的和可以表示为：sum(i+1, j) = prefixSum[j] - prefixSum[i]因为
prefixSum[i] % k == prefixSum[j] % k，所以：(prefixSum[j] - prefixSum[i]) % k == 0
- 也就是说：子数组
nums[i+1..j]的和一定是k的倍数。所以说：如果这个
remainder之前已经出现过n次，那么当前前缀和可以和之前所有出现过相同余数的前缀和配对，形成n个新的K倍区间。因此：
K倍区间的数量直接增加了之前出现过该余数的次数。
举个例子：假设
k = 5，数组为[4, 5, 0, -2, -3, 1]，我们计算前缀和及其对k的余数：
索引 元素 前缀和 前缀和 % 5 0 4 4 4 1 5 9 4 2 0 9 4 3 -2 7 2 4 -3 4 4 5 1 5 0
当遍历到索引
1时：
- 前缀和为
9，余数为4。此时余数4已经出现过一次（在索引0），所以我们可以形成一个K倍区间[1]（子数组[5]）当遍历到索引
2时：
- 前缀和仍为
9，余数仍为4。此时余数4已经出现过两次（在索引0和1），所以我们可以形成两个新的K倍区间：
- 从索引
0到2的子数组[4, 5, 0]，和为9- 从索引
1到2的子数组[5, 0]，和为5当遍历到索引
4时：
- 前缀和为
4，余数为4。此时余数4已经出现过三次（在索引0、1和2），所以我们可以形成三个新的K倍区间：
- 从索引
0到4的子数组[4, 5, 0, -2, -3]，和为4- 从索引
1到4的子数组[5, 0, -2, -3]，和为0- 从索引
2到4的子数组[0, -2, -3]，和为-5（仍然是5的倍数）
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
