做编程网站有哪些,seo商城,开发公司工程部经理岗位职责,厦门市建设质量安全协会网站目录 1.题目2.题解C# 解法一#xff1a;滑动窗口算法C# 解法二#xff1a;索引寻找Java 解法一#xff1a;滑动窗口算法Java 解法二#xff1a;遍历字符串 1.题目 给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 示例1:
输入: s ab… 目录 1.题目2.题解C# 解法一滑动窗口算法C# 解法二索引寻找Java 解法一滑动窗口算法Java 解法二遍历字符串 1.题目 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 示例1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。提示 每0 s.length 5 * 104s 由英文字母、数字、符号和空格组成
2.题解
C# 解法一滑动窗口算法 滑动窗口算法Sliding Window可以用来解决字符串数组的子元素问题查找满足一定条件的连续子区间可以将嵌套的循环问题转化为单循环问题降低时间复杂度。 滑动窗口算法需要用到双指针遍历字符串数组时两个指针都起始于原点并一前一后地向终点移动两个指针一前一后夹着的子串子数组就像一个窗口窗口的大小和覆盖范围会随着前后指针的移动而发生变化。 窗口该如何移动需要根据求解的问题来决定通过左右指针的移动遍历字符串数组寻找满足特定条件的连续子区间。 public class Solution {public int LengthOfLongestSubstring(string s) {HashSetchar letter new HashSetchar();// 哈希集合记录每个字符是否出现过int left 0,right 0;//初始化左右指针指向字符串首位字符int length s.Length;int count 0,max 0;//count记录每次指针移动后的子串长度while(right length){if(!letter.Contains(s[right]))//右指针字符未重复{letter.Add(s[right]);//将该字符添加进集合right;//右指针继续右移count;}else//右指针字符重复左指针开始右移直到不含重复字符即左指针移动到重复字符(左)的右边一位{ letter.Remove(s[left]);//去除集合中当前左指针字符left;//左指针右移count--;}max Math.Max(max,count);}return max;}
}C# 解法二索引寻找 历所有字符然后当碰到重复字符时存储值同时处理List进行下一队的查找。 public class Solution {
public int LengthOfLongestSubstring(string s) {Listchar ls new Listchar();int n s.Length;int intMaxLength 0;for (int i 0; i n; i){if (ls.Contains(s[i])){ls.RemoveRange(0, ls.IndexOf(s[i]) 1);}ls.Add(s[i]);intMaxLength ls.Count intMaxLength ? ls.Count : intMaxLength;}return intMaxLength;}} Java 解法一滑动窗口算法
我们不妨以示例一中的字符串 abcabcbb\texttt{abcabcbb}abcabcbb 为例找出从每一个字符开始的不包含重复字符的最长子串那么其中最长的那个字符串即为答案。对于示例一中的字符串我们列举出这些结果其中括号中表示选中的字符以及最长的字符串 以 (a)bcabcbb\texttt{(a)bcabcbb}(a)bcabcbb 开始的最长字符串为 (abc)abcbb\texttt{(abc)abcbb}(abc)abcbb以 a(b)cabcbb\texttt{a(b)cabcbb}a(b)cabcbb 开始的最长字符串为 a(bca)bcbb\texttt{a(bca)bcbb}a(bca)bcbb以 ab©abcbb\texttt{ab©abcbb}ab©abcbb 开始的最长字符串为 ab(cab)cbb\texttt{ab(cab)cbb}ab(cab)cbb以 abc(a)bcbb\texttt{abc(a)bcbb}abc(a)bcbb 开始的最长字符串为 abc(abc)bb\texttt{abc(abc)bb}abc(abc)bb以 abca(b)cbb\texttt{abca(b)cbb}abca(b)cbb 开始的最长字符串为 abca(bc)bb\texttt{abca(bc)bb}abca(bc)bb以 abcab©bb\texttt{abcab©bb}abcab©bb 开始的最长字符串为 abcab(cb)b\texttt{abcab(cb)b}abcab(cb)b以 abcabc(b)b\texttt{abcabc(b)b}abcabc(b)b 开始的最长字符串为 abcabc(b)b\texttt{abcabc(b)b}abcabc(b)b以 abcabcb(b)\texttt{abcabcb(b)}abcabcb(b) 开始的最长字符串为 abcabcb(b)\texttt{abcabcb(b)}abcabcb(b)。 这样一来我们就可以使用「滑动窗口」来解决这个问题了 我们使用两个指针表示字符串中的某个子串或窗口的左右边界其中左指针代表着上文中「枚举子串的起始位置」而右指针即为上文中的 rk;在每一步的操作中我们会将左指针向右移动一格表示 我们开始枚举下一个字符作为起始位置然后我们可以不断地向右移动右指针但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后这个子串就对应着 以左指针开始的不包含重复字符的最长子串。我们记录下这个子串的长度在枚举结束后我们找到的最长的子串的长度即为答案。 判断重复字符 在上面的流程中我们还需要使用一种数据结构来判断 是否有重复的字符常用的数据结构为哈希集合即 C 中的 std::unordered_setJava 中的 HashSetPython 中的 set, JavaScript 中的 Set。在左指针向右移动的时候我们从哈希集合中移除一个字符在右指针向右移动的时候我们往哈希集合中添加一个字符。
class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合记录每个字符是否出现过SetCharacter occ new HashSetCharacter();int n s.length();// 右指针初始值为 -1相当于我们在字符串的左边界的左侧还没有开始移动int rk -1, ans 0;for (int i 0; i n; i) {if (i ! 0) {// 左指针向右移动一格移除一个字符occ.remove(s.charAt(i - 1));}while (rk 1 n !occ.contains(s.charAt(rk 1))) {// 不断地移动右指针occ.add(s.charAt(rk 1));rk;}// 第 i 到 rk 个字符是一个极长的无重复字符子串ans Math.max(ans, rk - i 1);}return ans;}
}Java 解法二遍历字符串
遍历字符串每次以 i 值记录不回溯 i 值用flag记录遍历过程找到的重复的字符的位置。如果遇到重复字符i-flag 即为子串长度此时flag重新定位到子串中重复字符的位置i 继续往后遍历。这里length跟result记录长度
class Solution {public int lengthOfLongestSubstring(String s) {int i 0;int flag 0;int length 0;int result 0;while (i s.length()) {int pos s.indexOf(s.charAt(i),flag);if (pos i) {if (length result) {result length;}if (result s.length() - pos - 1) {return result;}length i - pos - 1;flag pos 1;}length;i;}return length;}
}
