Μετρήστε υποστρώματα με ίσο αριθμό 0s, 1s και 2s


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις Citrix Χωρίς χρέωση Goldman Sachs Δωμάτια OYO Times Internet Twilio
Χασίσι κορδόνι

Το πρόβλημα "Count Substrings με ίσο αριθμό 0s, 1s και 2s" δηλώνει ότι σας δίνεται ένα κορδόνι που έχει μόνο 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. σετ μηδενικός αριθμός, εκτίμηση, διπλό ποσό, παραγωγή να 0.
  4. Βρόχος από i = 0 έως i
    1. Ελέγξτε για κάθε χαρακτήρα του τρέχοντος υποστρώματος εάν είναι 0, 1 και 2. Στη συνέχεια, ενημερώστε ανάλογα τον αριθμό.
    2. Υπολογίστε τις διαφορές του ζεύγους.
    3. Ελέγξτε εάν η διαφορά δεν υπάρχει στο χάρτη και, στη συνέχεια, προσθέστε 0 στην έξοδο.
    4. Διαφορετικά, προσθέστε την τιμή του χάρτη του temp στην έξοδο.
    5. Προσθέστε temp στον χάρτη.
  5. Επιστροφή εξόδου.

εξήγηση

Μας δίνεται μια συμβολοσειρά που έχει μόνο 0, 1 και 2. Το καθήκον μας είναι να ανακαλύψουμε τον συνολικό αριθμό των υποστρωμάτων που δεν είναι ίσο με 0, 1 και 2. Για αυτό, θα χρησιμοποιήσουμε Hashing. Αρχικοποιήστε ένα ζεύγος με (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.

Κώδικας

Κωδικός 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

O (n)  όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Δεδομένου ότι χρησιμοποιήσαμε το HashMap, όλη η εισαγωγή, η διαγραφή και η αναζήτηση απαιτούν μόνο O (1) χρόνο ανά λειτουργία.

Διαστημική πολυπλοκότητα

O (n)  όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.