Növbəti Permutasiya

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Facebook Məlumat dəsti Flipkart google microsoft Morgan Stanley Salesforce Über
SimBaxılıb 111

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.

Növbəti yer dəyişdirmə problemində bir söz verdik, leksikoqrafik cəhətdən daha böyük_ötürmə tapın.

misal

input : str = "tutorialcup"
output : tutorialpcu

input : str = "nmhdgfecba"
output : nmheabcdfg

input : str = "algorithms"
output : algorithsm

input : str = "spoonfeed"
output : Next Permutation Doesnt exist

Lüğət lüğəti

Bir lüğətdə düzəldildikdə bir sözün bütün permutasiyaları, belə əldə edilən sözlərin sırasına leksikoqrafiya qaydası deyilir.

Məsələn:

word = 'cat'
lexicographical order of permutations of 'cat' : 

act
atc
cat
cta
tac
tca

'pişik' leksikoqrafik cəhətdən 'hərəkət' dən daha böyük olduğunu görə bilərik.

Növbəti Permutasiya üçün Alqoritm

Tamamilə azalan qaydada sıralanan bir söz üçün, məsələn: “nmhgfedcba” -da növbəti permutasiya yoxdur. Tamamilə azalan qaydada sıralanmamış bir söz üçün növbəti permutasiyanı tapa bilərik. ex: “nmhdgfecba” .Aşağıda alqoritm:
Verilmişdir: str = “nmhdgfecba”

  1. Sətrin sağından keçin və azalan sıraya əməl etməyən ilk simvol axtarın. 'd' in str azalan əmri izləmir. 'd' = 3 indeksi.
  2. 'D' -in sağında, ASCII dəyərində 'd' -dən çox (və ya ən yaxın) xarakteri axtarın. [nmhd] gfecba içindəki 'e' 'd'dən çoxdur. Bu, binarySearch () funksiyasından istifadə edilir.
  3. 'e' və 'd' dəyişdirin. Nəticə sətri "nmhegfdcba" dır.
  4. İndi tərs (tərs () funksiyasından istifadə edilərək) addım 1-də tapılan indeksdən sonra meydana gələn sətrin bir hissəsini tərs edin (gfdcba) tərsinə çevirin və yenidən əsas sətrə əlavə edin.
  5. output = “nmheabcdfg”, leksikoqrafik cəhətdən “nmhgfedcba” nın növbəti permutasiyasıdır.  Növbəti PermutasiyaPin

Növbəti Permutasiya üçün tətbiqetmə

C ++ Proqramı

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

// function to reverse the string between index l and r
void reverse(string &str,int l,int r)
{
    while(l < r)
    swap(str[l++],str[r--]);
}

// function to search a character lying between index l and r 
// which is closest greater (just greater) than val
// and return it's index 
int binarySearch(string& str,int l,int r,char val) 
{ 
  int index = -1; 
  
  while (l <= r) 
  { 
    int mid = (l+r)/2;
    if (str[mid] <= val) 
    {
        r = mid - 1;
    }
    else 
    { 
      l = mid + 1; 
      if (index == -1 || str[index] >= str[mid]) 
        index = mid; 
    } 
  } 
  return index; 
} 

// this function generates next permutation (if there exists any such permutation) from the given string
// and returns True
// Else returns false
bool nextPermutation(string& str) 
{ 
  int len = str.length();
  int i = len-2; 
  
  while (i >= 0 && str[i] >= str[i+1]) 
  i--;
  
  if (i < 0) 
    return false; 
  else 
  { 
    int index = binarySearch(str,i+1,len-1,str[i]); 
    swap(str[i],str[index]); 
    reverse(str,i+1,len-1); 
    return true; 
  } 
} 

// main function to find next permutation
int main() 
{ 
  string str = "nmhdgfecba"; 
  bool is = nextPermutation(str); 
  
  if(is == false) 
    cout<< "Next Permutation Doesnt exist" <<endl; 
  else
    cout<<str<<endl; 
    
  return 0; 
} 
nmheabcdfg

Java Proqramı

class permutation
{
    // swap two characters of string 
    static void swap(StringBuilder sb,int l,int r)
    {
        char temp = sb.charAt(l);
        sb.setCharAt(l,sb.charAt(r));
        sb.setCharAt(r,temp);
    }
    
    // function to reverse the string between index l and r
    static void reverse(StringBuilder sb,int l,int r)
    {
        while(l < r)
        {
            swap(sb,l,r);
            l++;
            r--;
        }
    }
    
    // function to search a character lying between index l and r 
    // which is closest greater (just greater) than val
    // and return it's index 
    static int binarySearch(StringBuilder sb,int l,int r,char val) 
    { 
    	int index = -1; 
    	
    	while (l <= r) 
    	{ 
    		int mid = (l+r)/2;
    		if (sb.charAt(mid) <= val) 
    		{
    		    r = mid - 1;
    		}
    		else 
    		{ 
    			l = mid + 1; 
    			if (index == -1 || sb.charAt(index) >= sb.charAt(mid)) 
    				index = mid; 
    		} 
    	} 
    	return index; 
    } 
    
    // this function generates next permutation (if there exists any such permutation) from the given string
    // and returns True
    // Else returns false
    static boolean nextPermutation(StringBuilder sb) 
    { 
    	int len = sb.length();
    	int i = len-2; 
    	
    	while (i >= 0 && sb.charAt(i) >= sb.charAt(i+1)) 
    	i--;
    	
    	if (i < 0) 
    		return false; 
    	else 
    	{ 
    		int index = binarySearch(sb,i+1,len-1,sb.charAt(i)); 
    		swap(sb,i,index); 
    		reverse(sb,i+1,len-1); 
    		return true; 
    	} 
    }    
    
    // main function to find next permutation
    public static void main(String args[])
    {
        String str = "nmhdgfecba";
        // strings in java are immutable,so we convert strings into StringBuilder
        // StringBuilder are mutable strings        
        StringBuilder sb = new StringBuilder(str);

    	boolean is = nextPermutation(sb); 
    	
    	if(is == false) 
    		System.out.println("Next Permutation Doesnt exist"); 
    	else
    		System.out.println(sb);
           
    }
}
nmheabcdfg

STL kitabxanasından istifadə edərək növbəti permutasiya

STL kitabxanası C + + verilən sətrin növbəti permutasiyasını yaradan next_permutation () funksiyasını ehtiva edir

#include <iostream>
#include <bits/stdc++.h>    // STL library of C++
using namespace std;

int main() 
{
    string str = "nmhdgfecba";
    
    // next_permutation() is present in STL library
    // next_permutation() generates Next Permutation of a string if it exists
    // and returns true
    // else returns false
    if(next_permutation(str.begin(),str.end()))
    cout<<str<<endl;
    else
    cout<<"Next Permutation Doesnt exist";

    return 0;
}
nmheabcdfg

Mürəkkəblik təhlili

  1. Zamanın mürəkkəbliyi: Ümumi vaxt mürəkkəbliyi T (n) = O (n)
    • Ən pis halda, nextPermutation () ın ilk addımı O (n) vaxt alır.
    • binarySearch () O (logn) vaxt aparır.
    • reverse () O (n) vaxtını alır.
  2. Kosmik Mürəkkəblik: A (n) = O (1), çünki burada tapşırıq hesablanarkən heç bir köməkçi yer istifadə etmirik. Bu, növbəti permütasiya probleminin kosmik mürəkkəbliyi deməkdir, bu vəziyyətdə sabitdir.

arayış

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