算法刷题笔记：从滑动窗口到哈夫曼编码，我的算法进阶之路

在算法的学习过程中刷题是提升编程能力和逻辑思维的重要途径。最近我刷了几道不同类型的算法题包括字符串处理、广度优先搜索BFS、动态规划以及哈夫曼编码等这些题目涵盖了不同的算法思想让我对算法的应用有了更深入的理解。现在我将这几道题的解题思路和实现过程整理成这篇博客希望能对同样在算法学习路上的小伙伴们有所帮助。一、包含不超过两种字符的最长子串滑动窗口题目描述给定一个长度为n的字符串找出最多包含两种字符的最长子串t返回这个最长的长度。字符串仅包含小写英文字母数据范围1 ≤ n ≤ 10^5。解题思路这道题可以使用滑动窗口双指针的方法来解决。我们维护一个窗口[left, right]窗口内的字符种类数不超过 2 种。具体步骤如下使用一个哈希表这里用数组模拟因为字符是小写字母所以数组大小为 26来统计窗口内每种字符的出现次数。使用变量count记录窗口内不同字符的种类数。右指针right不断向右移动将当前字符加入窗口如果该字符在窗口内的出现次数从 0 变为 1说明窗口内多了一个新字符count加 1。当count 2时需要移动左指针left缩小窗口直到count ≤ 2如果左指针指向的字符在窗口内的出现次数从 1 变为 0说明窗口内少了一个字符count减 1。每次调整窗口后更新最长子串的长度。代码实现#include iostream #include string using namespace std; int main() { string s; cin s; int left 0, right 0, n s.size(); int hash[26] {0}; // 统计窗口内每种字符出现的次数 int count 0; // 统计窗口内一共有多少种字符 int ret 0; while (right n) { if (hash[s[right] - a] 0) count; // 0-1,窗口内多了一种字符 while (count 2) { if (hash[s[left] - a]-- 1) count--; // 1-0,窗口内少了一种字符 } ret max(ret, right - left 1); right; } cout ret endl; return 0; }二、迷宫出口问题广度优先搜索 BFS题目描述koton 在一个n*m迷宫里迷宫的最外层被岩浆淹没无法涉足迷宫内有k个出口。koton 只能上下左右四个方向移动。她想知道有多少出口是她能到达的最近的出口离她有多远解题思路这道题是典型的广度优先搜索BFS应用场景。BFS 适合寻找最短路径因为它按层遍历第一次到达目标节点时的步数就是最短距离。具体步骤如下读取输入找到 koton 的起始位置(x1, y1)和所有出口的位置。初始化一个距离数组dist用于记录每个位置到起始点的最短距离初始值为 -1表示未访问。使用队列进行 BFS从起始点开始依次访问其上下左右四个方向的相邻位置如果相邻位置在迷宫范围内、不是墙壁、且未被访问过则更新其距离并将其加入队列。注意如果是出口也需要加入队列继续传播距离因为可能其他出口的距离更近。遍历结束后统计所有出口中可到达的数量和最小距离。代码实现#include iostream #include cstring #include queue using namespace std; const int N 35; int x1, y1; int n, m; char arr[N][N]; int dist[N][N]; queuepairint, int q; int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; void bfs() { memset(dist, -1, sizeof dist); dist[x1][y1] 0; q.push({x1, y1}); while (q.size()) { auto [x2, y2] q.front(); q.pop(); for (int i 0; i 4; i) { int a x2 dx[i], b y2 dy[i]; if (a 1 a n b 1 b m dist[a][b] -1 arr[a][b] ! *) { dist[a][b] dist[x2][y2] 1; if (arr[a][b] ! e) { // 出口不需要再入队因为已经是终点但其他路径可能经过 q.push({a, b}); } } } } } int main() { cin n m; for (int i 1; i n; i) { for (int j 1; j m; j) { cin arr[i][j]; if (arr[i][j] k) { x1 i, y1 j; } } } bfs(); int count 0, ret 1e9; for (int i 1; i n; i) { for (int j 1; j m; j) { if (arr[i][j] e dist[i][j] ! -1) { count; ret min(ret, dist[i][j]); } } } if (count 0) cout -1 endl; else cout count ret endl; return 0; }三、字符串的编辑距离动态规划题目描述给定两个字符串word1和word2计算将word1转换成word2所使用的最少操作数。操作包括插入一个字符、删除一个字符、替换一个字符。数据范围1 ≤ word1.length, word2.length ≤ 500。解题思路这道题是经典的动态规划问题。我们可以定义一个二维数组dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最少操作数。状态转移方程如下如果word1[i-1] word2[j-1]则dp[i][j] dp[i-1][j-1]不需要操作。否则dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1其中dp[i-1][j]表示删除word1的第i个字符。dp[i][j-1]表示在word1中插入word2的第j个字符。dp[i-1][j-1]表示替换word1的第i个字符为word2的第j个字符。代码实现#include iostream #include vector #include algorithm using namespace std; int minDistance(string word1, string word2) { int n word1.size(), m word2.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); // 初始化边界条件 for (int i 0; i n; i) dp[i][0] i; // word1前i个字符转成空字符串需要删除i次 for (int j 0; j m; j) dp[0][j] j; // 空字符串转成word2前j个字符需要插入j次 // 状态转移 for (int i 1; i n; i) { for (int j 1; j m; j) { if (word1[i-1] word2[j-1]) { dp[i][j] dp[i-1][j-1]; }se { el dp[i][j] min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) 1; } } } return dp[n][m]; } int main() { string word1, word2; cin word1 word2; cout minDistance(word1, word2) endl; return 0; }四、哈夫曼编码贪心 优先队列题目描述给定n个权值构造哈夫曼树并输出每个权值对应的哈夫曼编码。哈夫曼编码是一种变长编码用于数据的压缩出现频率高的字符使用较短的编码频率低的字符使用较长的编码。解题思路哈夫曼编码的构造过程是典型的贪心算法应用每次选择两个权值最小的节点合并直到形成一棵哈夫曼树。具体步骤如下将所有权值放入优先队列小根堆中。每次从队列中取出两个最小的权值合并成一个新的节点新节点的权值为两个子节点权值之和并将新节点重新放入队列中。重复步骤 2直到队列中只剩下一个节点哈夫曼树的根节点。在合并的过程中记录每个权值的父节点和左右子节点的关系然后递归生成每个权值的哈夫曼编码左子树编码为 0右子树编码为 1。代码实现#include iostream #include queue #include vector #include map using namespace std; typedef long long LL; typedef pairLL, int PII; // 权值节点编号 struct Node { LL w; int l, r; Node(LL w 0, int l 0, int r 0) : w(w), l(l), r(r) {} bool operator (const Node other) const { return w other.w; // 小根堆所以重载为w大的排后面 } }; vectorNode huff; mapLL, string code; // 生成哈夫曼编码 void dfs(int u, string s) { if (huff[u].l 0 huff[u].r 0) { // 叶子节点 code[huff[u].w] s; return; } if (huff[ul)]. dfs(huff[u].l, s 0); if (huff[u].r) dfs(huff[u].r, s 1); } int main() { int n; cin n; priority_queuePII pq; // 小根堆存储权值和节点编号这里节点编号可以暂时用权值代替或者后续处理 for (int i 0; i n; i) { LL w; cin w; pq.push({w, i}); // 节点编号暂时用i后续可能需要调整 huff.emplace_back(w, 0, 0); // 初始化叶子节点 } while (pq.size() 1) { auto [w1, u] pq.top(); pq.pop(); auto [w2, v] pq.top(); pq.pop(); LL w w1 w2; int node huff.size(); huff.emplace_back(w, u, v); // 新节点左孩子是u右孩子是v pq.push({w, node}); } if (!huff.empty()) { dfs(pq.top().second, ); // 从根节点开始遍历 for (int i 0; i n; i) { cout huff[i].w code[huff[i].w] endl; } } return 0; }总结这几道题分别涵盖了滑动窗口、广度优先搜索、动态规划和贪心算法哈夫曼编码等不同的算法思想。通过解决这些题目我不仅巩固了算法的基础知识还学会了如何根据不同的问题场景选择合适的算法。刷题的过程虽然有时会遇到困难和挫折但每解决一道题带来的成就感都是巨大的也让我更加热爱算法学习。希望这篇博客能对你有所启发也欢迎大家在评论区交流讨论一起进步以上是我对这几道算法题的总结和分享如果你有任何问题或建议欢迎留言交流