精华内容
下载资源
问答
  • 这道题一开始的思路是个人首先都会想到暴力吧(我这么认为),但是很不幸...听着是可行的,因为我们这样是找出了所有不重复子串!但是到了具体实现上,我们需要知道我们这个以某个元素结尾的字符串从哪开始,我们...

    这道题一开始的思路是个人首先都会想到暴力吧(我这么认为),但是很不幸,当我千辛万苦写出暴力,又告诉我时间超了。

    好吧于是只能不走寻常路了,我们只能遍历一遍字符串,就要找出这个最大值。

    思路:遍历每个元素,每次循环都找出以这个元素结尾的最长字符串,最后再与历史最大值相比取最大。

    听着是可行的,因为我们这样是找出了所有不重复的子串!但是到了具体实现上,我们需要知道我们这个以某个元素结尾的字符串从哪开始,我们才能算长度,才能找出以这个元素结尾的最长字符串。首先,这个开始的点到我们结尾处一定不能有相同的元素,其次我们要在有相同元素时修改这个开始点。

    于是贴代码

    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            max_len = 0
            one_max = 0
            data = {}
            start = 0
            for i in range(len(s)):
                if s[i] in data and data[s[i]] >= start:
                    start = data[s[i]] + 1
                one_max = i - start + 1
                data[s[i]] = i
                max_len = max(max_len, one_max)
            return max_len

    关键是,每次都找以这个元素结尾的最长无重复字符串,要先保证前面的元素不重复,后面的才有可能不重复。

    展开全文
  • 关键就是这个无重复,KMP算法算的...关于KMP算法,它本来是在一个字符串里寻找另一个字符串的程序,再复杂一点才是在字符串里面寻找最大子串,因此kmp算法挺适合找子串位置的。 next数组的特点是1开始,为什么1...

    关键就是这个无重复,KMP算法算的是最长子串,本身就不怎么会KMP,然后它还要不重复的,一般寻找子串程序会给你两个结果,一个是子串起始位置,第二个是字串长度,其实还应该有第三个结果,即子串数量,这个看网上题解会更快一些。

    关于KMP算法,它本来是在一个字符串里寻找另一个字符串的程序,再复杂一点才是在字符串里面寻找最大子串,因此kmp算法挺适合找子串位置的。

    next数组的特点是从1开始,为什么从1开始呢?那要看next数组是什么,它代表的是字符串每一个位置的最大公共长度,什么意思呢?就是next数组表示的是长度,举个例子吧:

    这里有字符串A,和字符串B,字符串B有next数组,然后从字符串A里面找字符串B,最开始自然是从头开始比较,假设一开始都是一样的,例如字符串A是QWER*******,字符串B也是QWER$$$$$$,它们前面是一样的,因此可以接着比对下去,等到突然有一个地方,二者不同了,那么说明这一段与B不像,自然不算数,那么接下来怎么办呢?按照常规方法,就是字符串A从W开始,也就是从第二位开始,B字符串从Q开始,还是从第一位开始,比对,然后不同的话字符串A紧接着移动到下一位,就这样,这是普通做法。

    KMP呢,它采用的不是字符串A后退法,它采用的是字符串B前进法,一旦不同了,它不是还有一个next数组么,它指定的是最近一个相同的字符位置,我这么说肯定不清楚,因为我自己都说不清楚,举个例子:

    字符串A:QWEQWEQ*******
    字符串B:QWEQWET*******

    假设它们从头开始比较,比较到这一位,不一样了,这时候字符串B开始前进

    QWEQWEQ******                                    QWEQWEQ********
       QWEQWET******                                          QWEQWET*******

    这两种方法哪一种更快呢?自然是B方法更快,这就是next数组的功劳,next数组之所以能用得上,是因为之前的字符有重复的,如果前面没有重复的,那么自然也用不上,它的实质是一个字符的前几位会与更远的几位有重合,一旦对比不同,就直接跳到那几位而不是从头开始。

    因此,怎么生成这个next数组呢?首先它是从下标1开始,也就是第二位,因为第一位之前就没有字符了,更重要的是,我们需要把第一位设置成一个标志位,标志结束,不用再往前移动了,设为-1,第一位肯定设为0,因为一旦不对,它只能从头开始了,然后从第二位开始,它是一个自己比对自己的过程,第一步,设[0]=-1,第二步,将B2[0]移动到B1[1]的位置开始比对,如果相同,即B[0]==B[1]的时候,将next[1]设为0,然后比对B2[1]和B1[2],如果开始相同,设next[2]=1,也就是说,如果比对相同的时候,设此时的next为上一位字符的索引。

    如果不同呢?那么就是移动B2了,因为B2始终滞后于B1,因此用next绝对没问题,然后切换到next的那一个位置(前提是有啊),此时便能够保证之前的字符是一样的,但不能保证这个字符是一样的。

    从开始第三位与第二位进行比对,相同,设为上一位,不相同,切换next,相同,设为上一位,不相同,切换next,,,,直到0,到位置0后,如果相同,继续比对下去,如果不同,就都向下移动一位,就这样。

    既然能比对下去,说明之前的的确是对的上的,那么取更短的一点,自然也能对的上,也就是说,本身比对的那个并不是相等的,才会有next的跳跃。也就是说,在创造next数组的时候,如果二者相等,那么B1[i+1]要设定B2[j+1]的那个索引,这是非常巧妙的办法。











     

    展开全文
  • * 请从字符串中找出至少重复一次的子字符串的最大长度 var str=readline(); var len=str.length; // 子串长度 var mylen=Math.floor(len/2); var tem=mylen;// 临时存储长度 var max=0; // 子串长度至少为1,存在...
    * 请从字符串中找出至少重复一次的子字符串的最大长度
    var str=readline();
    var len=str.length;
    // 子串长度
    var mylen=Math.floor(len/2);
    var tem=mylen;// 临时存储长度
    var max=0;
    // 子串长度至少为1,不存在则输出0
    for(var i=0;i<=tem;i++){
        //console.log(mylen);
        for(var j=0;j<=len-2*mylen;j++){
            var mystr=str.slice(j,mylen+j);
            //console.log(mystr,(str.lastIndexOf(mystr)-str.indexOf(mystr)));
            if((str.lastIndexOf(mystr)-str.indexOf(mystr))>=mylen){
                //console.log(mystr.length);
                if(mystr.length>max){
                    max=mystr.length;
                }
                break;
            }
        }
        mylen--;
    }
    console.log(max)
    
    展开全文
  • Leetcode-3. Longest Substring Without Repeating ...找到后,该重复字符之前的字符设置为未访问过(关键),新窗口左边该重复字符串下一位开始,右边(v)的下一位开始,重新寻找最大长度不重复字符子串

    Given a string, find the length of the longest substring without repeating characters.

    Examples:

    Given "abcabcbb", the answer is "abc", which the length is 3.

    Given "bbbbb", the answer is "b", with the length of 1.

    Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring"pwke" is a subsequence and not a substring.

    O(n)时间复杂度,窗口滑动解决,遍历字符串,打访问标记,记录最大长度,如果有访问过(v),则从窗口左边开始寻找重复访问过的字符,

    找到后,该重复字符之前的字符设置为未访问过(关键),新窗口左边从该重复字符串下一位开始,右边从(v)的下一位开始,重新寻找最大长度不重

    复字符子串。

    int lengthOfLongestSubstring(string s) {
        	int maxlen,tmplen;
        	maxlen=tmplen=0;
        	int i,j;
        	i=j=0;
        	bool set[128]={false};
        	while(j<s.size()){
        		if(set[s[j]]==false){
        			set[s[j]]=true;
        			j++;
        		}
        		else{
        			while(s[i]!=s[j]){
        				set[s[i]]=false;
        				i++;
        			}
        			i++;
        			j++;
        		}
        		tmplen=j-i;
        		maxlen=tmplen>maxlen?tmplen:maxlen;
        	}
        	return maxlen;
        }


    展开全文
  • 题目链接:...解题思路:一个字符开始,往后寻找不含重复字符的最长子串,然后记录其中的最大值。 代码如下: class Solution { public:
  • 题目大意:给出一个字符串,找到该字符串中不含重复字符的最长子串,返回其长度。 示例:给出子串:abcabcbb,其最长子串是“abc”,则返回其长度值3。 解题思路:看到题目,首先想到的最“笨”的方法就是第一个...
  • LeetCode解题总结

    2018-10-09 16:02:19
    5.3.1 生成不重复的二叉查找树数目 5.3.2 验证是否为二叉查找树 5.3.3 将有序数组转为二叉树 5.3.4 将有序链表转为二叉树 5.4 二叉树的递归 5.4.1 二叉树的最大深度 5.4.2 二叉树的最小深度 5.4.3 路径和 5.4.4 满...
  • Python Cookbook

    2013-07-31 22:33:26
    1.10 过滤字符串属于指定集合的字符 20 1.11 检查一个字符串是文本还是二进制 23 1.12 控制大小写 25 1.13 访问子字符串 26 1.14 改变多行文本字符串的缩进 29 1.15 扩展和压缩制表符 31 1.16 替换字符串...
  • 面试题28:字符串的排列:依次取一个元素,然后依次和之前递归形成的所有子串组合,形成新的字符串。扩展:字符串的组合 面试题29:数组中出现次数超过一半的数字:两种思路。第一种思路,出现次数超过一半的数字,...
  • 正则表达式经典实例.pdf

    热门讨论 2013-01-26 15:14:37
    3.6 检查正则表达式能否整个匹配目标字符串 3.7 获取匹配文本 3.8 决定匹配的位置和长度 3.9 获取匹配文本的一部分 3.10 获取所有匹配的列表 3.11 遍历所有匹配 3.12 在过程代码中对匹配结果进行验证 3.13 在另一个...
  • 正则表达式经典实例

    2014-07-11 14:39:05
    3.6 检查正则表达式能否整个匹配目标字符串 3.7 获取匹配文本 3.8 决定匹配的位置和长度 3.9 获取匹配文本的一部分 3.10 获取所有匹配的列表 3.11 遍历所有匹配 3.12 在过程代码中对匹配结果进行验证 3.13 在...
  • 0686. 重复叠加字符串匹配 0718. 最长重复子数组 0714. 买卖股票的最佳时机含手续费 0735. 行星碰撞 0754. 到达终点数字 0785. 判断二分图 0790. 多米诺和托米诺平铺 0799. 香槟塔 0801. 使序列递增...
  • 你必须知道的495个C语言问题

    千次下载 热门讨论 2015-05-08 11:09:25
    5.6 如果NULL定义成#defineNULL((char*)0),就可以向函数传入加转换的NULL了吗? 5.7 我的编译器提供的头文件中定义的NULL为0L。为什么? 5.8 NULL可以合法地用作函数指针吗? 5.9 如果NULL和0作为空指针...
  • 《你必须知道的495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    书中列出了C用户经常问的400多个经典问题,涵盖了初始化、数组、指针、字符串、内存分配、库函数、C预处理器等各个方面的主题,并分别给出了解答,而且结合代码示例阐明要点。 《你必须知道的495个C语言问题》结构...
  • 5.6 如果NULL定义成#define NULL((char *)0) ,就可以向函数传入加转换的NULL 了吗? 57 5.7 我的编译器提供的头文件中定义的NULL为0L。为什么? 57 5.8 NULL可以合法地用作函数指针吗? 57 5.9 如果NULL...
  • 世界500强面试题.pdf

    2019-11-01 14:33:26
    1.5.7. 输入一个表示整数的字符串,把该字符串转换成整数并输出.............. 118 1.5.8. 给出一个数列,找出其中最长的单调递减(或递增)子序列..............121 1.5.9. 四对括号可以有多少种匹配排列方式........
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    3、终端读入字符集大小为n(即字符的个数),逐一输入n个字符和相应的n个权值(即字符出现的频度),建立哈夫曼树,进行编码并且输出。 注:可用C或C++编写。 4、用邻接矩阵或邻接图实现一个有向图的...
  • 周 源 -《浅析"最小表示法"思想在字符串循环同构问题中的应用》 ## 2004 何 林 -《信息学中守恒法的应用》 胡伟栋 -《减少冗余与算法优化》 金 恺 -《极限法——解决几何最优化问题的捷径》 李锐喆 -...
  • + [字符串匹配](#字符串匹配) * [动态规划](#动态规划) + [动态规划](#动态规划-1) + [状态压缩](#状态压缩) + [状态设计](#状态设计) + [树形DP](#树形dp) + [优化](#优化-1) * [计算几何](#计算几何) + ...
  • 3.5.1 c风格的字符串 44 3.6 输入 44 3.7 容器 46 3.7.1 向量—vector 46 3.7.2 范围检查 47 3.7.3 表—list 48 3.7.4 映射—map 49 3.7.5 标准容器 49 3.8 算法 50 3.8.1 迭代器的使用 51 3.8.2 迭代器...
  • 3.5.1 c风格的字符串 44 3.6 输入 44 3.7 容器 46 3.7.1 向量—vector 46 3.7.2 范围检查 47 3.7.3 表—list 48 3.7.4 映射—map 49 3.7.5 标准容器 49 3.8 算法 50 3.8.1 迭代器的使用 51 3.8.2 迭代器...
  • C++程序设计语言(特别版)--源代码

    热门讨论 2012-04-23 07:33:51
    3.5.1 c风格的字符串 44 3.6 输入 44 3.7 容器 46 3.7.1 向量—vector 46 3.7.2 范围检查 47 3.7.3 表—list 48 3.7.4 映射—map 49 3.7.5 标准容器 49 3.8 算法 50 3.8.1 迭代器的使用 51 3.8.2 迭代器...
  • 前序与中序遍历序列构造二叉树,Simple O(n) without map,JavaScript,详细注释 LeetCode 题解:389. 找不同,ASCII 码求和,JavaScript,详细注释 LeetCode 题解:389. 找不同,位运算,JavaScript,详细注释 ...

空空如也

空空如也

1 2
收藏数 26
精华内容 10
关键字:

从字符串寻找最大不重复子串