このC++関数は、同等のJava関数とはどのように異なった働きをしていますか？私は、次のC++アルゴリズムのJavaバージョンを実装しようとしている

Question

：ここ

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}で、正しい結果が624, 2069, 5547, 7027, 9636である場合、C++アルゴリズムは正しい結果を出力します。しかし、私が書いたJavaのバージョンは、624, 6880, 2660, 2069, 5547, 7027, 9636, 1487の不正確な結果を返し、私はなぜそれを理解できません。私はデバッガでそれをトレースしようとしましたが、何がうまくいかないのか分かりません。

if文が毎回真偽に評価され、C++プログラムと比較されたかどうかを示すprint文を追加しようとしましたが、それは問題ではないので同じでした。

私はそれがベクトルとArrayListの微妙な違いと関係していると思われますが、わかりません。

Answer 1

Javaでは、キャッシュにはリストにの参照が含まれていますが、C++ではリスト自体が含まれていると考えられます。

したがって、

L[i] = L[j]; 

コピーインデックスiに対するインデックスjでリスト、C++でJava

で

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

コピー参照一方。つまり、後でアイテムを追加すると、そのアイテムももう一方のアイテムに追加されます。あなたがC++のように、コピーを作成するよう

たぶん

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

を使用しています。