LeetCode Hot100 (2、3、4、5、6、8、9、12)

题2--字母异或位分词

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {//  一开始的思路是，对于其中的一个单词，遍历所有排序组合，然后判断这些组合是否在哈希表里//，在的话就加入数组，然后从哈希表里删掉，问题是如何遍历所有排序组合，dfs？//这里学习一种方法，将哈希表中的不同字符串排序，如果排序后是相等的就代表字母一样//如果有这种思路，就很简单了，依次遍历数组，看他排序后的字符串是否在哈希表里，在就修改哈希表的值，不在就加入这个keyunordered_map<string,vector<string>> m;for(int i=0;i<strs.size();i++){string str=strs[i];sort(str.begin(),str.end());m[str].emplace_back(strs[i]);}vector<vector<string>> s;for(auto t:m){s.emplace_back(t.second);}return s;}
};

 1.push_back vs emplace_back

函数	行为	性能影响	适用场景
push_back	接受一个 ​​已构造的对象​​，通过拷贝或移动操作添加到容器末尾	若传递临时对象（如右值），触发移动构造（比拷贝快）；若传递左值，触发拷贝构造	当已持有构造好的对象时使用
emplace_back	直接在容器内存中 ​​构造对象​​，无需创建临时对象	完全避免拷贝/移动操作，​​性能更优​​（尤其对复杂对象）	需要直接构造对象时使用（传递构造参数而非对象本身）

• 对于简单类型（如 int, double）：两者性能几乎相同。
• 对于复杂类型（如 std::string, 自定义类）：emplace_back 效率更高（减少一次拷贝/移动）。
• 对于不可拷贝/移动的对象（如 std::unique_ptr）：​​必须使用 emplace_back​​。

• 在 C++11 及以上环境中，​​优先使用 emplace_back​​。

2.vector 常用操作表格

操作	函数	用途	时间复杂度
​​添加元素​​	push_back(const T& value)	在末尾添加元素的拷贝	O(1) 均摊
	emplace_back(Args&&... args)	在末尾直接构造元素	O(1) 均摊
​​删除元素​​	pop_back()	删除末尾元素	O(1)
​​容量查询​​	size()	返回元素数量	O(1)
	empty()	判断是否为空	O(1)
​​内存管理​​	reserve(size_type n)	预分配至少容纳 n 个元素的内存	O(n)
	capacity()	返回当前分配的内存容量	O(1)
	shrink_to_fit()	释放未使用的内存（C++11起）	O(n)
​​修改大小​​	resize(size_type n)	调整元素数量（多删少补默认值）	O(n)
	resize(size_type n, const T& value)	调整元素数量（多删少补指定值）	O(n)
​​元素访问​​	operator[]	通过下标访问（无边界检查）	O(1)
	at(size_type pos)	通过下标访问（有边界检查）	O(1)
	front()	访问第一个元素	O(1)
	back()	访问最后一个元素	O(1)
​​批量操作​​	insert(iterator pos, InputIt first, InputIt last)	在指定位置插入区间元素	O(n + m)
	erase(iterator pos)	删除指定位置元素	O(n)
	clear()	清空所有元素（不释放内存）	O(n)
​​迭代器​​	begin() / end()	获取首尾迭代器	O(1)

string类型基础操作

 string类型的排序是通过 begin（） end（）

1.构造与赋值​​

操作	函数/语法	描述	示例	注意事项
​​默认构造​​	string s;	创建空字符串	string s;	初始为空
​​拷贝构造​​	string s(str);	复制另一个字符串	string s2(s1);	深拷贝
​​C 字符串构造​​	string s("text");	从 C 风格字符串构造	string s("hello");	自动计算长度
​​重复字符构造​​	string s(n, 'c');	创建含 n 个字符的字符串	string s(5, 'a'); → "aaaaa"	字符需明确
​​移动构造​​ (C++11)	string s(std::move(str));	转移另一个字符串的内容	string s2 = std::move(s1);	原字符串失效
​​赋值操作符​​	s = "text";	用新内容覆盖原字符串	s = "world";	支持多种类型
​​assign()​​	s.assign(str);	重新赋值	s.assign("test", 3); → "tes"	可指定长度

---

​​2.元素访问​​

操作	函数/语法	描述	示例	注意事项
​​下标访问​​	s[i]	访问第 i 个字符	char c = s[0];	不检查越界
​​at()​​	s.at(i)	访问第 i 个字符（检查越界）	char c = s.at(0);	越界抛出 out_of_range
​​front()​​	s.front()	访问第一个字符	char c = s.front();	等价于 s[0]
​​back()​​	s.back()	访问最后一个字符	char c = s.back();	等价于 s[s.size()-1]
​​data()​​	s.data()	返回指向字符数组的指针	const char* p = s.data();	非终止符（C++11 前）
​​c_str()​​	s.c_str()	返回 C 风格字符串（以 \0 结尾）	printf("%s", s.c_str());	指针不可修改

---

​​3.修改操作​​

操作	函数/语法	描述	示例	注意事项
​​append()​​	s.append(str);	追加字符串	s.append("world");	支持多种类型
​​push_back()​​	s.push_back('c');	追加单个字符	s.push_back('!');	等价于 s += 'c'
​​insert()​​	s.insert(pos, str);	在指定位置插入字符串	s.insert(2, "xx"); → "hexxllo"	位置需有效
​​erase()​​	s.erase(pos, len);	删除从 pos 开始的 len 个字符	s.erase(1, 2); → "hlo"	默认删到结尾
​​replace()​​	s.replace(pos, len, str);	替换部分内容	s.replace(0, 2, "HE"); → "HEllo"	长度可动态调整
​​clear()​​	s.clear();	清空字符串	s.clear(); → s.empty() 为 true	容量可能保留
​​swap()​​	s1.swap(s2);	交换两个字符串的内容	s1.swap(s2);	高效（O(1)）

---

​​4.查找与子字符串​​

操作	函数/语法	描述	示例	注意事项
​​find()​​	s.find(str, pos);	查找子字符串首次出现的位置	s.find("ll"); → 2	未找到返回 string::npos
​​rfind()​​	s.rfind(str, pos);	查找子字符串最后一次出现的位置	s.rfind("l"); → 3	反向搜索
​​find_first_of()​​	s.find_first_of(chars);	查找字符集中任意字符首次出现的位置	s.find_first_of("aeiou"); → 1	匹配集合
​​substr()​​	s.substr(pos, len);	提取子字符串	s.substr(1, 3); → "ell"	默认到结尾

---

​​5.容量操作​​

操作	函数/语法	描述	示例	注意事项
​​size() / length()​​	s.size();	返回字符数量	int len = s.size();	两者等价
​​empty()​​	s.empty();	判断是否为空	if (s.empty()) {...}	等价于 size() == 0
​​resize()​​	s.resize(n, 'c');	调整字符串长度	s.resize(10, 'x'); → "helloxxxxx"	默认填充 \0
​​capacity()​​	s.capacity();	返回当前分配的内存容量	int cap = s.capacity();	通常 ≥ size()
​​reserve()​​	s.reserve(n);	预分配内存（避免重复扩容）	s.reserve(100);	不影响 size()
​​shrink_to_fit()​​ (C++11)	s.shrink_to_fit();	释放多余内存	s.shrink_to_fit();	容量可能减少

---

​​6.比较与连接​​

操作	函数/语法	描述	示例	注意事项
​​比较操作符​​	==, !=, <, >, etc.	按字典序比较字符串	if (s1 < s2) {...}	区分大小写
​​compare()​​	s.compare(str);	返回字典序比较结果	s.compare("apple"); → 正数/负数/0	类似 strcmp
​​连接操作符​​	s1 + s2;	连接两个字符串	string s3 = s1 + s2;	生成新对象
​​+= 操作符​​	s1 += s2;	追加内容到字符串	s1 += "world";	直接修改原字符串

---

​​7.其他操作​​

操作	函数/语法	描述	示例	注意事项
​​迭代器访问​​	s.begin(), s.end()	获取迭代器	for (auto it = s.begin(); it != s.end(); ++it) {...}	支持范围 for 循环
​​数值转换​​ (C++11)	stoi(), to_string()	字符串与数值互转	int num = stoi("123");

题3--最长连续序列

自己想的方法，没有达到n复杂度，在n到n方之间，能通过74/81

class Solution {
public:int longestConsecutive(vector<int>& nums) {//题目要求的是n的复杂度，也就是说在遍历一遍或者几遍数组后就应该得出答案//一开始的思路是像前几道哈希表一样，依次遍历每个数，然后看这个数的前一个数和后一个//在不在哈希表里，但是涉及到一个问题，比如 1 2 3 4 0，遍历到2的时候可以去更新1的值，遍历到4的时候还能去更新1吗，这样复杂度就说n方了//n复杂度不代表遍历一次数组就得出答案，遍历几次也行//直接先将所有数放入哈希表，且全部为1（此时没有重复）//然后遍历哈希表，只判断这个数的前一个数在不在，然后更新这个数的值，每个数更新后的值代表以这个数结尾的连续序列的长度//此时还有一个问题，就是哈希表里是乱序，所以，你便利到当前这个值，你的值取决于你上一个数的值，但是你要去判断，你下一个数的值可能在之前你还没变的时候就变了//此时要一直往前判断，不过没关系，这是有限次的，复杂度还是n
unordered_map<int,int> m;for(int i=0;i<nums.size();++i)m[nums[i]]=1;for(auto t:m)
{
int a=t.first;if(m.find(a-1)!=m.end())m[a]=m[a-1]+1;
while(m.find(a+1)!=m.end())
{if(m[a+1]<=m[a]&&m[a+1]!=1){m[a+1]=m[a]+1;++a;}else{break;//如果存在且没有被错误更新就直接break，如果没有这一步就全错了，所以有if一定要考虑else}
}}int u=0;
for(auto t:m)
{
u=max(u,t.second);}return u;}
};

官方题解：

class Solution {
public:int longestConsecutive(vector<int>& nums) {
//每个数都判断一次这个数是不是连续序列的开头那个数。
// 怎么判断呢，就是用哈希表查找这个数前面一个数是否存在，即num-1在序列中是否存在。存在那这个数肯定不是开头，直接跳过。
// 因此只需要对每个开头的数进行循环，直到这个序列不再连续，因此复杂度是O(n)。
// 以题解中的序列举例:
// [100，4，200，1，3，4，2]
// 去重后的哈希序列为：
// [100，4，200，1，3，2]
// 按照上面逻辑进行判断：
// 元素100是开头,因为没有99，且以100开头的序列长度为1
// 元素4不是开头，因为有3存在，过，
// 元素200是开头，因为没有199，且以200开头的序列长度为1
// 元素1是开头，因为没有0，且以1开头的序列长度为4，因为依次累加，2，3，4都存在。
// 元素3不是开头，因为2存在，过，
// 元素2不是开头，因为1存在，过。//只需要一个setunordered_set<int> s;for(int i=0;i<nums.size();++i) s.insert(nums[i]);int v=0;
for(auto t:s)
{if(!s.count(t-1)) {int u=1;int a=t;while(s.count(a+1)){++u;a++;}v=max(v,u);}}return v;}
};

题4---移动0

挺简单的题，唯一问题是需要注意语法，也就是数组越界问题，访问数组严格不能越界

  while(j<n&&nums[j]==0)

  {

    ++j;

    }

必须保证访问nums[j]的时候j一定没越界，否则直接全错

class Solution {
public:void moveZeroes(vector<int>& nums) {//我的想法是双指针，一个找0，一个找非0（最左边的）
//从第一个0的位置开始，j找到右边第一个数字，然后和这个0交换，i往右边遍历继续找第一个0
//此时第一个0的位置一定在j上或者j前面，然后j往后走继续找数字，这样就能保证两个指针都是往后走
//数字的顺序不会变
int n=nums.size();
int i=0;
while(i<n&&nums[i]!=0)++i;
if(i>=n)return;int j=i;while(j<n)
{while(j<n&&nums[j]==0){++j;} if(j>=n)return ;swap(nums[i],nums[j]);while(i<n&&nums[i]!=0)++i;}}
};

题5--盛最多水的容器

本质上是贪心，所以比较难解释

最大水量=Math.min(height[left],height[right])*长度，往中间移动长度一定会变短

如果移动高的那一边，会有两种情况：

1、下一根柱子的高度比现在高，高度还取最小值低的那边，最大水量比原来小

2、下一根柱子的高度比现在低，高度比原来的最小值还小，最大水量比原来小

如果移动低的那一边，会有两种情况：

1、下一根柱子的高度比现在高，高度就可以取更高的值，最大水量不一定比原来小

2、下一根柱子的高度比现在低，高度比原来的最小值还小，最大水量比原来小

class Solution {
public:int maxArea(vector<int>& height) {//对于左边界，右边的比他矮的垂线都可以排除，无法威胁到他
//对于右边界，左边比他矮的也可以排除
//如果暴力，复杂度是n方
//题解思路
//答案来自于两个边界里，长度最短的一个垂线和这两个边界的距离
//所以如何确定左右边界呢，一开始我们让左右边界的距离最大
//这个时候决定因素就是短的那一边，此时移动长的那一边毫无意义，只有移动短的才可能得到更大的值
//相当于是一开始我选择最大边界，在这个基础上，我朝着可能变得更大的方向上探索int i=0,j=height.size()-1;
int m=(j-i)*min(height[i],height[j]);while(i<j)
{
if(height[i]<height[j])i++;
else j--;m=max(m,(j-i)*min(height[i],height[j]));}return m;}
};

题6--三数之和

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//为了不重复，我们可以先将数组排序//我们需要在排序后的数组中选出三个数字，满足相加为0//此时还有重复的可能，比如数组为0 0 0 0//所以在for循环时，无论是外层循环还是内层循环，下一个数如果和上一个相等就跳过//不需要三层for循环，当第一个数确定时，剩下两个数因为数组已经排好序，相当于//在有序数组里求两数之和，由于第一个数从前往后遍历，所以不会重复，列举出的数列都是递增数列sort(nums.begin(),nums.end());vector<vector<int>> v;for(int i=0;i<nums.size()-2;i++){if(i>=1&&nums[i]==nums[i-1]) continue;int k=nums.size()-1;for(int j=i+1;j<nums.size()-1;j++){    if(j>=i+2&&nums[j]==nums[j-1])continue ;while(k>j&&nums[j]+nums[k]>(0-nums[i]))k--;if(k>j&&nums[j]+nums[k]==(0-nums[i])){v.push_back({nums[i],nums[j],nums[k]});}}}return v;}
};

官方题解：

差不多，但有break 很重要的是if里要一直判断 j<k

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//为了不重复，我们可以先将数组排序//我们需要在排序后的数组中选出三个数字，满足相加为0//此时还有重复的可能，比如数组为0 0 0 0//所以在for循环时，无论是外层循环还是内层循环，下一个数如果和上一个相等就跳过//不需要三层for循环，当第一个数确定时，剩下两个数因为数组已经排好序，相当于//在有序数组里求两数之和，由于第一个数从前往后遍历，所以不会重复，列举出的数列都是递增数列sort(nums.begin(),nums.end());vector<vector<int>> v;for(int i=0;i<nums.size()-2;++i){if(i>0&&nums[i]==nums[i-1]) continue;int k=nums.size()-1;for(int j=i+1;j<nums.size()-1;++j){    if(j>i+1&&nums[j]==nums[j-1])continue ;while(k>j&&nums[j]+nums[k]>(0-nums[i]))--k;if(j==k)break;if(k>j&&nums[j]+nums[k]==(0-nums[i])){v.push_back({nums[i],nums[j],nums[k]});}}}return v;}
};

题7--接雨水

困难题，先跳过

详解滑动窗口

首先复习一下滑动窗口（滑动窗口最大值那道题本质上不是个滑动窗口的题目）

题目列表：算法思想总结：滑动窗口算法_滑窗算法-CSDN博客

视频（讲的非常好）：【掌握滑动窗口本质，秒杀相关题型】https://www.bilibili.com/video/BV1GAV7zHEWD?vd_source=5ee68676a0e9e18690592f6c4e3cff49

本质就是边遍历边剪枝

​

也就是说，对于一个数组或者一个串，我们如果暴力枚举，需要依次遍历所有字串，然后再判断满不满足条件，这个复杂度大约在三次方

对于一个长度为7的串，所有子串如下

​

我们不必遍历所有子串然后判断，可以边遍历边剪枝，具体来说就是

​

以上题为例子，当 （0，2）没有重复时，（1，2）（2，2）都没有重复（小于0，2的长度）

当（0，3）有重复时 （0，4）（0，5）（0，6）（0，7）都有重复，这些都可以不用判断

基于上面的思想，我们可以得到一个滑动窗口的模板

​

在这个模板的基础上，我们对下面几个题型进行解析

无重复字符的最长子串长度

​

长度最小的子数组

​

乘积小于k的子数组 

​

字符串中所有的字母异位词 

​

最小覆盖子串

题8--无重复字符的最长子串

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char,int> m;int ans=0;for(int right=0,left=0;right<s.size();right++){m[s[right]]++;while(m[s[right]]>1)//加入当前字母后发现哈希表中字母数大于1，说明当前字母就是重复字母{m[s[left]]--;left++;}ans=max(ans,right-left+1);}return ans;}
};

题9--找到字符串中所有的字母异位词

class Solution {
public:vector<int> findAnagrams(string s, string p) {unordered_map<char,int> m;for(auto t:p){m[t]++;}
vector<int> v;for(int right=0,left=0;right<s.size();right++){m[s[right]]--;while(m[s[right]]<0){m[s[left]]++;left++;}if(right-left+1==p.size())
{v.push_back(left);
}}return v;}
};

题10--和为k的子数组

前缀和加哈希表（两数之和）

前缀和明天抽空复习

题12--最小覆盖子串

class Solution {
public:string minWindow(string s, string t) {unordered_map<char,int> m;for(auto c:t){m[c]++;}int u=0;string ans="";int  a=s.size();int start=-1,end=-1;for(int right=0,left=0;right<s.size();right++){m[s[right]]--;if(m[s[right]]>=0){u++;}if(u==t.size()){while(u==t.size()){if(a>(right-left+1)||a==(right-left+1)){a=right-left+1;start=left;end=right;}m[s[left]]++;if(m[s[left]]>0) u--;left++;}}}if(start==-1&&end==-1) return  ans;
else return s.substr(start,end-start+1);}
};