C/C++教程

LeetCode算法题:(3)求无重复字符的 最长子串 的长度(c语言)

本文主要是介绍LeetCode算法题:(3)求无重复字符的 最长子串 的长度(c语言),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

问题

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例

输入:abcabcbb

输出:3

解释:其无重复字符的最长子串为“abc”,长度为3


 题解

  • 这里主要介绍滑动窗口解法,并先以最常见的暴力解法与其对比。

一、暴力解法

  • 暴力解法的方式很直接,其思想是利用两层循环,第一层循环对字符串进行遍历,第二层循环对每一个遍历到的字符往后检索,得到无重复字符最长子串,并记录其长度,最后返回其最长子串的长度。

例:(abcbd)

  1. (a)bcbd:最长子串为(abc)bd,长度为3
  2. a(b)cbd:最长子串为a(bc)bd,长度为2
  3. ab(c)bd:最长子串为ab(cbd),长度为3
  4. abc(b)d:最长子串为abc(bd),长度为2
  5. abcb(d):最长子串为abcb(d),长度为1
  • 最后得到最长子串长度为3(这里主要介绍滑块窗口,故无代码片段)

二、滑块窗口

基本思想:滑动窗口可分为两个部分,一个是窗口的移动收缩,一个是重复字符的判断。

  • 滑动窗口:针对存储字符串的数组,我们可以对数组进行遍历,同时对标记序号来记录其位置,然后用两个变量来记录窗口两边的位置(相当于两个指针),在遍历开始后,‘左指针’不动,‘右指针’往右移动,并同时判断两指针所限定的窗口中的子串是否有重复字符,如果有,则将‘左指针’移动到左重复字符之后的字符上,在这个过程中记录最大的子串长度,直到遍历结束。
  • 标记序号:标记序号的实现是创建一个长度为128的数组,并把值都初始化为0,根据键盘所有可输入的字符的ascll码的值与数组序号一一对应,例如a:97、b:98、2:50,如此一来,相当于把所有可输入字符都存储在这个数组中,当我们对原数组遍历时,每遇到一个字符,便可以为其在此数组中标记一个序号。
  • 重复判断:当我们的‘右指针’往右移动,每遇到一个字符,便判断其序号是否大于或等于‘左指针’的的序号,如果成立,便是遇到了重复字符 。 

注:初始化

 

流程图:

 代码实现:

int lengthOfLongestSubstring(char * s){
    int a[128]={0};
    int max=0,len=0,i=0,j=0;
    while(s[j]){
        if(a[s[j]]>i){
            i=a[s[j]];
        }
        a[s[j]]=j+1;
        len=j-i+1;
        max=max>len?max:len;
        j++;
    }
    return max;
}

这篇关于LeetCode算法题:(3)求无重复字符的 最长子串 的长度(c语言)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!