我有一個名為 lengthOfLongestSubstring 的函數(shù)，它的工作是找到?jīng)]有任何重復(fù)字符的最長子字符串。在大多數(shù)情況下，它可以工作，但是當(dāng)它獲得像“dvdf”這樣的輸入時，它會打印出 2（而不是 3），并在應(yīng)該是 [d, vdf] 時給出 [dv, df]。因此，我首先檢查該字符串，看看是否有任何獨特的字符。如果有，我將其附加到 ans 變量中。（我認(rèn)為這是需要修復(fù)的部分）。如果存在重復(fù)項，我將其存儲在子字符串鏈表中，并將 ans 變量重置為重復(fù)字符串。遍歷整個字符串后，我找到最長的子字符串并返回它的長度。public static int lengthOfLongestSubstring(String s) { String ans = ""; int len = 0; LinkedList<String> substrings = new LinkedList<String>(); for (int i = 0; i < s.length(); i++) { if (!ans.contains("" + s.charAt(i))) { ans += s.charAt(i); } else { substrings.add(ans); ans = "" + s.charAt(i); } } substrings.add(ans); // add last seen substring into the linked list for (int i = 0; i < substrings.size(); i++) { if (substrings.get(i).length() >= len) len = substrings.get(i).length(); } System.out.println(Arrays.toString(substrings.toArray())); return len;}下面是一些測試結(jié)果：//correctlengthOfLongestSubstring("abcabcbb") -> 3 ( [abc, abc, b, b]) lengthOfLongestSubstring("pwwkew") -> 3 ([pw, wke, w]).lengthOfLongestSubstring("ABDEFGABEF"); -> 6 ([ABDEFG, ABEF]) // wrongSystem.out.println(lengthOfLongestSubstring("acadf")); -> 3, ([ac, adf]) *should be 4, with the linked list being [a, cadf]有什么建議來解決這個問題嗎？我必須重做所有邏輯嗎？
3 回答
FFIVE
TA貢獻(xiàn)1797條經(jīng)驗 獲得超6個贊
您的代碼錯誤地假設(shè)當(dāng)您找到重復(fù)字符時，下一個候選子字符串從重復(fù)字符開始。這不是真的，它是在原始角色之后開始的。
示例：如果字符串為"abcXdefXghiXjkl"，則有 3 個候選子串："abcXdef"、"defXghi"、 和"ghiXjkl"。
正如您所看到的，候選子字符串在重復(fù)字符之前結(jié)束，并在重復(fù)字符之后開始（以及字符串的開頭和結(jié)尾）。
因此，當(dāng)您找到重復(fù)字符時，需要該字符的前一個實例的位置來確定下一個候選子字符串的開頭。
處理這個問題的最簡單方法是將Map角色構(gòu)建到上次看到的位置。這也比不斷執(zhí)行子字符串搜索來檢查重復(fù)字符（就像問題代碼和其他答案所做的那樣）執(zhí)行得更快。
像這樣的東西：
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> charPos = new HashMap<>();
List<String> candidates = new ArrayList<>();
int start = 0, maxLen = 0;
for (int idx = 0; idx < s.length(); idx++) {
char ch = s.charAt(idx);
Integer preIdx = charPos.get(ch);
if (preIdx != null && preIdx >= start) { // found repeat
if (idx - start > maxLen) {
candidates.clear();
maxLen = idx - start;
}
if (idx - start == maxLen)
candidates.add(s.substring(start, idx));
start = preIdx + 1;
}
charPos.put(ch, idx);
}
if (s.length() - start > maxLen)
maxLen = s.length() - start;
if (s.length() - start == maxLen)
candidates.add(s.substring(start));
System.out.print(candidates + ": ");
return maxLen;
}
僅candidates用于調(diào)試目的，并且不是必需的，因此如果沒有它，代碼會更簡單一些：
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> charPos = new HashMap<>();
int start = 0, maxLen = 0;
for (int idx = 0; idx < s.length(); idx++) {
char ch = s.charAt(idx);
Integer preIdx = charPos.get(ch);
if (preIdx != null && preIdx >= start) { // found repeat
if (idx - start > maxLen)
maxLen = idx - start;
start = preIdx + 1;
}
charPos.put(ch, idx);
}
return Math.max(maxLen, s.length() - start);
}
測試
System.out.println(lengthOfLongestSubstring(""));
System.out.println(lengthOfLongestSubstring("x"));
System.out.println(lengthOfLongestSubstring("xx"));
System.out.println(lengthOfLongestSubstring("xxx"));
System.out.println(lengthOfLongestSubstring("abcXdefXghiXjkl"));
System.out.println(lengthOfLongestSubstring("abcabcbb"));
System.out.println(lengthOfLongestSubstring("pwwkew"));
System.out.println(lengthOfLongestSubstring("ABDEFGABEF"));
輸出（帶有候選列表）
[]: 0
[x]: 1
[x, x]: 1
[x, x, x]: 1
[abcXdef, defXghi, ghiXjkl]: 7
[abc, bca, cab, abc]: 3
[wke, kew]: 3
[ABDEFG, BDEFGA, DEFGAB]: 6
滄海一幻覺
TA貢獻(xiàn)1824條經(jīng)驗 獲得超5個贊
ans當(dāng)找到字符匹配時，而不是設(shè)置為當(dāng)前字符
ans = "" + s.charAt(i);
您應(yīng)該將當(dāng)前字符添加到當(dāng)前字符的第一個匹配之后的所有字符
ans = ans.substring(ans.indexOf(s.charAt(i)) + 1) + s.charAt(i);
完整的方法因此變成
public static int lengthOfLongestSubstring(String s) {
String ans = "";
int len = 0;
LinkedList<String> substrings = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
if (!ans.contains("" + s.charAt(i))) {
ans += s.charAt(i);
} else {
substrings.add(ans);
// Only the below line changed
ans = ans.substring(ans.indexOf(s.charAt(i)) + 1) + s.charAt(i);
}
}
substrings.add(ans); // add last seen substring into the linked list
for (int i = 0; i < substrings.size(); i++) {
if (substrings.get(i).length() >= len)
len = substrings.get(i).length();
}
System.out.println(Arrays.toString(substrings.toArray()));
return len;
}
使用此代碼，您指定的驗收標(biāo)準(zhǔn)已成功通過
//correct
lengthOfLongestSubstring("dvdf") -> 3 ( [dv, vdf])
lengthOfLongestSubstring("abcabcbb") -> 3 ([abc, bca, cab, abc, cb, b])
lengthOfLongestSubstring("pwwkew") -> 3 ([pw, wke, kew]).
lengthOfLongestSubstring("ABDEFGABEF"); -> 6 ([ABDEFG, BDEFGA, DEFGAB, FGABE, GABEF])
lengthOfLongestSubstring("acadf"); -> 4 ([ac, cadf])
陪伴而非守候
TA貢獻(xiàn)1757條經(jīng)驗 獲得超8個贊
創(chuàng)建一個嵌套的 for 循環(huán)來檢查數(shù)組中的每個索引。
public static int lengthOfLongestSubstring(String s) {
String ans = "";
int len = 0;
LinkedList<String> substrings = new LinkedList<String>();
int k = 0;
for (int i = 0; i < s.length(); i++) {
if(k == s.length()) {
break;
}
for(k = i; k < s.length(); k++) {
if (!ans.contains("" + s.charAt(k))) {
ans += s.charAt(k);
} else {
substrings.add(ans);
ans = "";
break;
}
}
}
substrings.add(ans); // add last seen substring into the linked list
for (int i = 0; i < substrings.size(); i++) {
if (substrings.get(i).length() >= len)
len = substrings.get(i).length();
}
System.out.println(Arrays.toString(substrings.toArray()));
return len;
}
例子：
lengthOfLongestSubstring("ABDEFGABEF"); -> 6 ([ABDEFG, BDEFGA, DEFGAB, EFGAB, FGABE, GABEF])
添加回答
舉報
0/150
提交
取消