ការអនុញ្ញាតបន្ទាប់

កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ByteDance Facebook រោងចក្រ Flipkart ក្រុមហ៊ុន google ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Morgan Stanley ការលក់ Uber
ខ្សែអក្សរចំនួនមើល 131

សំណួរសំភាសន៍រចនាប្រព័ន្ធ អាចជាការបើកចំហរ ដូច្នេះវាពិបាកពេកក្នុងការដឹងពីវិធីត្រឹមត្រូវក្នុងការរៀបចំ។ ឥឡូវនេះខ្ញុំអាចបំបែកការរចនានៃ Amazon, Microsoft និង Adobe បន្ទាប់ពីទិញ សៀវភៅ​នេះ. ពិនិត្យឡើងវិញប្រចាំថ្ងៃ សំណួររចនា ហើយខ្ញុំសន្យាថាអ្នកអាចបំបែកការរចនាជុំ។

នៅក្នុងបញ្ហានៃការអនុញ្ញាតិបន្ទាប់យើងបានផ្តល់ពាក្យរកពាក្យដែលមានលក្ខណៈកាន់តែច្រើន។

ឧទាហរណ៍

input : str = "tutorialcup"
output : tutorialpcu

input : str = "nmhdgfecba"
output : nmheabcdfg

input : str = "algorithms"
output : algorithsm

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

សទ្ទានុក្រមសទ្ទវិទ្យា

រាល់ការអនុញ្ញាតនៃពាក្យនៅពេលដែលបានរៀបចំនៅក្នុងវចនានុក្រមលំដាប់នៃពាក្យដែលទទួលបានត្រូវបានគេហៅថាលំដាប់សូរស័ព្ទ។

ឧ។

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

act
atc
cat
cta
tac
tca

យើងអាចមើលឃើញថា "ឆ្មា" គឺមានលក្ខណៈជាលក្ខណៈស័ព្ទដែលមានលក្ខណៈធំជាងការសម្តែង។

ក្បួនដោះស្រាយសម្រាប់ការអនុញ្ញាតបន្ទាប់

សម្រាប់ពាក្យដែលត្រូវបានតម្រៀបទាំងស្រុងតាមលំដាប់លំដោយពោលគឺ“ nmhgfedcba” មិនមានការអនុញ្ញាតបន្ទាប់ទេ។ យើងអាចរកការអនុញ្ញាតិបន្ទាប់សម្រាប់ពាក្យដែលមិនត្រូវបានតម្រៀបទាំងស្រុងតាមលំដាប់ចុះ។ ឧ។ “ nmhdgfecba” ។ ប៊លគឺជាធ ក្បួនដោះស្រាយ:
ដែលបានផ្តល់ជូន៖ str =“ nmhdgfecba”

  1. ឆ្លងកាត់ពីខាងស្តាំនៃខ្សែអក្សរហើយរកមើលតួអក្សរទីមួយដែលមិនធ្វើតាមលំដាប់ចុះ។ 'd' នៅក្នុង str មិនធ្វើតាមលំដាប់ដែលកំពុងដំណើរការទេ។ សន្ទស្សន៍នៃ 'ឃ' = ៣ ។
  2. នៅខាងស្តាំនៃ 'ឃ' ស្វែងរកតួអក្សរដែលមានទំហំធំជាង 'ឃ' ក្នុងតម្លៃ ASCII ។ 'e' នៅក្នុង [nmhd] gfecba គឺធំជាង 'd ។ នេះត្រូវបានធ្វើរួចដោយប្រើមុខងារ binarySearch () ។
  3. ប្តូរ 'e' និង 'd ។ ខ្សែលទ្ធផលគឺ“ nmhegfdcba” ។
  4. ឥឡូវបញ្ច្រាស (ធ្វើដោយប្រើមុខងារបញ្ច្រាស () មុខងារ) ផ្នែកនៃខ្សែលទ្ធផលដែលកើតឡើងបន្ទាប់ពីលិបិក្រមបានរកឃើញនៅក្នុងជំហានទី 1 បញ្ច្រាស“ gfdcba” ហើយបន្ថែមវាទៅខ្សែអក្សរសំខាន់។
  5. លទ្ធផល =“ nmheabcdfg” វាគឺជាការអនុញ្ញាតិបន្ទាប់នៃ“ nmhgfedcba” ។  ការអនុញ្ញាតបន្ទាប់ពិន

ការអនុវត្តសម្រាប់ការអនុញ្ញាតបន្ទាប់

កម្មវិធី C ++

#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

កម្មវិធីចាវ៉ា

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

ការអនុញ្ញាតបន្ទាប់ដោយប្រើបណ្ណាល័យអេសអិល

បណ្ណាល័យអេសអិលនៃ C ++ មានអនុគមន៍ next_permutation () ដែលបង្កើតអនុគមន៍បន្ទាប់នៃខ្សែអក្សរដែលបានផ្តល់

#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

ការវិភាគស្មុគស្មាញ

  1. ស្មុគស្មាញពេលវេលា៖ សរុបពេលវេលាស្មុគស្មាញ T (n) = O (n)
    • ក្នុងករណីអាក្រក់បំផុតជំហានដំបូងនៃ NextPermutation () ចំណាយពេល O (n) ពេលវេលា។
    • binarySearch () ចំណាយពេល O (ចូល) ។
    • បញ្ច្រាស () ចំណាយពេល O (n) ពេលវេលា។
  2. ភាពស្មុគស្មាញនៃលំហ៖ A (n) = O (១) ពីព្រោះនៅទីនេះយើងមិនប្រើកន្លែងជំនួយក្នុងកំឡុងពេលគណនាភារកិច្ចទេ។ នោះមានន័យថាភាពស្មុគស្មាញអវកាសនៃបញ្ហាអនុញ្ញាតិលើកក្រោយក្នុងករណីនេះគឺថេរ។

ឯកសារយោង

បទសម្ភាសន៍រចនាប្រព័ន្ធបំបែក
Translate »