String - Reduktion- Programming Contest . Lösung benötigt

Ich gehe davon aus, dass Sie sich für die Länge der kürzesten Zeichenkette, die nach der Reduktion.

Eine einfache Lösung wäre, um alle Möglichkeiten in eine gierige Art und Weise und hoffe, dass es explodiert nicht exponentiell. I ' m gonna write Python-pseudocode hier, weil das ist einfacher zu verstehen (zumindest für mich ;)):

from collections import deque

def try_reduce(string):
    queue = deque([string])
    min_length = len(string)
    while queue:
        string = queue.popleft()
        if len(string) < min_length:
            min_length = len(string)
        for i in xrange(len(string)-1):
            substring = string[i:(i+2)]
            if substring == "AB" or substring == "BA":
                queue.append(string[:i] + "C" + string[(i+2):])
            elif substring == "BC" or substring == "CB":
                queue.append(string[:i] + "A" + string[(i+2):])
            elif substring == "AC" or substring == "CA":
                queue.append(string[:i] + "B" + string[(i+2):])
    return min_length

Ich denke die Grundidee ist klar: Sie nehmen eine Warteschlange (std::deque sollte in Ordnung sein), fügen Sie Ihren Text hinein, und dann implementieren Sie eine einfache Breite-zuerst-Suche im Raum aller möglichen Ermäßigungen. Während der Suche, Sie nehmen das erste element aus der queue, nehmen Sie alle möglichen Teilfolgen von es, führen alle mögliche Reduzierungen, und drücken Sie die reduzierten Streichern zurück in die Warteschlange. Der gesamte Raum erkundet, wenn die Warteschlange leer ist.

Können Sie verallgemeinern das Resultat, basierend auf der individuellen Anzahl Zeichen der Zeichenkette. Der algo ist wie folgt,

traverse durch die string-und die individuelle char zählen.

Können sagen, wenn

• a = no# einer ist, der im gegebenen string
• b = no# von b ist, der im gegebenen string
• c = no# c ist im gegebenen string

dann kann man sagen, dass das Ergebnis wird sein,

if((a == 0 && b == 0 && c == 0) ||
   (a == 0 && b == 0 && c != 0) ||
   (a == 0 && b != 0 && c == 0) ||
   (a != 0 && b == 0 && c == 0))
{
    result = a+b+c;
}
else if(a != 0 && b != 0 && c != 0)
{
    if((a%2 == 0 && b%2 == 0 && c%2 == 0) ||
       (a%2 == 1 && b%2 == 1 && c%2 == 1))
        result = 2;
    else
        result = 1;
}
else if((a == 0 && b != 0 && c != 0) || 
        (a != 0 && b == 0 && c != 0) || 
        (a != 0 && b != 0 && c == 0))
{
    if(a%2 == 0 && b%2 == 0 && c%2 == 0)
        result = 2;
    else
        result = 1;
}

Vergleichen Sie zwei Zeichen in einer Zeit und ersetzen Sie Sie, wenn beide benachbarten Zeichen sind nicht dasselbe. Zu bekommen optimale Lösung, führen Sie einmal vom Anfang der Zeichenfolge und einmal vom Ende der Zeichenfolge. Return der minimale Wert.

int same(char* s){
    int i=0;
    for(i=0;i<strlen(s)-1;i++){
            if(*(s+i) == *(s+i+1))
                    continue;
            else
                    return 0;
    }
    return 1;
}


int reduceb(char* s){
    int ret = 0,a_sum=0,i=0;
    int len = strlen(s);
    while(1){
            i=len-1;
            while(i>0){
                    if ((*(s+i)) == (*(s+i-1))){
                                    i--;
                                    continue;
                    } else {
                            a_sum = (*(s+i)) + (*(s+i-1));
                            *(s+i-1) = SUM - a_sum;
                            *(s+i) = '\0';
                            len--;
                    }
                    i--;
            }
            if(same(s) == 1){
                    return strlen(s);
                    }
}
}


int reducef(char* s){
    int ret = 0,a_sum=0,i=0;
    int len = strlen(s);
    while(1){
            i=0;
            while(i<len-1){
                    if ((*(s+i)) == (*(s+i+1))){
                                    i++;               
                                    continue;
                    } else {
                            a_sum = (*(s+i)) + (*(s+i+1));
                            *(s+i) = SUM - a_sum;
                            int j=i+1;
                            for(j=i+1;j<len;j++)
                                    *(s+j) = *(s+j+1);
                            len--;
                    }
                    i++;
            }
            if(same(s) == 1){
                    return strlen(s);
                    }
}
}

int main(){
    int n,i=0,f=0,b=0;
    scanf("%d",&n);
    int a[n];

    while(i<n){
            char* str = (char*)malloc(101);
            scanf("%s",str);
            char* strd = strdup(str);
            f = reducef(str);
            b = reduceb(strd);

            if( f > b)
                    a[i] = b;
            else
                    a[i] = f;
            free(str);
            free(strd);
            i++;
    }

    for(i=0;i<n;i++)
            printf("%d\n",a[i]);

}

Wäre das nicht ein guter start sein, um zu zählen, die Buchstaben, die Sie haben die meisten und suchen nach Möglichkeiten, um es zu entfernen? Halten Sie tun dies, bis wir nur einen Brief. Vielleicht haben wir es viele Male, aber solange ist es das gleiche wir kümmern uns nicht, wir sind fertig.

Vermeiden, dass so etwas wie ABCCCCCCC immer CCCCCCCC.

Entfernen wir die beliebtesten Brief:

-ABCCCCCCC

-AACCCCCC

-ABCCCCC

-AACCCC

-ABCCC

-AACC

-ABC

-AA

Ich Stimme mit den vorherigen poster, die Staaten müssen wir eine Länge von 1 oder 2 - was passiert, wenn ich geben Sie die start-Zeichenfolge AAA?

Dies ist greedy-Ansatz und die Traversierung beginnt der Pfad mit jedem möglichen paar und überprüfung der min Länge.

import java.io.*;
import java.util.*;

class StringSim{

public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    StringTokenizer st = new StringTokenizer(sc.nextLine(), " ");
    int N = Integer.parseInt(st.nextToken());
    String op = "";
    for(int i=0;i<N;i++){
        String str = sc.nextLine();
        op = op + Count(str) + "\n";
    }
    System.out.println(op);
}

public static int Count( String str){
    int min = Integer.MAX_VALUE;
    char pre = str.charAt(0);
    boolean allSame = true;
    //System.out.println("str :" + str);
    if(str.length() == 1){
        return 1;
    }
    int count = 1;
    for(int i=1;i<str.length();i++){
        //System.out.println("pre: -"+ pre +"- char at "+i+" is : -"+ str.charAt(i)+"-");
        if(pre != str.charAt(i)){
            allSame = false;
            char rep = (char)(('a'+'b'+'c')-(pre+str.charAt(i)));
            //System.out.println("rep :" + rep);
            if(str.length() == 2)
                count = 1;
            else if(i==1)
                count = Count(rep+str.substring(2,str.length()));
            else if(i == str.length()-1) 
                count = Count(str.substring(0,str.length()-2)+rep);
            else
                count = Count(str.substring(0,i-1)+rep+str.substring(i+1,str.length()));

            if(min>count) min=count;
        }else if(allSame){
            count++;
            //System.out.println("count: " + count);
        }
        pre = str.charAt(i);
    }
    //System.out.println("min: " + min);
    if(allSame) return count;
    return min;
  }
}

Gibt es einige zugrunde liegende Struktur, die verwendet werden können, zu lösen dieses problem in O(n) Zeit.

Die Regeln gegeben sind die (meisten) Regeln definieren eine mathematische Gruppe, insbesondere die Gruppe D_2 manchmal auch bekannt als K (für Klein-Gruppe vier) oder V (Deutsch für Viergruppe, vier Gruppe). D_2 ist eine Gruppe mit vier Elementen, A, B, C, und 1 (Identität-element). Eine der Erkenntnisse von D_2 ist die Menge der Symmetrien von einem rechteckigen Kasten mit drei verschiedenen Seiten. A, B, und C sind 180-Grad-Drehungen um die einzelnen Achsen, und ist 1 die Identität-rotation (keine rotation). Die Gruppe Tisch für D_2 ist

 |1 A B C
-+------- 
1|1 A B C
A|A 1 C B
B|B C 1 A
C|C B A 1

Wie Sie sehen können, die Regeln entsprechen den Regeln, die in das problem, mit der Ausnahme, dass die Regelungen, die 1 nicht in das problem.

Seit D_2 ist eine Gruppe, die es erfüllt eine Reihe von Regeln: Schließung (das Produkt von zwei Elementen der Gruppe ist ein anderes element), Assoziativität (Bedeutung (x*y)*z = x*(y*z) für alle Elemente x, y, z; d.h., die Reihenfolge, in der die Streicher reduziert werden spielt keine Rolle), die Existenz der Identität (es ist ein element 1 so dass 1*x=x*1=x für alle x), und Existenz von inversen (für jedes element x, es ist ein element x^{ -1} so dass x*x^{ -1}=1 and x^{ -1}*x=1; in unserem Fall, jedes element ist sein eigenes inverses).

Es ist auch erwähnenswert, dass D_2 ist kommutativ, d.h., x*y=y*x für alle x,y.

Gegeben eine beliebige Zeichenfolge von Elementen in D_2, können wir reduzieren auf ein einziges element in der Gruppe in eine gierige Weise. Zum Beispiel ABCCCCCCC=CCCCCCCC=CCCCCC=CCCC=CC=1. Beachten Sie, dass wir nicht schreiben, das element 1 es sei denn, es ist das einzige element in der Zeichenfolge. Die Assoziativität sagt uns, dass die Reihenfolge der Operationen spielt keine Rolle, z.B., könnten wir gearbeitet haben, von rechts nach Links oder begann in der Mitte und bekommen das gleiche Ergebnis. Lasst uns versuchen von der rechten Seite: ABCCCCCCC=ABCCCCC=ABCCC=ABC=AA=1.

Die situation des Problems ist anders, weil Operationen mit 1 sind nicht zulässig, so können wir nicht einfach beseitigen Paare AA, BB oder CC. Die situation ist aber nicht , dass anders. Betrachten Sie die Zeichenfolge ABB. Wir können nicht schreiben ABB=A in diesem Fall. Allerdings können wir beseitigen BB in zwei Schritten mit A: ABB=CB=A. Da die Reihenfolge egal ist, von Assoziativität, sind wir garantiert das gleiche Ergebnis zu erhalten. Also wir können nicht direkt von ABB zu A aber wir können das gleiche Ergebnis durch eine andere route.

Solche Alternative Routen verfügbar sind, Wann immer es gibt mindestens zwei unterschiedliche Elemente in einem string. In allem, in jedem ABB, ACC, BAA, BCC, CAA, CBB, AAB, AAC, BBA, BBC, CCA, CCB, wir können handeln, als ob wir die Reduktion xx=1 und dann fallen die 1.

Daraus folgt, dass jede Zeichenfolge, die ist nicht homogen, (nicht alle den gleichen Brief) und hat einen Doppel-Brief substring ( AA , BB oder CC) kann reduziert werden durch die Beseitigung der doppelten Buchstaben. Strings, die nur aus zwei identischen Buchstaben können nicht weiter reduziert werden (weil es keine 1 erlaubt in das problem), also es scheint sicher zu vermuten, dass alle nicht-homogene string kann reduziert werden A, B, C, AA, BB, CC.

Wir haben immer noch vorsichtig sein, aber, weil CCAACC konnte sich in CCCC durch entfernen der mittleren paar AA, aber das ist nicht das beste, was wir tun können: CCAACC=AACC=CC or AA nimmt uns mit nach unten, um einen string der Länge 2.

Anderen situation müssen wir vorsichtig sein, der ist AABBBB. Hier konnten wir beseitigen AA zu Ende mit BBBB, aber es ist besser, zu beseitigen, die Mitte B's erste, dann was auch immer: AABBBB=AABB=AA or BB (beide sind gleichwertig 1 in der Gruppe, aber kann nicht weiter reduziert werden das problem).

Gibt es eine weitere interessante situation, die wir haben könnten: AAAABBBB. Blind Beseitigung von Paaren führt uns entweder AAAA oder BBBB, aber wir könnten noch besser: AAAABBBB=AAACBBB=AABBBB=AABB=AA or BB.

Oben zeigen, dass die Beseitigung von Doppel-blind ist nicht unbedingt die Art und Weise zu gehen, aber es war trotzdem aufschlussreich.

Stattdessen scheint es, als ob die wichtigste Eigenschaft eine Zeichenfolge ist, die nicht-Homogenität. Wenn die saite ist homogen, stop, es gibt nichts, was wir tun können. Ansonsten, identifizieren, ein Vorgang, der erhält die nicht-Homogenität-Eigenschaft, wenn möglich. Ich behaupten, dass es immer möglich ist zu identifizieren, ein Vorgang, der bewahrt nicht-Homogenität, wenn der string nicht-homogenen und der Länge vier oder mehr.

Beweis: wenn ein 4-substring enthält zwei verschiedene Briefe, ein Dritter Brief kann eingeführt werden, bei der eine Grenze zwischen zwei verschiedenen Buchstaben, z.B. AABA geht ACA. Da der ein oder andere von den ursprünglichen Buchstaben müssen unverändert irgendwo in der Zeichenfolge, es folgt, dass das Ergebnis noch nicht homogen.

Nehmen wir statt dessen haben wir eine 4-substring mit drei verschiedenen Elementen, sagen wir AABC, mit die äußeren zwei Elemente verschiedenen. Dann, wenn die zwei mittleren Elemente sind unterschiedlich, führen Sie die operation auf diese; das Ergebnis ist nicht homogen, weil die beiden äußersten Elemente sind immer noch unterschiedlich. Auf der anderen Seite, wenn die beiden inneren Elemente sind die gleichen, z.B. ABBC, dann haben Sie, anders zu sein als die beiden äußersten Elemente (sonst würden wir nur zwei Elemente in der Reihe von vier, nicht drei). In diesem Fall führen Sie entweder die erste oder die Dritte operation; das lässt entweder die beiden letzten Elemente unterschiedlich ist (z.B., ABBC=CBC) oder die ersten beiden Elemente unterschiedlich ist (z.B., ABBC=ABA) so nicht-Homogenität erhalten bleibt.

Schließlich betrachten wir den Fall, wo die ersten und letzten Elemente sind die gleichen. Dann haben wir eine situation wie ABCA. Die zwei mittleren Elemente beide haben, anders zu sein als die äußeren Elemente, sonst hätten wir nur noch zwei Elemente in diesem Fall nicht drei. Wir können nehmen Sie den ersten verfügbaren Betrieb ABCA=CCA - und non-Homogenität bewahrt wird, wieder.

Ende der Beweis.

Haben wir einen greedy-Algorithmus zur Verringerung der nicht-homogenen string der Länge 4 oder größer: wählen Sie die erste Vorgang, der bewahrt nicht-Homogenität; diese muss eine operation existieren, die von den oben genannten argument.

Wir haben nun reduziert auf den Fall, wo wir eine nicht-homogene saite der 3 Elemente. Wenn zwei die gleichen, entweder haben wir verdoppelt wie AAB etc., was wir wissen, können reduziert werden, um ein einzelnes element, oder wir haben zwei Elemente, die keine Doppel-wie ABA=AC=B kann auch reduziert werden, um ein einzelnes element, oder wir haben drei verschiedene Elemente wie ABC. Es gibt sechs Permutationen, die alle =1 in der Gruppe, die durch die Assoziativität und commutativity; alle von Ihnen können reduziert werden, um zwei Elemente, die von jedem Betrieb, aber Sie können unter keinen Umständen reduziert werden unter eine homogene pair ( AA , BB oder CC) seit 1 ist, dürfen Sie nicht in das problem, so wissen wir, dass ist das beste, was wir tun können, in diesem Fall.

In der Zusammenfassung, falls eine saite ist homogen, es gibt nichts, was wir tun können, wenn eine saite nicht homogen und die =A in der Gruppe, kann es reduziert werden, um A in das problem durch einen greedy-Algorithmus, die behauptet, die nicht-Homogenität bei jedem Schritt; das gleiche gilt, wenn der string =B oder =C in der Gruppe; schließlich, wenn Sie eine Zeichenfolge ist nicht homogen und die =1 in der Gruppe, es kann reduziert werden, indem ein greedy-Algorithmus, die behauptet, die nicht-Homogenität, so lange wie möglich ein AA, BB oder CC. Das sind die besten, die wir tun können, indem Sie die Eigenschaften der Gruppe der operation.

Programm die Lösung des Problems:

Nun, da wir wissen, dass die möglichen Ergebnisse, die unser Programm ausgeführt werden kann, in O(n) Zeit wie folgt: wenn alle Buchstaben in der gegebenen Folge sind die gleichen, keine Reduzierung möglich ist, also nur die Ausgabe der Länge der Zeichenkette. Wenn der string ist nicht homogen, und ist gleich um die Identität in der Gruppe, die Ausgabe die Zahl "2"; sonst Ausgabe die Nummer 1.

Schnell entscheiden, ob ein element entspricht der Identität in der Gruppe, wir verwenden commutativity und Assoziativität wie folgt: nur die Anzahl der A's, B's und C's in der Variablen a, b, c. Ersetzen a = a mod 2, b = b mod 2, c = c mod 2 weil wir beseitigen können Paare AA, BB, und CC in der Gruppe. Wenn keine der resultierenden a, b, c ist gleich 0, wir haben ABC=1 in der Gruppe, so sollte das Programm die Ausgabe 2, da eine Reduktion auf die Identität 1 ist nicht möglich. Wenn alle drei der resultierenden a, b, c sind gleich 0 ist, haben wir wieder die Identität (A, B, und C alle storniert sich von selbst) also sollten wir die Ausgabe 2. Andernfalls wird die Zeichenfolge nicht-Identität, und wir sollten die Ausgabe-1.

Vergleichen Sie zwei Zeichen in einer Zeit und ersetzen Sie Sie, wenn beide benachbarten Zeichen sind nicht dasselbe. Zu bekommen optimale Lösung, führen Sie einmal vom Anfang der Zeichenfolge und einmal vom Ende der Zeichenfolge. Return der minimale Wert.

Rav Lösung ist :-

int same(char* s){
    int i=0;
    for(i=0;i<strlen(s)-1;i++){
            if(*(s+i) == *(s+i+1))
                    continue;
            else
                    return 0;
    }
    return 1;
}


int reduceb(char* s){
    int ret = 0,a_sum=0,i=0;
    int len = strlen(s);
    while(1){
            i=len-1;
            while(i>0){
                    if ((*(s+i)) == (*(s+i-1))){
                                    i--;
                                    continue;
                    } else {
                            a_sum = (*(s+i)) + (*(s+i-1));
                            *(s+i-1) = SUM - a_sum;
                            *(s+i) = '\0';
                            len--;
                    }
                    i--;
            }
            if(same(s) == 1){
                    return strlen(s);
                    }
}
}


int reducef(char* s){
    int ret = 0,a_sum=0,i=0;
    int len = strlen(s);
    while(1){
            i=0;
            while(i<len-1){
                    if ((*(s+i)) == (*(s+i+1))){
                                    i++;               
                                    continue;
                    } else {
                            a_sum = (*(s+i)) + (*(s+i+1));
                            *(s+i) = SUM - a_sum;
                            int j=i+1;
                            for(j=i+1;j<len;j++)
                                    *(s+j) = *(s+j+1);
                            len--;
                    }
                    i++;
            }
            if(same(s) == 1){
                    return strlen(s);
                    }
}
}

int main(){
    int n,i=0,f=0,b=0;
    scanf("%d",&n);
    int a[n];

    while(i<n){
            char* str = (char*)malloc(101);
            scanf("%s",str);
            char* strd = strdup(str);
            f = reducef(str);
            b = reduceb(strd);

            if( f > b)
                    a[i] = b;
            else
                    a[i] = f;
            free(str);
            free(strd);
            i++;
    }

    for(i=0;i<n;i++)
            printf("%d\n",a[i]);

}

@Rav

dieser code wird nicht für die Eingabe "abccaccba".
Lösung sollte nur "b"
aber dieser code wird nicht geben. Da bin ich nicht immer richtigen Kommentar platzieren(wegen der niedrigen Punkte oder aus einem anderen Grund), so habe ich es hier.

Lösen können Sie dieses mit 2 pass.

Im ersten Durchgang, die Sie anwenden,

len = strlen (str) ;
index = 0 ;
flag = 0 ;

/* 1st pass */
for ( i = len-1 ; i > 0 ; i -- ) {
  if ( str[i] != str[i-1] ) {
    str[i-1] = getChar (str[i], str[i-1]) ;
    if (i == 1) {
      output1[index++] = str[i-1] ;
      flag = 1 ;
      break ;
    }
  }
  else output1[index++] = str[i] ;

}

if ( flag == 0 ) 
  output1[index++] = str[i] ;
output1[index] = '\0';

Und im 2. pass werden Sie die gleichen auf 'output1', um das Ergebnis zu erhalten.
So, Einer ist nach vorne gehen, eine andere ist die backward-pass.

import java.util.Scanner;

public class StringReduction {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine();
    int length = str.length(); 
    String result = stringReduction(str);
    System.out.println(result); 
}

private static String stringReduction(String str) {
    String result = str.substring(0);
    if(str.length()<2){
        return str;
    }
    if(str.length() == 2){
        return combine(str.charAt(0),str.charAt(1));
    }
    for(int i =1;i<str.length();i++){
        if(str.charAt(i-1) != str.charAt(i)){ 
            String temp = str.substring(0, i-1) + combine(str.charAt(i-1),str.charAt(i)) + str.substring(i+1, str.length()); 
            String sub = stringReduction(temp);
            if(sub.length() < result.length()){
                result = sub;
            }
        }
    }
    return result;
}

private static String combine(char c1, char c2) { 
    if(c1 == c2){
        return "" + c1 + c2;
    }
    else{
        if(c1 == 'a'){
            if(c2 == 'b'){
                return "" + 'c';
            }
            if(c2 == 'c') {
                return "" + 'b';
            }
        }
        if(c1 == 'b'){
            if(c2 == 'a'){
                return "" + 'c';
            }
            if(c2 == 'c') {
                return "" + 'a';
            }
        }
        if(c1 == 'c'){
            if(c2 == 'a'){
                return "" + 'b';
            }
            if(c2 == 'b') {
                return "" + 'a';
            }
        }
        return null;
    } 
}

}