精华内容
下载资源
问答
  • 2021-07-01 09:03:07

    剑指 Offer 48. 最长不含重复字符的子字符串

    难度中等

    请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

    示例 1:

    输入: "abcabcbb"

    输出: 3

    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

    示例 2:

    输入: "bbbbb"

    输出: 1

    解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

    示例 3:

    输入: "pwwkew"

    输出: 3

    解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

    请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

    提示:

    • s.length <= 40000

    注意:本题与主站 3 题相同:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

    class Solution {

        public int lengthOfLongestSubstring(String s) {

                int max = 0;

                int start = 0;

                HashMap<Character, Integer> hashMap = new HashMap<>(s.length());

                for (int i = 0; i < s.length(); i++) {

                    char c = s.charAt(i);

                    if (hashMap.containsKey(c)) {

                        max = Math.max(max, i - start);

                        start =Math.max(start, hashMap.get(c)+1);

                    }

                    hashMap.put(c, i);

                }

                max = Math.max(max, s.length() - start);

            return max;

        }

    }

    更多相关内容
  • Offer(Python多种思路实现):最长不含重复字符的子字符串 面试48题: 题目:最长不含重复字符的子字符串 题:请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长字符串的长度。假设字符串中只包含...
  • 最长不含重复字符的子字符串 JavaScript剑Offer题解 包含数组、对象、链表、堆栈、树等经典题型 ☕️每天一道,轻松不累 详细的题目解析,收藏方便阅读 在线star地址 在线阅读地址 在线阅读地址 请从字符串中找...

    剑指 Offer 48.最长不含重复字符的子字符串

    JavaScript剑指Offer题解

    🚀包含数组、对象、链表、堆栈、树等经典题型
    ☕️每天一道,轻松不累
    💬详细的题目解析,收藏方便阅读
    🙏在线star地址

    在线阅读地址

    在线阅读地址

    请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

    示例 1:

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

    示例 2:

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

    解法一:暴力搜索

    var lengthOfLongestSubstring = function(s) {
        let res = [];
        let i = 0;
        let len = 0;
        while (i < s.length) {
            const cur = s[i];
            const findI = res.findIndex((v) => v === cur);
    
            if (findI === -1) {
                res.push(cur);
            } else if (findI === 0) {
                res.push(res.shift());
            } else {
                res = res.slice(findI + 1);
                res.push(cur);
            }
            // max
            len = Math.max(len, res.length);
            i++;
        }
        return len;
    };
    

    解法二:动态窗口

    var lengthOfLongestSubstring1 = function(s) {
        let i = 0,
            j = 0;
        let ans = 0;
        const map = {};
        while (i < s.length && j < s.length) {
            if (!map[s[j]]) {
                ans = Math.max(j - i + 1, ans);
                map[s[j]] = true;
                ++j;
            } else {
                // 如果char重复,那么缩小滑动窗口,并更新对应的map
                map[s[i]] = false;
                ++i;
            }
        }
        return ans;
    };
    

    写在最后

    本篇是剑指Offer的第23题,俗话说好的合理的数据结构+算法才是写好代码的关键,不妨跟我一起来吧~

    热门开源项目

    在这里插入图片描述

    展开全文
  • 如在"arabcacfr”中,最长的不含重复字符的子字符串是"rabc" / “acfr”,长度为4。 我们可以找出字符串的所有子字符串,然后就可以判断每个子字符串中是否包含重复的字符。但是这种暴力法的缺点也不言而喻,效率很...

    题目:请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。假设字符串中只包含’a’~’z’的字符。如在"arabcacfr”中,最长的不含重复字符的子字符串是"rabc" / “acfr”,长度为4。

    分析:
    不难找出字符串的所有子字符串,然后判断每个子字符串中是否包含重复的字符。但这种暴力法的缺点也不言而喻,效率很低。

    我们试着用动态规划的思想来看解这道题,首先定义函数f(i)表示以第i个字符为结尾的不包含重复字符的子字符串的最长长度。我们从左到右逐一扫描字符串中的每个字符。当我们计算以第i个字符为结尾的不包含重复字符的子字符串的最长长度f(i)时,我们已经知道f(i-1)了。如果第i个字符之前没有出现过,那么f(i)=f(i-1)+1。例如,在字符串“arabcacfr”中,显然f(0)等于1。在计算f(1)时,下标为1的字符r之前没有出现过,因此f(1)等于2,即f(1)=f(0)+1。到目前为止,最长的不含重复字符的子字符串是"ar”。如果第i个字符之前已经出现过,那情况就要复杂一点了。

    我们先计算第i个字符和它上次出现在字符串中的位置的距离,并记为d,接着分两种情形分析。第一种情形是d小于或者等于f(i-1),此时第i个字符上次出现在f(i-1)对应的最长子字符串之中,因此f(i)=d。同时这也意味着在第i个字符出现两次所夹的子字符串中再也没有其他重复的字符了。在前面的例子中,我们继续计算f(2),即以下标为2的字符’a’为结尾的不含重复字符的子字符串的最长长度。我们注意到字符’a’在之前出现过,该字符上一次出现在下标为0的位置,它们之间的距离d为2,也就是字符’a’出现在f(1)对应的最长不含重复字符的子字符串"ar”中,此时f(2)=d,即f(2)=2,对应的最长不含重复字符的子字符串是"ra”。

    第二种情形是d大于f(i-1),此时第i个字符上次出现在f(i-1)对应的最长子字符串之前,因此仍然有f(i)=f(i-1)+1。我们接下来分析以字符串"arabcacfr”最后一个字符r为结尾的最长不含重复字符的子字符串的长度,即求f(8)。以它前一个字符f为结尾的最长不含重复字符的子字符串是"acf”,因此(7)=3。我们注意到最后一个字符r之前在字符串"arabcacft”中出现过,上一次出现在下标为1的位置,因此两次出现的距离d等于7,大于f(7)。这说明上一个字符r不在f(7)对应的最长不含重复字符的子字符串"acf”中,此时把字符r拼接到"acf”的后面也不会出现重复字符。因此f(8)=f(7)+1,f(8)=4,对应的最长不含重复字符的子字符串是“acft”。

    #include<iostream>
    #include<string.h>
    using namespace std;
    int longestSubStirngWithoutDuplication(string str)
    {
    	int curlength = 0;//当前字符位置不重复字串的最长长度
    	int maxlength = 0;
    
    	int position[26] = {-1}; 
    
    	for(int i = 0;i < str.length();i++){
    		int preIndex = position[str[i]-'a'];
    		if(preIndex < 0 || i-preIndex > curlength)
    		//该字符第一次出现或者现在出现的位置和上一次出现的位置间距离大于f(i-1)
    			curlength++;
    		else 
    		{  //更新最大长度
    			if(curlength > maxlength)
    				maxlength = curlength;
               //d<f(i-1),则f(i)等于d
    			curlength = i- preIndex;
    		}
    		position[str[i]-'a'] = i; //该字符这次出现的位置
    	}
    	if(curlength > maxlength){
    		maxlength = curlength;
    	}
    	return maxlength;
    }
    
    int main()
    {
    	string str = "arabcacfr";
    
    	cout<<longestSubStirngWithoutDuplication(str)<<endl;
    
    	return 0;
    }
    

    在这里插入图片描述

    我们使用数组position来记录该字符出现的位置,刚开始都初始化为-1;如果出现过则里面的数值将会大于等于0。

    展开全文
  • Offer 48 最长不含重复字符的子字符串 题解一: class Solution { public: int lengthOfLongestSubstring(string s) { int res = 0, temp = 0; unordered_map<char, int> map; for(int j = 0;...

    题目链接:

    剑指 Offer 48 最长不含重复字符的子字符串

     

    题解一:

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) 
        {
            int res = 0, temp = 0;
            unordered_map<char, int> map;
            for(int j = 0; j < s.size(); ++j)
            {
                int count = map.count(s[j]);
                int i = count ? map[s[j]] : -1;
                map[s[j]] = j;
                temp = temp < j - i ? temp + 1 : j - i;
                res = max(res, temp);
            }
            return res;
        }
    };

     

    解题思路:

    动态规划思想就是每一步的求解都与上一步有关,根据上一步的结果求这一步的解。

    这道题先找到每一步之间的对应关系:(j - i)是以当前字符为结尾的无重复字符的最大长度,如果这一步的字符在之前(j - i)这个范围内出现过,那么以当前字符为结尾的无重复字符的最大长度就是(j - i);否则最大长度是上一字符最大长度加1,这就是每一步求解之间的关系。

    另外哈希表的用法值得注意。

     

    题解二:

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) 
        {
            int res = 0, temp = 0;
            for(int j = 0; j < s.size(); ++j)
            {
                int i = j - 1;
                while(i >= 0 && s[i] != s[j])
                    --i;
                temp = temp < j - i ? temp + 1 : j - i;
                res = max(res, temp);
            }
            return res;
        }
    };

     

    解题思路:

    这个方法不用哈希表确定上一个出现该字符的位置,而是采用从后向前遍历的方法。理论上时间复杂度更高,但是实际耗时反而更少了,空间还用的更少了...

     

     

    题解三:

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) 
        {
            int res = 0, i = -1;
            unordered_map<char, int> map;
            for(int j = 0; j < s.size(); ++j)
            {
                if(map.count(s[j]))
                    i = max(map[s[j]], i);
                map[s[j]] = j;
                res = max(res, j - i);
            }
            return res;
        }
    };

     

    解题思路:

    双指针+哈希表

    i指向子串的左边界,j指向子串的右边界。每次循环都要重新判断左边界

    展开全文
  • * 最长不含重复字符的子字符串 * * @param str * @return */ public int longestSubstringWithoutDuplication(String str) { if (null == str || 0 == str.length()) return 0; //记录字母最后一次出现的...
  • 描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 数据范围: \ \text{s.length}\le 40000 s.length≤40000 示例1 ...输入:"abcabcbb" ...说明:因为无重复字符的最长子串是"abc...
  • 题目描述: 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。...
  • 对于示例一中的字符串,我们列举出这些结果,其中括号中表示选中的字符以及最长的字符串: 以第1个字符a开头的不含重复字符的最长子串为(abc)abcbb 以第2个字符b开头的不含重复字符的最长子串为a(bca)bcbb 以第3个...
  • Offer II 016. 不含重复字符的最长子字符串 题目描述 给定一个字符串 s ,请你找出其中不含有重复字符的 最长连续子字符串 的长度。 示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子字符...
  • 一、原题描述 剑 Offer 48. 最长不含重复字符的子字符串 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串...
  • 【剑Offer】48. 最长不含重复字符的子字符串

    多人点赞 热门讨论 2020-08-27 12:48:40
    输入一个字符串(只包含 a~z 的字符),求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr,最长不含重复字符的子字符串为 acfr,长度为 4。 解题思路 class Solution { public int ...
  • Offer 48. 最长不含重复字符的子字符串 class Solution { public: int lengthOfLongestSubstring(string s) { int len=s.length(),maxlen=0,j=-1; //j=-方便最初自动右移 unordered_set<char> occur; ...
  • 原来的做法错的 请看评论 link 转载于:https://www.cnblogs.com/xzm123/p/9868642.html
  • 题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 思路 详见链接 代码 class Solution: def lengthOfLongestSubstring(self,s): result = 0 low = 0 ...
  • 文章目录面试题48:最长不含重复字符的子字符串一、题目描述二、问题分析三、问题解决 面试题48:最长不含重复字符的子字符串 一、题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符...
  • Offer 48. 最长不含重复字符的子字符串 难度中等187收藏分享切换为英文接收动态反馈 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例 1: 输入: "abcabcbb" 输出: 3 ...
  • 使用循环实现。其中创建了一个长度为26的辅助数组,存放各字符在字符串中最后出现的位置。 /** ... *Filename: *Author: Zhang Peng *Date: *Version: *Description:剑offer<... 面试题48 最长不含重复字符的子...
  • 假设字符串只包含 'a'~'z' 的字符的,例如在字符串“arabcacfr”中,最长不含重复字符的子字符串为 “acfr”,长度为 4。 测试用例 功能测试(包含多个字符的字符串;只要一个字符的字符串;所有都唯一的字符串...
  • Offer 48. 最长不含重复字符的子字符串 题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 ...
  • 最长不含重复字符的子字符串
  • # 举例 public class Main_48 { public static void main(String[] args) { String str = "abcdcbefc"; System.out.println(maxsubstr(str)); } private static int maxsubstr(String str) { ...
  • public static String nodup_String(String str){ char ch[]=str.toCharArray(); int[] pos=new int[25];//记录每个字母的上一次出现的位置 for (int i=0;i&lt;25;i++){ pos[i]=-1; } ...
  • 题目: 请从字符串中找出一个...例如,在字符串“arabcacfr”中,最长的不含重复字符的子字符串是"acfr",长度为4. //数组 最长不重复的字符串长度 // 动态规划 public static void gui(String str){ if(st...
  • 题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 思路 动态规划。设f(i)表示以第i个字符为结尾的不包含重复字符的子字符串的最长长度。那么当第i个字符之前没有...
  • [48]最长不含重复字符的子字符串 文章目录[48]最长不含重复字符的子字符串题目思路代码 题目 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度 假设字符串中只包含从’a’到’z’的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 58,962
精华内容 23,584
关键字:

不含指什么