시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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”
- 문자열의 오른쪽에서 순회하여 내림차순을 따르지 않는 첫 번째 문자를 찾습니다. str의 'd'는 내림차순을 따르지 않습니다. 'd'의 인덱스 = 3.
- 'd'오른쪽에서 ASCII 값의 'd'보다 더 큰 (또는 가장 가까운) 문자를 검색합니다. [nmhd] gfecba의 'e'는 'd'보다 큽니다.이 작업은 binarySearch () 함수를 사용하여 수행됩니다.
- 'e'와 'd'를 바꾸십시오. 결과 문자열은“nmhegfdcba”입니다.
- 이제 1 단계에서 찾은 인덱스 이후에 발생하는 결과 문자열의 일부를 뒤집습니다 (reverse () 함수를 사용하여 수행). "gfdcba"를 뒤집고 기본 문자열에 다시 추가합니다.
- output =“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
STL 라이브러리를 사용한 다음 순열
STL 라이브러리 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
복잡성 분석
- 시간 복잡성: 전체 시간 복잡도 T (n) = O (n)
- 최악의 경우 nextPermutation ()의 첫 번째 단계는 O (n) 시간이 걸립니다.
- binarySearch ()는 O (logn) 시간이 걸립니다.
- reverse ()는 O (n) 시간이 걸립니다.
- 공간 복잡성: A (n) = O (1) 여기서는 작업 계산 중에 보조 공간을 사용하지 않기 때문입니다. 즉,이 경우 다음 순열 문제의 공간 복잡도는 일정합니다.
