我正在嘗試這個問題，我們需要找到陣列中元素的排列。
這是leetcode 的第 46 題。我面臨的問題是我無法輸出ans它只是一直回傳一個空白ArrayLists：
代碼：
public List<List<Integer>> permute(int[] nums)
{
List<List<Integer>> fans = new ArrayList<>();
HashMap<Integer, Integer> fmap = new HashMap<>();
for(int i: nums){
fmap.put(i, fmap.getOrDefault(i, 0) 1);
}
int n=nums.length;
List<Integer> ans=new ArrayList<>(n);
dfs(1, n, fmap, ans, fans);
return fans;
}
public void dfs(int cs, int ts, HashMap<Integer, Integer> fmap,List<Integer> ans, List<List<Integer>> fans)
{
if (cs > ts)
{
fans.add(ans);
return;
}
for(Integer val: fmap.keySet())
{
if (fmap.get(val) > 0)
{
fmap.put(val, fmap.get(val) - 1);
ans.add(val);
dfs(cs 1, ts, fmap, ans, fans);
ans.remove(ans.size() - 1);
fmap.put(val, fmap.get(val) 1);
}
}
}
測驗用例的輸出 [0,1]：
[[],[]]
實際輸出應該是：
[[0,1],[1,0]]
當我檢查遞回方法中的“潛在答案”時，我能夠看到正確的答案。我的意思是，如果我在dfs方法中列印輸出，它會顯示正確的答案：
代碼中的變化：
if (cs > ts)
{
fans.add(ans);
System.out.println(fans);
return;
}
現在它正在列印的值fans：
[[0, 1]]
[[1, 0], [1, 0]]
但是這些值沒有在 中更新，fans并且回傳的值是空白的。
我讀到有人提到過同樣的問題，但它是針對 Python 的，在這種情況下，解決方案是對串列進行深層復制。
我不確定如何在 Java 中做到這一點。
我做錯了什么？
uj5u.com熱心網友回復：
為了生成排列串列，您不需要Map. 您只引入了多余的操作，無論如何這些操作都沒有用。如果您有疑問，請添加幾個列印陳述句來可視化地圖狀態，它將始終包含與值相同的鍵1（輸入中的所有數字都保證是唯一的）并且它對結果沒有影響。
生成排列的資料源
除了嘗試利用 .HashMap作為生成排列的資料源的嘗試由于錯誤而無法正常作業之外，這也不是一個好主意，因為不能保證對keySet的順序迭代是一致的。HashMap
作為存盤尚未在當前排列中應用的數字的統一平均值，我們可以使用ArrayList. 在這種情況下，因為輸入中不會有重復項（請參閱下面leetcode中的參考），我們可以使用 aLinkedHashSet來提高性能。如下所述，元素的洗掉將在每次遞回呼叫之前發生，并且從 anArrayList中洗掉的成本為O(n)，同時LinkedHashSet它將減少到O(1)。
約束：
1 <= nums.length <= 6
-10 <= 數字[i] <= 10
nums 的所有整數都是唯一的。
生成排列
每個生成的排列都應該包含在它自己的串列中。在您的代碼中，您創建了一個串列，該串列在遞回呼叫期間被傳遞，最終每個遞回分支都將相同的串列添加到結果串列中。這顯然不應該發生。
你看，結果被列印為[[],[]]. 看起來像是一個包含兩個串列的串列，但實際上它們參考的是同一個空串列。
這個串列是空的，因為添加到其中的每個元素都在執行遞回呼叫后被洗掉：
ans.add(val);
... <- rursive call in between
ans.remove(ans.size() - 1); // removes the last element
如果我在 dfs 方法中列印輸出，它會顯示正確的答案：
實際上，這是不正確的。如果您仔細查看結果，您會發現嵌套串列是相同的[[1, 0], [1, 0]]。
最終結果是空白的，因為所有遞回呼叫都發生在每個被添加和洗掉的值之間（參見上面的代碼片段）。即洗掉將按照尊敬的順序執行。那將是要執行的最后幾行，而不是return陳述句。為了更好地理解它，我建議您逐行瀏覽代碼并在紙上畫出對ans串列所做的所有更改，以便進行簡單的輸入，例如[0, 1].
相反，您應該創建一個包含未完全生成的排列( ) 的串列副本，然后將一個元素添加到副本中。這樣初始排列( ) 不受影響，并且可以在所有后續迭代中用作模板。answeranswer
List<Integer> updatedAnswer = new ArrayList<>(answer);
updatedAnswer.add(next);
并且您還需要創建資料源的副本并洗掉添加到新創建的排列( answer ) 中的元素，以避免重復此元素：
Set<Integer> updatedSource = new LinkedHashSet<>(source);
updatedSource.remove(next);
旁注：為方法和變數賦予有意義的名稱是一種好習慣。例如，名稱cs和ts不提供資訊（不看代碼就不清楚它們的存盤含義），方法名稱dfs令人困惑，DFS 是一種眾所周知的演算法，用于遍歷樹或圖資料結構，但與此問題無關。
構建遞回解決方案
保持遞回方法是有道理的，void以避免將結果包裝在一個額外的串列中，該串列隨后將被丟棄，但通常回傳結果而不是在引數中累積它更方便。出于性能原因，我將方法保留為void.
每個遞回實作都應該包含兩個部分：
- 基本情況- 表示一個簡單的邊緣情況（或一組邊緣情況），其結果是預先知道的。對于這個問題，基本情況將代表給定排列達到初始陣列大小的情況，即源將不包含任何元素，我們需要檢查它是否為空。問題中提供的解決方案中用于此檢查的引數
cs和引數是多余的。ts - 遞回案例- 解決方案的一部分，其中遞回呼叫和主邏輯駐留。在遞回情況下，我們需要如上所述復制給定的答案和來源，并使用更新的副本作為每個遞回呼叫的引數。
這就是它的實作方式：
public static List<List<Integer>> permute(int[] nums) {
Set<Integer> source = new LinkedHashSet<>();
for (int next: nums) source.add(next);
List<List<Integer>> result = new ArrayList<>();
permute(source, new ArrayList<>(), result);
return result;
}
public static void permute(Set<Integer> source, List<Integer> answer,
List<List<Integer>> result) {
if (source.isEmpty()) {
result.add(answer);
return;
}
for (Integer next: source) {
List<Integer> updatedAnswer = new ArrayList<>(answer);
updatedAnswer.add(next);
Set<Integer> updatedSource = new LinkedHashSet<>(source);
updatedSource.remove(next);
permute(updatedSource, updatedAnswer, result);
}
}
main()
public static void main(String[] args) {
int[] source = {1, 2, 3};
List<List<Integer>> permutations = permute(source);
for (List<Integer> permutation: permutations) {
System.out.println(permutation);
}
}
輸出：
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
在線演示的鏈接
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/486302.html
上一篇：SQL查詢：聚合具有時間戳欄位的記錄，其中欄位時間戳屬于相同的時間單位（秒，分鐘，小時..）
下一篇：從盒子中取出物品的方法數