Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Schreiben Sie eine effiziente Methode, die die Länge der längsten Sequenz von
Leerzeichen in einem gegebenen String sucht und dabei möglichst wenig Zeichen im
String untersucht (Hinweis: Das Programm sollte schneller werden, wenn die Länge
der Sequenz von Leerzeichen zunimmt). Geben Sie außerdem die Zahl der
benötigten Vergleiche aus.
Das Thema hatte ich hier schon mal da wurde es über Binäresuche gelöst. Ich habe aber einen neuen Ansatz denn auch Ich hin bekomme bis jetzt
Ich fülle einen String mit Leerzeichen und vergleiche diese dann ob die Anzahl der Leerzeichen im String vorhanden sind. Mein Programm sieht bis jetzt so aus:
Mein Problem sind die Vergleiche.
Die Sequenz stimmt ja damit da ich durch den String laufe und die Anzahl immer wieder erhöhe vorher habe ich gefragt ob der String Null ist oder leer ist!
Wie bekomme ich das nun aber mit den Vergleichen hin?
Hat da vielleicht jemand eine Idee?
ich glaube ich verstehe dich nicht so recht.
Meinst du etwas ich soll ein String Array erstellen dort dann 1,2,3,4,5,... etc. Leerzeichen abspeichern lassen mit einer Schleife so lange bis ich die Länge des übergebenen Strings habe.
Dann vergleiche ich jede Position also im String Array [0] = 1 Leerzeichen mit meinem übergebenen String und so weiter?
Dann hätte man die Antwort auch also Anzahl der vergleiche aber ist das nicht mega viel Aufwand?
LG
Ich glaube ihr überseht eine wichtige Sache an der Aufgabenstellung.
Zuerst mal: ein split ist ja nicht besser (bzgl. den benötigten Vergleichen) als brute-force. (Einmal über String iterieren und zusammenhängende Leerzeichen zählen)
Wenn man während der Iteration weiß, dass die bisherig längste Sequenz 3 lang war. Dann kann ich beim letzten Buchstaben, der kein Leerzeichen war 3 weiter springen, und schauen, ob ein Leerzeichen vorliegt. d.h. ich im Fall dass eins vorliegt, muss ich nochmal zurück. Falls es aber kein Leerzeichen war, kann ich getrost weitersuchen, weil die Sequenz kann ja nicht länger als 3 an dieser Stelle werden. (Das ganze gibt es als dynamischen Programmierungs-Algo, allerdings hab ich den speziellen Namen gerade nicht parat.)
Die Probleme, die du hast, hat in der Vergangenheit schon jemand gelöst. Erweitere doch dein Horizont durch die Vielfalt der verschiedenen Klassen und deine Werkzeugkiste wird mit der Zeit größer und besser
Ich finde, dass der Split sehr übersichtlich ist und eine Menge an Tipparbeit abnimmt. Wer die Klasse String kennt, sollte sich für ihre Methoden interessieren, vor allem als Anfänger
Ich finde, dass der Split sehr übersichtlich ist und eine Menge an Tipparbeit abnimmt. Wer die Klasse String kennt, sollte sich für ihre Methoden interessieren, vor allem als Anfänger
Natürlich. Programmierer sollten immer "das Rad nicht neu erfinden".
Man muss aber schauen, ob die Lösung das Problem tatsächlich löst:
Möchte man nur eine funktionierende Lösung oder eine performante. ( Insbesondere eine die, die Anforderung in der Aufgabenstellung erfüllt )
Danke erstmal
Ich mache die Sachen gerne selbst das ist meine Übung!
Klar ist es später besser die Methoden der String Klasse zu kennen und sowas dann darüber zu machen. Leider hatte ich bis jetzt noch nicht so sehr die Zeit mich damit auseinander zu setzen vielleicht liegt es auch daran das ich immer wieder alles selbst schreibe und so lange an den Aufgaben sitze
Javinner ist damit die Aufgabe erfüllt? Das mit dem Splitt verstehe ich nicht so wirklich wie schon gesagt werde ich mir wieder anschauen.
Ich hab ja eigentlich nur noch die Vergleiche benötigt die ich ja nun auch hin bekommen habe. So gesehen wird das Programm nicht schneller es ist ein "Pseudo Vergleich" da ich einen String oder gar ein String Array fülle mit leer Zeichen und diese mit dem gegebenen String vergleiche. Es wird nur dann schneller wenn mehr Leerzeichen drin sind als 1 denn dann habe ich ja 1 Vergleich weniger denn ich machen muss etc.!
Bei der Aufgabe kommt es sehr darauf an, was man als "Vergleich" zählt. Ich würde sagen, dass damit jeder Vergleich eines Zeichens der Zeichenkette mit einem beliebigen Zeichen gemeint ist. In dem Fall hast Du sehr viele Vergleiche, weil Dein String-Vergleich ja selbst Zeichen miteinander vergleicht.
Ich werfe mal folgende Lösung in den Raum:
Java:
public class Test {
private int max;
private int vergleiche;
private String str;
private int len;
public Test(String str) {
this.str = str;
this.len = str.length();
}
public void zaehle() {
vergleiche = 0;
max = 0;
int lastNonSpace = -1;
int i = 0;
while (i < len) {
if (isSpace(i)) {
int bs = beginnSequenz(i, lastNonSpace);
int es = endeSequenz(i+1);
lastNonSpace = es;
int sl = es - bs;
max = Math.max(max, sl);
i = es;
} else {
lastNonSpace=i;
}
i += max + 1;
}
}
private int beginnSequenz(int ix, int lastNonSpace) {
while (ix > lastNonSpace+1 && isSpace(ix-1)) {
ix--;
}
return ix;
}
private int endeSequenz(int ix) {
while (ix < len && isSpace(ix)) {
ix++;
}
return ix;
}
private boolean isSpace(int ix) {
vergleiche++;
return str.charAt(ix) == ' ';
}
public static void main(String[] args) throws Exception {
Test ws = new Test("AB ABDEFGB C");
ws.zaehle();
System.out.printf("Maximale Länge: %d, Vergleiche %d\n", ws.max, ws.vergleiche);
}
}