возможные отдельные подмассивы

Question

Получить такое количество возможных отдельных подмассивов, чтобы в них было не более заданного количества нечетных чисел.

Пример:

arr = [2,1,2,1,3]
m = 2.

Ответ:

10

Пояснение:

• Отдельные подмассивы с 0 нечетными числами = [2 ]
• Отдельные подмассивы с 1 нечетным числом = [2,1], [1], [2,1,2], [1,2] и [3]
• Отдельные подмассивы массивы с 2 нечетными числами = [2,1,2,1], [1,2,1], [2,1,3], [1,3]

Таким образом, всего 10 возможных различных подмассивов.

Ограничения:

Размер массива может составлять до 1000 элементов, m может варьироваться от 1 до размера массива.

public static int process(List<Integer> arr, int m) {
    Set<String> set = new LinkedHashSet<>();
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i; j < arr.size(); j++) {
            int odd = 0;
            StringBuilder sb = new StringBuilder();
            for (int k1 = i; k1 <= j; k1++) {
                if (arr.get(k1) % 2 != 0) {
                    odd++;
                }
                sb.append(arr.get(k1) + " ");
            }
            if (odd <= m) {
                set.add(sb.toString());
            }

        }
    }
    return set.size();
}

Эта программа работает для небольших входов, но, поскольку у меня есть 3 цикла for, она не работает для больших входов. Каков правильный подход к решению этой программы?

Я уже просмотрел этот пост - найти количество подмассивов с указанным количеством нечетных целых чисел но здесь вопросы не рассматриваются о отдельные подмассивы.

Answer 1

Я построил решение этой проблемы на C ++, используя Tr ie. Сложность составляет O (n²), но она дешевле в пространстве.

Идея состоит в том, чтобы построить Tr ie со всеми возможностями, а затем выполнить BFS в Tr ie, не обращая внимания на превышают лимит нечетных чисел.

#include <bits/stdc++.h>
using namespace std;
#define odd(n) (n % 2 != 0)

struct trie {
    unordered_map<int, trie*> root;
    trie(){ root.clear(); }
    bool contains(int key){ return root.find(key) != root.end();}
    void add(int *arr, int index, int n){
        trie *t = this;
        for(int i = index; i < n; i++){
            if(t->contains(arr[i])){
                t = t->root[arr[i]];
            }
            else{
                t->root[arr[i]] = new trie();
                t = t->root[arr[i]];
            }
        }
    }
    int BFS(int m){
        queue<pair<trie*, int>> q;
        q.push(make_pair(this, 0));
        int ans = 0;
        while(q.size()){
            pair<trie*, int> p = q.front();
            q.pop();
            
            for (auto& it: p.first->root) {
                if(p.second + odd(it.first) <= m) ans++;
                else continue;
                q.push(make_pair(it.second, p.second + odd(it.first)));
            }
        }
        return ans;
    }
};

trie* t;

int main(){
    t = new trie();
    int arr[] = {2,1,2,1,3};
    int n = 5;
    int m = 2;
    
    for(int i = 0; i < n; i++){
        t->add(arr, i, n);
    }
    
    cout<<t->BFS(m)<<endl;

    return 0;
}

ВЫХОД: 10.

Answer 2

Вот подход O (n ^ 2):

1. позволяет предположить, что элементы хранятся в массиве размера n + 1, в местах [1 .... n]
2. позволяет изменить массив соответственно: A[0]=0 и A[i] = A[i-1] + (A[i]%2==1 ? 1 : 0), поэтому теперь A [i] хранит количество нечетных чисел в диапазоне [0 ... i]
3. Обратите внимание на количество нечетных чисел в некотором диапазоне [i,j] теперь такое же, как A[j]-A[i-1]
4. Теперь просто проверьте все возможные диапазоны в O (n ^ 2)
5. Для отдельных подмассивов мы можем использовать структуру данных Set / Ha sh , но нам нужно эффективно хранить подмассив.
6. наиболее эффективным кажется хеширование, мы можем выполнять полиномиальное хеширование, используя некоторую базу b и модуль m, так что H[0] = 0, H[i] = H[i-1] * b + A[i] % m, если a и m - простые числа, которые больше, чем максимальное входное значение должно работать

псевдокод:

int res = 0;

for(int i=1; i<=n; i++)
 A[i] = A[i-1] + (A[i]%2 == 1);

for(int i=1; i<=n; i++)
for(int j=i; j<=n; j++)
  res+=A[j]-A[i-1] <= m;