Ich wurde in einem Interview gebeten, das folgende Szenario zu programmieren
Ein Fernseher hat 0-450 Kanäle, aber die Fernbedienungstasten 2,5,8,9 haben eine Fehlfunktion, also schreiben Sie ein Programm, um eine Eingabe vom Benutzer zu erhalten und diesen Kanal über den kürzesten Weg zu durchlaufen
BEISPIEL:
47 - & gt; es ist nicht notwendig, den Knopf 4,7 zu durchlaufen, ist verfügbar
45 - & gt; 44 + 1 Ausgabe von welchem Kanal zu durchlaufen und wie viele durchlaufen erforderlich, um 45 zu erreichen.
55 - & gt; 55 kann von 47 erreicht werden nur coz 54 hat 5. ||| ly (50-55) hat 5 In ihm haben also wieder 48 und 49 jeweils 8 und 9.
Ich habe meine Logik versucht, aber nicht einmal in der Lage, so zu programmieren, dass es der kürzeste Weg für alle Eingaben ist. Bitte helfen Sie mir bei der Logik oder zeigen Sie mir das Programm.
Denken Sie anders. Eine gültige Lösung kann nur durch gültige Ziffern gebildet werden.
0,1,3,4,6,7
Generieren Sie zwei Zahlen, die der Kanalnummer auf beiden Seiten am nächsten sind, nur mit gültigen Schaltflächen.
Zum Beispiel: Kanalnummer = 189
Alle Ziffern auf der rechten Seite der ersten ungültigen Ziffer ausblenden - & gt; 18x
Obere Grenze: Suchen Sie nach einer etwas größeren Ziffer von 8 aus dem gültigen Satz, aber nicht gefunden. In diesem Fall suchen wir nach einer größeren gültigen Ziffer von 1, wir erhalten 3. Dann packen Sie die kleinste gültige Ziffer für den Rest. Wir bekommen 300.
Untere Grenze: Suchen Sie nach einer etwas kleineren Ziffer von 8 aus der gültigen Menge, wir erhalten 7. Dann packen Sie die größte gültige Ziffer für den Rest. Wir bekommen 177.
Berücksichtigen Sie den Grenzfall, wenn die untere oder obere Grenze nicht gebildet werden kann (die Kanalnummer 450 sollte 0 als gültige Lösung erhalten) und außerhalb der oberen Grenze liegen
Vergleichen Sie die beiden Zahlen mit der Kanalnummer und erhalten Sie die nächste.
Formatieren und ausgeben
Zeitkomplexität: O (log (n)) für alle Fälle
Für eine TV-Fernbedienung können wir einige Annahmen machen:
Ausgehend von diesen Annahmen, um den Kanal mit den wenigsten Schritten in beide Richtungen zu finden:
%Vor% Die Methoden StepsForward und StepsBackward zählen einfach, bis wir ein gültiges Ergebnis erhalten. Beachten Sie nur die oberen und unteren Grenzen (0 und 450 in Ihrem Beispiel):
Die Validierung sieht dann nur aus, ob die zu testende Zahl ungültige Zeichen enthält:
%Vor% Das funktioniert wie erwartet, glaube ich.
Es kann weiter optimiert werden, ist aber das Beste, was ich jetzt tun kann.
Die Formatierung ist wegen der Eckfälle notwendig, wenn der Benutzertyp 8 oder 9 oder 89..99 verwendet, in diesen Fällen gibt es eine Änderung der Dezimalstellen und das ist der einzige Weg, den ich gefunden habe, um es zu beheben.