精华内容
下载资源
问答
  • Offer 48. 最长不含重复字符的子字符串 难度中等 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串...

    剑指 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;

        }

    }

    展开全文
  • 使用循环实现。其中创建了一个长度为26的辅助数组,存放各字符在字符串中最后出现的位置。 /** ... *Filename: *Author: Zhang Peng *Date: *Version: *Description:剑offer<... 面试题48 最长不含重复字符的子...

    使用循环实现。其中创建了一个长度为26的辅助数组,存放各字符在字符串中最后出现的位置。

    /**
     *Copyright @ 2019 Zhang Peng. All Right Reserved.
     *Filename:
     *Author: Zhang Peng
     *Date:
     *Version:
     *Description:剑指offer<第二版> 面试题48 最长不含重复字符的子字符串
    **/
    
    #include<iostream>
    using namespace std;
    
    int findLongStr(char * str)
    {
    	
    	int s = strlen(str);
    	if (s == 0)
    		return 0;
    	int record[26];
    	for (int i = 0; i < 26; i++)
    		record[i] = -1;
    	int start = 0;
    	record[str[0] - 'a'] = 0;
    	int maxlen = 1;
    	for (int i = 1; i < s; i++)
    	{
    		int findindex = str[i] - 'a';
    		int len = 0;
    		if (record[findindex] == -1)
    			len = i - start + 1;
    		else
    		{	
    			if (record[findindex]<start)
    				len = i - start + 1;
    			else
    			{
    				len = i - record[findindex];
    				start = record[findindex]+1;
    			}		
    		}
    		if (len>=maxlen)
    		{
    			cout << "length " << len << " str:" << endl;
    			maxlen = len;
    			for (int k = start; k < (start+maxlen); k++)
    				cout << str[k];
    			cout << endl;
    		}	
    		record[findindex] = i;   //记录最新的字符所处位置
    	}
    	return maxlen;
    }
    
    
    int main()
    {
    	char * testcase = "arabcaacfr";
    	int num = findLongStr(testcase);
    
    	cout << "max num: " << num << endl;
    
        system("pause");
        return 0;
    }
    
    

    运行结果如下:
    在这里插入图片描述

    展开全文
  • 文章目录面试题48:最长不含重复字符的子字符串一、题目描述二、问题分析三、问题解决 面试题48:最长不含重复字符的子字符串 一、题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符...

    面试题48:最长不含重复字符的子字符串

    一、题目描述

    请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。假设字符串中只包含从’a’到’z’的字符。

    例如,在字符串“arabcacfr”中,最长的不含重复字符的子字符串是“acfr”,长度为4.

    二、问题分析

    遇到问题,先分析问题,由分析的结果确定所运用的算法。

    一般而言,我们都会在纸上动笔画画,罗列一些基本的情况。这道题分析之后,可以找到关系式。

    定义函数f(i)为:以第i个字符为结尾的不含重复字符的子字符串的最大长度。
    (1)当第i个字符之前未出现过,则有:f(i)=f(i-1)+1
    (2)当第i个字符之前出现过,记该字符与上次出现的位置距离为d

    1. 如果d<=f(i-1),则有f(i)=d;
    2. 如果d>f(i-1),则有f(i)=f(i-1)+1;

    可以从第一个字符开始遍历,定义两个int变量preLength和curLength来分别代表f(i-1)和f(i),并创建一个长度为26的pos数组来存放26个字母上次出现的位置,即可根据上述说明进行求解。

    三、问题解决

        public int  maxLength(String str) {
            if(str==null || str.length()<=0) {
                return 0;
            }
            // 即f(i-1)
            int preLength=0;
            // 即f(i)
            int curLength;
            int maxLength=0;
            // 用于存放字母上次出现的位置
            int[] pos= new int[26];
            Arrays.fill(pos, 0);
    
            for(int i=0;i<str.length();i++) {
                int letterNumber = str.charAt(i)-'a';
                if(pos[letterNumber]<0 || i-pos[letterNumber]>preLength) {
                    curLength=preLength + 1;
                } else {
                    curLength=i-pos[letterNumber];
                }
                pos[letterNumber]=i;
                if(curLength>maxLength) {
                    maxLength=curLength;
                }
                preLength=curLength;
            }
            return maxLength;
        }
    
    展开全文
  • 【剑Offer】48. 最长不含重复字符的子字符串

    多人点赞 热门讨论 2020-08-27 12:48:40
    输入一个字符串(只包含 a~z 的字符),求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr,最长不含重复字符的子字符串为 acfr,长度为 4。 解题思路 class Solution { public int ...

    力扣

    题目描述

    输入一个字符串(只包含 a~z 的字符),求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr,最长不含重复字符的子字符串为 acfr,长度为 4。

    解题思路

    class Solution {
        public int lengthOfLongestSubstring(String s) {
            int res = 0, left = 0;
            HashMap<Character, Integer> hash = new HashMap<>();
            for(int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if(hash.containsKey(c)) {
                    left = Math.max(left, hash.get(c) + 1);
                }
                hash.put(c, i);
                res = Math.max(res, i - left + 1);
            }
            return res;
        }
    }
    
    展开全文
  • offer 48.最长不含重复字符的子字符串
  • offer48:最长不含重复的字符字串 题目:请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,...
  • package ... import java.util.ArrayList; import java.util.LinkedList; import java.util.List; ... * @Class LengthOfLongestSubstring * @Description 剑offer 48 最长不含重复字符的子字符串 ...
  • offer 48 最长不含重复字符的子字符串 动态规划 class Solution { public int lengthOfLongestSubstring(String s) { if(s.isEmpty()){ return 0; } int len = s.length(); int[] dp = new int[len]; ...
  • offer48. 最长不含重复字符的子串 P236 leetcode 3 题目:请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。假设字符串中只包含从’a’到’z’的字符。 用压缩优化后的dp,...
  • Offer48.最长不含重复字符的子字符串 题目: 输入一个字符串s,返回其中最长的一段不含重复字符的子串长度; 思路: 1.双指针 + 滑动窗口:O(n),O(128):字符最多有128个 [ i,j ]表示一个不含重复元素的...
  • [剑offer]最长不含重复字符的子字符串 剑offer-最长不含重复字符的子字符串 题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例 1: 输入: “abcabcbb” 输出: 3 ...
  • * 最长不含重复字符的子字符串 * 用双指针i,j分别指向第一第二个元素,当j发现了重复元素,则从i的下一位开始搜索。 * * 代码中用了个trick,用vector生成256个-1,用来存储每个字符上一次出现的下标。 */ ...
  • Offer 48. 最长不含重复字符的子字符串 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,...
  • java script版 - 剑 48. 最长不含重复字符的子字符串 - 难度中等(动态规划、哈希表、双指针)
  • offer 48. 最长不含重复字符的子字符串 题目描述 解题思路 滑动窗口 class Solution { public int lengthOfLongestSubstring(String s) { if (s == null || s.length() == 0) return 0; //窗口的左右边界,...
  • 输入一个字符串(只包含 a~z 的字符),求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr,最长不含重复字符的子字符串为 acfr,长度为 4。 public int longestSubStringWithoutDuplication(String str) {...
  • 题目: 请从字符串中找出一个...例如,在字符串“arabcacfr”中,最长的不含重复字符的子字符串是"acfr",长度为4. //数组 最长不重复的字符串长度 // 动态规划 public static void gui(String str){ if(st...
  • Offer(Python多种思路实现):最长不含重复字符的子字符串 面试48题: 题目:最长不含重复字符的子字符串 题:请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长字符串的长度。假设字符串中只包含...
  • Offer 48.最长不含重复字符的子字符串 暴力法需要O(n^2),我们可以借助哈希表查找,只需要O(1)的时间,整体时间复杂度就降到了O(n) class Solution { public int lengthOfLongestSubstring(String s) { ...
  • 题目:输入一个字符串(只包含 a~z 的字符),求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr,最长不含重复字符的子字符串为 acfr,长度为 4。 思路: 1、如果遍历到的字符没有出现过,则f(i)=f(i-1)...
  • /** 题目:最长不含重复字符的子字符串* 解法:动态规划* 定义函数f(i)表示以第i个字符结尾的包含当前字符的不含重复字符的子字符串的最长长度* 如果当前的第i个字符没有出现过,那么f(i)=f(i-1)+1,如果已经出现过,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,799
精华内容 20,319
关键字:

不含指什么