Ini adalah masalah tentang substring yang saya buat. Saya bertanya-tanya bagaimana menerapkan solusi O(nlog(n)) untuk masalah ini karena pendekatan naifnya cukup mudah. Inilah yang terjadi. Anda memiliki string S. S memiliki banyak substring. Dalam beberapa substring, karakter pertama dan karakter terakhir ada lebih dari sekali. Temukan berapa banyak substring di mana karakter pertama dan terakhir ada lebih dari sekali.

Input: "ABCDCBE"
Expected output: 2
Explanation: "BCDCB" and "CDC" are two such substrings

Penjelasan kasus uji hanya memiliki "BCDCB" dan "CDC" di mana karakter pertama dan terakhir sama.

Mungkin ada kasus lain selain dari kasus sampel dengan "ababcac" menjadi substring di mana karakter pertama "A" muncul 3 kali dan karakter terakhir "C" muncul dua kali. "AAAABB" juga merupakan substring lain.

"Aaaab" tidak memuaskan.

Apa yang telah saya pelajari adalah O(nlog(n)) yang mungkin atau mungkin tidak berkontribusi terhadap solusi adalah pohon yang diindeks biner. Pohon-pohon diindeks biner entah bagaimana dapat digunakan untuk menyelesaikan ini. Ada juga pencarian dan pencarian biner, tetapi pertama-tama saya ingin fokus terutama pada pohon-pohon yang diindeks biner.

Saya mencari kompleksitas ruang O(n log(n)) atau lebih baik.

Juga karakter dalam UTF-16

1
halcyon44 4 April 2021, 04:24

1 menjawab

Jawaban Terbaik

Inti dari solusi saya adalah sebagai berikut:

Iterat dari array input, dan, untuk setiap posisi, hitung jumlah substring 'valid' yang berakhir pada posisi itu. Jumlah nilai-nilai ini adalah jumlah total substring yang valid. Kami mencapainya dengan menghitung jumlah yang valid mulai ke substring, yang datang sebelum posisi saat ini, menggunakan pohon yang diindeks biner.

Sekarang untuk detail penuh:

Ketika kami mengulangi array kami memikirkan elemen saat ini sebagai akhir substring, dan kami mengatakan bahwa posisi yang merupakan awal yang valid adalah sedemikian rupa sehingga nilainya muncul lagi antara , dan posisi kita saat ini mengisinya. (I.E. Jika nilai pada awal substring muncul setidaknya dua kali di dalamnya)

Sebagai contoh:

current index              V
data  = [1, 2, 3, 4, 1, 4, 3, 2]
valid = [1, 0, 1, 1, 0, 0, 0, 0]
         0  1  2  3  4  5  6  7

Yang pertama 1 (pada index {0) adalah awal yang valid, karena ada 1 (pada index 4) setelah itu, tetapi sebelum indeks saat ini (indeks { {X4}}).

Sekarang, menghitung jumlah awal yang valid yang datang sebelum indeks saat ini memberi kita sesuatu yang cukup dekat dengan apa yang kita inginkan, kecuali bahwa kita dapat mengambil beberapa substring yang tidak memiliki dua penampilan dari nilai terakhir substring (yaitu kita saat ini sedang berlebihan)

Sebagai contoh:

current index              V
data  = [1, 2, 3, 4, 1, 4, 3, 2]
valid = [1, 0, 1, 1, 0, 0, 0, 0]
         0  1  2  3  4  5  6  7
                  ^--------^

Di sini, 4 ditandai sebagai awal yang valid (karena ada 4 lain yang muncul setelah itu), tetapi substring yang sesuai tidak memiliki dua 3 s.

Untuk memperbaikinya, kami hanya akan mempertimbangkan hal yang berlaku untuk penampilan sebelumnya dari nilai saat ini. (Ini berarti bahwa substring akan berisi nilai saat ini, dan penampilan sebelumnya, dengan demikian, elemen terakhir akan berada dalam substring setidaknya dua kali)

Pseudocode berjalan sebagai berikut:

fn solve(arr) {
  answer := 0
  for i from 1 to length(arr) {
    previous_index := find_previous(arr, i)

    if there is a previous_index {
      arr[previous_index].is_valid_start = true
      answer += count_valid_starts_up_to_and_including(arr, previous_index)
    }
  }
  return answer
}

Untuk mengimplementasikan operasi ini secara efisien, kami menggunakan tabel hash untuk melihat posisi sebelumnya dari nilai, dan pohon indeks biner (bit) untuk melacak dan menghitung posisi yang valid.

Dengan demikian, pseudocode yang lebih halus akan terlihat seperti

fn solve(arr) {
  n := length(arr)

  prev := hash_table{}
  bit  := bit_indexed_tree{length = n}

  answer := 0
  for i from 1 to length(arr) {
    value := arr[i]
    previous_index := prev[value]

    if there is a previous_index {
      bit.update(previous_index, 1)
      answer += bit.query(previous_index)
    }

    prev[value] = i
  }
  return answer
}

Akhirnya, karena pseudocode tidak selalu cukup, berikut adalah implementasi dalam C ++, di mana aliran kontrol agak munch, untuk memastikan penggunaan efisiensi std::unordered_map (tabel hash built-in C ++)

class Bit { 
    std::vector<int> m_data;
public:
    // initialize BIT of size `n` with all 0s
    Bit(int n);

    // add `value` to index `i`
    void update(int i, int value);

    // sum from index 0 to index `i` (inclusive)
    int query(int i);
};

long long solve (std::vector<int> const& arr) {
    int const n = arr.size();

    std::unordered_map<int, int> prev_index;
    Bit bit(n);

    long long answer = 0;
    int i = 0;
    for (int value : arr) {

        auto insert_result = prev_index.insert({value, i});
        if (!insert_result.second) { // there is a previous index
            int j = insert_result.first->second;

            bit.update(j, 1);
            answer += bit.query(j);

            insert_result.first->second = i;
        }

        ++i;
    }

    return answer;
}

EDIT: Untuk transparansi, berikut adalah implementasi Fenwick Tree yang saya gunakan untuk menguji kode ini

struct Bit {
    std::vector<int> m_data;
    Bit(int n) : m_data(n+2, 0) { }
    int query(int i) {
        int res = 0;
        for(++i; i > 0; i -= i&-i) res += m_data[i];
        return res;
    }
    void update(int i, int x) {
        for(++i; i < m_data.size(); i += i&-i) m_data[i] += x;
    }
};
1
Sebastián Mestre 5 April 2021, 01:24