精华内容
下载资源
问答
  • js代码-(算法)(字符串)找最大不重复子串
  • 最大不重复子串是经典的滑动窗口问题思路:mp记录每个字符出现的最大索引位置start记录当前不重复子串的起始索引位置先用Python实现一遍def lengthOfLongestSubstring(s: str) -> int:if len(s) <= 1: return ...

    最大不重复子串是经典的滑动窗口问题

    思路:

    mp记录每个字符出现的最大索引位置

    start记录当前不重复子串的起始索引位置

    先用Python实现一遍

    def lengthOfLongestSubstring(s: str) -> int:

    if len(s) <= 1: return len(s)

    mp, start, res = {}, 0, 0

    for i, v in enumerate(s):

    if v in mp and mp[v]>=start:

    start = mp[v]+1

    mp[v] = i

    res = max(res, i-start+1)

    return res

    完全相同的思路再用Go实现一遍

    func lengthOfLongestSubstring(s string) int {

    if len(s) <= 1 {return len(s)}

    mp := make(map[rune]int)

    start, res := 0, 0

    for i, v := range s {

    if _, ok := mp[v]; ok && mp[v] >= start {

    start = mp[v] + 1

    }

    mp[v] = i

    if i-start+1 > res {

    res = i-start+1

    }

    }

    return res

    }

    leetcode结果如下 (Python总是被碾压, 哭, 不过代码更精简, 笑)

    展开全文
  • Python 求最大不重复子串

    千次阅读 2019-05-20 11:11:56
    例子: 假定给出字符串:"mabcafrab" , 那么它的最长不重复子串是“bcafr” 加入给出是“aaaaaaaa”,那么它的最长不重复是“a” 思路: 设置一个字典类型,dic{当前字符, 当前字符的位置}, 初始为{}, 判断...

    题目:一个字符串,找出不含有重复字符的最长子串的长度。

    例子: 假定给出字符串:"mabcafrab" , 那么它的最长不重复子串是“bcafr”

               加入给出是“aaaaaaaa”,那么它的最长不重复是“a”

     

    思路: 设置一个字典类型,dic{当前字符, 当前字符的位置}, 初始为{}, 判断字符串字符,如果字符不在dic中,则把这个字符加入,{'m':0}, 同时如果当前位置的字符所在的value大于等于start 值,则把start 置为value+1. 比如上例中, 到第5个字符‘a’时,dic['a']其实是 1.那么我们需要把start 设置为1+1,start 从b开始,就是说重复的我们暂时摒弃了。这种情况dic['a'] = 4, 在这次计算中。字符长度是i-start+1. 比较max_len 和当前i-start+1的大小。赋值给max_len

     

    def maxlengthofSubstring(s):
    
        max_len =0
        
        dic = {}
    
        flag_len = 0
    
        start = 0
    
        if s is None or len(s)==0:
    
            return 0
    
        for i in range(len(s)):
    
            if(s[i] in dic and dic[s[i]]>=start):
                start = dic[s[i]]+1
    
            flag_len = i- start +1
            dic[s[i]] = i
    
            max_len= max(max_len, flag_len)
    
            print(dic, start, max_len)
    
        return max_len
    
    print(maxlengthofSubstring("mabcafrab"))

    {'m': 0} 0 1
    {'m': 0, 'a': 1} 0 2
    {'m': 0, 'a': 1, 'b': 2} 0 3
    {'m': 0, 'a': 1, 'b': 2, 'c': 3} 0 4
    {'m': 0, 'a': 4, 'b': 2, 'c': 3} 2 4
    {'m': 0, 'a': 4, 'b': 2, 'c': 3, 'f': 5} 2 4
    {'m': 0, 'a': 4, 'b': 2, 'c': 3, 'f': 5, 'r': 6} 2 5
    {'m': 0, 'a': 7, 'b': 2, 'c': 3, 'f': 5, 'r': 6} 5 5
    {'m': 0, 'a': 7, 'b': 8, 'c': 3, 'f': 5, 'r': 6} 5 5
    5

    展开全文
  • 最大不重复子串(Java)

    千次阅读 2017-04-20 13:26:49
    一个经典问题,就是求字符串中包含重复字符的最大子串。如果有多个这样的子串,则输出第一个。 我的思路其实也就是从头比较到尾来找,只是中间加了一些判断条件进行了优化。具体流程(先转化成char[] ch): 1、...

    一个经典问题,就是求字符串中不包含重复字符的最大子串。如果有多个这样的子串,则输出第一个。例:str=”abxacsvada”,最大不重复子串为:“bxacsv”。
    我的思路其实也就是从头比较到尾来找,只是中间加了一些判断条件进行了优化。具体流程(先转化成char[] ch):
    1、假设该最长子串的首字符为ch [i] (0<=i< ch.length),则找到ch[i]==ch[j] (i< j< ch.length).此时”j”也就确定了该子串有可能的最大长度了。
    2、进一步确定该子串的长度,也就是要确定从ch[i]起,“j”长度的子串里有没有重复的字符,为了区分,这里定义int value=j。确认是否有ch[i+1]==ch[j] (i+1< j< value)。如果有,则进一步确定子串长度,再把此时的”j”赋值给value。
    3、重复上诉2步骤直到“i+n”==value.此时的value也就是以ch[i]为起点的最大不重复子串的长度值。
    代码如下:

    import java.util.Scanner;
    public class Main {
    
        static String calDuplicateString(String str) {//分别以0-ch.length的字符为首字符寻找最大不重复子串
            char[] ch=str.toCharArray();//转化成char数组
            int max=0;//记录最大不重复子串的长度
            int value;//记录以ch[i]为首字符的最大不重复子串的长度
            int k=0;//记录最大不重复子串的起始下标
            for(int i=0;i<ch.length;i++){//i表示起始字符的下标
    
                if((i-1)<(max+k) && i>0 && ch[i-1]!=ch[max+k])//优化算法①
                    continue;
    
                value=search(ch,i,max+k);//以ch[i]为首字符,寻找最大不重复子串,返回长度
                if(max<value){//如果此时得到的长度比原来得到的长度长,那就赋值给max,并且记录下此时的首字符下标
                    max=value;
                    k=i;
                }
                if(max>=ch.length-i-1)//优化算法②
                    break;
            }
    
            return new String(ch,k,max);//返回该最大子串
    
        }
    
        //该方法为了寻找以ch[head]为起始字符的最大子串,其中head表示起始字符的下标,left表示最开始需要比较的起始位置
        static int search(char[] ch,int head, int left) {
            int m=ch.length;//表示最大子串的最后一个字符的下标
            //上面思路对应的代码就是这里
            for(int i=head;i<m-1;i++)③
                for(int j=left;j<m;j++)
                    if(ch[i]==ch[j]){//一旦出现相同字符,则后面的字符都不可能是该最大子串的了
                        m=j;
                        break;
                    }
            return m-head;//返回最大子串的长度
    
    
        }
    
        //main函数测试
        public static void main(String[] args){
            Scanner in = new Scanner(System.in);
    
            String _str;
            _str = in.nextLine();
    
            System.out.println(calDuplicateString(_str));
    
        }
    }

    原始思路就是暴力解法,中间我加了两步优化,其实严格算三步。代码中标号处为优化的地方,逐一解释:
    ①:假设String str=”abcdbacdjas”。当第一次寻找以第一个字符为首字符的最长子串时,找的最长子串为“abcd”,此时我们寻找以第二个字符为首字符的最大子串,分析一下:
    对于第一次找到的结果来看,前四个字符是没有重复字符的,并且说明第五个字符肯定与前四个字符中的某一个相同(不考虑到末尾的情况)。当且仅当第一个字符等于第五个字符时,第二个字符为首字符的最大子串的长度才有可能大于等于第一次找到的最大子串。因为如果ch[0]!=ch[4],那么肯定存在ch[i](0< i <4)==ch[4]。所以以第二个字符为首字符的最大子串的长度不可能大于3了。所以得出三个判断条件:
    (i-1)<(max+k) && i>0 && ch[i-1]!=ch[max+k]
    i>0:因为第一次时没有前面得出的最大子串。

    ch[i-1]!=ch[max+k]:也就是上面分析得出的判断式

    (i-1)<(max+k):例如上面,所有分析都是比较前面得出的最大子串与第五个字符是否相等,那么显然不能比较大于第五个字符后的字符了。不然如果一直没有寻找到大于原来的最大子串的最大子串,那么max+k始终不变,而i-1已经>=max+k了,这样就会continue掉很多不该continue的地方。

    ②:max>=ch.length-i-1:这个好理解,就是寻找以ch[i]为首字符的最大子串时,如果ch[i]加上它后面的所有字符如果都不能大于之前得到最大子串的长度max时,那么,后面的这些字符都没有去寻找的必要了。

    ③:这里是缩小了两个循环的范围,假设:在寻找以第一个字符为首字符的最大子串时,因为不知道最开始有多长,所以需要设为ch.length,如果此时找到ch[0]==ch[5],那么此时最大子串的长度就<=5了,所以此时还需要判断ch[1]到ch[4]里有没有重复字符就可以了。而left是根据上一次得出的最大子串来确定的,上面已经①中分析过了。

    上面代码有可能还存在bug,毕竟我没有把所有特殊情况都测试一遍。

    展开全文
  • 算法题之求最大不重复子串的个数(滑动窗口) 题目描述 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度...

    算法题之求最大不重复子串的个数(滑动窗口)

    题目描述

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

    输入: “abcabcbb”
    输出: 3
    解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
    示例 2:

    输入: “bbbbb”
    输出: 1
    解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
    示例 3:

    输入: “pwwkpw”
    输出: 3
    解释: 因为无重复字符的最长子串是 “kpw”,所以其长度为 3。

    题解(滑动窗口)

    以输入: "pwwkpw"为例
    在这里插入图片描述

    滑动窗口思路分析:利用HashMap的键唯一性

    • (1)当我们判断字符串当前字符在HashMap中key中未曾出现过:
      • 则直接将其加入到HashMap中:其中键(key)即为当前的字符(Character),值(value)即为该字符在String字符串的索引
      • 其中此时的最大字符串的最大长度(maxLength)即为当前索引 – left(初始值为0) + 1;第一次添加p,则maxLength = 1;
    • (2)若依次添加字符,字符key值未在HashMap中出现过,则一直将其加入HashMap中,故p,w的maxLength = 1 – left + 1 = 2;
    • (3)若添加字符,当前key值在HashMap中出现过,根据HashMap的键唯一性:
      • 首先我们需要更新此时的left指针变量,即更新窗口的滑动:
      • 开始时,left位于0位置,此时,选择之前的left指针和当前key值字符的位置 + 1,即移除重复出现的字符,取两者的最大值为新的left指针
      • 故此时的left为2,此时再将当前键值加入HashMap集合中时,替换之前的value值,即更新w的索引位置,而此时的maxLength,即为之前的maxLength[p,w = 2]和现在的i – left + 1 = 1[w]的最大值
      • 接着,也是同上思路,当遍历到p字符时,需要更新left的位置:因为先前的left索引大于此时p之前的索引 + 1,则窗口不发生偏移
        maxLength = [p,w] vs [w,k,p] = 3;
      • 最后到w,更新left位置为k的位置,此时maxLength = [w,k,p] vs [k,p,w] = 3;
    • (4)故最终的maxLength = 3;即最大的非重复子串的长度为:3.

    图解过程

    在这里插入图片描述

    在这里插入图片描述

    代码实现

    public static void main(String[] args) {
            String str = "pwwkpw";
            LongestSubString2 solution = new LongestSubString2();
            int maxLength = solution.lengthOfLongestSubstring(str);
            System.out.println("最大不重复的子字符串的长度为: " + maxLength);
        }
    
        private int lengthOfLongestSubstring(String s) {
            //定义该字符串的长度为n
            int n = s.length();
            //若长度小于等于1,则maxLength即为字符串本身的长度,直接返回
            if (n <= 1) {
                return n;
            }
            //定义maxLength作为最大不重复子串的长度
            int maxLength = 0;
            //定义滑动窗口的左指针的变量,初始化为0
            int left = 0;
            //定义一个HashMap进行存储
            HashMap<Character,Integer> hashMap = new HashMap<>();
            for (int i = 0; i < n; i++) {
                if (hashMap.containsKey(s.charAt(i))) {
                    //如果当前key值在hashmap中已经存在
                    //则更新left指针为之前的出现的指针向右平移一位
                    left = Math.max(left, hashMap.get(s.charAt(i)) + 1);
                }
                //将该键值添加到hashmap集合中
                hashMap.put(s.charAt(i),i);
                maxLength = Math.max(maxLength,i - left + 1);
            }
            //返回最大值maxLength
            return maxLength;
        }
    
    展开全文
  • 主要介绍了Python简单实现查找一个字符串中最长不重复子串的方法,涉及Python针对字符串的简单遍历、运算等相关操作技巧,需要的朋友可以参考下
  • 最大不重复子串

    千次阅读 2018-10-01 00:03:43
    1、如果当前字符ch已经出现过(hashTable[ch]==1),则表示一个局部最长不重复子串已经出现: 此时判断该子串长度len是否大于mlen,如果是,则更新mlen,以及最长子串的起始位置mstart。 同时将start到重复字符ch...
  • 最大不重复子串代码 public static int lengthOfLongestSubstring(String s) { // 哈希集合,记录每个字符是否出现过 Set<Character> occ = new HashSet<Character>(); int n = s.length(); // 右...
  • 求字符串不重复子串最大长度问题描述解题思路Python实现 问题描述 Given a string, find the length of the longest substring without repeating characters. Example: Input: "bbbbb" Output: 1 Explanation: ...
  • //不断更新非重复子串最大长度 if (res >= lastres) { cout "res:" ;; maxindex = i; minindex = pre+ 1 ; lastres = res; } //当遇到出现过的字符时,res=当前出现的字符索引-上次出现相同字符的...
  • Leetcode 3 - 最大不重复子串

    千次阅读 2016-11-10 15:02:44
    有一个字符串,现在让我们求出最大不重复的连续的子串的长度 Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length ...
  • 给定一个字符串,请你找出其中含有重复字符的最长子串的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无...
  • 最大不重复子串长度

    2017-03-05 17:23:22
    Longest Substring Without Repeating Characters(最长不重复子串) 题目 给定一个字符串,找到最长的子串的长度,这个子串不存在重复的字符。 例如: 输入”abcabcbb”, 符合条件的子串就是”abc”, 长度为3。 ...
  • [Java教程]找出给定的一个字符串中最长的不重复子串不重复子串即一个子串中不出现两个相同的字符0 2017-05-25 00:01:28思路一:先找出一个字符串中所有子串,再找出所有子串中最长的那一个;思路二:每次找出的...
  • 输入:abcc 输出:3  输入:baddabce 输出: 5 #include&lt;iostream&gt; #include&lt;string&gt; #include&lt;vector&gt; using namespace std; int main() { ... int max ...
  • 给定一个字符串,请你找出其中含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为...
  • 若d小于或等于f(i-1),即说明前一个非重复子字符串中已经包含当前字符,则可以添加当前字符,所以,f(i) = d。 关键点: 动态规划,两个重复字符的距离 public static int maxLength(String str) { if(str==null |...
  • 寻找最大不重复子串
  • 前言最近学习有点断断续续,整理的一些知识点要么完整,要么完全没搞懂,不好拿上台面,还是先在草稿箱躺着吧。偶尔在浏览大牛博客http://coolshell.cn的时候,发现大牛业余时间也在做编程训练...
  • 寻找最长不重复子串

    2017-06-23 18:21:36
    寻找最长不重复子串 python代码
  • 给定一个字符串,请你找出其中含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 #include <stdio.h> #include <...
  • js 求最长不重复子串

    2019-09-11 23:37:46
    var lengthOfLongestSubstring = function(s) { ... // 用于存放当前最长无重复子串的长度 var str = ""; // 用于存放无重复子串 var len = s.length; for(var i = 0; i < len; i++) { var char = s.char...
  • 本题要求传入一个字符串,求出不重复最长子串的长度,但 我在求最大长度的基础上,增加了输出最长子串(存在bug) 思路: 通过hashmap的key值唯一来判断是否出现重复字符,当出现重复字符,再判断是否为最大长度,...
  • 最长不重复子串

    千次阅读 2015-10-09 11:46:44
    题:从一个字符串中找到一个连续子串,该子串中任何两个字符不能相同,求子串的最大长度并输出一条最长不重复子串。 本节从最直接的方法逐步优化,渐进探索了四种实现方式,并最终找到时间复杂度为O(N),辅助空间为...
  • 本文转载自【微信公众号:机器学习算法与Python精研,ID:AITop100】经微信公众号授权转载,如需转载与原文作者联系题目:给定一个字符串,找出含有重复字符的最长子串的长度。示例:给定 "abcabcbb" ,没有重复...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 42,269
精华内容 16,907
关键字:

最大不重复子串