დაითვალეთ ქვესადგურები თანაბარი რაოდენობის 0s, 1s და 2s


Რთული ტური Hard
ხშირად ეკითხებიან Citrix უფასო დატენვა Goldman Sachs OYO ოთახები Times ინტერნეტი Twilio
Hash სიმებიანი

პრობლემა "დაითვალეთ ქვესუქნები 0, 1 და 2 თანაბარი რაოდენობით" აღნიშნავს, რომ თქვენ გეძლევათ ა სიმებიანი რომ აქვს მხოლოდ 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. უცნობია zerocount, თანხის დათვლა, twocount, და გამომავალი to 0.
  4. მარყუჟი i = 0-დან i- მდე
    1. შეამოწმეთ მიმდინარე ქვესტრიქონის თითოეული სიმბოლო, არის 0, 1 და 2. შემდეგ განაახლეთ რაოდენობა შესაბამისად.
    2. გამოთვალეთ წყვილის განსხვავებები.
    3. შეამოწმეთ, თუ განსხვავება არ არის რუკაზე, შემდეგ დაამატეთ 0 გამომავალს.
    4. სხვაგვარად, დაამატეთ რუკის დროებითი მნიშვნელობა გამომავალში.
    5. დაამატეთ დროებითი რუქა.
  5. დაბრუნების შედეგი.

განმარტება

გვეძლევა სტრიქონი, რომელსაც აქვს მხოლოდ 0, 1 და 2. ჩვენი ამოცანაა გავეცნოთ ქვესადგურების საერთო რაოდენობას, რომელთა ტოლი არ არის 0, 1 და 2. ამისათვის ჩვენ გამოვიყენებთ ჰაშინგი. ნაგულისხმევად ინიცირება მოახდინე წყვილს (0, 0) გასაღებად და მისი მნიშვნელობა 1-ით. გამოთვალეთ განსხვავება შორის zerocount და თანხის დათვლადა zerocount და twocount. ჩვენ შევაგროვებთ მნიშვნელობას წყვილში და ამ წყვილში რუკაზე. თუ წყვილში სხვაობა უკვე არსებობს რუკაზე, მაშინ მარტივად მიიღეთ / წაიღეთ ამჟამინდელი წყვილის მნიშვნელობა რუკიდან. შემდეგ დაამატეთ ეს გამომავალს. თუ განსხვავება უკვე არ არის რუქაზე. შემდეგ გამომავალს დაამატეთ 0. ჩვენ ასევე უნდა ჩავსვათ განსხვავების წყვილი რუკაზე და გავზარდოთ მისი სიხშირე, თუ ის უკვე არსებობს რუკაზე. სხვა შეინახეთ ახალი ჩანაწერი განსხვავების წყვილისთვის 1-ით, როგორც მნიშვნელობა რუკაზე.

მოდით განვიხილოთ ამის მაგალითი:

მაგალითი

სიმებიანი = "01200"

ჩვენ უკვე შევადგინეთ წყვილი 0-მდე და ჩასვით წყვილი, როგორც გასაღები და 1, როგორც მნიშვნელობა რუკაზე. ჩვენ ვიღებთ პირველ სიმბოლოს 0. – ის მსგავსად. ასე რომ, ჩვენ გამოვთვლით სხვაობის წყვილს და მივიღებთ (1,1). ასევე, ეს იმიტომ ხდება, რომ ჩვენ გავზარდეთ ნულის რაოდენობა. ასე რომ, ჩვენ გამოვთვლით სხვაობას და მივიღებთ ამ შედეგს. რუქის ამჟამინდელი მნიშვნელობის ღირებულების მიღების და გამომავალს 0-ის დამატების შემდეგ, რადგან ეს წყვილი ახალია. ჩვენ უბრალოდ ჩავსვამთ წყვილს რუკაში. ამჟამინდელი გამომავალია 0.

ჩვენ წავალთ შემდეგ სიმბოლოზე, რომელიც არის 1. ახლა ჩვენ გავზრდით ერთის რაოდენობას. შემდეგ ჩვენ მივიღებთ განსხვავებებს 0,1-ით. ვინაიდან ეს წყვილი ასევე ახალია, ამიტომ ჩვენ დავამატებთ მას რუქაზე და გამომავალი იგივე რჩება.

შემდეგ მივიღებთ 2-ს შეყვანის სახით, მივიღებთ წყვილს 0, 0-ს, რადგან ყველა ციფრის რაოდენობა ახლა არის 1. ჩვენ ისიც შევინახავთ რუქაზე და ამჯერად გამოვაქვეყნებთ გამომავალს, რადგან 0,0 ჩვენ უკვე დავიწყეთ რუქაზე გამომავალი არის 1.

შემდეგი, ჩვენ 0-ს ვგავართ, ახლა zerocount არის ორი. მივიღებთ 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

ჯავის კოდი 0, 1 და 2 თანაბარი რაოდენობის ქვესტრიქონების დასათვლელად

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

სირთულის ანალიზი

დროის სირთულე

O (n)  სადაც "ნ" არის მასივის ელემენტების რაოდენობა. ვინაიდან ჩვენ გამოვიყენეთ HashMap, ყველა ჩასმა, წაშლა და ძიება მოითხოვს მხოლოდ O (1) დროს ოპერაციისთვის.

სივრცის სირთულე

O (n)  სადაც "ნ" არის მასივის ელემენტების რაოდენობა.