Dada una string binaria S de tamaño N , la tarea es encontrar el número de grupos de 1 s solo en la string S.
Ejemplos:
Entrada: S = “100110111”, N = 9
Salida: 3
Explicación:
Los siguientes grupos son de 1 solamente:
- Agrupe sobre el rango [0, 0] que es igual a «1».
- Agrupe sobre el rango [3, 4] que es igual a «11».
- Agrupe sobre el rango [6, 8] que es igual a «111».
Por lo tanto, hay un total de 3 grupos de 1 solamente.
Entrada: S = “0101”
Salida: 2
Enfoque: el problema se puede resolver iterando sobre los caracteres de la string . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos count as 0 , que almacena el número de substrings de 1 s en S .
- Inicialice una pila , digamos st , para almacenar la substring antes de un índice de 1 s solamente.
- Itere sobre los caracteres de la string S , usando la variable i y haga lo siguiente:
- Si el carácter actual es 1 , empuje 1 en stack st .
- De lo contrario, si st no está vacío, incremente la cuenta en 1 . De lo contrario Clear st .
- Si st no está vacío, incremente la cuenta en 1, es decir, si hay un sufijo de 1s.
- Finalmente, imprima el conteo total obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the number of the
// groups of 1s only in the binary
// string
int groupsOfOnes(string S, int N)
{
// Stores number of groups of 1s
int count = 0;
// Initialization of the stack
stack<int> st;
// Traverse the string S
for (int i = 0; i < N; i++) {
// If S[i] is '1'
if (S[i] == '1')
st.push(1);
// Otherwise
else {
// If st is empty
if (!st.empty()) {
count++;
while (!st.empty()) {
st.pop();
}
}
}
}
// If st is not empty
if (!st.empty())
count++;
// Return answer
return count;
}
// Driver code
int main()
{
// Input
string S = "100110111";
int N = S.length();
// Function call
cout << groupsOfOnes(S, N) << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.Stack;
class GFG{
// Function to find the number of the
// groups of 1s only in the binary
// string
static int groupsOfOnes(String S, int N)
{
// Stores number of groups of 1s
int count = 0;
// Initialization of the stack
Stack<Integer> st = new Stack<>();
// Traverse the string S
for(int i = 0; i < N; i++)
{
// If S[i] is '1'
if (S.charAt(i) == '1')
st.push(1);
// Otherwise
else
{
// If st is empty
if (!st.empty())
{
count++;
while (!st.empty())
{
st.pop();
}
}
}
}
// If st is not empty
if (!st.empty())
count++;
// Return answer
return count;
}
// Driver code
public static void main(String[] args)
{
// Input
String S = "100110111";
int N = S.length();
// Function call
System.out.println(groupsOfOnes(S, N));
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach # Function to find the number of the # groups of 1s only in the binary # string def groupsOfOnes(S, N): # Stores number of groups of 1s count = 0 # Initialization of the stack st = [] # Traverse the string S for i in range(N): # If S[i] is '1' if (S[i] == '1'): st.append(1) # Otherwise else: # If st is empty if (len(st) > 0): count += 1 while (len(st) > 0): del st[-1] # If st is not empty if (len(st)): count += 1 # Return answer return count # Driver code if __name__ == '__main__': # Input S = "100110111" N = len(S) # Function call print(groupsOfOnes(S, N)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the number of the
// groups of 1s only in the binary
// string
static int groupsOfOnes(string S, int N)
{
// Stores number of groups of 1s
int count = 0;
// Initialization of the stack
Stack<int> st = new Stack<int>();
// Traverse the string S
for (int i = 0; i < N; i++) {
// If S[i] is '1'
if (S[i] == '1')
st.Push(1);
// Otherwise
else {
// If st is empty
if (st.Count > 0) {
count++;
while (st.Count > 0) {
st.Pop();
}
}
}
}
// If st is not empty
if (st.Count > 0)
count++;
// Return answer
return count;
}
// Driver code
public static void Main()
{
// Input
string S = "100110111";
int N = S.Length;
// Function call
Console.Write(groupsOfOnes(S, N));
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the number of the
// groups of 1s only in the binary
// string
function groupsOfOnes(S, N) {
// Stores number of groups of 1s
let count = 0;
// Initialization of the stack
var st = [];
// Traverse the string S
for (let i = 0; i < N; i++) {
// If S[i] is '1'
if (S[i] == '1')
st.push(1);
// Otherwise
else {
// If st is empty
if (st.length != 0) {
count++;
while (st.length != 0) {
st.pop();
}
}
}
}
// If st is not empty
if (st.length != 0)
count++;
// Return answer
return count;
}
// Driver code
// Input
var S = "100110111";
let N = S.length;
// Function call
document.write(groupsOfOnes(S, N));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por AakashSingh_17 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA