Hammerlisten

Wöchentliche Herausforderung 301

Jede Woche verschickt Mohammad S. Anwar die Weekly Challenge, eine Chance für uns alle, Lösungen für zwei wöchentliche Aufgaben zu finden. Meine Lösungen werden zunächst in Python geschrieben und dann in Perl konvertiert. Es ist eine großartige Möglichkeit für uns alle, etwas Codierung zu üben.

Herausforderung, meine Lösungen

Aufgabe 1: Größte Zahl

Aufgabe

Sie erhalten eine Liste positiver Ganzzahlen, @ints.

Schreiben Sie ein Skript, um alle Elemente in der angegebenen Liste so anzuordnen, dass sie die größte Zahl bilden, und geben Sie diese zurück.

Meine Lösung

Vielleicht überdenke ich es, aber das ist nicht so einfach, wie es sich anhört.

Eine Möglichkeit wäre, alle Permutationen zu berechnen und zu sehen, welche Zahl am größten ist. Dies wird jedoch ressourcenintensiv, je mehr Ganzzahlen wir hinzufügen. Wenn ich dreizehn ganze Zahlen hätte, gäbe es über 6 Milliarden Permutationen. Daher schließe ich dies als mögliche Lösung aus.

Also liegt es nahe, die Ganzzahlen zu sortieren, zu kombinieren und das Ergebnis auszugeben. Da Python Strings und Integer-Zahlen unterschiedlich behandelt, muss ich die sortierte Liste in Strings umwandeln, diese verknüpfen und wieder in eine Integer-Zahl umwandeln.

def largest_number(ints: list) -> int:
    sorted_ints = sorted(ints, key=cmp_to_key(number_sort), reverse=True)
    return int(''.join(map(str, sorted_ints)))

Beim Sortieren ist das etwas kompliziert. Im zweiten bereitgestellten Beispiel können wir sehen, dass 3, 30 und 34 alle gegebene ganze Zahlen sind. Dabei weiß ich, dass man die größte Zahl erhält, wenn man die Artikel (von der höchsten zur niedrigsten) 34, 3 und 30 bestellt.

Für meine Funktion „number_sort“ konvertiere ich die Ganzzahlen in Zeichenfolgen, s1 und s2. Ich habe dann die ganze Zahl c1, die die Verkettung von s1 und s2 ist, während c2 die Verkettung von s2 und s1 ist.

Wenn c1 kleiner als c2 ist, gebe ich -1 zurück. Wenn sie größer ist, gebe ich 1 zurück. Wenn sie gleich sind, gebe ich 0 zurück. Die Sortierfunktion verwendet diese Informationen, um die Liste nach Bedarf zu sortieren.

def number_sort(i1: int, i2: int) -> int:
    s1 = str(i1)
    s2 = str(i2)

    c1 = int(s1 + s2)
    c2 = int(s2 + s1)

    if c1 < c2:
        return -1
    if c1 > c2:
        return 1

    return 0

Der Perl-Code ist viel einfacher :)

sub number_sort() {
    return "$a$b" <=> "$b$a";
}

Beispiele

$ ./ch-1.py 20 3
320

$ ./ch-1.py 3 30 34 5 9
9534330

Aufgabe 2: Hamming-Distanz

Aufgabe

Sie erhalten ein Array von Ganzzahlen, @ints.

Schreiben Sie ein Skript, um die Summe der Hamming-Abstände zwischen allen Ganzzahlpaaren im angegebenen Array von Ganzzahlen zurückzugeben.

Der Hamming-Abstand zwischen zwei ganzen Zahlen ist die Anzahl der Stellen, an denen sich ihre binären Darstellungen unterscheiden.

Meine Lösung

In der vorherigen Aufgabe habe ich erwähnt, wie Python ganze Zahlen und Zeichenfolgen als unterschiedliche Typen behandelt. Einer der Vorteile von Perl besteht darin, dass uns gesagt wird, dass wir uns praktisch keine Gedanken über die Typisierung von Variablen machen müssen. Auch wenn sie intern unterschiedlich gespeichert sind, weiß Perl, was zu tun ist.

In Perl 5.10 und Perl 5.16 (wo ich den Großteil meiner Perl-Entwicklung durchgeführt habe) gibt es zwei bemerkenswerte Ausnahmen. Eines ist das JSON-Modul, das „10“ für eine Zeichenfolge und 10 für eine Ganzzahl ausgibt.

Das andere sind bitweise Operationen. Von der Perlop-Seite, 105 | 150 (zwei ganze Zahlen) ist 255, während „105“ | „150“ (zwei Zeichenfolgen) ist 155.

Deshalb war ich angenehm überrascht, als ich die Perlop-Seite noch einmal las und sah, dass dies in einer späteren Version von Perl behoben wurde. Es verfügt jetzt über die bitweise Funktion, die in Perl 5.22 experimentell und in Perl 5.28 verfügbar ist. Dadurch wird sichergestellt, dass bitweise Operatoren die Werte immer als Ganzzahl behandeln und stringbasierte bitweise Operatoren über neue Operatoren verfügen.

Wie auch immer, zurück zur eigentlichen Aufgabe. Dazu berechne ich alle Kombinationen zweier Ganzzahlen. Für jede Kombination führe ich eine XOR-Verknüpfung (exklusives Oder) der beiden Werte durch, konvertiere sie in Binärwerte und zähle die Anzahl der Einsen in der Binärdarstellung.

def largest_number(ints: list) -> int:
    sorted_ints = sorted(ints, key=cmp_to_key(number_sort), reverse=True)
    return int(''.join(map(str, sorted_ints)))

Beispiele

def number_sort(i1: int, i2: int) -> int:
    s1 = str(i1)
    s2 = str(i2)

    c1 = int(s1 + s2)
    c2 = int(s2 + s1)

    if c1 < c2:
        return -1
    if c1 > c2:
        return 1

    return 0

Das obige ist der detaillierte Inhalt vonHammerlisten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!