我正在研究一個函數，它使用遞歸調用將給定的輸入分解為面額。在每一步，它都會遞歸成兩個變體：繼續使用當前硬幣：將其添加到列表中并遞歸。切換到下一個硬幣：增加硬幣位置并遞歸。除了在剩余 == 0 時打印出列表中捕獲的面額組合之外，我還打算捕獲該列表的值并從函數中返回它。這是代碼： static final int[] DENOMINATIONS = {9,5,3}; private static void change(int remaining, List<Integer> coins, int pos) if (remaining == 0) { // This correctly prints the desired output. // I want to return that exact value from the function. System.out.println(coins); } else { if (remaining >= DENOMINATIONS[pos]) { coins.add(DENOMINATIONS[pos]); another.addAll(coins); change(remaining - DENOMINATIONS[pos], coins, pos); coins.remove(coins.size() - 1); } if (pos + 1 < DENOMINATIONS.length) { change(remaining, coins, pos + 1); } } } public static List<Integer> denominations(int amount) { List<Integer> result = new ArrayList<Integer>(); List<Integer> another = new ArrayList<Integer>(); change(amount, result, another ,0); System.out.println(another.size()); return another; } public static void main(String[] args) { List<Integer> list = denominations(13); System.out.println(list); }輸出：[5, 5, 3]
3 回答
胡說叔叔
TA貢獻1804條經驗 獲得超8個贊
您必須添加return coins;at 和 ofchange方法，但您可以保留它的方式。返回和更改數組是一種代碼味道，因為該方法既對對象進行操作（修改它）并返回結果。
為了使其工作，您可以denomination按如下方式定義您的方法：
public static List<Integer> denominations(int amount) {
List<Integer> result = new ArrayList<Integer>();
change(amount, result, 0);
return result;
}
編輯：
該列表是空的，因為它唯一改變的地方是這里：
coins.add(DENOMINATIONS[pos]);
change(remaining - DENOMINATIONS[pos], coins, pos);
coins.remove(coins.size() - 1);
添加和刪除元素的位置。是你寫的讓它空了:)
編輯2：
我建議傳遞第二個對象，這將是您要返回的列表的副本，并且不會被修改。
四季花海
TA貢獻1811條經驗 獲得超5個贊
您似乎認為 java 是通過引用傳遞的，這是不正確的。Java 方法是按值傳遞的。
我已經更新了你的代碼：
改變方法：
private static List<Integer> change(int remaining, List<Integer> coins, int pos) { // Updated method return type;
if (pos < 0 || pos >= DENOMINATIONS.length) { // check if position is invalid
return new ArrayList<>(); // return an empty list
}
if (remaining == DENOMINATIONS[pos]) { // check if remaining is equal to denominations[pos]
coins.add(DENOMINATIONS[pos]); // add the denominations to the coins result
return coins; // return the result
} else if (remaining > DENOMINATIONS[pos]) { // check if remaining is greater than denominations[pos]
coins.add(DENOMINATIONS[pos]);// add the possible denominations to the coins result
remaining = remaining - DENOMINATIONS[pos]; // calculate the new remaining
if (remaining >= DENOMINATIONS[pos]) { // check if remaining is greater than or equal to denominations[pos]
return change(remaining, coins, pos); // stick to this position
} else {
return change(remaining, coins, pos + 1); // increment pos to go to the lower denominations
}
} else if (remaining < DENOMINATIONS[pos]) { // check if remaining is lesser than denominations[pos]
if (coins.isEmpty()) { // if coins is empty then go to the next denomination
return change(remaining, coins, pos + 1);
} else {
coins.remove(coins.size() - 1); // remove the previous denomination
return change(remaining + DENOMINATIONS[pos - 1], coins, pos); // go back to the previous remaining and // try this DENOMINATIONS[pos]
}
}
return coins;
}
面額法：
public static List<Integer> denominations(int amount) {
return change(amount, new ArrayList<Integer>(), 0);
}
輸入：13
輸出：[5, 5, 3]
收到一只叮咚
TA貢獻1821條經驗 獲得超5個贊
change應該返回布爾值，表示是否已找到答案。
所以change身體看起來像這樣：
if (remaining == 0) {
return true;
}
...
if (change(...)) return true;
...
return false; // It's last line of body
添加回答
舉報
0/150
提交
取消