子串數

我正在完成這個編程任務：具有相等的連續 0 和 1 的子字串的計數，

給定只有 0 和 1 的二進制字串 str 。任務是計算字串 str 的子串總數，使每個子串中的連續 0 和 1 的數量相等。

例子 ：

Input: str = “010011” 
Output: 4 

解釋：

The substrings with consecutive 0’s and 1’s are “01”, “10”, “0011”, “01”. Hence, the count is 4. 

筆記：

The two “01” are at different positions: [0, 1] and [3, 4]. 
“010011” has the same number of 0’s and 1’s but they are not consecutive.

例子 ：

Input: str = “0001110010” 
Output: 7

解釋：

The substrings with consecutive 0’s and 1’s are “000111”, “0011”, “01”, “1100”, “10”, “01”, “10”.

這是它的 Java 程式：

class GFG{
 
    // Function to find the count
    // of substrings with equal no.
    // of consecutive 0's and 1's
    static int countSubstring(String S, int n)
    {
        // To store the total count
        // of substrings
        int ans = 0;
     
        int i = 0;
     
        // Traversing the string
        while (i < n) {
     
            // Count of consecutive
            // 0's & 1's
            int cnt0 = 0, cnt1 = 0;
     
            // Counting subarrays of
            // type "01"
            if (S.charAt(i) == '0') {
     
                // Count the consecutive
                // 0's
                while (i < n && S.charAt(i) == '0') {
                    cnt0  ;
                    i  ;
                }
     
                // If consecutive 0's
                // ends then check for
                // consecutive 1's
                int j = i;
     
                // Counting consecutive 1's
                while (j < n && S.charAt(j) == '1') {
                    cnt1  ;
                    j  ;
                }
            }
     
            // Counting subarrays of
            // type "10"
            else {
     
                // Count consecutive 1's
                while (i < n && S.charAt(i) == '1') {
                    cnt1  ;
                    i  ;
                }
     
                // If consecutive 1's
                // ends then check for
                // consecutive 0's
                int j = i;
     
                // Count consecutive 0's
                while (j < n && S.charAt(j) == '0') {
                    cnt0  ;
                    j  ;
                }
            }
     
            // Update the total count
            // of substrings with
            // minimum of (cnt0, cnt1)
            ans  = Math.min(cnt0, cnt1);
        }
     
        // Return answer
        return ans;
    }
     
    // Driver code
    static public void main(String args[])
    {
        String S = "0001110010";
        int n = S.length();
     
        // Function to print the
        // count of substrings
        System.out.println(countSubstring(S, n));
    }
}

該鏈接說： Time Complexity: O(N), where N = length of string.

但是在這段代碼中，我們有一個外觀while (i < n) {，然后是內部回圈 while (i < n && S.charAt(i) == '0')and while (j < n && S.charAt(j) == '1')，所以這怎么可能是 O(N) 而不是 O(N^2)。

uj5u.com熱心網友回復：

我們有兩種型別的內回圈。第一種型別是迭代i。如果滿足該型別的條件，i則外回圈中的值也會增加。因此，迭代的總和將為Theta(n)。

第二種型別是迭代j。的一點是，如果內部的任何的兩個條件（if (S.charAt(i) == '0')或else）的j計數器迭代k次數（例如），這意味著對于外部回圈的下一次迭代，相反的條件將是其中真if (S.charAt(i) == '0')和else。因此，內回圈i會迭代k多次，并增加外回圈k步驟的值。因此，2n在這種情況下，計算的總和最多可以是。

因此，關鍵點在于條件的依賴型別以及內回圈與外回圈。基于解釋的依賴關系，該演算法在Theta(n)和 中O(n)。

標籤：爪哇 算法

上一篇：Python中字串的子詞

下一篇：不同的被加數問題-貪心演算法（Python）