我正在做一個經典的 leet 代碼問題：找到字符串中最長的非重復子字符串。盡管堆棧溢出還有很多類似的問題。我撓了撓頭好幾個小時，不知道為什么我的代碼會產生這個奇怪的結果。希望有人能告訴我為什么我的我是用Java做的 public static void main( String[] args ) { String s= "wwhoamiUrektxineabcdefghijklmno"; longestNonRepeatStr(s); } public static void longestNonRepeatStr(String tstring) { String str=""; String compare=""; List<String> list= new ArrayList<String>(); int biggest =0; //find the nonrepeating string in each loop and add to list str for (int i=0; i<tstring.length(); i++) { for (int j=i; j<tstring.length()-1; j++) { str+= tstring.charAt(j); compare= Character.toString(tstring.charAt(j+1)); if (str.contains(compare)){ list.add(str); str=""; break; } } } //find the longest nonrepeating string in the list for (int i=0; i<list.size(); i++) { if (list.get(biggest).length()< list.get(i).length()) { biggest=i; } } System.out.println(list); System.out.println(list.get(biggest)); }對于輸入字符串"wwhoamiUrektxineabcdefghijklmno"輸出是"abcdefghijklmnb" 但這是錯誤的，最后一個字母應該是“o”
4 回答
猛跑小豬
TA貢獻1858條經驗 獲得超8個贊
您有幾個問題（請參閱我更正代碼的評論）：
public static void longestNonRepeatStr(String tstring) {
String str="";
String compare="";
List<String> list= new ArrayList<String>();
int biggest =0;
for (int i=0; i<tstring.length(); i++) {
str = ""; // you must clear the current String before each iteration of the inner loop
for (int j=i; j<tstring.length(); j++) { // here you were skipping the last character
str+= tstring.charAt(j);
// I improved the following condition
if (j+1 < tstring.length() && str.contains(Character.toString(tstring.charAt(j+1)))){
list.add(str);
str="";
break;
}
}
if (str.length() > 0) { // if you finish the inner loop without breaking, you should
// add the current String to the List
list.add(str);
}
}
for (int i=0; i<list.size(); i++) {
if (list.get(biggest).length()< list.get(i).length()) {
biggest=i;
}
}
System.out.println(list);
System.out.println(list.get(biggest));
}
或者，作為替代方案，您可以在內部循環的最后一次迭代中將當前 String 添加到 List 中：
public static void longestNonRepeatStr(String tstring) {
String str="";
String compare="";
List<String> list= new ArrayList<String>();
int biggest =0;
for (int i=0; i<tstring.length(); i++) {
str = "";
for (int j=i; j<tstring.length(); j++) {
str+= tstring.charAt(j);
if (j+1 >= tstring.length() || str.contains(Character.toString(tstring.charAt(j+1)))){
list.add(str);
str="";
break;
}
}
}
for (int i=0; i<list.size(); i++) {
if (list.get(biggest).length()< list.get(i).length()) {
biggest=i;
}
}
System.out.println(list);
System.out.println(list.get(biggest));
}
關于如何獲得輸出“abcdefghijklmnb”的進一步說明：
當 時i==16，您的內部循環構建String“abcdefghijklmn”。然后它會跳過“o”，因為您提前結束了該循環（由于j<tstring.length()-1）。由于您尚未檢測到重復字符，因此String尚未將其添加到 中。List現在i==17，當 時，您將“b”附加到str并得到“abcdefghijklmnb”?，F在您檢查下一個字符“c”是否已出現在 中str，即true，因此您將“abcdefghijklmnb”添加到您的List.
紅糖糍粑
TA貢獻1815條經驗 獲得超6個贊
這里的問題是循環結構的最后一次迭代：
for (int i=0; i<tstring.length(); i++) {
for (int j=i; j<tstring.length() - 1; j++) {
...
}
}
如果我們采用你的 string wwhoamiUrektxineabcdefghijklmno，那么當i=30它將處理字符串的最后一個字符（“o”）時，但是 的長度tstring是 31 所以下一行（你的嵌套 for 循環）將不會運行為int j=30和tstring.length() - 1 = 30
相反，你應該開始下一個 for 循環int j = i + 1并讓它運行到tstring.length()
關于何時向字符串添加字符以及何時決定需要將字符串添加到列表中，還存在一些邏輯問題。在這里試試這個...
for (int i = 0; i < tstring.length(); i++) {
str += tstring.charAt(i);
for (int j = i + 1; j<tstring.length(); j++) {
compare= Character.toString(tstring.charAt(j));
if (str.contains(compare)){
break;
} else {
str += tstring.charAt(j);
}
}
list.add(str);
str = "";
}
最后，您不需要str位于循環外部。您可以在循環中實例化它（這將為您節省大約 2 行代碼）。
墨色風雨
TA貢獻1853條經驗 獲得超6個贊
for當您處于最后一個循環任務時，問題出在嵌套中。如果if不匹配，則不會將其添加str到列表中，并且不會重新發送str變量。為了解決這個問題，我稍微改變了你的源代碼：
public static void longestNonRepeatStr(String tstring) {
String str="";
String compare="";
List<String> list= new ArrayList<String>();
int biggest =0;
//find the nonrepeating string in each loop and add to list str
for (int i=0; i<tstring.length()-1; i++) {
for (int j=i+1; j<tstring.length(); j++) {
str+= tstring.charAt(j-1);
compare= Character.toString(tstring.charAt(j));
if (str.contains(compare)){
list.add(str);
str="";
break;
}else{
if (j==tstring.length()-1){
str+= tstring.charAt(j);
list.add(str);
str="";
}
}
}
}
//find the longest nonrepeating string in the list
for (int i=0; i<list.size(); i++) {
if (list.get(biggest).length()< list.get(i).length()) {
biggest=i;
}
}
//System.out.println(list);
System.out.println(list.get(biggest));
}
千巷貓影
TA貢獻1829條經驗 獲得超7個贊
當 j 到達輸入字符串的末尾而沒有找到重復字符時，您不會將該子字符串添加到列表中，并且不會重置str。
嘗試這樣的事情：
for (int i = 0; i < tstring.length(); i++) {
String str = Character.toString(tstring.charAt(i));
for (int j = i + 1; j < tstring.length(); j++) {
char c = tstring.charAt(j);
if (str.indexOf(c) >= 0) {
break;
}
str += c;
}
list.add(str);
}
添加回答
舉報
0/150
提交
取消