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...


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

查看所有标签

猜你喜欢:

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

软件测试经验与教训

软件测试经验与教训

Cem Kaner、James Bach、Bret Pettichord / 机械工业出版社 / 2004-1 / 35.00

本书汇总了293条来自软件测试界顶尖专家的经验与建议,阐述了如何做好测试工作、如何管理测试,以及如何澄清有关软件测试的常见误解,读者可直接将这些建议用于自己的测试项目工作中。这些经验中的每一条都是与软件测试有关的一个观点,观点后面是针对运用该测试经验的方法、时机和原因的解释或例子。 本书还提供了有关如何将本书提供的经验有选择性地运用到读者实际项目环境中的建议,在所有关键问题上所积累的经验,以......一起来看看 《软件测试经验与教训》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试