Eingabeformat
Die erste Zeile enthält die Zahlengruppe in der Sequenz. Nummer sind in aufsteigender Reihenfolge aufgeführt.
Randbedingungen
1 & lt; = M & lt; = 99999 Die Länge der Kette S liegt zwischen 5 und 200.
Ausgabeformat
Die erste Zeile enthält die fehlende Nummer M.
Beispiel Eingabe / Ausgabe 1
Eingabe: 12346789
Ausgabe: 5
Eingang / Ausgang 2 Eingang 596597598600601602
Ausgabe: 599
Die Zahlen einer Sequenz in der Sequenz sind 596 597 598 599 600 601 602. 599 sind die fehlenden Nummern
Meine Java-Lösung ist:
Ich habe split(("?<=\G...")) usw. verwendet, um die Zahlen in eine, zwei, drei, vier und fünf Ziffern aufzuteilen. Und speicherte die Nummern in einem entsprechenden Array. Dann habe ich nach einem Unterschied zwischen zwei benachbarten Zahlen in einem Array gesucht - wenn es eins ist, wird es eine Funktion aufrufen, um die fehlende Nummer zu finden.
Aber das Problem ist, wenn:
Eingabe:
%Vor%Ausgabe:
%Vor%Die Reihenfolge ist 9998 9999 10001 10002. Die fehlende Zahl ist 10000
Wie würde ich die Zeichenfolge teilen, wenn ein Übergang von einer 4-stelligen zu einer 5-stelligen Zahl möglich ist? Gibt es einen besseren Weg, dieses Problem zu lösen?
%Vor%Wenn (wie ich annehme) die Zahlen der Reihe nach aufgelistet sind, dann wird ein sehr einfacher Algorithmus funktionieren:
try(toInt(S[1 .. d]), S[d+1 .. |S|]) auf, um die Zahlenfolge zu versuchen, die mit der von S [1 .. d] codierten Zahl beginnt. Wenn diese Sequenz "funktioniert", geben Sie sie aus und stoppen Sie sie. Die obige Hauptschleife endet bei d = 5, weil Sie die Einschränkung angeben, dass M & lt; = 99999, aber es kann leicht dazu gebracht werden, mit beliebig großen Zahlen zu arbeiten, indem einfach d bis zu | S | erhöht wird .
Der zweite Schritt ("Try ...") ist einfach, da Sie in dieser (Kandidaten-) Sequenz bereits die erste Zahl x haben, so dass Sie einfach die Ziffernfolge erzeugen können, die der nächsten Zahl entspricht ( dh, entspricht x + 1) und vergleicht sie mit dem Rest von S. Wenn die Ziffernfolge, die x + 1 entspricht, nicht mit den ersten Zeichen von S übereinstimmt, dann versuche die Ziffernfolge, die x + 2 entspricht. Wenn das übereinstimmt, dann setze ein Flag, das die Tatsache aufzeichnet, dass x + 1 möglicherweise die fehlende Nummer ist, und mach weiter. Wenn sowohl x + 1 als auch x + 2 nicht übereinstimmen oder wenn x + 1 nicht übereinstimmt und das Flag bereits gesetzt ist, wissen wir, dass der Anfangswert nicht richtig sein konnte, also geben Sie zurück und lassen Sie die nächsthöhere Anfangsnummer von der Hauptschleife probieren :
%Vor%Offensichtlich können Sie die Schritte "Erste ... Zeichen von S löschen" ersetzen, indem Sie einfach einen Versatz in die (unveränderte) Zeichenkette einfügen, aber ich fühlte, dass das obige für eine Erklärung einfacher war.
Dies sollte funktionieren, wenn Sie bereits die erste zu erwartende Zahl kennen. Das Bestimmen der ersten Zahl könnte jedoch schwierig sein.
%Vor%Zusätzlich zur Lösung des Problems, das das OP gab, müssen Sie zwei zusätzliche Probleme lösen.
Wie auch immer, hier sind die Testfälle, die ich gegen meinen Code ausgeführt habe. Die erste Zeile ist der Zahlenstring. Die zweite Zeile ist das Zahlenfeld aus der Zeichenfolge. Die dritte Zeile ist die fehlende Nummer.
%Vor%Der Punkt, den Sie aus diesem Code entnehmen können, besteht darin, alle Kantenfälle auszuprobieren, die Sie sich ausdenken können. Ich hätte nicht über die 9899, 9900 Sequenz nachgedacht, außer ich hätte den Code geschrieben.
%Vor%Ich denke, Sie können diesen Code verbessern, aber versuchen Sie es:
%Vor%Sie werden immer mit last-first == sequence.size () // d. h. 7-3 = 4
endenAuf diese Weise ist es einfach, die richtige Nummernlänge zu finden (zumindest die Listennummern deutlich zu reduzieren).
Um die Leistung zu verbessern, können Sie überprüfen, ob String.length durch Zahlenlänge teilbar ist, sonst wäre ein Fehler:
1230124 Wenn Sie nur die ersten 3 und die letzten 3 Zeichen auswählen, um die Länge 3 zu testen.
%Vor%Ich habe zuerst eine Scala-Lösung geschrieben, einen One-Liner, der eine ziemlich lange Linie zulässt:
%Vor%oder besser lesbar:
%Vor%Dabei ist s die zu analysierende Zeichenfolge. Die Menge der Sammlungsfunktionen ist reicher, nicht so mühsam, von Array zu List oder Vector umzurechnen, weil eine bequeme Funktion hier nur definiert ist, die andere nur dort. Fließende Konvertierung von int zu Integer im Hintergrund.