如何更改网站内链网站排名消失

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

如何更改网站内链,网站排名消失,景观石网站建设方案,滨州网站建设 中企动力链接无重复字符的最长子串题序号3类型字符串解题方法滑动窗口难度中等 题目 给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”#xff0c;所以其长度为 3。 …链接无重复字符的最长子串题序号3类型字符串解题方法滑动窗口难度中等 题目 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2: 输入: s “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例 3: 输入: s “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。 提示 0 s.length 5 * 104 s 由英文字母、数字、符号和空格组成 解题 核心要点这个问题可以通过滑动窗口的方法来解决。滑动窗口表示当前考虑的子串的范围我们通过移动窗口的边界来找到不含有重复字符的最长子串。 初始化定义两个指针 left 和 right 分别表示窗口的左右边界以及一个哈希表 char_index_map 来存储字符及其索引。扩展窗口将 right 指针向右移动扩展窗口直到遇到重复的字符。更新最大长度在每次移动 right 指针时更新不含有重复字符的子串的最大长度。收缩窗口当遇到重复的字符时移动 left 指针收缩窗口直到重复的字符被移出窗口。重复步骤2-4直到 right 指针到达字符串的末尾。 时间复杂度 O(n) 空间复杂度O(n) c 实现算法
class Solution { public:int lengthOfLongestSubstring(string s) {unordered_mapchar, int map; // 哈希表记录字符的最新索引map 的键是字符值是该字符的最后出现的索引位置int max_len 0; // 最长子串长度int left 0; // 滑动窗口的左边界for (int right 0; right s.size(); right) {// 如果当前字符在窗口内出现过更新窗口的左边界//如果 map.find(s[right]) 返回的不是 map.end()意味着哈希表中存在字符 s[right]//也就是说字符 s[right] 在哈希表中出现过。//如果返回 map.end()则说明哈希表中没有这个字符即字符 s[right] 没有在哈希表中出现过。//map[s[right]] left字符 s[right] 在窗口中的 上一次出现的位置 //大于等于当前窗口的左边界 left那么就说明它是重复的。if (map.find(s[right]) ! map.end() map[s[right]] left) {//将 left 更新为字符 s[right] 最新出现位置的下一个位置left map[s[right]] 1;}// 更新当前字符的最新位置map[s[right]] right;// 计算当前窗口的大小更新最大长度max_len max(max_len, right - left 1);}return max_len;} };演示以示例1为例 遍历字符串 sright 从 0 到 7 right 0字符 ‘a’ map.find(s[right]) ! map.end() 检查字符 ‘a’ 是否已经出现过。由于 map 为空所以字符 ‘a’ 不在其中。 更新哈希表map[‘a’] 0。字符 ‘a’ 的最新索引是 0。计算当前窗口大小right - left 1 0 - 0 1 1。 更新 max_lenmax_len max(0,1) 1。 right 1字符 ‘b’ map.find(s[right]) ! map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 不在哈希表中。 更新哈希表map[‘b’] 1。字符 ‘b’ 的最新索引是 1。计算当前窗口大小right - left 1 1 - 0 1 2。 更新 max_lenmax_len max(1, 2) 2。 right 2字符 ‘c’ map.find(s[right]) ! map.end() 检查字符 ‘c’ 是否已经出现过。字符 ‘c’ 不在哈希表中。 更新哈希表map[‘c’] 2。字符 ‘c’ 的最新索引是 2。计算当前窗口大小right - left 1 2 - 0 1 3。 更新 max_lenmax_len max(2, 3) 3。 right 3字符 ‘a’ map.find(s[right]) ! map.end() 检查字符 ‘a’ 是否已经出现过。字符 ‘a’ 已经在 map 中且它的索引是 0小于 right 3。 由于 ‘a’ 重复了我们需要更新滑动窗口的左边界 left map[‘a’] 1 0 1 1新的左边界是 1即跳过 a 在左边的位置。 更新哈希表map[‘a’] 3。字符 ‘a’ 的最新索引是 3。 计算当前窗口大小right - left 1 3 - 1 1 3。 max_len 仍然是 3不更新。 right 4字符 ‘b’ map.find(s[right]) ! map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 已经在 map 中且它的索引是 1小于 right 4。 由于 ‘b’ 重复了我们需要更新滑动窗口的左边界 left map[‘b’] 1 1 1 2新的左边界是 2即跳过 b 在左边的位置。 更新哈希表map[‘b’] 4。字符 ‘b’ 的最新索引是 4。 计算当前窗口大小right - left 1 4 - 2 1 3。 max_len 仍然是 3不更新。 right 5字符 ‘c’ map.find(s[right]) ! map.end() 检查字符 ‘c’ 是否已经出现过。字符 ‘c’ 已经在 map 中且它的索引是 2小于 right 5。 由于 ‘c’ 重复了我们需要更新滑动窗口的左边界 left map[‘c’] 1 2 1 3新的左边界是 3即跳过 c 在左边的位置。 更新哈希表map[‘c’] 5。字符 ‘c’ 的最新索引是 5。 计算当前窗口大小right - left 1 5 - 3 1 3。 max_len 仍然是 3不更新。 right 6字符 ‘b’ map.find(s[right]) ! map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 已经在 map 中且它的索引是 4小于 right 6。 由于 ‘b’ 重复了我们需要更新滑动窗口的左边界 left map[‘b’] 1 4 1 5新的左边界是 5即跳过 b在左边的位置。 更新哈希表map[‘b’] 6。字符 ‘b’ 的最新索引是 6。 计算当前窗口大小right - left 1 6 - 5 1 2。 max_len 仍然是 3不更新。 right 7字符 ‘b’ map.find(s[right]) ! map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 已经在 map 中且它的索引是 6小于 right 7。 由于 b’重复了我们需要更新滑动窗口的左边界 left map[‘b’] 1 6 1 7新的左边界是 7即跳过 b 在左边的位置。 更新哈希表map[‘b’] 7。字符 ‘b’ 的最新索引是 7。 计算当前窗口大小right - left 1 7 - 7 1 1。 max_len 仍然是 3不更新。 c demo #include iostream #include unordered_map #include algorithm using namespace std;class Solution { public:int lengthOfLongestSubstring(string s) {unordered_mapchar, int map; // 哈希表记录字符的最新索引map 的键是字符值是该字符的最后出现的索引位置int max_len 0; // 最长子串长度int left 0; // 滑动窗口的左边界for (int right 0; right s.size(); right) {// 如果当前字符在窗口内出现过更新窗口的左边界//如果 map.find(s[right]) 返回的不是 map.end()意味着哈希表中存在字符 s[right]//也就是说字符 s[right] 在哈希表中出现过。//如果返回 map.end()则说明哈希表中没有这个字符即字符 s[right] 没有在哈希表中出现过。//map[s[right]] left字符 s[right] 在窗口中的 上一次出现的位置 //大于等于当前窗口的左边界 left那么就说明它是重复的。if (map.find(s[right]) ! map.end() map[s[right]] left) {//将 left 更新为字符 s[right] 最新出现位置的下一个位置left map[s[right]] 1;}// 更新当前字符的最新位置map[s[right]] right;// 计算当前窗口的大小更新最大长度max_len max(max_len, right - left 1);}return max_len;} };int main() {Solution sol;string s abcabcbb;cout The length of the longest substring without repeating characters is: sol.lengthOfLongestSubstring(s) endl;return 0; }