“Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details.”

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 89th day 🎈!
🚀 Algorithm 🚀

🌲 Example: Count binary substrings

Given a string s, count the number of non-empty (continuous) substrings with the same number of zeros and ones, and all zeros and all ones in those substrings are continuous.

Repeated substrings count the number of times they occur.

Example 1:

Input:"00110011"Output:6Explanation:6Substrings have the same number of continuities1and0:"0011","01","1100","10","0011"And"01". Note that some repeated substrings count their occurrences. In addition,"00110011"Is not a valid substring because all0(and1) Not put together.Copy the code

Example 2:

Input:"10101"Output:4Explanation:4Substring:"10","01","10","01", they have the same amount of continuity1and0.Copy the code

Tip:

  • S. length is between 1 and 50,000.
  • The s contains only 0 or 1 characters.

🌻C# method: new space traversal

  • Define a dictionary to hold strings and subscripts, and store an array to the dictionary
  • Loop through another array and dictionary to see if the key has the same value, then check the index and

Code:

public class Solution {
    public int CountBinarySubstrings(string s) {
        int last = 0;
        int curlength = 1;
        int ans = 0;
        for(int i=1; i<s.Length; i++) {if(s[i]==s[i- 1])
            {
                curlength++;
            }
            else
            {
                ans += Math.Min(last,curlength);
                last = curlength;
                curlength = 1;
            }
        }
        ans += Math.Min(last,curlength);
        returnans; }}Copy the code

The execution result

By execution time:76Ms, in all C# beat 90.50% of users in submissionMemory consumption:41.4MB, in all C# beat 20.90% of users in submission
Copy the code

🌻Java methods: Group by character

Thinking analytical

We can group the string s by 0 and 1 segments. For example, s=00111011. We get counts={2,3,1,2}.

The two adjacent numbers in the COUNTS array must represent two different characters. Suppose the two adjacent numbers in the COUNTS array are u or V. They correspond to u zeros and V ones, or U ones and V zeros. The number of substrings they can form that satisfy the condition is min{u,v}, that is, the contribution of a pair of adjacent numbers to the answer.

We can just go through all the neighboring pairs, sum up their contributions, and get the answer.

It is not difficult to get an implementation like this:

Code:

class Solution {
    public int countBinarySubstrings(String s) {
        List<Integer> counts = new ArrayList<Integer>();
        int ptr = 0, n = s.length();
        while (ptr < n) {
            char c = s.charAt(ptr);
            int count = 0;
            while (ptr < n && s.charAt(ptr) == c) {
                ++ptr;
                ++count;
            }
            counts.add(count);
        }
        int ans = 0;
        for (int i = 1; i < counts.size(); ++i) {
            ans += Math.min(counts.get(i), counts.get(i - 1));
        }
        returnans; }}Copy the code

The execution result

By execution time:12Ms, beat out all Java commits45.41% user memory consumption:39.8MB, beat out all Java commits33.40% of the userCopy the code

Complexity analysis

Time complexity: O(n) Space complexity: O(n)Copy the code

💬 summary

  • Today is the 89th day of buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!