我正在尝试实现以下 C++ 算法的 Java 版本:
void constructPrintLIS(int arr[], int n)
{
std::vector< std::vector<int> > L(n);
L[0].push_back(arr[0]);
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if ((arr[i] > arr[j]) &&
(L[i].size() < L[j].size() + 1))
{
L[i] = L[j];
cout << true << endl;
}
else
{
cout << false << endl;
}
}
L[i].push_back(arr[i]);
}
std::vector<int> max = L[0];
for (std::vector<int> x : L)
{
if (x.size() > max.size())
{
max = x;
}
}
printLIS(max);
}
这是Java版本
private static List<Integer> getLongestIncreasingSubsequence(
List<Integer> sequence
)
{
ArrayList<ArrayList<Integer>> cache =
new ArrayList<ArrayList<Integer>>(sequence.size());
// Populate the elements to avoid a NullPointerException
for(int i = 0; i < sequence.size(); i++)
{
cache.add(new ArrayList<Integer>());
}
cache.get(0).add(sequence.get(0));
// start from the first index, since we just handled the 0th
for(int i = 1; i < sequence.size(); i++)
{
// Add element if greater than tail of all existing subsequences
for(int j = 0; j < i; j++)
{
if((sequence.get(i) > sequence.get(j))
&& (cache.get(i).size() < cache.get(j).size() + 1))
{
cache.set(i, cache.get(j));
}
}
cache.get(i).add(sequence.get(i));
}
// Find the longest subsequence stored in the cache and return it
List<Integer> longestIncreasingSubsequence = cache.get(0);
for(List<Integer> subsequence : cache)
{
if(subsequence.size() > longestIncreasingSubsequence.size())
{
longestIncreasingSubsequence = subsequence;
}
}
return longestIncreasingSubsequence;
}
我不明白我在做什么不同。当测试序列为 {9766, 5435, 624, 6880, 2660, 2069, 5547, 7027, 9636, 1487}
时,C++ 算法打印正确结果,正确结果为 624 , 2069, 5547, 7027, 9636
。但是,我编写的 Java 版本返回了 624, 6880, 2660, 2069, 5547, 7027, 9636, 1487
的错误结果,我不明白为什么。我试过在调试器中跟踪它,但我不知道出了什么问题。
我尝试添加一个 print 语句来指示 if 语句每次评估是否为 true/false,并将其与 C++ 程序进行比较,结果相同,所以这不是问题所在。
我怀疑这与 vector 和 ArrayList 之间的细微差别有关,但我不知道。
最佳答案
我怀疑问题在于在 Java 中,缓存包含对列表的引用,而在 C++ 中它包含列表本身。
因此,在 C++ 中
L[i] = L[j];
将索引 j
处的列表复制到索引 i
,而在 Java 中
cache.set(i, cache.get(j));
复制引用。这意味着,当您随后将项目添加到其中一个时,它们也会添加到另一个。
也许用
cache.set(i, new ArrayList<>(cache.get(j)));
这样您就可以创建一个拷贝,就像在 C++ 中一样。
关于java - 这个 C++ 函数与等效的 java 函数有何不同?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43504548/