binary string Archives - Huahua's Tech Road

Input: s = "1101" Output: 6 Explanation: "1101" corressponds to number 13 in their decimal representation. Step 1) 13 is odd, add 1 and obtain 14. Step 2) 14 is even, divide by 2 and obtain 7. Step 3) 7 is odd, add 1 and obtain 8. Step 4) 8 is even, divide by 2 and obtain 4. Step 5) 4 is even, divide by 2 and obtain 2. Step 6) 2 is even, divide by 2 and obtain 1.

Solution: Simulation

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int numSteps(string s) {

int ans = 0;

int carry = 0;

// The highest bit must be 1,

// process to the 2nd highest bit

for (int i = s.length() - 1; i > 0; --i) {

if (s[i] - '0' + carry == 1) {

ans += 2; // odd: +1, even: / 2

carry = 1; // always has a carry

} else {

ans += 1; // even: / 2

// carray remains e.g. 1 + 1 = 10, or 0 + 0 = 00

}

// If there is a carry, then it's even, one more step.

return ans + carry;

}

};

Python3

# Author: Huahua

class Solution:

def numSteps(self, s: str) -> int:

ans, carry = 0, 0

for i in range(1, len(s)):

if ord(s[-i]) - ord('0') + carry == 1:

ans += 2

carry = 1

else:

ans += 1

return ans + carry

题目大意：给你一个二进制的字符串，问有多少子串的0个数量等于1的数量。

Problem:

https://leetcode.com/problems/count-binary-substrings/description/

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"

Output: 6

Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: "10101"

Output: 4

Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Note:

s.length will be between 1 and 50,000.
s will only consist of “0” or “1” characters.

Solution 0: Search

Try all possible substrings and check whether it’s a valid one or not.

Time complexity O(2^n * n) TLE

Space complexity: O(n)

Solution 1: Running Length

For S = “000110”, there are two virtual blocks “[00011]0” and “000[110]” which contains consecutive 0s and 1s or (1s and 0s)

Keep tracking of the running length of 0, 1 for each block

“00011” => ‘0’: 3, ‘1’:2

ans += min(3, 2) => ans = 2 (“[0011]”, “0[01]1”)

“110” => ‘0’: 1, ‘1’: 2

ans += min(1, 2) => ans = 3 (“[0011]”, “0[01]1”, “1[10]”)

We can reuse part of the running length from last block.

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 43 ms

class Solution {

public:

int countBinarySubstrings(string s) {

vector<int> lens(128, 0);

int i = 0;

int l = 0;

int ans = 0;

while (true) {

while (i < s.length() && s[i] == s[l]) ++i;

lens[s[l]] = i - l;

ans += min(lens['0'], lens['1']);

if (i == s.length()) break;

lens[s[i]] = 0;

l = i;

}

return ans;

}

};

Posts tagged as “binary string”

花花酱 LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One

Solution: Simulation

C++

Python3

花花酱 LeetCode 696. Count Binary Substrings