資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。示例輸入輸出解釋因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是，所以其長(zhǎng)度為。
題目：給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。
請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。
解答：
1.暴力破解
var lengthOfLongestSubstring = function(s) {
var l = s.length;
var re = 0;
for (var i= 0; i < l; i++) { //1
for(var j = i + 1; j <= l; j++){ //2
if(check(i, j)) {
re = Math.max(re, j - i)
} else {
break
}
}
}
function check(start, end) {
var a = [];
for (var k = start; k < end; k++) { //3
if (a.indexOf(s[k]) !== -1) {
return false
} else {
a.push(s[k])
}
}
return true;
}
return re
};
上來(lái)就是一頓for循環(huán)操作，這樣暴力寫(xiě)我們的leetcode肯定是不會(huì)給過(guò)的，因?yàn)橛龅匠?jí)長(zhǎng)的字符串測(cè)試用例，執(zhí)行時(shí)間會(huì)超出時(shí)間限制，上面代碼的優(yōu)化空間很大。
理一下邏輯，我們每次在2里面檢測(cè)出有重復(fù)的字符時(shí)，記錄這個(gè)重復(fù)字符前一次出現(xiàn)的位置index，然后中斷這次循環(huán)，開(kāi)始下一次1的循環(huán)，并且i的位置應(yīng)該為index+1。
比如在i=0的時(shí)，在2循環(huán)里j=4時(shí)就會(huì)出現(xiàn)重復(fù)的字符d，字符d前一次出現(xiàn)的位置是1，這時(shí)最長(zhǎng)字符串長(zhǎng)度是4，并且被記錄，這時(shí)應(yīng)該開(kāi)始1循環(huán)的下一次循環(huán)，并且是從i=2開(kāi)始。
3循環(huán)和2循環(huán)其實(shí)是不必要的，我們創(chuàng)建一個(gè)動(dòng)態(tài)的字符串，把每次循環(huán)到的字符加進(jìn)去并實(shí)時(shí)記錄它的長(zhǎng)度，遇到重復(fù)的字符串就砍掉字符第一次出現(xiàn)跟它之前的字符串，比如上圖，i循環(huán)到4時(shí)，出現(xiàn)重復(fù)字符d,d在之前出現(xiàn)的位置是1，我們應(yīng)該砍掉動(dòng)態(tài)字符串位置1跟它之前的字符串，來(lái)保證它是無(wú)重復(fù)的字符串。代碼如下
var lengthOfLongestSubstring = function(s) {
var l = s.length;
var re = 0;
var a = "", index;
for (var i = 0; i < l; i++) {
index = a.indexOf(s[i])
if (index !== -1) {
a = a.slice(index + 1)
}
a+=s[i]
re = Math.max(re, a.length);
}
return re
};
一下從矮窮挫變成高富帥，速度杠杠?chē)}！
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/100402.html
摘要：無(wú)重復(fù)字符的最長(zhǎng)子串難度中等描述給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。輸入輸出解釋因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是，所以其長(zhǎng)度為。 無(wú)重復(fù)字符的最長(zhǎng)子串 難度：中等 描述： 給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。 樣例： 輸入: abcabcbb 輸出: 3 解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 abc，所以其長(zhǎng)度為 3。 輸入: bbbbb ...
摘要：示例輸入輸出解釋因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是，所以其長(zhǎng)度為。請(qǐng)注意，你的答案必須是子串的長(zhǎng)度，是一個(gè)子序列，不是子串。 LeetCode3.無(wú)重復(fù)字符的最長(zhǎng)子串JavaScript 給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。 示例 1: 輸入: abcabcbb輸出: 3 解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 abc，所以其長(zhǎng)度為 3。 示例 2: 輸入: bbbbb輸出...
摘要：示例輸入輸出解釋因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是，所以其長(zhǎng)度為。請(qǐng)注意，你的答案必須是子串的長(zhǎng)度，是一個(gè)子序列，不是子串。完成循環(huán)后取隊(duì)列中出現(xiàn)的最大長(zhǎng)度即可。 給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的?最長(zhǎng)子串?的長(zhǎng)度。 示例?1： 輸入: abcabcbb 輸出: 3 解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 abc，所以其長(zhǎng)度為 3。 示例 2： 輸入: bbbbb 輸出: 1 解釋:...
摘要：先跳到第三題是因?yàn)榈诙}第一眼沒(méi)讀懂一題目無(wú)重復(fù)字符的最長(zhǎng)子串給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。示例輸入輸出解釋因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是，所以其長(zhǎng)度為。以此來(lái)實(shí)現(xiàn)判斷是否包含重復(fù)字符。 先跳到第三題是因?yàn)榈诙}第一眼沒(méi)讀懂 一、題目 無(wú)重復(fù)字符的最長(zhǎng)子串： 給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。 示例1 輸入: abcabcbb輸...
摘要：題目解答方法一我們從前往后遍歷字符串，代表最長(zhǎng)子串的起始位置，一開(kāi)始設(shè)置為零。如果沒(méi)有遇到重復(fù)字符，則更新子串的長(zhǎng)度，向后遍歷。最長(zhǎng)子串的起始位置重復(fù)的字符在子串中的位置初始化映射自動(dòng)初始化為零獲取更多精彩，請(qǐng)關(guān)注 1. 題目 showImg(https://segmentfault.com/img/remote/1460000016867082); 2. 解答 2.1. 方法一 我們...
閱讀 2856·2021-11-22 15:22
閱讀 19298·2021-09-22 15:00
閱讀 1445·2021-09-07 09:58
閱讀 1247·2019-08-30 13:01
閱讀 2452·2019-08-29 16:27
閱讀 2355·2019-08-26 13:25
閱讀 1627·2019-08-26 12:13
閱讀 947·2019-08-26 11:53
