如何從初始陣列生成所有子陣列？
讓我們考慮一個陣列：[1,1,1,1].
我想生成所有可能的子陣列（沒有特別的順序）。
預期結果：
[1], [1], [1], [1],
[1, 1], [1, 1], [1, 1],
[1, 1, 1], [1, 1, 1],
[1, 1, 1, 1]
我的嘗試：
List<List<Integer>> list = new ArrayList<>();
generateAllSubArrays(nums, list, 0, 0);
private void generateAllSubArrays(int[] nums, List<List<Integer>> list, int start, int end) {
if (end == nums.length) {
List<Integer> l = new ArrayList<>();
for (int n : nums) {
l.add(n);
}
list.add(l);
} else if (start > end) {
generateAllSubArrays(nums, list, 0, end 1);
} else {
List<Integer> l = new ArrayList<>();
for (int i = start; i < end; i ) {
l.add(nums[i]);
}
list.add(l);
generateAllSubArrays(nums, list, start 1, end);
}
}
我得到以下結果：
[[], [1], [], [1, 1], [1], [], [1, 1, 1], [1, 1], [1], [], [1, 1, 1, 1]]
問題：
[]結果中存在一些空串列（這是不希望的）。不幸的是，我不明白他們為什么在這里。缺少某些預期值，導致結果不正確。
我做錯了什么，我應該怎么做才能得到正確的計算？
我相信我嘗試的是使用某種遞回，增加空間和時間復雜度。具有最佳空間和時間復雜度的演算法是什么？
uj5u.com熱心網友回復：
迭代實作
這是迭代生成給定陣列的所有非空子陣列的演算法：
維護兩個嵌套串列：一個用于正在進行的子陣列，而結果串列用于已構建的子陣列。
在每個迭代步驟中，創建仍在進行中的每個子陣列的副本并將下一個元素添加到其中。雖然原始子陣列完整地進入結果串列。
在迭代的最后，將包含下一個元素的單例串列添加到包含子陣列的串列中，我們將繼續作業，以便在下一個迭代步驟中，該串列將作為新子陣列的藍圖，并立即執行進入結果串列。
這就是它的實作方式：
public static List<List<Integer>> getSubArrays(int[] arr) {
List<List<Integer>> result = new ArrayList<>();
List<List<Integer>> inProgress = new ArrayList<>();
for (int next: arr) {
List<List<Integer>> proceedWith = new ArrayList<>();
for (List<Integer> subArray: inProgress) {
result.add(subArray); // we are done with this subarray
List<Integer> copy = new ArrayList<>(subArray);
copy.add(next);
proceedWith.add(copy); // we should continue working with copy
}
proceedWith.add(List.of(next)); // to avoid empty subarrays appear in the result
inProgress = proceedWith;
}
result.addAll(inProgress);
return result;
}
main()
public static void main(String[] args) {
int[] arr = {1, 2, 3};
getSubArrays(arr).forEach(System.out::println);
}
輸出：
[1]
[1, 2]
[2]
[1, 2, 3]
[2, 3]
[3]
遞回實作
主要邏輯保持不變：
如果還有一些未使用的元素，每個子陣列都充當另一個子陣列的藍圖。
每個單元素子陣列都會產生一個新的子陣列分支（如果還有一些未使用的元素）。
基本情況（遞回應該終止的條件） - 沒有要探索的元素，即當前索引等于陣列的長度。
遞回案例：
創建作為引數接收的子陣列的副本并將下一個元素添加到，原始子陣列應該進入結果串列。
然后執行兩次遞回呼叫：一次使用子陣列的副本，另一次使用單元素子陣列（包含下一個元素）。
這就是遞回實作的樣子：
public static List<List<Integer>> getSubArraysRecursively(int[] arr) {
if (arr.length == 0) return Collections.emptyList();
List<List<Integer>> result = new ArrayList<>();
List<Integer> subarray = List.of(arr[0]);
generateSubArrays(result, subarray, arr, 1);
return result;
}
private static void generateSubArrays(List<List<Integer>> result,
List<Integer> subarray,
int[] arr, int i) {
if (i == arr.length) { // base case
result.add(subarray);
return;
}
// recursive case
result.add(subarray);
List<Integer> copy = new ArrayList<>(subarray);
copy.add(arr[i]);
generateSubArrays(result, copy, arr, i 1); // proceed working with the copy
generateSubArrays(result, List.of(arr[i]), arr, i 1); // start a new branch of subarrays
}
uj5u.com熱心網友回復：
List#subList
您可以使用簡單的嵌套回圈、計數器和一些函式（例如Math#min等）來完成List#subList，如下所示：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String args[]) {
int[] arr = { 1, 1, 1, 1 };
List<Integer> list = Arrays.stream(arr).boxed().toList();
List<List<Integer>> result = new ArrayList<>();
int counter = 1;
for (int i = 0; i < arr.length; i ) {
for (int j = 0; j < arr.length; j )
result.add(list.subList(j, Math.min(j counter, arr.length)));
counter ;
}
System.out.println(result);
}
}
輸出：
[[1], [1], [1], [1], [1, 1], [1, 1], [1, 1], [1], [1, 1, 1], [1, 1, 1], [1, 1], [1], [1, 1, 1, 1], [1, 1, 1], [1, 1], [1]]
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/515850.html
標籤：爪哇数组算法子阵列
上一篇：帶有mockEndpointsAndSkip()的ApacheCamel測驗沒有收到訊息，但是weaveById().replace().to()是