日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網(wǎng)站首頁 編程語言 正文

C#算法之無重復字符的最長子串_C#教程

作者：癡者工良 ? 更新時間： 2022-03-29 編程語言

題目

給定一個字符串，請你找出其中不含有重復字符的?最長子串?的長度。

示例 1:

輸入: "abcabcbb"
輸出: 3?
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。

示例 2:

輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。

示例 3:

輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。

要注意字符串為空、變量為null、字符串長度 Length = 1 等情況。

測試實例

輸入
" "
"au"
"abcabcbb"
"bbbbb"
"pwwkew"
"aab"

預期結(jié)果分別是 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();      //字符串轉(zhuǎn)為字符數(shù)組
            int start = 0;                   //區(qū)間開始位置
            int stop = 0;                    //區(qū)間結(jié)束位置
            int newMax = 1;                   //當前區(qū)間數(shù)
            int max = 1;                     //區(qū)間最大個數(shù)

            for (stop = 1; stop < a.Length; stop++)   //每次向后移動一位
            {
                bool b = false;                       //是否存在重復
                for (int i = start; i < stop; i++)  //檢查當前元素在區(qū)間是否有相同值
                {
                    if (a[stop] == a[i])        //如果stop+1位在區(qū)間找到相同的字符
                    {
                        char ls = a[stop];
                        if (newMax > max) max = newMax;
                        start = i + 1;              //區(qū)間開始位置重置
                        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();      //字符串轉(zhuǎn)為字符數(shù)組
            int start = 0;                   //區(qū)間開始位置
            int stop = 0;                    //區(qū)間結(jié)束位置
            int newMax = 1;                   //當前區(qū)間數(shù)
            int max = 1;                     //區(qū)間最大個數(shù)

            for (stop = 1; stop < a.Length; stop++)   //每次向后移動一位
            {
                bool b = false;                       //是否存在重復
                for (int i = start; i < stop; i++)  //檢查當前元素在區(qū)間是否有相同值
                {
                    if (a[stop] == a[i])        //如果stop+1位在區(qū)間找到相同的字符
                    {
                        char ls = a[stop];
                        if (newMax > max) max = newMax;
                        start = i + 1;              //區(qū)間開始位置重置
                        newMax = stop - start + 1;      //重新設(shè)置區(qū)間數(shù)
                        b = true;            
                        break;
                    }
                }
                if (b == false)             ////沒有重新設(shè)置區(qū)間數(shù)時加1
                    newMax += 1;
            }
            if (newMax > max) max = newMax;
            return max;
        }
    }
    class Program
    {


        static void Main(string[] args)
        {
            Testa t1 = new Testa();                                     //正確結(jié)果
            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區(qū)間起點，stop區(qū)間終點
            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區(qū)間起點，stop區(qū)間終點
            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();                                     //正確結(jié)果
            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();
        }
    }
}

原文鏈接：https://www.cnblogs.com/whuanle/p/10342416.html

欄目分類
最近更新