زیرشاخه ها را با تعداد برابر 0 ، 1 و 2 بشمارید


سطح دشواری سخت
اغلب در خودتان هستید؟ شارژ رایگان گلدمن ساکس اتاق های OYO بار اینترنت Twilio
مخلوط رشته

مسئله "شمارش زیرلایه ها با تعداد برابر 0 ، 1 و 2" بیان می کند که به شما a داده می شود رشته که فقط 0 ، 1 و 2 دارد. بیانیه مسئله می خواهد تعداد زیر رشته هایی را که شامل هیچ عدد برابر 0 ، 1 و 2 هستند ، دریابد.

مثال

زیرشاخه ها را با تعداد برابر 0 ، 1 و 2 بشمارید

str= “01200”
2

توضیح

دو زیر رشته که تعداد برابر 0 ، 1 و 2 دارند (012) و (120) هستند.

str= “10201012”
4

توضیح

چهار زیر رشته که دارای تعداد برابر 0 ، 1 و 2 هستند ، (102) و (201) ، (012) و (201012) هستند.

الگوریتم

  1. اعلام الف نقشه.
  2. یک جفت را 0 کنید و آن را با 1 قرار دهید.
  3. تنظیم صفر حساب کردن, حساب کردن, دو حساب کردن ، و تولید به 0.
  4. از i = 0 به i حلقه بزنید
    1. از نظر وجود هر یک از کاراکترهای زیر رشته فعلی ، 0 ، 1 و 2 بررسی کنید.
    2. تفاوت های جفت را محاسبه کنید.
    3. بررسی کنید که آیا تفاوت در نقشه وجود ندارد ، 0 را به خروجی اضافه کنید.
    4. در غیر این صورت ، مقدار temp را به خروجی اضافه کنید.
    5. دما را به نقشه اضافه کنید.
  5. خروجی را برگردانید.

توضیح

رشته ای به ما داده می شود که فقط 0 ، 1 و 2 داشته باشد. وظیفه ما این است که تعداد کل زیرشاخه ها را که هیچ برابر 0 ، 1 و 2 نیست ، پیدا کنیم. برای این ، ما قصد داریم از هشی کردن. به طور پیش فرض یک جفت با کلید (0 ، 0) و مقدار آن را به عنوان 1 در نقشه شروع کنید. تفاوت بین را محاسبه کنید صفر حساب کردن و حساب کردنو صفر حساب کردن و دو حساب کردن. ما مقدار را به صورت یک جفت و آن جفت در نقشه ذخیره خواهیم کرد. اگر اختلاف یک جفت از قبل در نقشه وجود دارد ، پس به سادگی مقدار جفت فعلی را از نقشه دریافت / بازیابی کنید. سپس آن را به خروجی اضافه کنید. اگر اختلاف از قبل در نقشه وجود نداشته باشد. سپس 0 را به خروجی اضافه کنید. همچنین باید جفت اختلاف را در نقشه وارد کنیم و اگر قبلاً در نقشه وجود دارد ، فرکانس آن را افزایش دهیم. در غیر اینصورت یک ورودی جدید برای جفت اختلاف با 1 به عنوان یک مقدار در نقشه ذخیره کنید.

اجازه دهید مثالی برای آن در نظر بگیریم:

مثال

رشته = "01200"

ما قبلاً جفت را 0 قرار داده و جفت را به عنوان کلید و 1 را به عنوان مقدار در نقشه وارد کرده ایم. اولین کاراکتر را مانند 0 بازیابی خواهیم کرد. بنابراین جفت اختلاف را محاسبه می کنیم و (1,1،0) را بدست می آوریم. همچنین ، این بدان دلیل است که تعداد صفرها را افزایش داده ایم. بنابراین ما اختلاف را محاسبه می کنیم و نتیجه را می گیریم. پس از دریافت مقدار مقدار فعلی نقشه و افزودن 0 به خروجی ، زیرا این جفت جدید است. ما فقط جفت را وارد نقشه می کنیم. خروجی فعلی XNUMX است.

ما به سراغ کاراکتر بعدی می رویم که 1 است. اکنون تعداد افراد را افزایش می دهیم. سپس اختلافات را به صورت 0,1/XNUMX بدست خواهیم آورد. از آنجا که این جفت نیز جدید است ، بنابراین ما آن را به نقشه اضافه خواهیم کرد و بازده همچنان ثابت است.

سپس 2 به عنوان ورودی بدست می آوریم و جفت را 0 ، 0 می گیریم زیرا تمام شمارش رقم اکنون 1 است. بنابراین خروجی اکنون 0,0 است.

بعد ، ما مانند 0 می شویم ، اکنون صفر عدد دو است. ما 1,1،2 را دریافت می کنیم زیرا این از قبل در نقشه است. سپس خروجی را به روز کرده و با مقدار XNUMX در نقشه وارد می کنیم.

در این مرحله همه زیر رشته های ممکن خود را پیدا کرده ایم ، این روشی است که از 0 ، 1 و 2 برابر برابر می شویم.

رمز

کد C ++ برای شمارش زیر رشته ها با تعداد برابر 0 ، 1 و 2

#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)  جایی که "n" تعداد عناصر آرایه است. از آنجایی که ما از HashMap استفاده کرده ایم ، تمام درج ، حذف و جستجو برای هر عملیات فقط به O (1) زمان نیاز دارد.

پیچیدگی فضا

O (N)  جایی که "n" تعداد عناصر آرایه است.