C#算法之無重復字符的最長子串
更新時間：2022年01月14日 10:46:04 作者：癡者工良
這篇文章介紹了C#算法之無重復字符的最長子串，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
題目
給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。
示例 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; //區(qū)間開始位置
int stop = 0; //區(qū)間結束位置
int newMax = 1; //當前區(qū)間數
int max = 1; //區(qū)間最大個數
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(); //字符串轉為字符數組
int start = 0; //區(qū)間開始位置
int stop = 0; //區(qū)間結束位置
int newMax = 1; //當前區(qū)間數
int max = 1; //區(qū)間最大個數
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; //重新設置區(qū)間數
b = true;
break;
}
}
if (b == false) ////沒有重新設置區(qū)間數時加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區(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(); //正確結果
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();
}
}
}以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要為大家分享了C#圖片處理類的相關代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-06-06
state傾向于condition，是一種延續(xù)性的狀態(tài)。status常用于描述一個過程中的某階段（phase），類似于C語言中枚舉型變量某一個固定的值，這個值屬于一個已知的集合。這篇文章主要介紹了英語單詞state與status的區(qū)別,需要的朋友可以參考下2016-11-11
這篇文章主要介紹了C#7中Tuple特性的相關資料，文中通過示例代碼介紹的非常詳細，相信對大家具有一定的參考價值，需要的朋友可以們下面來一起學習學習吧。2017-03-03
在C#中可以對整型運算對象按位進行邏輯運算。按位進行邏輯運算的意義是：依次取被運算對象的每個位，進行邏輯運算，每個位的邏輯運算結果是結果值的每個位。2008-10-10
C# OpenCvSharp實現(xiàn)去除文字中的線條
這篇文章主要為大家詳細介紹了C#如何使用OpenCvSharp實現(xiàn)去除文字中的線條效果,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2023-11-11
在WPF（Windows Presentation Foundation）中,值轉換器（Value Converter）是一種機制,允許你在綁定時轉換綁定源和綁定目標之間的值,本文給大家介紹了WPF中值轉換器的使用方法,需要的朋友可以參考下2024-02-02
這篇文章主要給大家介紹了C#中的let字句，文中通過應用實例介紹的很詳細，相信對大家具有一定的參考價值，有需要的朋友們下面來一起看看吧。2017-02-02
這篇文章主要為大家詳細介紹了C#獲取系統(tǒng)當前IE版本號，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-12-12
這篇文章主要介紹了C#使用迭代法實現(xiàn)Fibnaci數列的方法,較為詳細的分析了Fibnaci數列的原理與迭代法實現(xiàn)技巧,需要的朋友可以參考下2015-05-05
這篇文章主要介紹了C#實現(xiàn)的JS操作類,封裝了C#關于javascript的彈出對話框、返回上一頁、跳轉等常用操作,非常具有實用價值,需要的朋友可以參考下2015-03-03