Рубрики

Для заданной двоичной строки подсчитайте количество подстрок, которые начинаются и заканчиваются на 1.

Для заданной двоичной строки подсчитайте количество подстрок, которые начинаются и заканчиваются на 1. Например, если входной строкой является «00100101», то есть три подстроки «1001», «100101» и «101».

Источник: Amazon Интервью Опыт | Комплект 162

Уровень сложности: Новичок

Простое решение — запустить два цикла. Внешние циклы выбирают каждый 1 как начальную точку, а внутренний цикл ищет конец 1 и увеличивает счетчик всякий раз, когда находит 1.

C ++

// Простая программа на C ++ для подсчета количества
// подстроки, начинающиеся и заканчивающиеся 1
#include<iostream>

   

using namespace std; 

  

int countSubStr(char str[]) 

int res = 0; // Инициализировать результат

  
// Выберите начальную точку

for (int i=0; str[i] !='\0'; i++) 

        if (str[i] == '1'

        

            // Поиск всех возможных конечных точек

            for (int j=i+1; str[j] !='\0'; j++) 

            if (str[j] == '1'

                res++; 

        

return res; 

  
// Программа драйвера для проверки вышеуказанной функции

int main() 

char str[] = "00100101"

cout << countSubStr(str); 

return 0; 

Джава

// Простая программа на C ++ для подсчета количества
// подстроки, начинающиеся и заканчивающиеся 1

  

class CountSubString 

{

    int countSubStr(char str[],int n) 

    {

        int res = 0// Инициализировать результат

  

        // Выберите начальную точку

        for (int i = 0; i<n; i++) 

        {

            if (str[i] == '1'

            {

                // Поиск всех возможных конечных точек

                for (int j = i + 1; j< n; j++) 

                {

                    if (str[j] == '1')

                        res++;

                }

            }

        }

        return res;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        CountSubString count = new CountSubString();

        String string = "00100101";

        char str[] = string.toCharArray();

        int n = str.length;

        System.out.println(count.countSubStr(str,n));

    }

}

python3

# Простая программа на Python 3 для подсчета количества
# подстроки, начинающиеся и заканчивающиеся 1

  

def countSubStr(st, n) :

      

    # Инициализировать результат

    res = 0   

   

   # Выберите отправную точку

    for i in range(0, n) :

        if (st[i] == '1') :

  

            # Поиск всех возможных конечных точек

            for j in range(i+1, n) :

                if (st[j] == '1') :

                    res = res + 1

          

    return res

      

   
# Программа драйвера для проверки вышеуказанной функции

st = "00100101";

list(st)

n= len(st)

print(countSubStr(st, n), end="")

  

  
# Этот код добавлен
# Никита Тивари.

C #

// Простая программа на C # для подсчета количества
// подстроки, начинающиеся и заканчивающиеся 1

using System;

  

class GFG

{

public virtual int countSubStr(char[] str, 

                               int n)

{

    int res = 0; // Инициализировать результат

  

    // Выберите начальную точку

    for (int i = 0; i < n; i++)

    {

        if (str[i] == '1')

        {

            // Поиск всего возможного

            // конечная точка

            for (int j = i + 1; j < n; j++)

            {

                if (str[j] == '1')

                {

                    res++;

                }

            }

        }

    }

    return res;

}

  
// Код драйвера

public static void Main(string[] args)

{

    GFG count = new GFG();

    string s = "00100101";

    char[] str = s.ToCharArray();

    int n = str.Length;

    Console.WriteLine(count.countSubStr(str,n));

}
}

  
// Этот код предоставлен Shrikant13

PHP

<?php 
// Простая PHP-программа для подсчета количества
// подстроки, начинающиеся и заканчивающиеся 1

  

function countSubStr($str

    $res = 0; // Инициализировать результат

  

    // Выберите начальную точку

    for ($i = 0; $i < strlen($str); $i++) 

    

            if ($str[$i] == '1'

            

                // Поиск всего возможного

                // конечная точка

                for ($j = $i + 1; 

                     $j < strlen($str); $j++) 

                if ($str[$j] == '1'

                    $res++; 

            

    

    return $res

  
// Код драйвера

$str = "00100101"

echo countSubStr($str); 

  
// Этот код предоставлен ita_c
?>


Выход:

3

Временная сложность вышеуказанного решения составляет O (n 2 ). Мы можем найти количество в O (n), используя единственный обход входной строки. Ниже приведены шаги.
а) Подсчитайте количество единиц. Пусть счет 1 будет м.
б) Возврат м (м-1) / 2
Идея состоит в том, чтобы подсчитать общее количество возможных пар единиц.

C ++

// AO (n) C ++ программа для подсчета количества
// подстроки, начинающиеся и заканчивающиеся 1
#include<iostream>

  

using namespace std;

  

int countSubStr(char str[])

{

   int m = 0; // Количество единиц во входной строке

  

   // Обход входной строки и подсчет 1 в ней

   for (int i=0; str[i] !='\0'; i++)

   {

        if (str[i] == '1')

           m++;

   }

  

   // Возвращаем количество возможных пар среди m 1

   return m*(m-1)/2;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

  char str[] = "00100101";

  cout << countSubStr(str);

  return 0;

}

Джава

// AO (n) C ++ программа для подсчета количества подстрок
// начинаем и заканчиваем 1

  

class CountSubString 

{

    int countSubStr(char str[], int n) 

    {

        int m = 0; // Количество единиц во входной строке

  

        // Обход входной строки и подсчет 1 в ней

        for (int i = 0; i < n; i++) 

        {

            if (str[i] == '1')

                m++;

        }

  

        // Возвращаем количество возможных пар среди m 1

        return m * (m - 1) / 2;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        CountSubString count = new CountSubString();

        String string = "00100101";

        char str[] = string.toCharArray();

        int n = str.length;

        System.out.println(count.countSubStr(str, n));

    }

}

python3

# Программа Python3 для подсчета количества
# подстроки, начинающиеся и заканчивающиеся 1

  

def countSubStr(st, n) :

  

    # Количество единиц во входной строке

    m = 0  

   

    # Пройдите строку ввода и

    количество штук в нем

    for i in range(0, n) :

        if (st[i] == '1') :

            m = m + 1

          

    # Возврат количества возможных

    # пары среди м 1

    return m * (m - 1) // 2

     

   
# Программа драйвера для проверки вышеуказанной функции

st = "00100101";

list(st)

n= len(st)

print(countSubStr(st, n), end="")

  

  
# Этот код добавлен
# Никита Тивари.

C #

// AO (n) C # программа для подсчета
// количество начинающихся подстрок
// и заканчивая 1

using System;

  

class GFG 

{

int countSubStr(char []str, int n) 

{

    int m = 0; // Подсчет 1 в

               // строка ввода

  

    // Обход строки ввода и

    // количество единиц в нем

    for (int i = 0; i < n; i++) 

    {

        if (str[i] == '1')

            m++;

    }

  

    // Возвращаем количество возможных

    // пары среди м 1

    return m * (m - 1) / 2;

}

  
// Код драйвера

public static void Main(String[] args) 

{

    GFG count = new GFG();

    String strings = "00100101";

    char []str = strings.ToCharArray();

    int n = str.Length;

    Console.Write(count.countSubStr(str, n));

}
}

  
// Этот код предоставлен princiraj

PHP

<?php 
// Простая PHP-программа для подсчета количества
// подстроки, начинающиеся и заканчивающиеся 1

  

function countSubStr($str

    $m = 0; // Инициализировать результат

  

    // Выберите начальную точку

    for ($i = 0; $i < strlen($str); $i++) 

    

        if ($str[$i] == '1'

        

            $m++;

        }

    }

      

    // Возвращаем количество возможных

    // пары среди м 1

    return $m * ($m - 1) / 2;

}

  
// Код драйвера

$str = "00100101";

echo countSubStr($str);

  
// Этот код добавлен
// Аканкша Рай
?>


Выход:

3

Эта статья предоставлена Шивам . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Для заданной двоичной строки подсчитайте количество подстрок, которые начинаются и заканчиваются на 1.

0.00 (0%) 0 votes