当前位置: 首页> 房产> 建材 > ppt模板在哪里找_徐州模板建站系统_宁波企业seo服务_杭州小周seo

ppt模板在哪里找_徐州模板建站系统_宁波企业seo服务_杭州小周seo

时间:2025/7/11 1:10:58来源:https://blog.csdn.net/qq_41882808/article/details/124879158 浏览次数:0次
ppt模板在哪里找_徐州模板建站系统_宁波企业seo服务_杭州小周seo

滑动窗口思想

题目

题目链接
3. 无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

我的思路
滑动窗口+哈希
哈希使用的map

class Solution {
public:int lengthOfLongestSubstring(string s) {int n=s.size();int right=0;int left=0;int sum=0;int maxlen=0;map<char,int> mp;while(right<n){while(mp.count(s[right])==0&&right<n){mp[s[right]]++;sum++;right++;}maxlen=max(maxlen,sum);sum--;mp.erase(s[left]);left++;// right++;  这里right不应该++}return maxlen;}
};

bug点:

  1. while循环内没有判断right<n,则最后两个字符没办法判断
  2. 什么时候right++?当左边界left增加时,即滑动窗口缩小时,right不变;right只在满足题目条件时增加
  3. 注意maxlen的最大值不是INT_MAX,而是0

冗余
4. 哈希表如何构造?使用map只使用了map的“唯一”关键字的性质,后面的int没有用到; sum的设置冗余可以换成 max(maxlen, right-left)
5. 左指针并不需要依次递增,即多了很多无谓的循环。 发现有重复字符时,可以直接把左指针移动到第一个重复字符的下一个位置即可。

精进
看的官方题解评论区,发现,每次left可以直接从下一个相同字符的下一个开始,使用map<char,int> int 记录每个字符的位置,出现相同字符则记录的是该字符出现的上一个位置,如abcdefdgh, 当遇到第二个d时left会跳到e, 因为在a-第一个d之间的连续字串的长度都比a-d小,所以这是不必要的循环,直接跳到第一个d的下一个。
abcdefagh 遇到第二个a时会跳到b

class Solution {
public:int lengthOfLongestSubstring(string s) {int n=s.size();int left=0;int maxlen=0;map<char,int> mp;for(int right=0;right<n;right++){char ch=s.at(right);  //这里没有插入呢!只是记录当前right的位置if(mp.count(ch)==1){left=max(mp[ch]+1,left); //这里max里的left记录的是上一个相同字符的位置的下一个,上一次的下一个位置,和当前的下一个位置相比较//left=right+1;  这个是当前的=相同位置的下一个//left=mp[ch]+1;   这个是上一个的下一个} maxlen=max(maxlen,right-left+1);  //不好的地方是每次都要计算一下maxlen,而不是在滑动窗口停止时计算mp[ch]=right;     //更新相同的关键字的位置,覆盖}return maxlen;}
};

官方题解:

class Solution {
public:int lengthOfLongestSubstring(string s) {// 哈希集合,记录每个字符是否出现过unordered_set<char> occ;int n = s.size();// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动int rk = -1, ans = 0;// 枚举左指针的位置,初始值隐性地表示为 -1for (int i = 0; i < n; ++i) {if (i != 0) {// 左指针向右移动一格,移除一个字符occ.erase(s[i - 1]);}while (rk + 1 < n && !occ.count(s[rk + 1])) {// 不断地移动右指针occ.insert(s[rk + 1]);++rk;}// 第 i 到 rk 个字符是一个极长的无重复字符子串ans = max(ans, rk - i + 1);}return ans;}
};作者:LeetCode-Solution
链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

知识点补充
一、map的使用

  1. 定义:
map<int ,string> mp;
  1. 赋值插入
mp.insert(pair<int, string>(1,"first"));```
mp.insert(map<int,string>::value_type(2,"second"));
mp[1]="third";
  1. 查找
    count看是否找到该关键字;
    find定位元素出现的位置,返回的时迭代器,出现时返回该位置的迭代器;没有找到,返回迭代器等于end函数返回的迭代器。
map<string,int>mp1,::iterator it;
if(mp1.count("first")==0){cout<<"not find";}//没找到该关键字,=1找到该关键字
it=mp1.find("first");
if(mp1!=mp.end()){cout<<"find success"<<it->second;}
else {cout<<"not find";}
  1. 删除
mp.erase("first");   //用关键字删除
mp.erase(mp.begin(),mp.end()) ;   //成片删除, 删除区间:前闭后开
  1. 排序
    map种元素自动按照key升序排序(从小到大);

二、unordered_set用法
unordered_set是一种关联容器,unordered_set和unordered_map是基于hashtable,是无序的。set和map内部实现是基于RB-Tree,是有序的,

  1. 定义
unordered_set<int> hash;
  1. 操作
    size() 元素个数
    empty()
    maxsize() 获取最大容量值
    find(“ggg”) 通过给定主键查找元素
    insert(“aaa”)
    erase(“aaa”)
    clear() 清空
    swap() //hash.swap(hash2)
关键字:ppt模板在哪里找_徐州模板建站系统_宁波企业seo服务_杭州小周seo

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: