0, 1 ба 2 секундын тэнцүү тооны дэд мөрүүдийг тоол


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Citrix FreeCharge Goldman Sachs OYO өрөөнүүд Times Интернет Twilio
Хаш String

“Тоо тэнцүү тооны 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. Мэдүүлэх a газрын зураг.
  2. Хосыг 0 болгож эхлүүлээд 1-тэй хамт газрын зурагт оруулна уу.
  3. нь чансаанд тэг тоо, данс, хоёр удаа тоолох, болон Гаралт 0 рүү.
  4. I = 0-ээс i хүртэлх гогцоо
    1. Одоогийн дэд мөрийн тэмдэгт бүрийг 0, 1, 2 байгаа эсэхийг шалгаад дараа нь тооллогын дагуу шинэчилнэ.
    2. Хосуудын ялгааг тооцоол.
    3. Газрын зураг дээр ялгаа байхгүй байгаа эсэхийг шалгаад гаралт дээр 0 нэмнэ үү.
    4. Бусад тохиолдолд гаралтын температурын утгыг нэмнэ үү.
    5. Газрын зураг дээр түр зуур нэмэх.
  5. Гаралтыг буцаах.

Тайлбар

Бидэнд зөвхөн 0, 1, 2 гэсэн мөрийг өгдөг. Бидний даалгавар бол 0, 1, 2-той тэнцэхгүй нийт мөрийн тоог олох явдал юм. Үүний тулд бид ашиглах гэж байна. Хаширч байна. Анхдагч байдлаар (0, 0) хосыг түлхүүр болгон, түүний утгыг 1 болгон газрын зураг дээр эхлүүлнэ. Хоорондын ялгааг тооцоол тэг тоо болон дансБолон тэг тоо болон хоёр удаа тоолох. Бид үнэ цэнэ, хосыг газрын зураг дээр хадгалах болно. Хэрэв хосын ялгаа газрын зураг дээр аль хэдийн байгаа бол одоогийн хосын утгыг газрын зургаас авах / авах хэрэгтэй. Дараа нь үүнийг гаралтад нэмнэ үү. Хэрэв ялгаа нь газрын зураг дээр байхгүй бол. Дараа нь гаралт дээр 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-ын аль ч тоогоор тэнцэхгүй болно.

код

0, 1 ба 2 секундын тэнцүү тооны дэд мөрүүдийг тоолох C ++ код

#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

0s, 1s ба 2s-ийн тэнцүү тооны дэд мөрүүдийг тоолох Java код

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" массив дахь элементүүдийн тоо юм.