时间戳

首页 > 解决方案 > 查找 1 大于 0 的子串总数，需要优化

c++ - 查找 1 大于 0 的子串总数，需要优化

问题描述

给定字符串，我们需要找出其中 1 大于 0 的子字符串的总数。

我使用动态编程解决了这个问题，但我无法提出解决方案，我成功编写了一个简单的逻辑，但我无法优化代码（即超过时间限制）

任何对优化的帮助或对新方法的建议都将得到充分的帮助。以下代码的时间复杂度为 O(n^3) 任何降低时间复杂度的解决方案都会有所帮助。

预先感谢。

我使用的代码：

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(){
    int tc =0; //total count
    string st; //original string
    getline(cin,st);
    int lent = st.size(); //size of string
    for(int i =0;i<lent;i++){ //loop to generate all possible substrings
        int j = lent-1;
        while(j>=i){
            
            string st1(st.begin()+i,st.end()-j+i); // A substring
            int c1 = count(st1.begin(),st1.end(),'1'); // count of 1's in substring
            if(c1 > st1.size()-c1) tc++; // Condition to check if 1's are more
            j--;
        }
    }
    cout << tc; // Print total substrings
}

注意：子字符串是字符串中连续的字符序列。有关子字符串的更多信息，请访问Wikipedia

标签： c++algorithmoptimizationtime-complexitysubstring

解决方案

将“0”和“1”分别视为整数 1 和 -1。然后字符串变成一个整数数组。计算其前缀和数组s，即s[0] = 0和s[i] = a[0] + ... + a[i - 1]。现在每个具有 '1's > number of '0's 的子字符串对应于一对(i, j)这样i < j和s[i] > s[j]。然后，您可以使用该技巧在数组中查找 (i,j) 对的总数，例如 i<j 和 a[i]>a[j]。时间复杂度为 O(n log n)。

推荐阅读