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;                   //区间开始位置
            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();
        }
    }
}

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

时间: 2022-01-13

C++实现无重复字符的最长子串

目录 题目及要求: 提示: 原创代码: 代码思路: 题目及要求: 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度. 提示: 0 <= s.length <= 5 * 104 s 由英文字母.数字.符号和空格组成 原创代码: class Solution { public: int lengthOfLongestSubstring(string s) { int begin=0;//每个当前子串的开头 int end=0;//每个当前子串的末尾 int value=0;//

Python3 无重复字符的最长子串的实现

题目: 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度. 示例: 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3. 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1. 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 &quo

python3实现字符串的全排列的方法(无重复字符)

最近在学一些基础的算法,发现我的数学功底太差劲了,特别是大学的这一部分,概率论.线性代数.高数等等,这些大学学的我是忘得一干二净(我当时学的时候也不见得真的懂),导致现在学习算法,非常的吃力.唉!不说了,补习中... 抛出问题 求任意一个字符串的全排列组合,例如a='123',输出 123,132,213,231,312,321.(暂时假定字符串没有重复) 解决方案 目前有两种解决的方法 方法一: def str_sort(s=''): if len(s) <= 1: return [s] st

Python查找最长不包含重复字符的子字符串算法示例

本文实例讲述了Python查找最长不包含重复字符的子字符串算法.分享给大家供大家参考,具体如下: 题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度.例如在"arabcacfr"中,最长的不包含重复字符的子字符串是"acfr",长度为4 采用字典的方法,最后输出所有最长字符的列表 算法示例: # -*- coding:utf-8 -*- #! python3 class Solution: def __init__(self):

用位图排序无重复数据集实例代码(C++版)

<Programming Pearls>(编程珠玑下载)第一章讲述了如何用位图排序无重复的数据集,整个思想很简洁,今天实践了下. 一.主要思想 位图排序的思想就是在内存中申请一块连续的空间作为位图,初始时将位图的每一位都置为0,然后依次读取待排序文件的整数,将整数所在的位设置为1,最后扫描位图,如果某一位为1,则说明这个数存在,输出到已排序文件.比如待排序的数据S={3,0,4,1,7,2,5},max(S)=7,我们可以设置一个八位的位图B,将位图的每一位初始为0,即B=[0,0,0,0,0

Python输出由1,2,3,4组成的互不相同且无重复的三位数

题目:有四个数字:1.2.3.4,能组成多少个互不相同且无重复数字的三位数?各是多少? 程序分析:可填在百位.十位.个位的数字都是1.2.3.4.组成所有的排列后再去 掉不满足条件的排列. 程序源代码 方法1: #!/usr/bin/python # -*- coding: UTF-8 -*- for i in range(1,5): for j in range(1,5): for k in range(1,5): if( i != k ) and (i != j) and (j != k):

Python实现简单查找最长子串功能示例

本文实例讲述了Python实现简单查找最长子串功能.分享给大家供大家参考,具体如下: 题目选自edX公开课 MITx: 6.00.1x Introduction to Computer Science and Programming 课程 Week2 的Problem Set 1的第三题.下面是原题内容. Assume s is a string of lower case characters. Write a program that prints the longest substring

.net中string无重复数字的实现方法

复制代码 代码如下: //string strText = "1334677999";实现无重复        public static string qu(string lab)        {            string strResult = string.Empty;            for (int intIdx = 0; intIdx < lab.Length; intIdx++)            {                if (st

JS使用正则表达式除去字符串中重复字符的方法

本文实例讲述了JS使用正则表达式除去字符串中重复字符的方法.分享给大家供大家参考,具体如下: 这里演示一个简单的JavaScript正则表达式实例,将一串含有重复字符串中的多余字符滤除掉,请运行查看效果. 具体代码如下: <html> <head> <title>利用正则表达法除去字符串中的重复字符</title> </head> <body> <script language="javascript">

一个匹配重复字符正规表达式

前几天做邮件地址过滤,要求把连续重复多次的邮件地址删除,试了很多次,才试出了这个正规表达式. /([a-z0-9A-Z])\1{2,}/ 匹配3个或以上的重复字符,比如aaaa,bbb,cccc,000 /[a-z0-9A-Z]{3,}/ 匹配3个或以上的字符,比如abc,ab34

匹配5到10位无重复数字的正则表达式

对于有重复的5到10位数字可以使用\d{5,10} 这样的正则 无重复的5到10位数字我考虑了一下还不会,最然只好查网上. 有一个版本还不错,反正RegexBuddy测试通过了. 复制代码 代码如下: ^(?!\d*?(\d)\d*?\1)\d{5,10}$ 对于(?!---(--)---\1)这样的形式我还没有研究透,有时间我真要细细研究. 上一个php的例子: 复制代码 代码如下: <?php $str = '123456789'; $search = '/^(?!\d*?(\d)\d*?\