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

Question

给定一个字符串，我们需要找出其中 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

Answer 1

问题是您从同一起点多次计算相同的字符。您可以轻松地从每个起点计算一次 1 和 0：在遍历子字符串的同时。从长度为 0 的子串开始，而不是从最长的子串开始。

进行此更改后，您将从 O(n^3) 减少到 O(n^2)，而无需执行任何异常或违反直觉的操作。

“是 O(n^2) 最优化的解决方案”——不，但这是改进算法的良好开端。可以进一步优化。

Answer 2

将'0'和'1'分别视为整数1和-1。然后字符串变成一个整数数组。计算其前缀和数组s，即s[0] = 0和s[i] = a[0] + ... + a[i - 1]。现在，每个“1”个数 > “0”个数的子串都对应一对 (i, j)，使得 i < j 和 s[i] > s[j]。然后你可以使用 find total number of (i,j) pairs in array such that i<j and a[i]>a[j] 中的技巧。时间复杂度为 O(n log n).

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

Find total number of substrings with 1's greater than 0's, need optimization

c++

algorithm

optimization

substring

time-complexity