8

私はこの問題を解決しようとしていました。

整数 M と、N 個の非負の整数からなる空でないゼロ インデックスの配列 A が与えられます。配列 A のすべての整数は M 以下です。

0 ≤ P ≤ Q < N となる整数のペア (P, Q) は、配列 A のスライスと呼ばれます。スライスは、要素 A[P]、A[P + 1]、...、 A[Q]。個別のスライスは、一意の番号のみで構成されるスライスです。つまり、個々の番号がスライス内で複数回出現することはありません。

たとえば、次のような整数 M = 6 と配列 A を考えてみましょう。

A[0] = 3
A[1] = 4
A[2] = 5
A[3] = 5
A[4] = 2

(0, 0)、(0, 1)、(0, 2)、(1, 1)、(1,2)、(2, 2)、(3, 3)、( 3, 4) および (4, 4)。

目標は、個別のスライスの数を計算することです。

前もって感謝します。

#include <algorithm>
#include <cstring>
#include <cmath>
#define MAX 100002

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

using namespace std;

bool check[MAX];

int solution(int M, vector<int> &A) {
    memset(check, false, sizeof(check));
    int base = 0;
    int fibot = 0;
    int sum = 0;

    while(fibot < A.size()){

        if(check[A[fibot]]){
            base = fibot;
        }

        check[A[fibot]] = true;

   sum += fibot - base + 1;
        fibot += 1;  
    }

    return min(sum, 1000000000);
}
4

5 に答える 5

3

アルゴリズムが間違っているため、ソリューションは正しくありません。

まず、反例を示します。しましょうA = {2, 1, 2}。最初の反復: base = 0, fibot = 0,sum += 1.そうです。2 つ目: base = 0, fibot = 1, sum += 2. それも正しい。最後のステップ: fibot = 2, check[A[fibot]] is true, したがって, base = 2. しかし、そうあるべきです1。したがって、あなたのコードは1 + 2 + 1 = 4正しい答えを返します1 + 2 + 2 = 5。

それを行う正しい方法は次のようになりますL = 0。Rから0までのそれぞれについて、部分配列に個別の値のみが含まれるまで、 を右にn - 1移動し続けます (配列内の各値の出現回数を維持し、 2 回以上出現できる唯一の要素であるという事実を使用できます)。LA[R]

コードにはもう 1 つ問題があります。テスト プラットフォームで が 32 ビット型の場合 (たとえば、 のすべての要素が異なる場合) 、sum変数がオーバーフローする可能性があります。intA

なぜあなたのアルゴリズムが間違っているのかという質問については、そもそもなぜそれが正しいのかわかりません。証明できますか？base = fibot割り当ては、私には非常に恣意的に見えます 。

于 2016-11-28T17:37:27.923 に答える
0

私が C++ で実装したアルゴリズムの説明に続いて、実際の実装を共有したいと思います。

  1. 各要素は個別の 1 項目のスライスであるため、個別のスライスの最小量は N であることに注意してください。
  2. 最初の要素からバック インデックスを開始します。
  3. 最初の要素からフロント インデックスを開始します。
  4. シーケンスで重複が見つかるまで前線を進めます。
  5. 各反復で、必要な量でカウンターをインクリメントします。これは、表と裏の違いです。
  6. 任意の反復で最大カウントに達した場合は、すぐに戻ってわずかな最適化を行います。
  7. シーケンスの各反復で、発生した要素を記録します。
  8. 重複が見つかったら、バック インデックスを重複の 1 つ前に進めます。
  9. バック インデックスを進めながら、発生したすべての要素をクリアします。これは、それらの要素を超えて新しいスライスを開始するためです。

このソリューションの実行時の複雑さは、O(N)各
要素を処理するためです。

このソリューションのスペースの複雑さはO(M)、発生した要素をシーケンスに格納するためのハッシュがあるためです。このハッシュの最大要素は M です。

int solution(int M, vector<int> &A)                                             
{                                                                               
  int N = A.size();                                                             
  int distinct_slices = N;                                                      
  vector<bool> seq_hash(M + 1, false);                                          
  for (int back = 0, front = 0; front < N; ++back) {                            
    while (front < N and !seq_hash[A[front]]) { distinct_slices += front - back; if (distinct_slices > 1000000000) return 1000000000; seq_hash[A[front++]] = true; }
    while (front < N and back < N and A[back] != A[front]) seq_hash[A[back++]] = false;
    seq_hash[A[back]] = false;                                                  
  }                                                                             
                                                                                
  return distinct_slices;                                                       
}
于 2021-11-12T21:40:34.247 に答える