3

我试图在 Java 中解决的问题需要将输入数组划分为所有允许的子序列，其中允许的子序列仅包含连续值。例如，我希望 {A,E,D} 返回 {A,E,D},{A,E},{A},{E,D},{D},{E}

这与这个问题的不同之处在于（对于上面的例子）
1）我有“连续值”规则，这意味着 {A,D} 是不允许的，
2）我不能依赖此处答案中的 Python 语法。

我的问题尤其是如何对更一般的子序列问题实施“连续值”规则。

到目前为止，我已经为示例 {1,2,3} 提出了一种算法：
1. 复制 {1,2,3} 并存储在arr
2. 将 {1,2,3} 附加到解决方案中，剥离 3
3. 将 {1,2} 附加到解决方案，剥离 2
4. 将 {1} 附加到解决方案。从arr
5 中删除 1。将 {2,3} 附加到解决方案剥离 3
6.将 {2} 附加到解决方案。从arr
7 中删除 2。将 {3} 附加到解决方案

4

1 回答 1

4

您应该能够简单地使用两个嵌套的 for 循环，如下所示：

// Setup
char[] arr = { 'A', 'E', 'D' };

// Generate all subsequences
List<char[]> result = new ArrayList<>();
for (int start = 0; start < arr.length; start++) {
    for (int end = start + 1; end <= arr.length; end++) {
        result.add(Arrays.copyOfRange(arr, start, end));
    }
}

// Print result
result.forEach(a -> System.out.println(Arrays.toString(a)));

输出：

[A]
[A, E]
[A, E, D]
[E]
[E, D]
[D]
于 2015-05-26T17:02:26.497 回答