Längster Run

[yidaki]

Hallo zusammen....
ich hab ein kleines Problem. Ich möchte aus einem String auslesen, welches Zeichen am häufigsten vorkommt. Das Programm das ich geschrieben hab läuft soweit ganz gut, bis auf das kleine Problem, dass wenn der längste run am ende der zeichenkette steht.

String run = "aabbbcddddeefffdddddddddddddddd ";

dann müsste er noch einmal in meine anweisung reinspringen doch mir fällt im moment nix gescheites ein.
hier die If-Anweisung

if (str.charAt(counts) != str.charAt(i))

gruß

 

[Trespasser]

Ich würde das mit einem Zweidimensionalen Array machen...
Jede Spalte für einen Buchstaben und darunter die Anzahl.

dann würde ich jeden index durchgehen und bei dem jeweiligen buchstaben um
eins erhöhen.

Vielleicht gibts noch eine bessere Methode, aber mir fällt auf die schnelle nur
die ein.

mfg

 

[squeaker]

Ich würde mittels StringReader den String Zeichen für Zeichen durchgehen. In einer Temporären variable speicherst du das vorhergehende Zeichen um Zeichenwechsel zu erkennen. Wenn die Zeichen (aktuelles und vorhergehendes) gleich sind, erhöhst du den counter. Wenn sie verschieden sind, überprüfst du, ob der counter größer ist als der größte bisher gefundene, wenn ja, speicherst du den counter, das Zeichen sowie den Anfang der Kette zwischen. Dann counter zurücksetzen auf 1 und weitersuchen.
Am Ende hast du dann den größten Run an zeichen.


In pseudocode:

while (wir haben noch zeichen zu lesen) {
   prev=temp;
   temp=stringReader.read();
   temp_p++;
   if (temp==prev) {
      counter++
   } else {
     if (counter=max_counter) {
       max_counter=counter;
       max_char=prev;
       position=temp_p-counter;
     }
     counter=1; //siehe unten - 1 ist richtig, nicht 0
   }
}

so ungefähr. Ich kann's leider hier nicht programmieren - daher nur der vage Hinweis (ausserdem ist es sicher eine gute Übung - im Pseudocode sind sicher noch kleine Fehler).

 

[yidaki]

Naja, es sollte eigentlich schon mit nem normalen String passieren....
falls der code zu wenig sein sollte kann ich den rest schicken... das programm hat in dem fall oben als ausgabe

längster run : dddd
run.lenght : 4
...

er müsste nur noch einmal am schluss in die aufgeführte if anweisung reinspringen dann währe alles im lot

gruß

 

[Trespasser]

Noch was squeaker derine Methode ist zwar Ok, doch hat sie einen Haken:

: String s="abb";

a würde 0 bekommen.

 

[squeaker]

ich sagte doch - kleine Fehler sind noch drin - ausserdem wird vor dem lesen von a ein wechselnder Run entdeckt und damit der counter auf 1 gesetzt.

Zum Thema String und StringReader: ein StringReader kann man ganz einfach aus einem String basteln:

String s="abb";
StringReader sr=new StringReader(s);

Warum soll man sich auf nur einen Teil der Werkzeuge beschränken, wenn man den ganzen Schrank voll hat.

 

[Trespasser]

sorry habe mich verlesen.
aber im code schreibst du: cnt=0;

mfg

 

[squeaker]

Du hast natürlich recht - ich wollte 1 schreiben. Danke für den Hinweis.

 

[Trespasser]

Ich hätte noch eine Optimierung für deine Methode:

er braucht sich nicht die Position zu merken,außer aus statistischen Gründen ,wo welcher Run war.
Er kennt ja das Zeichen und wie lang der Run ist somit könnte er die zeichen in einer for oder while schleife ausgeben.

Wenn eher statistische Gründe vorhanden sind, würde ich auf emine Methode zurückgreifen, da jeder Run gespeichert wird, plus Anzahl.

mfg

 

[Thomas Darimont]

Hallo!

Siehe:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class LongestRun {

	public static void main(String[] args) {
		System.out.println(
			getLongestRun("aqqqqhkjdhkjhkjhdassdaewwzwzzzzwzqzzzzzzwwiiiiiiiqwiwqiweqwooooooooooooooooooas"));
	}

	/**
	 * @param string
	 */
	private static String getLongestRun(String string) {
		int len = string.length();
		int cnt = 0;
		char c = 0;
		char cOld = string.charAt(0);
		Map map = new HashMap();

		for (int i = 0; i < len; i++) {
			c = string.charAt(i);

			if (c != cOld) {
				String key = "" + cOld;
				Integer integer = (Integer) map.get(key);

				if (integer == null || integer.intValue() < cnt) {
					map.put(key, new Integer(cnt));
				}
				cnt = 0;
			}
			cnt++;
			cOld = c;
		}

		int max = cnt;
		String maxKey = cOld + "";

		for (Iterator iter = map.keySet().iterator(); iter.hasNext();) {
			Object key = iter.next();
			Integer i = (Integer) map.get(key);
			if (i.intValue() > max) {
				max = i.intValue();
				maxKey = (String) key;
			}
		}
		return maxKey + " kommt mit " + max + " mal am häufigsten direkt hintereinander in der übergebenen Zeichenkette vor";
	}
}

Gruß Tom