谷歌高畅LeetCode刷题指南：C++版101题详解
5星 · 超过95%的资源 需积分: 50 177 浏览量
更新于2024-07-09
1
收藏 3.54MB PDF 举报 "谷歌高畅的《LeetCode刷题笔记》是一本专门为C++编程基础者设计的教材和参考书，由作者ChangGao编撰，针对缺乏刷题经验的学习者提供系统性的指导。该书是在作者攻读硕士期间，为准备实习秋招而整理LeetCode题目，并在经历了一年的刷题和初步总结后，于2019年秋季升级为正式版1.04，旨在帮助读者更好地理解和掌握算法与数据结构。
书中的主要内容包括101道精选题目，这些题目代表了刷题过程中常用的技巧，既符合书名中的"一起轻松刷题"，也控制了读者的学习负担。每个章节都详细讲解了相应的算法和数据结构，并提供了清晰的题解。为了确保读者能全面理解，作者在每个章节末尾推荐了额外的练习题，并给予了解题思路的提示。尽管书是以C++作为主要编程语言，但对于Java用户来说，大部分内容可以迁移，只是语法上需要做一些调整。然而，对于Python或其他语言的用户，由于语法差异较大，可能需要适度适应。
值得注意的是，作者并非单纯教授C++语言，而是注重算法和数据结构的实际应用，因此书中不会深入讲解语法细节，而是采用C++11及以上版本的语法，以保持内容的现代性和实用性。如果读者对该书反响热烈，作者计划未来会添加更多题解。
《LeetCode刷题笔记》是一本实用且有针对性的刷题指南，尤其适合那些希望通过刷题提升C++技能和算法理解能力的读者。通过阅读此书，读者不仅能提升技术能力，还能了解到如何将理论知识应用于实际问题解决中。"
3.6 练习 – 12/143 –
题目描述
给定两个字符串 S 和 T，求 S 中包含 T 所有字符的最短连续子字符串的长度，同时要求时间
复杂度不得超过 O(n)。
输入输出样例
输入是两个字符串 S 和 T ，输出是一个 S 字符串的子串。
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
在这个样例中，S 中同时包含一个 A、一个 B、一个 C 的最短子字符串是“BANC”。
题解
本题使用滑动窗口求解，即两个指针 l 和 r 都是从最左端向最右端移动，且 l 的位置一定在
r 的左边或重合。注意本题虽然在 for 循环里出现了一个 while 循环，但是因为 while 循环负责移
动 l 指针，且 l 只会从左到右移动一次，因此总时间复杂度仍然是 O(n)。本题使用了长度为 128
的数组来映射字符，也可以用哈希表替代；其中 chars 表示目前每个字符缺少的数量，flag 表示
每个字符是否在 T 中存在。
string minWindow(string S, string T) {
vector<int> chars(128, 0);
vector<bool> flag(128, false);
// 先统计T中的字符情况
for (int i = 0; i < T.size(); ++i) {
flag[T[i]] = true;
++chars[T[i]];
}
// 移动滑动窗口，不断更改统计数据
int cnt = 0, l = 0, min_l = 0, min_size = S.size() + 1;
for (int r = 0; r < S.size(); ++r) {
if (flag[S[r]]) {
if (--chars[S[r]] >= 0) {
++cnt;
}
// 若目前滑动窗口已包含T中全部字符，
// 则尝试将l右移，在不影响结果的情况下获得最短子字符串
while (cnt == T.size()) {
if (r - l + 1 < min_size) {
min_l = l;
min_size = r - l + 1;
}
if (flag[S[l]] && ++chars[S[l]] > 0) {
--cnt;
}
++l;
}
}
}
return min_size > S.size()? "": S.substr(min_l, min_size);
}
剩余145页未读，继续阅读
2022-08-04 上传
2022-08-04 上传
2020-12-22 上传
2021-06-30 上传
2021-06-30 上传
2021-06-30 上传
2021-06-30 上传
2021-06-30 上传
KryHan
- 粉丝: 218
- 资源: 5
我的内容管理
展开
