Ən Uzun Ortaq Nəticə

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon eBay Facebook Morgan Stanley
Dinamik proqramlaşdırma SimBaxılıb 107

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

LinkedInBuferRedditTumblr

Sizə str1 və str2 iki simli verilir, ən uzun ümumi altlığın uzunluğunu öyrənin.

Nəticə: a sonradan qalan elementlərin sırasını dəyişdirmədən bəzi və ya heç bir elementi silməklə başqa bir ardıcıllıqdan əldə edilə bilən bir ardıcıllıqdır. Keçmiş üçüntticp'nin ardıcıllığıdır'tutorialcup".

misal

input : str1 = "AGCA", str2 = "GAC"
sol   : longest common subsequence (LCA) = "GA"
        length of LCA = 2  
output: 2
   
input : str1 = "ABC", str2 = "XYZ"
sol   : No common character found
        length of LCA = 0
output: 0
    
input : str1 = "MZJAWXU", str2 = "XMJYAUZ"
sol   : longest common subsequence (LCA) = "MJAU"
        length of LCA = 4
output: 4

Həll növləri

  1. Sadəlövh
  2. Rekursiv
  3. istifadə Dinamik proqramlaşdırma
    • Yaddaş həll.
    • Cədvəlli həll.
    • Space Optimize cədvəlli həll

aşağıda göstərilən həllərin hər birini müzakirə edəcəyik.

Sadəlövh

m və n uzunluğunda iki simli olduğumuzu düşünək.

Sadəlövh həllin ideyası həm str1, həm də str2-nin bütün alt ardıcıllığını yaratmaq, altlıqların hər birini bir-bir müqayisə etməkdir. Ən böyük uyğunluq sonrası tələb olunan cavabımız olacaqdır.

Cəmi 2 varm-1 və 2n-1 ardıcıllığı strings str1 (uzunluq = m) və str1 (uzunluq = n). Buna görə, bütün alt ardıcıllıqları yaratmaq üçün Zaman mürəkkəbliyi O (2)n+2m) ~ O (2n). Əlavə olaraq, hər bir alt ardıcıllığı müqayisə etmək və ümumi və ən uzununu çıxarmaq üçün O (mn) vaxt lazımdır. Buna görə ümumi zaman mürəkkəbliyi O (mn * 2) olurn). Bu zaman mürəkkəbliyi hesablama baxımından olduqca intensivdir və daha da yaxşılaşdırıla bilər.

Ən uzun ümumi nəticələr üçün rekursiv həll

Alqoritm

uzunluqlar n və m olan str1 və str2 iki sətiri nəzərdən keçirin. LCS (m, n), str1 və str2-nin ən uzun yayılmış ardıcıllığının uzunluğudur.

  1. ipləri sağ ucundan müqayisə etməyə başlayın.
  2. m və ya n 0 olarsa, 0-a qayıdın.
  3. str1 [m-1] == str2 [n-1] (son simvollar uyğun gəlsə), 1 + LCS (m-1, n-1) qaytarın. Rekursiv LCS-yə zəng edin (m-1, n-1) və 1 əlavə edin ona.
  4. əks halda str1 [m-1]! = str2 [n-1] (son simvollar uyğun gəlmirsə), max (LCS (m-1, n), LCS (m, n-1)) qaytarın. yəni LCS (m-1, n) və LCS (m, n-1) rekursiv olaraq zəng edin və maksimumunu qaytarın.

C ++ Proqramı

#include <iostream>
using namespace std;

int LCS(string str1,string str2,int m,int n)
{
    // if length of any string is 0, return 0
    if(n == 0 || m == 0)
    return 0;
    
    // if last characters match, remove them
    // then find LCS of remaining strings
    if(str1[m-1] == str2[n-1])
    return 1+LCS(str1,str2,m-1,n-1);
    
    // if last characters dont match
    // alternately remove last character of each string
    // to find LCS
    return max(LCS(str1,str2,m,n-1),LCS(str1,str2,m-1,n));
}

int main() 
{
  string str1 = "AGCA";
  string str2 = "GAC";
  
  int m = str1.length();
  int n = str2.length();
  
  cout<<"length of LCS : "<<LCS(str1,str2,m,n)<<endl;
  
  return 0;
}
Length of LCS : 2

Java Proqramı

class tutorialcup
{
    static int LCS(String str1,String str2,int m,int n)
    {
        // if length of any string is 0, return 0
        if(n == 0 || m == 0)
        return 0;
        
        // if last characters match, remove them
        // then find LCS of remaining strings
        if(str1.charAt(m-1) == str2.charAt(n-1))
        return 1+LCS(str1,str2,m-1,n-1);
        
        // if last characters dont match
        // alternately remove last character of each string
        // to find LCS
        return Math.max(LCS(str1,str2,m-1,n),LCS(str1,str2,m,n-1));
    }
    
    public static void main(String args[])
    {
        String str1 = "AGCA";
        String str2 = "GAC";
        
        int m = str1.length();
        int n = str2.length();
        
        System.out.print("Length of LCS : "+LCS(str1,str2,m,n));
    }
}
Length of LCS : 2

Mürəkkəblik təhlili

  1. Zamanın mürəkkəbliyi: T (n) = O (2)n), eksponent zamanın mürəkkəbliyi.
  2. Kosmik Mürəkkəblik: A (n) = O (1)

n = daha böyük sətrin uzunluğu.

Dinamik proqramlaşdırma

Fikri dinamik proqramlaşdırma sadəcə saxla / saxla təkrarlanan rekursiv zənglər zamanı hesablanan müxtəlif alt problemlərin nəticələri, daha sonra lazım olduqda onları yenidən hesablamamalıyıq. Bu sadə optimallaşdırma zaman mürəkkəbliklərini eksponentdən polinomlara endirir. Aşağıdakıları nəzərdən keçirək rekursiya ağacının diaqramı LCS (“AGCA”, “GAC”):

Ən Uzun Ortaq NəticəPin

Alt problemlər üçün bu həlləri müşahidə edirik LCS (“AG”, “G”) və LCS (“A”, ”“) dəfələrlə qiymətləndirilir (sırasıyla 1 & 0 olaraq). eyni alt problemlərin həllinin bu təkrar hesablanması daha böyük simlər halında daha tez-tez baş verir. Eyni alt problemi hesablamaq üçün əlavə səylər dəfələrlə xərc çəkir və alqoritmin mürəkkəbliyini artırır.

Məqsəd Dinamik proqramlaşdırma Çözüm, alt problemlərin həllini saxlamaq / saxlamaq və alqoritm bu həlli tələb etdikdə (yenidən hesablamaq əvəzinə) istehsal etməkdir. Bu metod zamanın mürəkkəbliyini çox azaldır.

Zaman mürəkkəbliyinin eksponensial sıra ilə müqayisədə daha az intensiv olan polinomal sıraya düşdüyü müşahidə olunur.

Ən uzun ümumi nəticələr üçün yadda saxlanan həll

Hər alt problemin həllini saxlayırıq / saxlayırıq. Bu, alt problemin açar və ədədi həllinin dəyər olduğu bir xəritə məlumatı strukturundan istifadə edilir. Daha sadə sözlə, alt problemi (açar) həll yolu (dəyər) ilə uyğunlaşdırırıq. Alt problem bir simli çevrilir və ədədi bir həll ilə eşlenir. bir xəritə 'memo' yaradırıq, bu memo alt problemlərə (string data type) açar, həll olaraq (integer data type) dəyərdir.

Bir alt problem üçün LCS-yə müraciət etdikdə, bu alt problemin həllinin Xəritədə saxlanılıb-saxlanılmadığını yoxlayırıq, əvvəlcədən saxlanılırsa, birbaşa həmin dəyəri istifadə edirik və ya başqa bir şəkildə dəyəri hesablayırıq.

Aşağıdakı cədvəldə alt problemlər, uyğun düymələr və dəyərlər göstərilir:

Ən Uzun Ortaq NəticəPin

C ++ Proqramı

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int LCS(string str1,string str2,int m,int n,unordered_map<string,int>& memo)
{
    // return if we have reached the end of either string
  if (n == 0 || m == 0)
    return 0;

  // construct an unique map key from dynamic elements of the input
  string key = to_string(m) + "|" + to_string(n);

  // if sub-problem is seen for the first time, solve it and
  // store its result in a map
  if (memo.find(key) == memo.end())
  {
    // if last character of str1 and str2 matches
    if (str1[m - 1] == str2[n - 1])
      memo[key] = 1 + LCS(str1, str2, m - 1, n - 1, memo);

    else
    // else if last character of str1 and str2 don't match
    memo[key] = max(LCS(str1, str2, m, n - 1, memo),
            LCS(str1, str2, m - 1, n, memo));
  }

  // return the subproblem solution from the map
  return memo[key];
}

int main() 
{
  string str1 = "AGCA";
  string str2 = "GAC";
  
  // we use map to store memoized values
  unordered_map <string,int> memo;
  
  int m = str1.length();
  int n = str2.length();
  
  cout<<"length of LCS : "<<LCS(str1,str2,m,n,memo)<<endl;
  
  return 0;
}
Length of LCS : 2

Java Proqramı

import java.util.HashMap;
class tutorialcup
{
    static int LCS(String str1,String str2,int m,int n,HashMap <String,Integer> memo)
    {
        // return if we have reached the end of either string
    	if (n == 0 || m == 0)
    		return 0;
    
    	// construct an unique map key from dynamic elements of the input
    	String key = m + "|" + n;
    
    	// if sub-problem is seen for the first time, solve it and
    	// store its result in a map
    	if (!memo.containsKey(key))
    	{
    		// if last character of str1 and str2 matches
    		if (str1.charAt(m-1) == str2.charAt(n-1))
    			memo.put(key,1 + LCS(str1, str2, m - 1, n - 1, memo));
    
    		else
    		// else if last character of str1 and str2 don't match
    		memo.put(key,Math.max(LCS(str1, str2, m, n - 1, memo),
    						LCS(str1, str2, m - 1, n, memo)));
    	}
    
    	// return the subproblem solution from the map
    	return memo.get(key);
    }

    
    public static void main(String args[])
    {
        String str1 = "AGCA";
        String str2 = "GAC";
        // we use map to store memoized values
        HashMap <String,Integer> memo = new HashMap <String,Integer>();
        
        int m = str1.length();
        int n = str2.length();
        
        System.out.print("Length of LCS : "+LCS(str1,str2,m,n,memo));
    }
}
Length of LCS : 2

Mürəkkəblik təhlili

  1. Zamanın mürəkkəbliyi: T (n) = O (mn), polinom zaman mürəkkəbliyi.
  2. Kosmik Mürəkkəblik: A (n) = O (mn), polinom boşluq mürəkkəbliyi.

m = str1 uzunluğu, n = str2 uzunluğu

Ən uzun yayılmış nəticələr üçün cədvəlli həll

Bu həllin məqsədi yenə də alt problemlərin hər birinin ədədi həllini başqa bir məlumat quruluşundan istifadə etməklə saxlamaqdır. Bu vəziyyətdə, alt problemlərə həllər saxlamaq üçün bir cədvəldən (2B sıra və ya matris) istifadə edirik. Cədvəlin indeksləri alt problemlərdir və bu indekslərin dəyəri həmin alt problemin ədədi həllidir.

LCS (“AGCA”, “GAC”) üçün alınan cədvəl

Ən Uzun Ortaq NəticəPin

C ++ Proqramı

#include<bits/stdc++.h> 
using namespace std; 

/* Returns length of LCS for str1 and str2 */
int LCS(string str1, string str2) 
{ 
    int m = str1.length();
    int n = str2.length();
    
    // matrix to store value of each subproblem
    int table[m+1][n+1]; 
    int i, j; 
  
  // Following steps build table[m+1][n+1] in bottom up fashion. 
  // value at table[i][j] contains length of LCS of str1[0,i-1] and str2[0,j-1]
  for (i = 0; i <= m; i++) 
  { 
    for (j = 0; j <= n; j++) 
    { 
    		if (i == 0 || j == 0) 
    		    table[i][j] = 0;
    	
    		else if (str1[i-1] == str2[j-1]) 
    			table[i][j] = 1 + table[i-1][j-1]; 
    	
    		else
    			table[i][j] = max(table[i-1][j], table[i][j-1]); 
    } 
  } 
    
  // table[m][n] contains length of LCS for str1[0,n-1] and str2[0,m-1] 
  return table[m][n]; 
} 

// main function to implement above functions
int main() 
{ 
  string str1 = "AGCA"; 
  string str2 = "GAC"; 
  
  cout << "Length of LCS : "<< LCS(str1,str2); 
  
  return 0; 
} 



Length of LCS : 2

Java Proqramı

class tutorialcup
{
    static int LCS(String str1, String str2)
    {
        int m = str1.length();
        int n = str2.length();
        
        // matrix to store value of each subproblem
        int[][] table = new int[m+1][n+1]; 
    	int i, j; 
    	
    	// Following steps build table[m+1][n+1] in bottom up fashion. 
    	// value at table[i][j] contains length of LCS of str1[0,i-1] and str2[0,j-1]
    	for (i = 0; i <= m; i++) 
    	{ 
    		for (j = 0; j <= n; j++) 
    		{ 
        		if (i == 0 || j == 0) 
        		    table[i][j] = 0;
        	
        		else if (str1.charAt(i-1) == str2.charAt(j-1)) 
        			table[i][j] = 1 + table[i-1][j-1]; 
        	
        		else
        			table[i][j] = Math.max(table[i-1][j], table[i][j-1]); 
    		} 
    	} 
    	
    	for(i=0;i<=m;i++)
    	{
    	    for(j=0;j<=n;j++)
    	    System.out.print(table[i][j]+" ");
    	    
    	    System.out.println();
    	}
    		
    	// table[m][n] contains length of LCS for str1[0,n-1] and str2[0,m-1] 
    	return table[m][n]; 
    }
    
    // main function to implement above functions
    public static void main(String args[])
    {
        String str1 = "AGCA";
        String str2 = "GAC";
        
        System.out.println("Length of LCS : "+LCS(str1,str2));
        
        
    }
}
Length of LCS : 2

Mürəkkəblik təhlili

  1. Zamanın mürəkkəbliyi: T (n) = O (mn), polinom zaman mürəkkəbliyi.
  2. Kosmik Mürəkkəblik: DP cədvəli üçün A (n) = O (mn)

m = str1 uzunluğu, n = str2 uzunluğu

Ən uzun ümumi nəticələr üçün kosmik optimallaşdırılmış cədvəlli həll

yuxarıdakı cədvəl həllində xarici döngənin hər təkrarlanmasında yalnız bizə lazım olduğunu müşahidə edirik dərhal əvvəlki sətirlərdən alınan dəyərlər. Beləliklə, bütün cədvəlləri 'cədvəl' matrisimizdə saxlamağımıza ehtiyac yoxdur, yalnız bir anda iki sətir saxlaya və istifadə edə bilərik, beləliklə istifadə edilmiş məkan cədvəldən azalacaq [m + 1] [n + 1] cədvələ [2] [n + 1].

Aşağıda alqoritmi tətbiq edirik.

C ++ Proqramı

#include<bits/stdc++.h> 
using namespace std; 

/* Returns length of LCS for str1 and str2 */
int LCS(string str1, string str2) 
{ 
    int m = str1.length();
    int n = str2.length();
    
    // matrix to store value of each subproblem
    int table[2][n+1]; 
    int i, j; 
    
    // binary index used to access current and previous rows
    bool index;
  
  // Following steps build table[m+1][n+1] in bottom up fashion. 
  // value at table[i][j] contains length of LCS of str1[0,i-1] and str2[0,j-1]
  for (i = 0; i <= m; i++) 
  { 
      // calculate the current binary index
      index = i & 1;
      
    for (j = 0; j <= n; j++) 
    { 
    		if (i == 0 || j == 0) 
    		    table[index][j] = 0;
    	
    		else if (str1[i-1] == str2[j-1]) 
    			table[index][j] = 1 + table[1-index][j-1]; 
    	
    		else
    			table[index][j] = max(table[1-index][j], table[index][j-1]); 
    } 
  } 
    
  // Last filled entry contains 
    // length of LCS for str1[0,n-1] and str2[0,m-1]  
  return table[index][n]; 
} 

// main function to implement above functions
int main() 
{ 
  string str1 = "AGCA"; 
  string str2 = "GAC"; 
  
  cout << "Length of LCS : "<< LCS(str1,str2); 
  
  return 0; 
} 

Length of LCS : 2

Java Proqramı

class tutorialcup
{
    static int LCS(String str1, String str2)
    {
        int m = str1.length();
        int n = str2.length();
        
        // matrix to store value of each subproblem
        int[][] table = new int[2][n+1]; 
        int i, j; 
        
        // binary index used to access current and previous rows
        int index = 1;
    	
    	// Following steps build table[m+1][n+1] in bottom up fashion. 
    	// value at table[i][j] contains length of LCS of str1[0,i-1] and str2[0,j-1]
    	for (i = 0; i <= m; i++) 
    	{ 
    	    // calculate the current binary index
    	    index = i & 1;
    	    
    		for (j = 0; j <= n; j++) 
    		{ 
        		if (i == 0 || j == 0) 
        		    table[index][j] = 0;
        	
        		else if (str1.charAt(i-1) == str2.charAt(j-1)) 
        			table[index][j] = 1 + table[1-index][j-1]; 
        	
        		else
        			table[index][j] = Math.max(table[1-index][j], table[index][j-1]); 
    		} 
    	} 
    		
    	// Last filled entry contains 
        // length of LCS for str1[0,n-1] and str2[0,m-1]  
    	return table[index][n]; 
    }
    
    // main function to implement above functions
    public static void main(String args[])
    {
        String str1 = "AGCA";
        String str2 = "GAC";
        
        System.out.println("Length of LCS : "+LCS(str1,str2));
        
    }
}
Length of LCS : 2

Mürəkkəblik təhlili

  1. Zamanın mürəkkəbliyi: T (n) = O (mn), polinom zaman mürəkkəbliyi.
  2. Kosmik Mürəkkəblik: A (n) = O (n), Xətti məkan mürəkkəbliyi

m = str1 uzunluğu, n = str2 uzunluğu

Ən uzun yayılmış ardıcıllığın çapı

Alqoritm

  1. cədvəldə göstərilən həlldəki kimi bir DP cədvəli qurun.
  2. boş bir sətir, 'lcs' yaradın.
  3. Cədvəli ən sağdakı hücrədən keçin, cədvəl [m] [n].
  4. Keçərkən hər bir hücrə masası üçün [i] [j] aşağıdakıları et:
    • [İ] [j] cədvəlinə uyğun simvollar (str1 və str2-də) eynidirsə (yəni str1 [i-1] == str2 [j-1]), onda bu işarəni lcs-ə əlavə edin.
    • Başqa cədvəl [i-1] [j] və cədvəl [i] [j-1] dəyərlərini müqayisə edin və daha böyük dəyərə malik olan istiqamətə (xana) keçin.
  5. Simvollar sağ ucdan əlavə olunduğundan, str1 və str2 tələb olunan ən uzun ortaq ardıcıllığı əldə etmək üçün 'lcs' sətrini tərs çevirin.

Pin

C ++ Proqramı

#include <iostream>
#include <bits/stdc++.h> 
using namespace std; 

/* Returns length of LCS for str1 and str2 */
string LCS(string str1, string str2) 
{ 
    int m = str1.length();
    int n = str2.length();
    string lcs = "";
    
    // matrix to store value of each subproblem
    int table[m+1][n+1]; 
    int i, j; 
    
    
  // Following steps build table[m+1][n+1] in bottom up fashion. 
  // value at table[i][j] contains length of LCS of str1[0,i-1] and str2[0,j-1]
  for (i = 0; i <= m; i++) 
  { 
    for (j = 0; j <= n; j++) 
    { 
    		if (i == 0 || j == 0) 
    		    table[i][j] = 0;
    	
    		else if (str1[i-1] == str2[j-1]) 
    			table[i][j] = 1 + table[i-1][j-1]; 
    	
    		else
    			table[i][j] = max(table[i-1][j], table[i][j-1]); 
    } 
  } 
    
  // Start from the right-most,bottom-most corner and one by one store characters in lcs 
  i = m,j = n;
  while(i > 0 && j > 0)
  {
      // if current characters match, then are part of LCS
      if(str1[i-1] == str2[j-1])
      {
          lcs.push_back(str1[i-1]);
          i--;
          j--;
      }
      
      // if current characters are not same 
      // then find larger of two cells(above and left)
      // and move in the direction of larger cell
      else if(table[i-1][j] > table[i][j-1])
      i--;
      else
      j--;
  }
  
  // since characters from string are appended from right end
  // we need to reverse the lcs string to obtain the actual string
  reverse(lcs.begin(),lcs.end());
  return lcs;
} 

// main function to implement above functions
int main() 
{ 
  string str1 = "AGCA"; 
  string str2 = "GAC"; 
  
  cout << "LCS of str1 and str2 : "<< LCS(str1,str2); 
  
  return 0; 
} 

LCS of str1 and str2 : GA

Java Proqramı

class tutorialcup
{
    static StringBuilder LCS(String str1, String str2)
    {
        int m = str1.length();
        int n = str2.length();
        // use mutable string to store lcs
        StringBuilder lcs = new StringBuilder();
        
        // matrix to store value of each subproblem
        int[][] table = new int[m+1][n+1]; 
        int i, j; 
    
    	
    	// Following steps build table[m+1][n+1] in bottom up fashion. 
    	// value at table[i][j] contains length of LCS of str1[0,i-1] and str2[0,j-1]
    	for (i = 0; i <= m; i++) 
    	{ 
    		for (j = 0; j <= n; j++) 
    		{ 
        		if (i == 0 || j == 0) 
        		    table[i][j] = 0;
        	
        		else if (str1.charAt(i-1) == str2.charAt(j-1)) 
        			table[i][j] = 1 + table[i-1][j-1]; 
        	
        		else
        			table[i][j] = Math.max(table[i-1][j], table[i][j-1]); 
    		} 
    	} 
    	
    	// Start from the right-most,bottom-most corner and one by one store characters in lcs 
    	i = m;
    	j = n;
    	while(i > 0 && j > 0)
    	{
    	    // if current characters match, then are part of LCS
    	    if(str1.charAt(i-1) == str2.charAt(j-1))
    	    {
    	        lcs.append(str1.charAt(i-1));
    	        i--;
    	        j--;
    	    }
    	    
    	    // if current characters are not same 
    	    // then find larger of two cells(above and left)
    	    // and move in the direction of larger cell
    	    else if(table[i-1][j] > table[i][j-1])
    	    i--;
    	    else
    	    j--;
    	}
    	
    	// since characters from string are appended from right end
    	// we need to reverse the lcs string to obtain the actual string
    	lcs.reverse();
    	return lcs;
    	
    }
    
    // main function to implement above functions
    public static void main(String args[])
    {
        String str1 = "AGCA";
        String str2 = "GAC";
        
        System.out.println("LCS of str1 and str2 : "+LCS(str1,str2));
        
    }
}
LCS of str1 and str2 : GA

LCS tətbiqi

  1. Ən uzun yayılmış ardıcıllıq problemi klassik bir kompüter elmi problemidir, diff proqramı kimi məlumatların müqayisəli proqramlarının əsasını təşkil edir.
  2. Hesablama dilçiliyi və bioinformatikada tətbiqləri var.
  3. Bundan əlavə, Git kimi revizyon nəzarət sistemləri tərəfindən, bir revizyonla idarə olunan sənədlər kolleksiyasında edilən çoxsaylı dəyişiklikləri uzlaşdırmaq üçün geniş istifadə olunur.

References

LinkedInBuferRedditTumblr
Crack Sistemi Dizayn Müsahibələri
Translate »