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

晓宇普通 2024年12月30日下午10:15

class Solution {
public:
    int dismantlingAction(string arr) {
        if(arr.size() == 0) return 0;
        int num = 1;
        int n = arr.size();
        vector<int> dp(n); // 以i招式为结尾连续不重复的招式数
        unordered_map<char,int> map; //  string idx
        map[arr[0]] = 0; 
        dp[0] = 1;
        for(int i = 1; i < n; i++){
            if(map.find(arr[i]) == map.end()){
                dp[i] = dp[i - 1] + 1; 
            }else{
                int k = map[arr[i]];
                dp[i] = i- k <= dp[i - 1] ? i - k : dp[i-1] + 1;

            }
            num = max(num,dp[i]);
            map[arr[i]] = i;
        }
        return num;
        // o(n) o(n)
    }
};

class Solution {
public:
    int dismantlingAction(string arr) {
        if(arr.size() == 0) return 0;
        int num = 1;
        unordered_map<char,int> map; //  string idx
        map[arr[0]] = 0; 
        int dp = 1;// 以i招式为结尾连续不重复的招式数
        for(int i = 1; i < arr.size(); i++){
            if(map.find(arr[i]) == map.end()){
                dp += 1; 
            }else{
                int k = map[arr[i]];
                dp = i- k <= dp? i - k : dp + 1;

            }
            num = max(num,dp);
            map[arr[i]] = i;

        }
        return num;
        // o(n) o(1)

    }
};

0 赞同 0 条回复

陆狗陆狗普通 2024年12月27日上午10:23

解题思路
– 找到dp[]的关键字符串中连续不重复的最长值—》转换成问题 Max（以每一个字符结尾的连续不重复子字符串长度），因为目标问题一定是某个字符结尾的
– 是否重复以及下标的位置需要用Map去存储，这样可以减少时间复杂度
– dp[i]和dp[i-1]的关系，关键是看两者的连续字符串的起始点是否是一致的。如果是一致的，dp[i]=dp[i-1]+1，如果不一致dp[i]=i-最近重复的为arr[i]的下标。如何去判断呢？通过dp[i-1]的长度和新的长度之间的大小来判断
【题解1】未优化前

class Solution {
    public int dismantlingAction(String arr) {
        // 使用Map去存储最新的字符的下标,能够减少重新判断时间复杂度
        // 字符串中连续不重复的最长值---》转换成问题Max（以每一个字符结尾的连续不重复子字符串长度），因为目标问题一定是某个字符结尾的
        // dp[i] 以每一个字符结尾的连续不重复子字符串长度
        // dp[i]=如果dp[i-1]的左右下标涵盖了dp[i]的范围，那么dp[i]=dp[i-1]+1；如果没有涵盖，那么dp[i]=i-最近重复的为arr[i]的下标
        char[] arrays = arr.toCharArray();
        if (arrays.length == 0) {
            return 0;
        }
        // dp
        int[] dp = new int[arrays.length];
        Map<Character, Integer> char2IndexMap = new HashMap<>();
        // 初始化
        dp[0] = 1;
        char2IndexMap.put(arrays[0], 0);
        // 正常dp
        int maxAction = 1;
        for (int i = 1; i < arrays.length; i++) {
            Character current = arrays[i];

            // 【错误点】contains需要改成containsKey
            if (char2IndexMap.containsKey(current)) {
                int currentLeftIndex = char2IndexMap.get(current);
                // 关键，通过长度来判断是否覆盖了(关键是比较dp[i-1]和dp[i]的连续字符串的起点位置的关系)
                if (dp[i - 1] >= i - currentLeftIndex) {
                    // > 表示，原本dp的覆盖范围更加广，=表示，也表示原本dp的覆盖范围更加广（恰好是原本dp起点的后面一个数字）
                    dp[i] = i - currentLeftIndex;
                } else {
                    // < 表示原本dp的覆盖范围不足
                    dp[i] = dp[i - 1] + 1;
                }
            } else {
                dp[i] = dp[i - 1] + 1;
            }
            // 【错误】不能一开始就写，要到最后写
            char2IndexMap.put(current, i);
            maxAction = Math.max(maxAction, dp[i]);
        }
        return maxAction;

    }
}

错误点1：contains需要改成containsKey
错误点2：char2IndexMap.put(current, i);不能一开始就写，要到最后写

题解2：把dp[]优化成1个变量

class Solution {
    public int dismantlingAction(String arr) {
        // 使用Map去存储最新的字符的下标,能够减少重新判断时间复杂度
        // 字符串中连续不重复的最长值---》转换成问题Max（以每一个字符结尾的连续不重复子字符串长度），因为目标问题一定是某个字符结尾的
        // dp[i] 以每一个字符结尾的连续不重复子字符串长度
        // dp[i]=如果dp[i-1]的左右下标涵盖了dp[i]的范围，那么dp[i]=dp[i-1]+1；如果没有涵盖，那么dp[i]=i-最近重复的为arr[i]的下标
        char[] arrays = arr.toCharArray();
        if (arrays.length == 0) {
            return 0;
        }
        // dp
        int lastAction=1;
        Map<Character, Integer> char2IndexMap = new HashMap<>();
        char2IndexMap.put(arrays[0], 0);
        // 正常dp
        int maxAction = 1;
        for (int i = 1; i < arrays.length; i++) {
            Character current = arrays[i];

            // 【错误点】contains需要改成containsKey
            if (char2IndexMap.containsKey(current)) {
                int currentLeftIndex = char2IndexMap.get(current);
                // 关键，通过长度来判断是否覆盖了(关键是比较dp[i-1]和dp[i]的连续字符串的起点位置的关系)
                if (lastAction>= i - currentLeftIndex) {
                    // > 表示，原本dp的覆盖范围更加广，=表示，也表示原本dp的覆盖范围更加广（恰好是原本dp起点的后面一个数字）
                    lastAction = i - currentLeftIndex;
                } else {
                    // < 表示原本dp的覆盖范围不足
                    lastAction = lastAction + 1;
                }
            } else {
                lastAction = lastAction + 1;
            }
            // 【错误】不能一开始就写，要到最后写
            char2IndexMap.put(current, i);
            maxAction = Math.max(maxAction, lastAction);
        }
        return maxAction;

    }
}

0 赞同 0 条回复

Pendulumpal 普通 2024年12月25日下午7:36

遍历字符串，用hash表记录当前字符最后一次出现的位置

class Solution {
    public int dismantlingAction(String arr) {
        HashMap<Character, Integer> mp = new HashMap<>();
        int st=0;
        int res=0;
        for(int i=0;i<arr.length();i++){
            char ch=arr.charAt(i);
            if(!mp.containsKey(ch)){
                res=Math.max(res,i-st+1);
            }else if(mp.get(ch)<st){
                res=Math.max(res,i-st+1);       
            }else{
                st=mp.get(ch)+1;
                res=Math.max(res,i-st+1);
            }
            mp.put(ch, i); 
        }
        return res;
    }
}

0 赞同 0 条回复

秋山丽奈普通 2024年12月23日下午7:56

思路：使用滑动窗口+HashSet 处理

class Solution {
    public int dismantlingAction(String arr) {
        if(arr.equals("")){
            return 0;
        }
        HashSet<String> hash = new HashSet<String>();
        String[] input = arr.split("");

        int head = 0;
        int tail = 1;
        hash.add(input[0]);
        int count = 1;
        int max = 1;
        while(tail < input.length){
            count ++;
            while(hash.contains(input[tail])){
                // 当前元素 已存在 
                hash.remove(input[head]);
                head ++;
                count --;
            }

            hash.add(input[tail]);
            tail ++;

            max = Math.max(max, count);
        }

        return max;
    }
}

0 赞同 0 条回复

Aatorx 永久会员 2024年12月23日上午11:25

class Solution {
public:
    unordered_map<char,int> map;
    int dismantlingAction(string arr) {
        if(arr.empty()) {
            return 0;
        }
        int l = -1;
        int res = 0;
        for(int i = 0; i < arr.size(); i++) {
            if(map.find(arr[i]) != map.end()){
                l = max(l, map.find(arr[i])->second);
            }
            map[arr[i]] = i;
            res = max((i - l),res);
        }
        return res;
    }
};

时间复杂度O(N)，空间复杂度O(1)。

0 赞同 0 条回复

月下足迹普通 2024年12月22日上午11:10

public int dismantlingAction(String arr) {
Map<Character, Integer> dic = new HashMap<>();
int res = 0, tmp = 0, len = arr.length();
for(int j = 0; j < len; j++) {
int i = dic.getOrDefault(arr.charAt(j), -1); // 获取索引 i
dic.put(arr.charAt(j), j); // 更新哈希表
tmp = tmp < j – i ? tmp + 1 : j – i; // dp[j – 1] -> dp[j]
res = Math.max(res, tmp); // max(dp[j – 1], dp[j])
}
return res;
}

0 赞同 0 条回复

Kisara 普通 2024年12月22日上午10:55

动态规划哈希表存储下标

class Solution {
    public int dismantlingAction(String arr) {
        if(arr==null||arr.length()<=0) return 0;
        Map<Character,Integer> map=new HashMap<>();
        int pivoit=1;
        map.put(arr.charAt(0),0);
        int res=1;
        for(int i=1;i<arr.length();i++){
            if(!map.containsKey(arr.charAt(i))) pivoit+=1;
            else {
                int k=map.get(arr.charAt(i));
                pivoit=i-k<=pivoit?i-k:pivoit+1;
            }
            res=Math.max(res,pivoit);
            map.put(arr.charAt(i),i);
        }
        return res;
    }
}

0 赞同 0 条回复

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

共以下 7 个回答

# 回答此问题取消回复

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

共以下 7 个回答

# 回答此问题 取消回复

# 回答此问题取消回复