精华内容
下载资源
问答
  • 最大不重复子串是经典的滑动窗口问题思路: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总是被碾压, 哭, 不过代码更精简, 笑)

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

    千次阅读 2018-10-01 00:03:43
    1、如果当前字符ch已经出现过(hashTable[ch]==1),则表示一个局部最长不重复子串已经出现: 此时判断该子串长度len是否大于mlen,如果是,则更新mlen,以及最长子串的起始位置mstart。 同时将start到重复字符ch...

    思路:

    利用hash表hashTable[256]来保存出现过的字符,然后从头开始遍历字符串,

    1、如果当前字符ch已经出现过(hashTable[ch]==1),则表示一个局部最长不重复子串已经出现:

    此时判断该子串长度len是否大于mlen,如果是,则更新mlen,以及最长子串的起始位置mstart。

    同时将start到重复字符ch之间的hash表重置为0(表示没有出现过),相应的长度len也减小,然后从ch的下个字符作为新的子串的开始;

    2、如果当前字符ch没有出现过:

    则设置hashTable为1(表示出现过),并len++。

    #include<iostream>
    
    using namespace std;
    
    int getLongestUnRepeatedSubStr(const string &str)
    {
        int hashTable[256]={0};
        int start=0;
        int mstart=0;
        int mlen=0;
        int idx=0;
        int len=0;
        while(idx!=str.size())
        {
            if(hashTable[str[idx]]==1)
            {
                if(len>mlen)
                {
                    mstart=start;
                    mlen=len;
                }
                while(str[start]!=str[idx])
                {
                    hashTable[str[start]]=0;
                    start++;
                    len--;
                }
                start++;
            }
            else
            {
                hashTable[str[idx]]=1;
                len++;
            }
            idx++;
        }
        if(len>mlen)
        {
            mlen=len;
            mstart=start;
        }
        cout<< str.substr(mstart,mlen) <<endl;
        return mlen;
    }
    
    int main()
        {
        string str;
        while(cin>>str)
        {
            cout << getLongestUnRepeatedSubStr(str) << endl;
        }
        return 0;
    }

     

    展开全文
  • 最大不重复子串代码 public static int lengthOfLongestSubstring(String s) { // 哈希集合,记录每个字符是否出现过 Set<Character> occ = new HashSet<Character>(); int n = s.length(); // 右...

    最大不重复子串代码

    public static int lengthOfLongestSubstring(String s) {
    	// 哈希集合,记录每个字符是否出现过
    	Set<Character> occ = new HashSet<Character>();
    	int n = s.length();
    	// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
    	int rk = -1, ans = 0;
    	for (int i = 0; i < n; ++i) {
    		if (i != 0) {
    			// 左指针向右移动一格,移除一个字符
    			occ.remove(s.charAt(i - 1));
    		}
    		while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
    			// 不断地移动右指针
    			occ.add(s.charAt(rk + 1));
    			++rk;
    		}
    		// 第 i 到 rk 个字符是一个极长的无重复字符子串
    		ans = Math.max(ans, rk - i + 1);
    	}
    	return ans;
    }
    

    字符串abcabcbb的最大不重复子串

    默认赋值:rk = -1,ans=0

    第一次循环(i=0)

    while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
    	// 不断地移动右指针
    	occ.add(s.charAt(rk + 1));
    	++rk;
    }
    // 第 i 到 rk 个字符是一个极长的无重复字符子串
    ans = Math.max(ans, rk - i + 1);
    

    经过while循环,此时HashSet中的元素分别是a、b、c,rk=2

    ans = max(0,2-0+1) = 3,可以得出最大不重复子串个数为3

    第二次循环(i=1)

    if (i != 0) {
    	// 左指针向右移动一格,移除一个字符
    	occ.remove(s.charAt(i - 1));
    }
    while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
    	// 不断地移动右指针
    	occ.add(s.charAt(rk + 1));
    	++rk;
    }
    // 第 i 到 rk 个字符是一个极长的无重复字符子串
    ans = Math.max(ans, rk - i + 1);
    

    经过第一次if (i != 0)判断,HashSet移除元素a,此时HashSet中的元素分别是b、c

    经过while循环,此时HashSet中的元素分别是b、c、a,rk = 3

    ans = max(3,3-1+1) = 3

    第三次循环(i=2)

    if (i != 0) {
    	// 左指针向右移动一格,移除一个字符
    	occ.remove(s.charAt(i - 1));
    }
    while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
    	// 不断地移动右指针
    	occ.add(s.charAt(rk + 1));
    	++rk;
    }
    // 第 i 到 rk 个字符是一个极长的无重复字符子串
    ans = Math.max(ans, rk - i + 1);
    

    经过第一次if (i != 0)判断,HashSet移除元素b,此时HashSet中的元素分别是c、a

    经过while循环,此时HashSet中的元素分别是c、a、b,rk = 4

    ans = max(3,4-2+1) = 3

    后续几次循环都如第二次、第三次循环所示

    字符串pwwkew的最大不重复子串

    第一次循环(i=0)

    while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
    	// 不断地移动右指针
    	occ.add(s.charAt(rk + 1));
    	++rk;
    }
    // 第 i 到 rk 个字符是一个极长的无重复字符子串
    ans = Math.max(ans, rk - i + 1);
    

    经过while循环,此时HashSet中的元素分别是p、w,rk=1

    ans = max(0,2-0+1) = 2,可以得出最大不重复子串个数为2

    第二次循环(i=1)

    if (i != 0) {
    	// 左指针向右移动一格,移除一个字符
    	occ.remove(s.charAt(i - 1));
    }
    while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
    	// 不断地移动右指针
    	occ.add(s.charAt(rk + 1));
    	++rk;
    }
    // 第 i 到 rk 个字符是一个极长的无重复字符子串
    ans = Math.max(ans, rk - i + 1);
    

    经过第一次if (i != 0)判断,HashSet移除元素p,此时HashSet中的元素只有w 注意:这里的w是下标为1的w

    经过while循环,此时HashSet中的只有w(因为w后面还是w,不会添加),rk = 1

    ans = max(2,1-1+1) = 2

    第三次循环(i=2)

    if (i != 0) {
    	// 左指针向右移动一格,移除一个字符
    	occ.remove(s.charAt(i - 1));
    }
    while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
    	// 不断地移动右指针
    	occ.add(s.charAt(rk + 1));
    	++rk;
    }
    // 第 i 到 rk 个字符是一个极长的无重复字符子串
    ans = Math.max(ans, rk - i + 1);
    

    经过第一次if (i != 0)判断,HashSet移除元素w,此时HashSet中的元素为空 注意:这里移除的w是下标为1的w

    经过while循环,此时HashSet中的元素有w、k、e,rk = 4

    ans = max(2,4-2+1) = 3

    第四次循环(i=3)

    if (i != 0) {
    	// 左指针向右移动一格,移除一个字符
    	occ.remove(s.charAt(i - 1));
    }
    while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
    	// 不断地移动右指针
    	occ.add(s.charAt(rk + 1));
    	++rk;
    }
    // 第 i 到 rk 个字符是一个极长的无重复字符子串
    ans = Math.max(ans, rk - i + 1);
    

    经过第一次if (i != 0)判断,HashSet移除元素w,此时HashSet中的元素为k、e 注意:这里移除的w是下标为2的w

    经过while循环,此时HashSet中的元素有k、e、w,rk = 5

    ans = max(2,5-3+1) = 3

    总结

    1、本道题目需要2个指针(i 和 right),一个指针作为遍历字符串的指针,另一个指针作为遍历中 while循环 往后移动的指针

    2、第一次循环,指针i保持不动,right向后遍历直到发现重复元素,停止遍历。这时候得出的right

    示意图如下:

    在这里插入图片描述

    在这里插入图片描述

    3、后续每次进行i++循环,重复步骤2

    部分细节语句以及参数说明

    int rk = -1 右指针,相当于right。

    备注:这里取值为-1,以下图例,是因为当right指向c时,right=2,也就是说String[2]=c,最后只需要right+1就可以拿到子串长度length=3

    在这里插入图片描述

    如果取值为0,那么将会以下图呈现,虽然可以直接得到right = 子串长度length = 3

    在这里插入图片描述

    但是实际上 String[3]在while循环判断 !occ.contains(s.charAt(rk))时,条件为false,不会被放入到HashSer中,但是指针却指向String[3],这样会容易导致误会。

    int i = 0 遍历字符串所需的变量

    ans = 0 记录最大子串,这也是为什么每次都是取max。假设上一个不重复子串最大长度为4,下一个为3,这时候取max依然是最大长度。

    rk - i + 1 +1的目的主要是为了解决 rk = -1 的问题,-i是因为for (int i = 0; i < n; ++i)时,每次i++递增的同时会导致right指针递增,所以需要减去递增的i值即可。

    set.remove(s.charAt(i - 1)) 因为第二次循环已经执行了一次i++,此时i=1,我们要删除的元素应该是i=0的元素

    重要:remove和while遍历不能返过来写,否则会导致right++,由于有重复元素导致无法放入,再进行移除的话就会少一位非重复元素

    代码练习 + 自己理解注释

        public static int lengthOfLongestSubstring(String s) {
            HashSet<Character> set = new HashSet<>();
            int right = -1 , length = 0;
            for (int i = 0; i < s.length(); i++) {
                if (i != 0){
                    set.remove(s.charAt(i - 1));            //第二次循环开始,每次都剔除字符串的首位
                }
                // 当right不超过字符串长度  并且  HashSet中没有该元素时
                while (right + 1 < s.length() && !set.contains(s.charAt(right + 1))){
                    set.add(s.charAt(right + 1));       //将该元素添加到HashSet中
                    right++;                            //并使指针后移1位
                }
                length = Math.max(length,right - i + 1);    //取最大值
            }
            return length;
        }
    ht + 1))){
                    set.add(s.charAt(right + 1));       //将该元素添加到HashSet中
                    right++;                            //并使指针后移1位
                }
                length = Math.max(length,right - i + 1);    //取最大值
            }
            return length;
        }
    
    展开全文
  • 找出最大不重复子串 关键在于利用哈希表的查找优势,设置一个记录不重复字串的开始位置。需要线性时间 public class Solution {  public int LengthOfLongestSubstring(string s)  {  Dictionary dict=new ...

    找出最大不重复子串

    关键在于利用哈希表的查找优势,设置一个记录不重复字串的开始位置。需要线性时间


    public class Solution {
        public int LengthOfLongestSubstring(string s)
        {
            Dictionary<char,int> dict=new Dictionary<char,int>();
            int a=0,cur=0,max=0;
            for(int i=0;i<s.Length;i++)
            {
                if(!dict.Keys.Contains(s[i]))
                {
                    dict.Add(s[i],i);
                    cur++;
                    max=max>cur?max:cur;
                }
                else
                {
                    a=a<dict[s[i]]?dict[s[i]]:a;
                    cur=i-a;
                    max=max>cur?max:cur;
                    dict[s[i]]=i;
                }
            }
            return max;
        }
    }

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

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

    2020-02-07 11:01:18
    public static int lengthOfLongestSubstring(String s) { int max=0; int from=0; for (int i=0;i<s.length();i++){ char c=s.charAt(i); for (int j=from;j&l...
  • 计算最大不重复子串

    2019-01-02 15:38:31
    //这样设置键值是为了下次能做判断,如果从0开始,下次循环就可以判断当前 map.put(s.charAt(j), j ); } return ans; } // public static Node reverse(Node head){ // //如果是空链表或者尾结点 // if ...
  • 给定一个字符串,请你找出其中含有重复字符的 最长子串 的长度。示例 1:输入: “abcabcbb”输出: 3解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。示例 2:输入: “bbbbb”输出: 1解释: 因为无重复...
  • 本文转载自【微信公众号:机器学习算法与Python精研,ID:AITop100】经微信公众号授权转载,如需转载与原文作者联系题目:给定一个字符串,找出含有重复字符的最长子串的长度。示例:给定 "abcabcbb" ,没有重复...
  • 题目:给定一个字符串,找出含有重复字符的最长子串的长度。示例:给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3。...采用Python的set,可以知道无重复子串的可能的最大长度,...
  • 给定一个字符串,请你找出其中含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 #include <stdio.h> #include <...
  • 最大不重复子串(Java)

    千次阅读 2017-04-20 13:26:49
    一个经典问题,就是求字符串中包含重复字符的最大子串。如果有多个这样的子串,则输出第一个。 我的思路其实也就是从头比较到尾来找,只是中间加了一些判断条件进行了优化。具体流程(先转化成char[] ch): 1、...
  • 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 ...
  • 题目:找到给定字符串(由小写字符组成)中的最长子串T,要求T中的每一字符出现次数都少于k。输出T的长度。示例 1:输入:s = "aaabb", k = 3输出:3最长子串为 "aaa" ,其中 ‘a‘ 重复了 3 次。示例 2:输入:s = ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 712
精华内容 284
关键字:

最大不重复子串