欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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();
        }
    }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。