C#算法之无重复字符的最长子串
程序员文章站
2022-03-08 16:31:51
题目给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。示例 1:输入: "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc",...
题目
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
要注意字符串为空、变量为null、字符串长度 length = 1 等情况。
测试实例
输入 " " "au" "abcabcbb" "bbbbb" "pwwkew" "aab" 预期结果分别是 1,2,3,1,3,2
代码格式模板
public class solution { public int lengthoflongestsubstring(string s) { } }
笔者的代码仅供参考
使用最笨的方式,200ms左右
public class solution { public int lengthoflongestsubstring(string s) { if (s == null || s == "") return 0; char[] a = s.tochararray(); //字符串转为字符数组 int start = 0; //区间开始位置 int stop = 0; //区间结束位置 int newmax = 1; //当前区间数 int max = 1; //区间最大个数 for (stop = 1; stop < a.length; stop++) //每次向后移动一位 { bool b = false; //是否存在重复 for (int i = start; i < stop; i++) //检查当前元素在区间是否有相同值 { if (a[stop] == a[i]) //如果stop+1位在区间找到相同的字符 { char ls = a[stop]; if (newmax > max) max = newmax; start = i + 1; //区间开始位置重置 newmax = stop - start + 1; b = true; break; } } if (b == false) newmax += 1; } if (newmax > max) max = newmax; return max; } }
完整测试代码(控制台)
using system; namespace consoleapp1 { public class testa { public int lengthoflongestsubstring(string s) { if (s == null || s == "") return 0; char[] a = s.tochararray(); //字符串转为字符数组 int start = 0; //区间开始位置 int stop = 0; //区间结束位置 int newmax = 1; //当前区间数 int max = 1; //区间最大个数 for (stop = 1; stop < a.length; stop++) //每次向后移动一位 { bool b = false; //是否存在重复 for (int i = start; i < stop; i++) //检查当前元素在区间是否有相同值 { if (a[stop] == a[i]) //如果stop+1位在区间找到相同的字符 { char ls = a[stop]; if (newmax > max) max = newmax; start = i + 1; //区间开始位置重置 newmax = stop - start + 1; //重新设置区间数 b = true; break; } } if (b == false) ////没有重新设置区间数时加1 newmax += 1; } if (newmax > max) max = newmax; return max; } } class program { static void main(string[] args) { testa t1 = new testa(); //正确结果 console.writeline(t1.lengthoflongestsubstring(" ")); //1 console.writeline(t1.lengthoflongestsubstring("au")); //2 console.writeline(t1.lengthoflongestsubstring("abcabcbb")); //3 console.writeline(t1.lengthoflongestsubstring("bbbbb")); //1 console.writeline(t1.lengthoflongestsubstring("pwwkew")); //3 console.writeline(t1.lengthoflongestsubstring("aab")); //2 console.readkey(); } } }
使用哈希集合,速度更快,100ms-150ms
public int lengthoflongestsubstring(string s) { int n = s.length; hashset<char> set = new hashset<char>(); //集合 int ans = 0, start = 0, stop = 0; //ans为字符串长度,starp区间起点,stop区间终点 while (start < n && stop < n) { // try to extend the range [i, j] if (!set.contains(s[stop])) { set.add(s[stop++]); ans = math.max(ans, stop - start); //或者ans = ans > (stop - start) ? ans : (stop - start) } else { set.remove(s[start++]); } } return ans; }
完整控制台测试代码
using system; using system.collections.generic; using system.linq; namespace consoleapp2 { public class solution { public int lengthoflongestsubstring(string s) { int n = s.length; hashset<char> set = new hashset<char>(); //集合 int ans = 0, start = 0, stop = 0; //ans为字符串长度,starp区间起点,stop区间终点 while (start < n && stop < n) { // try to extend the range [i, j] if (!set.contains(s[stop])) { set.add(s[stop++]); ans = math.max(ans, stop - start); //或者ans = ans > (stop - start) ? ans : (stop - start) } else { set.remove(s[start++]); } } return ans; } } class program { static void main(string[] args) { solution t1 = new solution(); //正确结果 console.writeline(t1.lengthoflongestsubstring(" ")); //1 console.writeline(t1.lengthoflongestsubstring("au")); //2 console.writeline(t1.lengthoflongestsubstring("abcabcbb")); //3 console.writeline(t1.lengthoflongestsubstring("bbbbb")); //1 console.writeline(t1.lengthoflongestsubstring("pwwkew")); //3 console.writeline(t1.lengthoflongestsubstring("aab")); //2 console.readkey(); } } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。