0s, 1s and 2s በእኩል ቁጥር ያላቸው ንዑስ ሐረጎችን ይቁጠሩ


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ Citrix ፍሪጅ ቻርጅ ጎልድማን ሳክስ ኦዮ ክፍሎች ታይምስ በይነመረብ ቴሊዮ
ሃሽ ሕብረቁምፊ

ችግሩ “የ 0 ፣ 1 እና 2 እኩል ቁጥር ያላቸው ንዑስ ሕብረቁምፊዎችን ይቆጥሩ” የሚለው ሀ ክር ያለው 0 ፣ 1 እና 2 ብቻ ነው ፡፡ የችግር መግለጫው የ 0 ፣ 1 እና 2 ብቻ ቁጥር እኩል የያዙ የስፕሪተሮችን ቁጥር ለማወቅ ይጠይቃል ፡፡

ለምሳሌ

0s, 1s and 2s በእኩል ቁጥር ያላቸው ንዑስ ሐረጎችን ይቁጠሩ

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. ሌላ ፣ የቴምፕ የካርታውን እሴት በውጤቱ ውስጥ ያክሉ።
    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 ዎቹ እኩል የምንሆንበት መንገድ ነው ፡፡

ኮድ

እኩል ቁጥር ያላቸው 0s ፣ 1s እና 2s ያላቸውን ቁጥሮችን ለመቁጠር 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 እኩል ቁጥር ያላቸውን ንዑስ ቁጥሮች ለመቁጠር የጃቫ ኮድ

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ሆይ (n)  የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። እኛ ሃሽማፕን ስለተጠቀምን ሁሉም ማስገባት ፣ መሰረዝ እና ፍለጋ በአንድ ኦፕሬሽን ኦ (1) ጊዜ ብቻ ይፈልጋል ፡፡

የቦታ ውስብስብነት

ሆይ (n)  የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።