Wyraźne następstwa

Poziom trudności Ciężko
Często zadawane pytania Amazonka Bloomberg MATHWORKS
Programowanie dynamiczne sznurodwiedzajacy 64

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Biorąc pod uwagę dwa smyczki S i P1, musimy policzyć całą liczbę różnych podciągów S, które są równe P1.

Uwaga: Podciąg danego ciągu to ciąg, który archiwizujemy, usuwając niektóre znaki lub możliwe znaki zerowe również z oryginalnego ciągu. Nie możemy zmienić kolejności elementów obecnych w oryginalnym ciągu.

Na przykład:

„EGY” jest podciągiem „AEDGYS”, podczas gdy „DAY” nie.

Uwaga: każdy podciąg jest podciągiem, ale każdy podciąg nie jest podciągiem.

Podejście siłowe

Sprawdzimy wszystkie podciągi struny S o długości takiej samej jak struna P1.

Algorytm:

  1. Weź pusty ciąg „ans”, który zapisze twój ciąg dla bieżącego stanu.
  2. Uruchom rekurencję, w której argumenty wskazują indeks łańcucha S i łańcucha P, na którym będziemy operować.
  3. Umieść skrzynki bazowe.
    • Jeśli wskaźnik łańcucha T stanie się równy długości łańcucha P1, zwróć 1.
    • Jeśli wskaźnik łańcucha S stanie się równy długości łańcucha S, zwróć 0.

Optimal Podbudowa:

Aby wziąć pod uwagę cały podciąg łańcucha S, dla każdego indeksu mogą być dwa przypadki.

  • Sprawa 1: Pozycja jest zawarta w optymalnym podzbiorze.
  • Sprawa 2: Element nie znajduje się w optymalnym zestawie.

Jeśli wartości wskaźników obu łańcuchów nie są równe, to rozważany jest tylko przypadek 2.

Realizacja

Program w C ++ dla wyraźnych następstw

#include <bits/stdc++.h>
using namespace std;
int ds(string &s, string &t, string &ans, int pointer_S, int pointer_T)
{
    if (pointer_T == t.length())
    {
        return 1;
    }
    if (pointer_S >= s.length())
    {
        return 0;
    }
    int count = 0;
    count += ds(s, t, ans, pointer_S + 1, pointer_T);
    if (s[pointer_S] == t[pointer_T])
    {
        ans += s[pointer_S];
        count += ds(s, t, ans, pointer_S + 1, pointer_T + 1);
        ans.pop_back();
    }
    return count;
}
int main()
{
    string S, P;
    cin >> S >> P;
    string ans;
    cout << ds(S, P, ans, 0, 0) << endl;
    return 0;
}

 

Jeśli uważnie przyjrzymy się powyższej funkcji, zobaczymy, że oblicza ona wielokrotnie te same podproblemy. Zobacz następujące drzewo rekurencji. Złożoność czasowa tego naiwnego rozwiązania rekurencyjnego jest wykładnicza.

Wyraźne następstwaszpilka

 

Ponieważ problemy podrzędne są ponownie oceniane, ten problem ma właściwość Nakładające się problemy podrzędne.

Więc ten problem ma obie właściwości pliku Programowanie dynamiczne problem:

  1. Pokrywające się problemy podrzędne
  2. Optymalna podkonstrukcja

Jak w innych Programowanie dynamiczne problemy, w tym również będziemy przechowywać odpowiedzi każdego stanu, abyśmy nie obliczali raz po raz tego samego problemu podrzędnego.

Dynamiczne podejście do programowania

Algorytm

  1. Zainicjuj tablicę dp [] [] o rozmiarze (długość łańcucha S + 1) * (długość łańcucha P1 + 1) zerami, gdzie dp [i] [j] reprezentuje liczbę odrębnych podciągów łańcucha S [0… .i-1], które są równe P1 [0… .j-1].
  2. Przypadek podstawowy:

dla I w zakresie od 0 do n

dp [i] [0] = 1, ponieważ do 1 podciągu (pustego podciągu), który jest równy pustemu łańcuchowi.

  1. Teraz mamy dwa przypadki

CASE 1: jeśli S [i-1] == P1 [j-1]

W tym przypadku możemy wybrać ith element lub i-1th element dla j-tego elementu, a więc

dp [i] [j] = dp [i-1] [j-1] + dp [i-1] [j].

PRZYPADEK 2: jeśli S [i-1]! = P1 [j-1]

W tym przypadku możemy wybrać tylko i-1th element dla j-tego elementu, a więc

dp [i] [j] = dp [i-1] [j].

  1. Zwróć dp [n] [m].

Realizacja

Program w C ++ dla wyraźnych następstw

#include <bits/stdc++.h>
using namespace std;
int distinctSubsequence(string s, string t)
{
    long long n, m;
    n = s.length();
    m = t.length();
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
    for (long long i = 0; i <= n; i++)
    {
        dp[i][0] = 1;
    }
    for (long long i = 1; i <= n; i++)
    {
        for (long long j = 1; j <= m; j++)
        {
            if (s[i - 1] == t[j - 1])
            {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][m];
}
int main()
{
    string s="abbbcdd", p="abc";
    cout << distinctSubsequence(s, p) << endl;
    return 0;
}

Wydajność

3

Program JAVA dla wyraźnych następstw

public class Main
{
    public static int distinctSubsequence(String s, String t)
    {
        int n = s.length(), m = t.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s.charAt(i) == t.charAt(j)) dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
                else dp[i + 1][j + 1] = dp[i][j + 1];
            }
        }
        return dp[n][m];
    }
  public static void main(String[] args) {
    String s="abccccdee", p ="abe";
    System.out.println(distinctSubsequence(s,p));
  }
}

Wydajność

2

Złożoność czasowa

T (n) = O (n * m) ponieważ wypełniamy macierz 2D (dp) o rozmiarze n * m za pomocą dwóch zagnieżdżonych pętli, stąd złożoność czasowa będzie wynosić O (n * m)

gdzie n jest długością pierwszej struny, a m jest długością drugiej struny.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »