Java - 在EULER硬幣中使用Pair for Map鍵困難

我一直在處理有關硬幣組合的Project Euler問題。我使用遞歸得到答案，但我想嘗試一些動態編程，所以我建立了自己的Pair類，並嘗試將它用作TreeMap的關鍵字。我能夠得到它，但我一直得到完全錯誤的解決方案。Java - 在EULER硬幣中使用Pair for Map鍵困難

我不確定發生了什麼。我的朋友建議說，Map可能試圖匹配Pair引用而不是值，但我嘗試覆蓋.equals並修改compareTo方法，但它仍然不起作用。（根據文檔，我認爲TreeMap鍵使用equals方法來匹配...

這是我的代碼希望有人可以快速瀏覽它並讓我知道爲什麼它不起作用...如果您取消註釋最後一個return語句，擺脫所有地圖的東西，你會看到我的遞歸唯一的解決方案和工程。

import java.util.Map; 
import java.util.TreeMap; 


public class Coins3 { 

public static class Pair implements Comparable<Pair> { 
    Integer i1; 
    Integer i2; 

    Pair(Integer i1, Integer i2) { 
     this.i1 = i1; 
     this.i2 = i2; 
    } 

    @Override 
    public int compareTo(Pair arg0) { 
     // TODO Auto-generated method stub 
     if(this.equals(arg0)) return 0; 
     return this.i1 - arg0.i1; 
    } 
    public boolean equals(Pair arg0) { 
     if(this.i1.equals(arg0.i1) && this.i2.equals(arg0.i2)) return true; 
     return false; 
    } 
} 

static int[] coins = {1, 2, 5, 10, 20, 50, 100, 200}; 
static Map<Pair,Integer> memo = new TreeMap<Pair,Integer>(); 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    System.out.println(nWays(coins.length,200)); 

} 

public static int nWays(int index, int target) { 

    if(target == 0) return 1; 
    if(target < 0) return 0; 
    if(index <= 0 && target > 0) return 0; 
    // use the coin or not 
    int n1, n2; 
    Pair p1 = new Pair(index, target-coins[index-1]); 
    Pair p2 = new Pair(index-1, target); 

    if(memo.containsKey(p1)) { 
     n1 = memo.get(p1); 
    } else { 
     n1 = nWays(index,target-coins[index-1]); 
     memo.put(p1, n1); 
    } 

    if(memo.containsKey(p2)) { 
     n2 = memo.get(p2); 
    } else { 
     n2 = nWays(index-1,target); 
     memo.put(p2, n2); 
    } 
    return n1 + n2; 

    //return nWays(index-1,target) + nWays(index,target-coins[index-1]); 


}

}

來源

2014-10-13 CodeSeven

您的'compareTo'沒有提及i2。這意味着你的equals和compareTo是不一致的。如果一個TreeMap在內部使用'equals'並得到false，然後使用'compareTo'並得到0 ...我不確定會發生什麼。 –

你需要知道 - stackoverflow.com/questions/17027777/relationship-between-hashcode-and-equals-method-in-java。但我也認爲這不是問題。 – Tirath

你已覆蓋equals()沒有覆蓋hashcode()，以及所使用的類（類對）作爲地圖/集合中的關鍵字（您的memo字段）。

古典初學者錯誤 - read this爲什麼你應該總是覆蓋equals()和hashcode()在一起。

短版：地圖總是使用哈希代碼爲「縮小」你提供的搜索鍵，然後才使用equals（）方法來匹配你對發現的「區域」鍵鍵。由於您沒有重寫hashcode（），您的電話memo.containsKey(p1)和memo.containsKey(p2)可能無法找到密鑰，即使等於存在p1/p2的密鑰

來源

2014-10-13 05:37:40 radai

Java - 在EULER硬幣中使用Pair for Map鍵困難

回答

相關問題