C#算法之無(wú)重復(fù)字符的最長(zhǎng)子串
更新時(shí)間：2022年01月14日 10:46:04 作者：癡者工良
這篇文章介紹了C#算法之無(wú)重復(fù)字符的最長(zhǎng)子串，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
題目
給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。
要注意字符串為空、變量為null、字符串長(zhǎng)度 Length = 1 等情況。
測(cè)試實(shí)例
輸入 " " "au" "abcabcbb" "bbbbb" "pwwkew" "aab" 預(yù)期結(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ū)間開(kāi)始位置
int stop = 0; //區(qū)間結(jié)束位置
int newMax = 1; //當(dāng)前區(qū)間數(shù)
int max = 1; //區(qū)間最大個(gè)數(shù)
for (stop = 1; stop < a.Length; stop++) //每次向后移動(dòng)一位
{
bool b = false; //是否存在重復(fù)
for (int i = start; i < stop; i++) //檢查當(dāng)前元素在區(qū)間是否有相同值
{
if (a[stop] == a[i]) //如果stop+1位在區(qū)間找到相同的字符
{
char ls = a[stop];
if (newMax > max) max = newMax;
start = i + 1; //區(qū)間開(kāi)始位置重置
newMax = stop - start + 1;
b = true;
break;
}
}
if (b == false)
newMax += 1;
}
if (newMax > max) max = newMax;
return max;
}
}完整測(cè)試代碼(控制臺(tái))
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ū)間開(kāi)始位置
int stop = 0; //區(qū)間結(jié)束位置
int newMax = 1; //當(dāng)前區(qū)間數(shù)
int max = 1; //區(qū)間最大個(gè)數(shù)
for (stop = 1; stop < a.Length; stop++) //每次向后移動(dòng)一位
{
bool b = false; //是否存在重復(fù)
for (int i = start; i < stop; i++) //檢查當(dāng)前元素在區(qū)間是否有相同值
{
if (a[stop] == a[i]) //如果stop+1位在區(qū)間找到相同的字符
{
char ls = a[stop];
if (newMax > max) max = newMax;
start = i + 1; //區(qū)間開(kāi)始位置重置
newMax = stop - start + 1; //重新設(shè)置區(qū)間數(shù)
b = true;
break;
}
}
if (b == false) ////沒(méi)有重新設(shè)置區(qū)間數(shù)時(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為字符串長(zhǎng)度，starp區(qū)間起點(diǎn)，stop區(qū)間終點(diǎn)
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;
}完整控制臺(tái)測(cè)試代碼
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為字符串長(zhǎng)度，starp區(qū)間起點(diǎn)，stop區(qū)間終點(diǎn)
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();
}
}
}以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要為大家分享了C#圖片處理類(lèi)的相關(guān)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-06-06
state傾向于condition，是一種延續(xù)性的狀態(tài)。status常用于描述一個(gè)過(guò)程中的某階段（phase），類(lèi)似于C語(yǔ)言中枚舉型變量某一個(gè)固定的值，這個(gè)值屬于一個(gè)已知的集合。這篇文章主要介紹了英語(yǔ)單詞state與status的區(qū)別,需要的朋友可以參考下2016-11-11
這篇文章主要介紹了C#7中Tuple特性的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，相信對(duì)大家具有一定的參考價(jià)值，需要的朋友可以們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2017-03-03
在C#中可以對(duì)整型運(yùn)算對(duì)象按位進(jìn)行邏輯運(yùn)算。按位進(jìn)行邏輯運(yùn)算的意義是：依次取被運(yùn)算對(duì)象的每個(gè)位，進(jìn)行邏輯運(yùn)算，每個(gè)位的邏輯運(yùn)算結(jié)果是結(jié)果值的每個(gè)位。2008-10-10
C# OpenCvSharp實(shí)現(xiàn)去除文字中的線(xiàn)條
這篇文章主要為大家詳細(xì)介紹了C#如何使用OpenCvSharp實(shí)現(xiàn)去除文字中的線(xiàn)條效果,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-11-11
在WPF（Windows Presentation Foundation）中,值轉(zhuǎn)換器（Value Converter）是一種機(jī)制,允許你在綁定時(shí)轉(zhuǎn)換綁定源和綁定目標(biāo)之間的值,本文給大家介紹了WPF中值轉(zhuǎn)換器的使用方法,需要的朋友可以參考下2024-02-02
這篇文章主要給大家介紹了C#中的let字句，文中通過(guò)應(yīng)用實(shí)例介紹的很詳細(xì)，相信對(duì)大家具有一定的參考價(jià)值，有需要的朋友們下面來(lái)一起看看吧。2017-02-02
C#獲取系統(tǒng)當(dāng)前IE版本號(hào)
這篇文章主要為大家詳細(xì)介紹了C#獲取系統(tǒng)當(dāng)前IE版本號(hào)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-12-12
C#使用迭代法實(shí)現(xiàn)Fibnaci數(shù)列
這篇文章主要介紹了C#使用迭代法實(shí)現(xiàn)Fibnaci數(shù)列的方法,較為詳細(xì)的分析了Fibnaci數(shù)列的原理與迭代法實(shí)現(xiàn)技巧,需要的朋友可以參考下2015-05-05
C#實(shí)現(xiàn)的JS操作類(lèi)實(shí)例
這篇文章主要介紹了C#實(shí)現(xiàn)的JS操作類(lèi),封裝了C#關(guān)于javascript的彈出對(duì)話(huà)框、返回上一頁(yè)、跳轉(zhuǎn)等常用操作,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-03-03