当前位置: 首页 > news >正文

违反建设投诉网站举报新十条优化措施

违反建设投诉网站举报,新十条优化措施,51ppt模板网免费,摄影公司作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 数据范围…

作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

题目描述:

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

数据范围:

 s.length≤40000 s.length≤40000

示例:

输入:

"abcabcbb"

返回值:

3

说明:

因为无重复字符的最长子串是"abc",所以其长度为 3。 

解题思路:

本题是动态规划的经典题目。有两个解题思路。

思路一:滑动窗口

  1. 设计一个滑动窗口,窗口的右边界先行,用哈希表统计字符出现次数。
  2. 当出现重复字符时,左边界出发缩小窗口直到重复字符消失。
  3. 持续刷新最值就可以了。

思路二:动态规划

  1. 用哈希表存放字符上次出现的位置下标;用长度比字符串大1的vector,存放截止到第i个字符时,能继续维持的子串长度,比如v[0]=0,v[1]=1,v[2]可能为1可能为2。
  2. 执行遍历。用哈希表判断当前字符是否为重复字符,如果不是重复字符,那就在前面子串长度基础上加1;若出现了重复字符,则该字符与其重复字符的距离为i-m[s[i]],但如果两者之间有别的重复字符,则需要考虑此类情况,可以认为在其重复字符之后的子串中,该字符未出现过,则有v[i]+1;所以,比较v[i]+1和i-m[s[i]]谁小取谁,因为小的子串没断开,后续可以继续连接,而断开的子串虽然长度大,但不可以继续增加了。
  3. 持续更新字符最新下标以及子串长度最大值。

测试代码:

思路一:滑动窗口

class Solution {
public:// 最长子串int lengthOfLongestSubstring(string s) {// 定义哈希表unordered_map<char, int> m;// 滑动窗口遍历int result = 0;for(int left = 0, right = 0; right < s.length(); ++right){// 窗口右边界先行,统计字符出现次数m[s[right]]++;// 当出现重复字符,窗口左边界右移缩小窗口直到重复字符消失while(m[s[right]] > 1){m[s[left]]--;left++;}// 持续刷新子串最大长度result = max(result, right - left + 1);}return result;}
};

思路二:动态规划

class Solution {
public:// 最长子串int lengthOfLongestSubstring(string s) {// 定义哈希表,存放的是字符出现的位置下标unordered_map<char, int> m;int result = 0;// v[i]表示截止到i个字符时,能继续维持的子串长度// 所以v[0]=0,v[1]=1vector<int> v = vector<int>(s.length() + 1, 0);// i是字符串中字符下标for(int i = 0; i < s.length(); ++i){// 当哈希表中没发现重复字符,那就在前面最长子串长度基础上+1if(m.find(s[i]) == m.end())v[i + 1] = v[i] + 1;// 若出现了重复字符,该字符与其重复字符的距离为i-m[s[i]]// 但如果两者之间有别的重复字符,那要考虑这类情况// 可以认为在其重复字符之后的子串中,该字符未出现过,则有v[i]+1// 所以v[i]+1和i-m[s[i]]谁小,取谁,因为小的这个子串没断开elsev[i + 1] = min(v[i] + 1, i - m[s[i]]);// 刷新该字符最新下标m[s[i]] = i;// 刷新最值result = max(result, v[i + 1]);}return result;}
};

http://www.tj-hxxt.cn/news/2204.html

相关文章:

  • 网站建设模板是什么意思seo臻系统
  • 做网站时怎么选择数据库类型cilimao磁力猫在线搜索
  • 容桂网站制作代理下载百度app最新版
  • 潍坊公司做网站微信营销模式有哪些
  • 网站怎么做留言的微信指数是搜索量吗
  • 淘宝店铺怎么运营起来青岛seo博客
  • 做暧视频网站大全网页设计与网站开发
  • 大连百度关键词优化电商关键词排名优化怎么做?
  • 移动端网站开发介绍网站搜索优化排名
  • 石家庄住建局网站网络营销实训个人总结
  • 网站建设总结优化网站性能
  • 局域网建设网站工具运营推广计划怎么写
  • 个人网站制作百度seo和sem
  • 房产网站怎么做400电话怎么优化网络
  • 手机版网站与app关键词排名怎么做好
  • 网站app 开发深圳百度推广属于哪家公司
  • wordpress 优势沈阳seo博客
  • 现在什么网站做基础销量好黑帽seo联系方式
  • 做按摩网站优化推广上海百度推广开户
  • 做房产的网站nba最新新闻消息
  • 建设银行信用卡管理中心网站如何设计企业网站
  • 附近装修设计公司人教版优化设计电子书
  • 政务公开网站建设工作情况汇报企业营销管理
  • wordpress整站源码绍兴seo排名收费
  • 大连seo交流群seo学徒招聘
  • 快速搭建个人网站seo网站推广杭州
  • 文化集团网站模板志鸿优化设计答案网
  • 网站开发前端和后端哪个费时间百度网页游戏
  • 暗网网站建设友情链接翻译
  • 淘宝网站怎么做视频教程百度搜图