資訊專(zhuān)欄INFORMATION COLUMN
摘要：難度題意是求最長(zhǎng)無(wú)重復(fù)子串給出一個(gè)字符串從所有子串中找出最長(zhǎng)且沒(méi)有重復(fù)字母的子串的長(zhǎng)度我的解法是以為例使用一個(gè)記錄當(dāng)前子串遇到的所有字符用一個(gè)游標(biāo)從頭開(kāi)始讀取字符加入到中如果碰到了重復(fù)字符遇到了重復(fù)則從當(dāng)前子串的頭部的字符開(kāi)始將該字符從中移
Longest Substring Without Repeating Characters
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 length of 1.
Given "pwwkew", 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.
難度: Medium
題意是求最長(zhǎng)無(wú)重復(fù)子串, 給出一個(gè)字符串, 從所有子串中, 找出最長(zhǎng), 且沒(méi)有重復(fù)字母的子串的長(zhǎng)度.
我的解法是: (以abcbcdabb為例)
使用一個(gè)set, 記錄當(dāng)前子串遇到的所有字符.
用一個(gè)游標(biāo), 從頭開(kāi)始讀取字符, 加入到set中.(a, ab, abc)
如果碰到了重復(fù)字符(i=3, 遇到了b, 重復(fù)), 則從當(dāng)前子串的頭部的字符開(kāi)始, 將該字符從set中移除, 直到移除了當(dāng)前這個(gè)重復(fù)字符為止. (abc, bc, c, cb)
期間記錄不重復(fù)的最大長(zhǎng)度.
遍歷完整個(gè)字符串后, 輸出最大長(zhǎng)度.
由于使用了HashSet, 每個(gè)元素訪問(wèn)不超過(guò)兩次(添加與移除), 所以算法時(shí)間復(fù)雜度為O(n).
public class Solution {
public int lengthOfLongestSubstring(String s) {
// a set to record chars for current substring
Set cset = new HashSet();
// length of longest non-repeat substring
int lgst = 0;
// length of current substring
int curLen = 0;
for (int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
curLen++;
// if encounters a duplicate character
if (cset.contains(c)) {
// record non-repeat length
lgst = (curLen - 1) > lgst ? (curLen - 1) : lgst;
// reduce character from the head of current substring,
// until current repeat letter is removed
for (int j = i - cset.size(); j < i; j++) {
curLen--;
cset.remove(s.charAt(j));
if (s.charAt(j) == c) {
break;
}
}
}
cset.add(c);
}
lgst = curLen > lgst ? curLen : lgst;
return lgst;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.lengthOfLongestSubstring("bbbbbb"));
System.out.println(s.lengthOfLongestSubstring("abcabcbb"));
System.out.println(s.lengthOfLongestSubstring("abcbcdabb"));
System.out.println(s.lengthOfLongestSubstring("aab"));
System.out.println(s.lengthOfLongestSubstring("dvdf"));
System.out.println(s.lengthOfLongestSubstring("advdf"));
}
}
main方法執(zhí)行的測(cè)試結(jié)果為:
1
3
4
2
3
3
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66376.html
摘要：題目詳情題目要求輸入一個(gè)字符串，我們要找出其中不含重復(fù)字符的最長(zhǎng)子字符串，返回這個(gè)最長(zhǎng)子字符串的長(zhǎng)度。對(duì)于字符串中的每一個(gè)字符，先判斷中是否已經(jīng)存在這個(gè)字符，如果不存在，直接將添加到，如果已存在，則新的字符串就從不含前一個(gè)字符的地方開(kāi)始。 題目詳情 Given a string, find the length of the longest substring without repe...
摘要：原問(wèn)題我的沙雕解法無(wú)重復(fù)字母存在重復(fù)字母挨打最暴力的無(wú)腦解法，耗時(shí)。。。 原問(wèn)題 Given a string, find the length of the?longest substring?without repeating characters. Example 1: Input: abcabcbb Output: 3 Explanation: The answer is a...
摘要：哈希表是最自然的想法。在遍歷字符串時(shí)，我們先根據(jù)哈希表找出該字符上次出現(xiàn)的位置，如果大于等于子字符串首，便更新子字符串首。結(jié)束后，將該字符新的位置放入哈希表中。 Longest Substring Without Repeating Characters 最新更新解法：https://yanjia.me/zh/2018/12/... Given a string, find the ...
摘要：最新思路解法哈希表法復(fù)雜度時(shí)間空間思路我們遍歷字符串時(shí)用一個(gè)哈希表，但這個(gè)哈希表只記錄兩個(gè)東西，一個(gè)字母和它上次出現(xiàn)的時(shí)的下標(biāo)，另一個(gè)字母和它上次出現(xiàn)時(shí)候的下標(biāo)。這個(gè)通過(guò)用哈希表記錄字母上次出現(xiàn)的下標(biāo)，來(lái)維護(hù)一個(gè)窗口的方法也可以用于。 Longest Substring with At Most Two Distinct Characters 最新思路解法：https://yanjia...
摘要：建立數(shù)組，存儲(chǔ)個(gè)字符最近一次出現(xiàn)的位置。首次出現(xiàn)某字符時(shí)，其位置標(biāo)記為，并用無(wú)重復(fù)字符計(jì)數(shù)器記錄無(wú)重復(fù)字符的長(zhǎng)度，再在更新其最大值。循環(huán)完整個(gè)字符串后，返回最大值。 Problem Given a string, find the length of the longest substring without repeating characters. Examples: Given ...
閱讀 2111·2021-11-23 10:13
閱讀 2819·2021-11-09 09:47
閱讀 2767·2021-09-22 15:08
閱讀 3348·2021-09-03 10:46
閱讀 2259·2019-08-30 15:54
閱讀 946·2019-08-28 18:09
閱讀 2448·2019-08-26 18:26
閱讀 2359·2019-08-26 13:48
