【动态规划专题】剑指 Offer 48. 最长不含重复字符的子字符串-跟着帅地玩副业，开拓第二曲线PlayOffer

hi 普通 2023年11月23日下午2:50

每个字符以它结尾的最长不重复字符串可能出现两种情况
不与上个字串中的字符冲突或没在记录字符的哈希表中出现过的话，数量+1
出现在上个字串内的话，数量变为i – h[arr[i]]

class Solution {
public:
    int dismantlingAction(string arr) {
        if(!arr.size()) return 0;

        //该位置能获取的最大子串
        int dp[40000];
        unordered_map<char, int> h;
        int n = arr.size();
        dp[0] = 1;
        int res = 1;
        h[arr[0]] = 0;

        for(int i = 1; i < n; i++){
            if(!h.count(arr[i]) || h[arr[i]] < i - dp[i - 1]) dp[i] = dp[i - 1] + 1;
            else dp[i] = i - h[arr[i]];
            h[arr[i]] = i;
            res = max(res, dp[i]);
        }

        return res;
    }
};

0 赞同 0 条回复

June 普通 2023年10月16日下午9:02

class Solution {
    public int dismantlingAction(String arr) {
        int n = arr.length();
        if (n == 0)
            return 0;
        Map<Character,Integer> lastLoc = new HashMap<>();
        int tmp = 0; int res = 0;
        for(int j = 0 ;j < n;j++) {
            int i = lastLoc.getOrDefault(arr.charAt(j),-1); // 记录最近一次相等字符的下标
            lastLoc.put(arr.charAt(j),j);
            if (i < 0)
                tmp++;
            else if(tmp < j-i)
                tmp++;
            else
                tmp = j - i;
            res = Math.max(tmp, res);
        }
        return res;
    }
}

0 赞同 0 条回复

Marshan 普通 2023年8月31日下午8:23

class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if(n 0){
return 0;
}
vector dp(n,0);
unordered_map<char,int> hashMap;
int res = 1;
// dp[i]表示以s[i]结尾时不重复字符的字符串长度
dp[0] = 1;
hashMap[s[0]] = 0;
for(int i = 1;i < n;++i){
if(hashMap.find(s[i]) hashMap.end()){
dp[i] = dp[i-1] + 1;
}
else{
if(i – hashMap[s[i]] > dp[i-1]){ //重复字符不影响
dp[i] = dp[i-1] + 1;
}
else{
dp[i] = i – hashMap[s[i]];
}
}
res = max(res,dp[i]);
hashMap[s[i]] = i;
}
return res;
}
};

0 赞同 0 条回复

人生何处不青山普通 2023年8月20日下午10:18

简单DP

function lengthOfLongestSubstring(s: string): number {
    let dir: Map<string, number> = new Map();
    let t = -1;
    let res = 0;
    for (let i = 0; i < s.length; i++) {
        if(dir.has(s.charAt(i))) {
            t = Math.max(t,dir.get(s.charAt(i)));
        }
        dir.set(s.charAt(i),i);
        res = Math.max(res,i - t);
    }
    return res;
};

0 赞同 0 条回复

北辰普通 2023年8月16日下午5:24

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int l=0,r=0;
        Set<Character> set = new HashSet<>();
        int res = 0;
        while(r<n) {
            if(!set.contains(chars[r])) {
                set.add(chars[r]);
                r++;
            }else {
                while(set.contains(chars[r])) {
                    set.remove(chars[l]);
                    l++;
                }
            }
            res = Math.max(res, r-l);
        }
        return res;
    }
}

滑动窗口：O（n）

0 赞同 0 条回复

Mby 普通 2023年8月14日下午8:03

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() <= 0){
            return 0;
        }
        //优化 =》 单个变量
        Map<Character, Integer> map = new HashMap<>();

        int a = 1;
        map.put(s.charAt(0), 0);
        int res = 1;
        for(int i = 1; i < s.length(); i++){
            if(!map.containsKey(s.charAt(i))){
                a = a + 1;//就是没刷新a之前， a表示dp[i - 1]
            }else{
                int k = map.get(s.charAt(i));
                a = i - k <= a ? i - k : a + 1;
            }
            res = Math.max(res,a);
            map.put(s.charAt(i), i);
        }

        return res;
        //时间复杂度：O(n)
        //空间复杂度：O(n)
    }
}

0 赞同 0 条回复

NullPointerException 普通 2023年8月8日下午5:42

class Solution {
public int lengthOfLongestSubstring(String s) {
//通过滑动窗口加hash找到
//也可以动态
Map<String,Integer> map =new HashMap<String,Integer>();
String s1[]=s.split(“”);
if(s.equals(“”)) return 0;
if(s1null||s1.length 0)
{
return 0;
}
int max= 1;
int left = 0;
map.put(s1[0],0);
for(int i=1;i<s1.length;i++)
{
if(!map.containsKey(s1[i]))
{
map.put(s1[i],i);
}else
{
left = Math.max(map.get(s1[i])+1,left);
map.put(s1[i],i);
}
max= Math.max(max,i-left+1);
}
return max;
}
}

0 赞同 0 条回复

AD钙奶普通 2023年8月8日下午2:38

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        //以字符s[i]为结尾的不含重复字符的字符串
        int res = 0, tmp = 0;
        for(int i = 0; i < s.length(); i ++) {
            int j = map.getOrDefault(s.charAt(i),-1);
            map.put(s.charAt(i),i);
            tmp = tmp < i - j ? tmp + 1 : i - j;
            res = Math.max(res,tmp);
        }
        return res;
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月7日下午7:33

8.7
Day28：下面是代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //HashMap
        //将Character映射到Integer,根据字符来查找它最近出现的索引
        Map<Character, Integer> dic = new HashMap<>();
        int tmp = 0, res = 0;
        for(int j = 0; j < s.length(); j++){
            //获取最近的相同字符索引，若没有，默认为-1，此时tmp + 1
            int i = dic.getOrDefault(s.charAt(j), -1);
            dic.put(s.charAt(j), j);
            tmp = tmp < j - i ? tmp + 1 : j - i;
            res = Math.max(tmp, res);
        }
        return res;
    }
}

0 赞同 0 条回复

阿尚普通 2023年8月7日下午5:33

//滑动窗口
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0;
        Map<Character, Integer> map = new HashMap<>();
        int maxLen = 1;
        int j = 0;
        for(int i = 0; i < s.length(); i++){
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
            while(map.get(s.charAt(i)) > 1){
                map.put(s.charAt(j), map.get(s.charAt(j)) - 1);
                j++;
            }
            maxLen = Math.max(maxLen, i - j + 1);
        }
        return maxLen;
    }
}

0 赞同 0 条回复

【动态规划专题】剑指 Offer 48. 最长不含重复字符的子字符串

共以下 10 个回答

# 回答此问题取消回复

【动态规划专题】剑指 Offer 48. 最长不含重复字符的子字符串

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复