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

Thaddeus 永久会员 2024年5月6日上午9:39

打卡

class Solution {
    public int dismantlingAction(String arr) {
        Map<Character, Integer> dic = new HashMap<>();
        int l = -1, n = arr.length(), res = 0;
        for(int r = 0; r < n; r++) {
            if(dic.containsKey(arr.charAt(r))) {
                if(dic.get(arr.charAt(r)) < l) l = l;
                else l = dic.get(arr.charAt(r));
                //l = Math.max(l, dic.get(arr.charAt(r))); // 将l移动到无重复值的区间左侧，且要最大
            }  // 取最大，是因为可能此时arr[r]对应的字符已经是在l左侧了，不在当前的无重复区间，因此l无需改变
                // 为什么已经在左侧了呢？因为其他字符重复了，且在它右边，就把它割掉了，此时该字符其实根本就不重复，因此不用更新左边界
            dic.put(arr.charAt(r), r);
            res = Math.max(res, r - l);
        }
        return res;
    }
}

0 赞同 0 条回复

=.= 普通 2024年4月15日下午2:57

class Solution {
public int dismantlingAction(String arr) {
int n = arr.length();
int ans = 0;

    int left = 0;
    int right = 0;
    HashMap<Character, Integer> window = new HashMap<>();

    while(right < n){
        char c = arr.charAt(right);
        right++;
        window.put(c, window.getOrDefault(c, 0) + 1);
        if(window.get(c) == 1){
            ans = Math.max(ans, window.size());
        }

        while(window.get(c) > 1){
            char d = arr.charAt(left);
            if(window.get(d)>1){
                window.put(d, window.get(d)-1);
            }
            else{
                window.remove(d);
            }
            left++;
        }
    }

    return ans;
}

}

时间：O(n)
空间：O(n)

0 赞同 0 条回复

神经蛙普通 2024年4月3日下午11:31

class Solution {
public:
int dismantlingAction(string arr) {
unordered_map<char, int> dic;
int res = 0, tmp = 0, len = arr.size(), i;
for(int j = 0; j < len; j++) {
if (dic.find(arr[j]) dic.end()) i = – 1;
else i = dic.find(arr[j])->second; // 获取索引 i
dic[arr[j]] = j; // 更新哈希表
tmp = tmp < j – i ? tmp + 1 : j – i; // dp[j – 1] -> dp[j]
res = max(res, tmp); // max(dp[j – 1], dp[j])
}
return res;
}
};
打卡

0 赞同 0 条回复

Jimmy 普通 2024年4月3日下午5:14

时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:
    int dismantlingAction(string arr) {
        unordered_map<char,int> dic;
        int res = 0,tmp = 0,len = arr.size(),i;
        for(int j=0;j<len;j++)
        {
            if(dic.find(arr[j]) == dic.end()) i = -1;
            else i = dic.find(arr[j])->second;
            dic[arr[j]] = j;//更新哈希表
            tmp = tmp < j-i ? tmp + 1 : j-i;// 转移方程
            res = max(res,tmp);
        }
        return res;
    }
};

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年4月3日下午2:24

class Solution {
    public int dismantlingAction(String arr) {
        if(arr == null || arr.length() <= 0){
            return 0;
        }

        Map<Character,Integer> map = new HashMap<>();

        //含义：以i结尾的字符串中的最大无重复子字符串的长度
        int[] dp = new int[arr.length()]; 
        //初始值
        dp[0]=1;

        map.put(arr.charAt(0), 0);
        int res = 1;

        for(int i=1;i<arr.length();i++){
            if(!map.containsKey(arr.charAt(i))){
                dp[i]=dp[i-1]+1;
            }else{
                int k = map.get(arr.charAt(i));
                dp[i]= i-k<=dp[i-1]? i-k : dp[i-1]+1;
            }
            res=Math.max(dp[i],res);
            map.put(arr.charAt(i),i);
        }

        return res;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

优化做法

// 优化版本
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() <= 0){
            return 0;
        }
        // 优化 => 单个变量
        Map<Character,Integer> map = new HashMap<>();
        //int[] dp = new int[s.length()];
        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;
        // 时间On,空间On
    }

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

方铎码农普通 2024年4月1日下午11:22

class Solution {
    public int dismantlingAction(String arr) {
        //哈希表记录字符最后一次出现的位置
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, len = arr.length(),i = -1,tmp = 0;
        for(int j = 0; j < len; j++){
            //固定右边界 j ，设字符左边距离最近的相同字符为 arr[i]，即 arr[i]=arr[j]
            i =  dic.getOrDefault(arr.charAt(j),-1);

            //i < 0, 即arr[j]左边无相同字符，则dp[j] = dp[j-1]+1
            //dp[j-1] < j-i, i在子字符串之外，dp[j] = dp[j-1]+1
            //dp[j-1] >= j-i，dp[j] = j - i;
            dic.put(arr.charAt(j),j);
            //tmp为暂时的最长字符串长度，在有哈希表记载最后一次出现某字母位置的情况下，无需dp数组记录，节约空间到O(1)复杂度
            tmp = tmp<j-i?tmp+1:j-i;
            res = Math.max(res,tmp);
        }

        return res;
    }
}

时间复杂度$O(n)$，空间复杂度$O(1)$

0 赞同 0 条回复

heathhou 普通 2024年4月1日下午11:20

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

        unordered_map<char, int> mp;
        int dp = 1;

        mp[arr[0]] = 0;
        int res = 1;

        for(int i = 1; i < arr.length(); ++i){
            if(mp.find(arr[i]) == mp.end()){
                dp++;
            }else{
                int k = mp[arr[i]];
                dp = (i - k <= dp) ? (i - k) : (dp + 1);
            }

            res = max(res, dp);
            mp[arr[i]] = i;
        }

        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

紫芝普通 2024年4月1日下午10:32

思路：滑动窗口

“`c++
class Solution {
public:
int dismantlingAction(string arr) {
if (arr.size() == 0) return 0;
int maxi = 0, left = 0;
map m;
for (int i=0; i 1) {
// maxi = max(maxi, i – left);
while (left < i && arr[left] != arr[i]) { m[arr[left]]--; left++; } left++; m[arr[i]]--; } maxi = max(maxi, i - left + 1); } return maxi; } }; ```

0 赞同 0 条回复

云无深雁影普通 2024年4月1日下午8:51

//滑动窗口
class Solution {
public int dismantlingAction(String arr) {
HashSet set = new HashSet<>();
int maxLength = 0;
int fastPtr = -1;
int slowPtr = 0;
while(fastPtr < arr.length()-1){
fastPtr++;
while(set.contains(arr.charAt(fastPtr))){
set.remove(arr.charAt(slowPtr));
slowPtr++;
}
set.add(arr.charAt(fastPtr));
maxLength = Math.max(maxLength,fastPtr – slowPtr + 1);

}
return maxLength;

}
}
//动态规划
class Solution {
public int dismantlingAction(String arr) {
if(arr.length() 0)
return 0;
HashMap<Character,Integer> lastLoc = new HashMap<>();
int max = 1;
int[] dp = new int[arr.length()];
dp[0] = 1;
lastLoc.put(arr.charAt(0),0);
for(int i = 1; i < arr.length(); i++){
if(!lastLoc.containsKey(arr.charAt(i))){
dp[i] = dp[i-1] + 1;
}else{
int j = lastLoc.get(arr.charAt(i));
if(i – j > dp[i-1]){
dp[i] = dp[i-1] + 1;
}
else{
dp[i] = i – j;
}
}
lastLoc.put(arr.charAt(i),i);
max = Math.max(max,dp[i]);
}
return max;
}
}
//两种方法时间复杂度均为O1 空间复杂度均为On

0 赞同 0 条回复

王位詮釋普通 2024年4月1日下午4:19

普通版本：
class Solution {
    public int dismantlingAction(String arr) {
        if(arr==null||arr.length()<=0){
            return 0;
        }
        Map<Character,Integer> map = new HashMap<>();
        int[] dp = new int[arr.length()];
        dp[0] = 1;
        map.put(arr.charAt(0),0);
        int max = 1;
        for(int i=1;i<arr.length();i++){
            if(!map.containsKey(arr.charAt(i))){
                dp[i] = dp[i-1]+1;
            }else{
                int k = map.get(arr.charAt(i));
                dp[i] = i-k<=dp[i-1]?i-k:dp[i-1]+1;
            }
            max = Math.max(max,dp[i]);
            map.put(arr.charAt(i),i);
        }
        return max;
    }
}
时间复杂度：O(n)
空间复杂度：O(n)
优化版本：
class Solution {
    public int dismantlingAction(String arr) {
        if(arr==null||arr.length()<=0){
            return 0;
        }
        Map<Character,Integer> map = new HashMap<>();
        int a = 1;
        map.put(arr.charAt(0),0);
        int max = 1;
        for(int i=1;i<arr.length();i++){
            if(!map.containsKey(arr.charAt(i))){
                a = a+1;
            }else{
                int k = map.get(arr.charAt(i));
                a = i-k<=a?i-k:a+1;
            }
            max = Math.max(max,a);
            map.put(arr.charAt(i),i);
        }
        return max;
    }
}
时间复杂度：O(n)
空间复杂度：因为用了哈希表，所以感觉也是O(n)
自己写的，算是滑动窗口双指针吧：
class Solution {
    Set<Character> set = new HashSet<>();
    public int dismantlingAction(String arr) {
        int left = 0;
        int right = 0;
        int length = arr.length();
        int max = 0;
        while(right<length){
            char temp = arr.charAt(right);
            if(set.contains(temp)){
                set.remove(arr.charAt(left));
                left++;
            }else{
                set.add(temp);
                max = Math.max(max,set.size());
                right++;
            }
        }
        return max;
    }
}

0 赞同 0 条回复

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

共以下 10 个回答

# 回答此问题取消回复

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

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复