我正在嘗試贖金記錄挑戰：
給定兩個字串ransomNote和magazine，如果ransomNote可以使用來自magazine的字母構造，則回傳true，否則回傳false。
雜志中的每個字母只能在贖金筆記中使用一次。
示例 1：
輸入：ransomNote = "a", magazine = "b" 輸出：false 示例 2：
輸入：ransomNote = "aa", magazine = "ab" 輸出：false 示例 3：
輸入：ransomNote = "aa", magazine = "aab" 輸出：true
這是我的解決方案：
public static boolean canConstruct(String ransomNote, String magazine) {
ArrayList<Character> ransomChar = new ArrayList<Character>();
ArrayList<Character> magazineChar = new ArrayList<Character>();
if (ransomNote.length() == 1 && magazine.length() == 1) {
if (ransomNote.equals(magazine)) {
return true;
}
return false;
}
else if (ransomNote.length() == 1 && magazine.length() > 1) {
for (int i = 0; i < magazine.length(); i ) {
if (magazine.charAt(i) == ransomNote.charAt(0)) {
return true;
}
}
return false;
}
else if (ransomNote.length() > 1 && magazine.length() > 1) {
for (int i = 0; i < ransomNote.length(); i ) {
ransomChar.add(ransomNote.charAt(i));
}
for (int i = 0; i < magazine.length(); i ) {
magazineChar.add(magazine.charAt(i));
}
while (ransomChar.size() > 1) {
for (int i = 0; i < ransomChar.size(); i ) {
boolean flag = false;
for (int j = 0; j < magazineChar.size(); j ) {
if (ransomChar.get(i).equals(magazineChar.get(j))) {
ransomChar.remove(i);
magazineChar.remove(j);
flag = true;
}
else if (ransomChar.isEmpty()) {
return true;
}
}
if (!flag) {
return false;
}
}
}
if (ransomChar.size() == 1 && magazineChar.size() == 1) {
if (ransomChar.equals(magazineChar)) {
return true;
}
return false;
}
else if (ransomChar.size() == 1 && magazineChar.size() > 1) {
for (int i = 0; i < magazineChar.size(); i ) {
if (ransomChar.get(0).equals(magazineChar.get(i))) {
return true;
}
}
return false;
}
}
return false;
}
我正在通過大多數測驗用例，但它在輸入時引發錯誤：
"bg"
"efjbdfbdgfjhhaiigfhbaejahgfbbgbjagbddfgdiaigdadhcfcj"
它拋出錯誤：
java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
at line: if (ransomChar.get(i).equals(magazineChar.get(j)))
uj5u.com熱心網友回復：
在此回圈的每次迭代中：
for (int i = 0; i < ransomChar.size(); i ) { boolean flag = false; for (int j = 0; j < magazineChar.size(); j ) { if (ransomChar.get(i).equals(magazineChar.get(j))) { ransomChar.remove(i); magazineChar.remove(j); flag = true; } else if (ransomChar.isEmpty()) { return true; } } if (!flag) { return false; } }
，您知道最初i小于，因此可以安全地執行。ransomChar.size()ransomChar.get(i)
但是，內部回圈可能會洗掉 的一個（或多個！）元素ransomChar，之后i小于可能不再正確ransomChar.size()。內部回圈繼續迭代，因此，它可以嘗試檢索ransomChar不存在的元素。
老實說，整個代碼是一團糟。除了這個特定的問題，
我認為沒有必要為紙幣和雜志尺寸的所有變化需要特殊情況。我認為，如果您投入一些精力來設計一種在所有情況下都能正常作業的方法，那么您可能會為此撰寫更好的代碼。
你沒有很好地利用你正在使用的類的可用特性
您沒有很好地利用適用的一般 Java 語言特性。
例如，我可以將那個特定的回圈寫成：
for (Character c : ransomChar) {
if (!magazineChar.remove(c)) {
return false;
}
}
return true;
那是在我們得出您選擇了次優演算法的事實之前。它的執行時間將按紙幣尺寸 * 雜志尺寸進行縮放，而其他替代方案將按紙幣尺寸 雜志尺寸進行縮放。這實際上可能很重要，因為選擇有效的演算法是諸如此類編碼挑戰的測驗用例經常嘗試檢測的一件事。
uj5u.com熱心網友回復：
這是一種通過構建一組候選字符來解決問題的簡單方法magazine。完成后，您只需遍歷ransomNote，檢查每個字符的集合。如果找到它，則將其從集合中移除。如果你不這樣做，那么你就回傳false。如果你一直堅持下去，你就回來了true。您需要使用 MultiSet，因為您需要能夠在雜志中表示同一字符的多個副本。
以下是如何做到這一點：
public static boolean canConstruct(String ransomNote, String magazine) {
MultiSet<Character> magazineChars = new HashMultiSet<>();
for (int i = 0; i < magazine.length(); i )
magazineChars.add(magazine.charAt(i));
for (int i = 0 ; i < ransomNote.length(); i ) {
Character c = ransomNote.charAt(i);
if (magazineChars.contains(c))
magazineChars.remove(c);
else
return false;
}
return true;
}
uj5u.com熱心網友回復：
請找到時間復雜度 O(n) 和空間復雜度 O(256) 或 O(1) 的小而簡單的解決方案
int[] count = new int[256];
for (char c : magazine.toCharArray()) {
count[c] ;
}
for (char c : ransomNote.toCharArray()) {
if (count[c]-- == 0) return false;
}
return true;
結果
uj5u.com熱心網友回復：
@Harsh，所以您正在嘗試訪問甚至不存在的 ransomChar 元素。看線
if (ransomChar.get(i).equals(magazineChar.get(j))) {
ransomChar.remove(i);
magazineChar.remove(j);
flag = true;
}
您正在從串列中洗掉元素，并且每次從串列中洗掉元素時，它們的索引都會更改，并且當它重新檢查條件時，串列在多次迭代后已經為空。因此給出運行時錯誤。為避免這種情況，您應該首先檢查串列是否為空（您正在檢查之后）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520470.html
標籤：爪哇算法
上一篇：計算排列中的排列數