0
오히려 간단한 하위 문제가 발생했을 때 문제를 해결하고있었습니다. 두 문자열 S1 및 S2이 제공된 경우 merge(S1,S2)은 두 문자열 S1 및 S2을 산재 시켜서 얻은 문자열을 나타내며 결과 문자열이 사전식이 최소가되도록 두 문자의 문자 순서를 유지합니다.두 문자열을 병합하고 가장 작은 병합 된 사전 식 문자열
예
S1 = abad
S2 = bbde
merge(S1, S2) = ababbdde
은 이제, 문자열 양자의 첫 번째 요소부터 욕심 기술을 적용하고 가장 작은 요소를 찾고, 그 결과로 추가함으로써이 문제를 해결하려고. 그러나 곧 이것이 최적의 솔루션으로 이어지지는 않는다는 것을 알게되었습니다. 코드는 다음과 같습니다.
int n = a.size(), m = b.size();
int i =0, j=0, k=0; char array[n+m];
for(; i< n && j<n;) {
if(a[i] < b[j]) {
array[k] = a[i];
++i;
}
else {
array[k] = b[j];
++j;
}
++k;
}
while(i<n) {
array[k] = a[i];
++i;
++k;
}
while(j<m) {
array[k] = b[j];
++j;
++k;
}
for (int i = 0; i < n+m; ++i) {
cout<<array[i];
}
cout<<endl;
나는 그것을 뒤집어서 가장 큰 문자를 선택하여 뒤에서 추가하기를 원했습니다. 제한된 테스트를 통해 나는 이것을 잘 수행했다.
int n = a.size(), m = b.size();
int i =n-1, j=m-1, k=n+m-1; char array[n+m];
for(; i>=0 && j>=0;) {
if(a[i] > b[j]) {
array[k] = a[i];
--i;
}
else {
array[k] = b[j];
--j;
}
--k;
}
while(i>=0) {
array[k] = a[i];
--i;
--k;
}
while(j>=0) {
array[k] = b[j];
--j;
--k;
}
for (int i = 0; i < n + m; ++i) {
cout<<array[i];
}
cout<<endl;
그러나 이것이 항상 최적의 솔루션을 항상 제공하는지 확신 할 수 없습니다.
처음에는이 해결책이 맞습니까? 그렇다면 누군가가 항상 최적의 솔루션을 만드는 이유에 대해 약간의 증거를 줄 수 있습니다.
나는 당신의 욕심이 알고리즘은 거의 정확 느낌이 있고 두 문자열에서 동일한 문자를 볼 때 당신이 당신의 검색 포크 경우는 작업을 시작해야한다. – Manvel