Пребройте поднизовете с еднакъв брой 0s, 1s и 2s


Ниво на трудност Трудно
Често задавани в Citrix FreeCharge Goldman Sachs OYO Стаи Times Internet Twilio
Хашиш Низ

Проблемът „Брой поднизове с еднакъв брой 0s, 1s и 2s” гласи, че ви е дадено a низ който има само 0, 1 и 2. Изявлението за проблем иска да открие броя на поднизовете, които съдържат равен номер само на 0, 1 и 2.

Пример

Пребройте поднизовете с еднакъв брой 0s, 1s и 2s

str= “01200”
2

Обяснение

Два подниза, които имат еднакъв брой 0, 1 и 2, са (012) и (120).

str= “10201012”
4

Обяснение

Четири подниза, които имат равен брой 0, 1 и 2, са (102) и (201), (012) и (201012).

алгоритъм

  1. Декларирайте а карта.
  2. Инициализирайте чифт до 0 и го поставете в картата с 1.
  3. комплект нулев брой, onecount, два броя, и продукция да 0.
  4. Примка от i = 0 до i
    1. Проверете за всеки знак от текущия подниз дали е 0, 1 и 2. След това актуализирайте броя съответно.
    2. Изчислете разликите по двойки.
    3. Проверете дали разликата не присъства в картата, след това добавете 0 към изхода.
    4. В противен случай добавете стойността на temp на map в изхода.
    5. Добавете temp към картата.
  5. Връщане на изхода.

Обяснение

Даден ни е низ, който има само 0, 1 и 2. Нашата задача е да открием общия брой на поднизовете, които са равни на 0, 1 и 2. За това ще използваме хеширане. Инициализирайте двойка с (0, 0) като ключ и нейната стойност като 1 по подразбиране в картата. Изчислете разликата между нулев брой и onecount, и нулев брой и twocount. Ще съхраняваме стойността в чифт и тази двойка в картата. Ако разликата на двойка вече съществува на картата, просто вземете / извлечете стойността на текущата двойка от картата. След това добавете това към изхода. Ако разликата вече не присъства в картата. След това добавете 0 към изхода. Също така трябва да вмъкнем двойката разлики в картата и да увеличим нейната честота, ако тя вече съществува в картата. В противен случай съхранява нов запис за двойката разлика с 1 като стойност в картата.

Нека разгледаме пример за него:

Пример

Низ = “01200”

Вече инициализирахме двойка на 0 и вмъкнахме двойка като ключ и 1 като стойност в картата. Ще извлечем първия знак като 0. Така че ще изчислим двойката разлика и ще получим (1,1). Освен това това е така, защото сме увеличили броя на нулите. Така че ще изчислим разликата и ще получим този резултат. След получаване на стойността на текущата стойност на картата и добавяне на 0 към изхода, защото тази двойка е нова. Ние просто ще вмъкнем двойката в картата. Текущият изход е 0.

Ще отидем за следващия знак, който е 1. Сега ще увеличим броя на нечии. Тогава ще получим разликите като 0,1. Тъй като тази двойка също е нова, ще добавим това към картата и изходът ще остане същият.

След това получаваме 2 като вход, ще получим двойката като 0, 0, защото всичкият брой на цифрите вече е 1. Ще съхраним и това в картата и този път ще актуализираме изхода, защото 0,0 вече сме инициализирани в карта така че изходът е 1 сега.

След това получаваме като 0, сега нулевото броене е две. Получаваме 1,1, тъй като това вече е на картата. След това ще актуализираме изхода и ще го вмъкнем в картата със стойността 2.

На този етап открихме всичките ни възможни поднизове, това е начинът, по който получаваме равни числа 0, 1 и 2.

код

C ++ код за преброяване на поднизове с еднакъв брой 0s, 1s и 2s

#include<bits/stdc++.h>
using namespace std;

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 

int getSubString(string str)
{
    int n = str.length();
    unordered_map< pair<int, int>, int, hash_pair > MAP;
    MAP[make_pair(0, 0)] = 1;
    int zerocount = 0, onecount = 0, twocount = 0;
    int output = 0;
    for (int i = 0; i < n; ++i)
    {
        if (str[i] == '0')
            zerocount++;
        else if (str[i] == '1')
            onecount++;
        else
            twocount++;
        pair<int, int> x = make_pair(zerocount - onecount,zerocount - twocount);
        output = output + MAP[x];
        MAP[x]++;
    }
    return output;
}
int main()
{
    string str = "10201012";
    cout << getSubString(str) << endl;
    return 0;
}
4

Java код за броене на поднизове с еднакъв брой 0s, 1s и 2s

import java.util.HashMap;
class Pair
{
    int first, second;
    Pair(int x, int y)
    {
        this.first=x;
        this.second=y;
    }
}
class SubstringCount
{
    public static int getSubString012(String str1)
    {
        int n = str1.length();

        HashMap< String, Integer > MAP=new HashMap<>();



        MAP.put("0:0", 1);

        int zerocount = 0, onecount = 0, twocount = 0;

        int output = 0;
        for (int i = 0; i < n; ++i)
        {
            if (str1.charAt(i)=='0')
                zerocount++;
            else if (str1.charAt(i) == '1')
                onecount++;
            else
                twocount++;

            Pair pair = new Pair(zerocount - onecount, zerocount - twocount);

            String str=pair.first+":"+pair.second;

            if(!MAP.containsKey(str))
                output = output + 0;
            else
                output = output + MAP.get(str);

            if(MAP.containsKey(str))
                MAP.put(str, MAP.get(str)+1);
            else
                MAP.put(str, 1);
        }

        return output;
    }
    public static void main(String [] args)
    {
        String str = "10201012";
        System.out.println(getSubString012(str));
    }
}
4

Анализ на сложността

Сложност във времето

О (п)  където "н" е броят на елементите в масива. Тъй като използвахме HashMap, цялото вмъкване, изтриване и търсене изисква само O (1) време за операция.

Сложност на пространството

О (п)  където "н" е броят на елементите в масива.