LeetCode——Longest Substring Without Repeating Characters

栏目: 编程工具 · 发布时间: 5年前

内容简介:Given a string, find the length of the longest substring without repeating characters.挨打:最暴力的无脑解法,耗时672ms。。。参考了排名较前的答案,多数是贪心思想,以下摘抄一位的代码并加上学习的注释

原问题

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

LeetCode——Longest Substring Without Repeating Characters

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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

十亿美金的教训

十亿美金的教训

林军 唐宏梅 / 浙江大学出版社 / 2011-5 / 39.00元

《十亿美金的教训》内容简介:创业者个人能力欠缺、团队涣散、经营方向把握不当、资金动用失措以及时局不利……这其中有哪一个细节被忽视,都可能是失败的导火索! 国内二十年互联网风云,有人成功,有人失败。两种结果,不同方向,却往往只是一线之隔。他们留给我们怎样的教训与启示?后来者要怎样才能跳出失败之殇? 《十亿美金的教训》选取了互联网十个经典的失败案例,并深层解读这些互联网企业与创业者们从成功......一起来看看 《十亿美金的教训》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

MD5 加密
MD5 加密

MD5 加密工具