成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

前端中等算法-無重復(fù)字符的最長子串

hyuan / 1348人閱讀

摘要：無重復(fù)字符的最長子串難度中等描述給定一個字符串，請你找出其中不含有重復(fù)字符的最長子串的長度。輸入輸出解釋因?yàn)闊o重復(fù)字符的最長子串是，所以其長度為。

無重復(fù)字符的最長子串 難度：中等 描述：

給定一個字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度。

樣例：

輸入: "abcabcbb"

輸出: 3

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。

輸入: "bbbbb"

輸出: 1

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1。

輸入: "pwwkew"

輸出: 3

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "wke"，所以其長度為 3。

輸入: "dvdf"

輸出: 3

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "vdf"，所以其長度為 3。

輸入: "asjrgapa"

輸出: 6

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "sjrgap"，所以其長度為 6。

輸入: "aabaab!bb"

輸出: 3

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "ab!"，所以其長度為 3。

輸入: "abcb"

輸出: 3

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。

輸入: "asljlj"

輸出: 4

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "aslj"，所以其長度為 4。

輸入: "qwnfenpglqdq"

輸出: 8

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "fenpglqd"，所以其長度為 8。

思路分析：

關(guān)鍵在于在出現(xiàn)重復(fù)字符時，如何更新不重復(fù)字符的index

代碼模板： 
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
}
想 一 想 再 看 答 案 代碼：

用對象儲存字符的位置, 出現(xiàn)重復(fù)字符時更新不重復(fù)字符的index。

var lengthOfLongestSubstring = function (s) {
    let obj = {}; // 用于儲存字符出現(xiàn)的位置
    let res = 0; // 最大值
    let j = 0; // 不重復(fù)字符的index
    for (let i = 0; i < s.length; i++) {
        // 當(dāng)前值是否在對象中存儲過
        const value = obj[s[i]]
        if (value !== undefined) {
            // 更新上一次重復(fù)值的index
            // value + 1 跳過之前重復(fù)的字符
            // j: 之前不重復(fù)的index 重復(fù)字符 需要全部跳過
            j = Math.max(value + 1, j)

        }
        // 每個字符都計(jì)算一下最長不重復(fù)值 保存最大值
        // 不重復(fù)最長長度 = 當(dāng)前index - 上一次重復(fù)值的index + index從0開始 長度從1開始
        res = Math.max(res, i - j + 1);
        // 存/更新 字符串index
        obj[s[i]] = i
    }
    return res;
};

從左到右，一個字符一個字符搜索，看是否重復(fù)。

var lengthOfLongestSubstring = function (s) {
    var i = 0, // 不重復(fù)字符的index
        res = 0; // 更新無重復(fù)字符的長度
    for (j = 0; j < s.length; j++) {
        // 查找：不重復(fù)字符-當(dāng)前index之間 有沒有出現(xiàn)當(dāng)前字符
        let index = s.slice(i, j).indexOf(s[j])
        if (index === -1) {
            // 更新無重復(fù)字符的長度：當(dāng)前index-不重復(fù)字符的index + 長度從1開始算
            res = Math.max(res, j - i + 1);
        } else {
            // 更新i = 不重復(fù)字符的index
            // 不重復(fù)字符的index = 原不重復(fù)的字符index + i-j中出現(xiàn)重復(fù)字符的index + 跳過該重復(fù)字符
            i = i + index + 1;
        }
    }
    return res;
};

點(diǎn)個Star支持我一下~

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/106573.html

相關(guān)文章

  • LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

    摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數(shù)組知識點(diǎn)?；蛘呃奖疚淖钕旅?，添加的微信等會根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

    tracy 評論0 收藏0

  • JS算法題之leetcode(1~10)

    摘要：先去空白，去掉空白之后取第一個字符，判斷正負(fù)符號，若是英文直接返回，若數(shù)字則不取?；匚臄?shù)題目描述判斷一個整數(shù)是否是回文數(shù)?；匚臄?shù)是指正序從左向右和倒序從右向左讀都是一樣的整數(shù)。 JS算法題之leetcode(1~10) 前言 一直以來，前端開發(fā)的知識儲備在數(shù)據(jù)結(jié)構(gòu)以及算法層面是有所暫缺的，可能歸根于我們的前端開發(fā)的業(yè)務(wù)性質(zhì)，但是我認(rèn)為任何的編程崗位都離不開數(shù)據(jù)結(jié)構(gòu)以及算法。因此，我作為...

    SoapEye 評論0 收藏0

  • 【leetcode】3. 無重復(fù)字符的最長子串

    摘要：示例輸入輸出解釋因?yàn)闊o重復(fù)字符的最長子串是，所以其長度為。請注意，你的答案必須是子串的長度，是一個子序列，不是子串。完成循環(huán)后取隊(duì)列中出現(xiàn)的最大長度即可。 給定一個字符串，請你找出其中不含有重復(fù)字符的?最長子串?的長度。 示例?1： 輸入: abcabcbb 輸出: 3 解釋: 因?yàn)闊o重復(fù)字符的最長子串是 abc，所以其長度為 3。 示例 2： 輸入: bbbbb 輸出: 1 解釋:...

    qc1iu 評論0 收藏0

  • Leetcode 3 Longest Substring Without Repeat... 最長無

    摘要：難度題意是求最長無重復(fù)子串給出一個字符串從所有子串中找出最長且沒有重復(fù)字母的子串的長度我的解法是以為例使用一個記錄當(dāng)前子串遇到的所有字符用一個游標(biāo)從頭開始讀取字符加入到中如果碰到了重復(fù)字符遇到了重復(fù)則從當(dāng)前子串的頭部的字符開始將該字符從中移 Longest Substring Without Repeating CharactersGiven a string, find the le...

    RyanHoo 評論0 收藏0

  • LeetCode3.無重復(fù)字符的最長子串JavaScript

    摘要：示例輸入輸出解釋因?yàn)闊o重復(fù)字符的最長子串是，所以其長度為。請注意，你的答案必須是子串的長度，是一個子序列，不是子串。 LeetCode3.無重復(fù)字符的最長子串JavaScript 給定一個字符串，請你找出其中不含有重復(fù)字符的最長子串的長度。 示例 1: 輸入: abcabcbb輸出: 3 解釋: 因?yàn)闊o重復(fù)字符的最長子串是 abc，所以其長度為 3。 示例 2: 輸入: bbbbb輸出...

    vboy1010 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<