LeetCode——Longest Substring Without Repeating Char

forsigner 发布于2019-08-26 13:31 / 3214人阅读

摘要：原问题我的沙雕解法无重复字母存在重复字母挨打最暴力的无脑解法，耗时。。。

原问题

Given a string, find the length of the longest substring without repeating characters.

Example 1:
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

我的沙雕解法

var lengthOfLongestSubstring = function(s) {
    let recordObj = {};
    let length = s.length;
    let max = 0;
    for(let i = 0; i < length; i++){
        let record = 0;
        for(let g = i; g < length; g++){
            if(recordObj[s[g]] === undefined){//无重复字母
                recordObj[s[g]] = true;
                record++;
            }else{//存在重复字母
                recordObj = {};
                break;
            }
        }
        max = record > max? record:max;
        if(max === length){break;}
    }
    return max;
};

挨打：最暴力的无脑解法，耗时672ms。。。

贪心解法学习

参考了排名较前的答案，多数是贪心思想，以下摘抄一位的代码并加上学习的注释

/**
*   通过i，j指针计算子序列长度
*   j指针：表示当前循环的字母，i指针：表示起点
*   map用于记录出现过的字母的相邻下标，给予i新的起点
*   重复字母出现时，比较当前起点与map的记录位置，取较大值，保证连续子序列，同时体现贪心：求
*   当前可求得的最长子序列
**/
var lengthOfLongestSubstring = function(s) {
    var n = s.length, ans = 0;
        var map = new Map(); // 记录出现过字母的相邻下标
        // try to extend the range [i, j]
        for (var j = 0, i = 0; j < n; j++) {
            if (map.has(s.charAt(j))) {    //若此字母在之前的循环中出现过
                i = Math.max(map.get(s.charAt(j)), i);   //保证连续子序列，同时体现贪心
            }
            ans = Math.max(ans, j - i + 1);  //比较
            map.set(s.charAt(j), j + 1);  //记录字母的相邻位置
        }
        return ans;
};

此算法耗时108ms
百度到一张图片很有利于理解
举例：qpxrjxkltzyx

图片来源：https://www.cnblogs.com/wangk...

云服务器 GPU云服务器 Repeating Without Longest LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/108979.html

[Leetcode]Longest Substring Without Repeating Char

摘要：解题思路本题借助实现。如果字符未出现过，则字符，如果字符出现过，则维护上次出现的遍历的起始点。注意点每次都要更新字符的位置最后返回时，一定要考虑到从到字符串末尾都没有遇到重复字符的情况，所欲需要比较下和的大小。 Longest Substring Without Repeating CharactersGiven a string, find the length of the lon...

awesome23 2019-08-16 10:26 评论0 收藏0
[LeetCode] Longest Substring Without Repeating Cha

摘要：建立数组，存储个字符最近一次出现的位置。首次出现某字符时，其位置标记为，并用无重复字符计数器记录无重复字符的长度，再在更新其最大值。循环完整个字符串后，返回最大值。 Problem Given a string, find the length of the longest substring without repeating characters. Examples: Given ...

CoderStudy 2019-08-14 15:48 评论0 收藏0
leetcode 3 Longest Substring Without Repeating Cha

摘要：题目详情题目要求输入一个字符串，我们要找出其中不含重复字符的最长子字符串，返回这个最长子字符串的长度。对于字符串中的每一个字符，先判断中是否已经存在这个字符，如果不存在，直接将添加到，如果已存在，则新的字符串就从不含前一个字符的地方开始。题目详情 Given a string, find the length of the longest substring without repe...

xcold 2019-08-15 14:21 评论0 收藏0
[Leetcode] Longest Substring Without Repeating Cha

摘要：哈希表是最自然的想法。在遍历字符串时，我们先根据哈希表找出该字符上次出现的位置，如果大于等于子字符串首，便更新子字符串首。结束后，将该字符新的位置放入哈希表中。 Longest Substring Without Repeating Characters 最新更新解法：https://yanjia.me/zh/2018/12/... Given a string, find the ...

FleyX 2019-08-14 12:18 评论0 收藏0
[LeetCode] Longest Substring Without Repeating Cha

Problem Given a string, find the length of the longest substring without repeating characters. Examples Given abcabcbb, the answer is abc, which the length is 3. Given bbbbb, the answer is b, with the...

graf 2019-08-19 10:52 评论0 收藏0