這個C++函數如何與等價的java函數不同地工作？

Question

我試圖實現以下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的錯誤結果，我不明白爲什麼。我試圖在調試器中追蹤它，並且我無法弄清楚什麼是錯誤的。

我嘗試添加指示if語句是否評估爲真/假每次，並比較其與C++程序打印語句，這是一樣的，所以這不是問題。

我懷疑這是值得做的一個載體，一個ArrayList之間細微的差別，但我不知道。

Answer 1

我懷疑問題是，在Java中，緩存包含引用到列表，而在C++中它包含列表本身。

因此，在C++

L[i] = L[j]; 

副本列表索引j索引i，而在爪哇

cache.set(i, cache.get(j)); 

拷貝的引用。這意味着，當您隨後將項目添加到其中時，它們也會添加到其他項目中。

也許使用

cache.set(i, new ArrayList<>(cache.get(j))); 

，讓你用C創建一個副本，像++。