可能的不同子数组 [英] possible distinct sub arrays

问题描述

获取许多可能的 distinct 子数组，以便它们中最多具有给定数量的奇数.

Get a number of possible distinct sub-arrays such that they have at most the given number of odd numbers in it.

示例:

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个可能的不同子数组.

So a total of 10 possible distinct sub arrays.

约束:

数组大小最多可以包含1000个元素，m的范围可以从1到数组大小.

The array size can be up to 1000 elements, m can range from 1 to array size.

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循环，因此对于大输入而言失败.解决该程序的正确方法是什么?

This program works for small inputs but as I have 3 for loops it fails for large inputs. What is the correct approach to solve this program?

我已经看过这篇文章-找到具有指定数量的奇数整数的子数组的数量，但是这里的问题不在考虑与 distinct 子数组有关.

I have already gone through this post - find number of subarrays with specified number of odd integers but here the questions is not considering about distinct sub arrays.

推荐答案

我使用Trie为此问题构建了C ++解决方案.复杂度为O(n²)，但在空间上却不那么昂贵.

I built a C++ solution for this problem using a Trie. The complexity is O(n²) but it is less expensive in space.

想法是建立一个具有所有可能性的Trie，然后在Trie中执行BFS，并注意不要超过奇数的限制.

The idea is to build a Trie with all the possibilities, then perform a BFS in the Trie paying attention not to overpass the limit of odd numbers.

#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.

这篇关于可能的不同子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！