Tief tauchen: Rekursive Lösungen für Palindrome und zusammenhängende Blöcke

In diesem Artikel werden wir zwei Aufgaben aus der Perl Weekly Challenge #288 angehen: das nächstgelegene Palindrom finden und die Größe des größten zusammenhängenden Blocks in einer Matrix bestimmen. Beide Lösungen werden rekursiv in Perl und Go implementiert.

Inhaltsverzeichnis

1. Nächstgelegenes Palindrom
2. Zusammenhängender Block
3. Fazit

Nächstes Palindrom

Die erste Aufgabe besteht darin, das nächstgelegene Palindrom zu finden, das sich selbst nicht einschließt.

Das nächstgelegene Palindrom ist dasjenige, das die absolute Differenz zwischen zwei ganzen Zahlen minimiert.

Wenn es mehrere Kandidaten gibt, sollte der kleinste zurückgegeben werden.

Aufgabenbeschreibung

Eingabe: Eine Zeichenfolge, $str, die eine Ganzzahl darstellt.

Ausgabe: Das nächstgelegene Palindrom als String.

Beispiele

• Eingabe: „123“
  Ausgabe: „121“

• Eingabe: „2“
  Ausgabe: „1“
  Es gibt zwei nächstliegende Palindrome: „1“ und „3“. Daher geben wir die kleinste „1“ zurück.

• Eingabe: „1400“
  Ausgabe: „1441“

• Eingabe: „1001“
  Ausgabe: „999“

Lösung

Perl-Implementierung

In dieser Implementierung verwenden wir einen rekursiven Ansatz, um das nächstgelegene Palindrom zu finden, das nicht der ursprünglichen Zahl entspricht. Die rekursive Funktion untersucht sowohl die Unter- als auch die Obergrenze um die ursprüngliche Zahl:

• Es prüft, ob die aktuellen Kandidaten (untere und obere) gültige Palindrome sind (und nicht mit dem Original übereinstimmen).
• Wenn keiner der Kandidaten gültig ist, dekrementiert die Funktion rekursiv den unteren Kandidaten und erhöht den oberen Kandidaten, bis sie ein gültiges Palindrom findet.

Diese rekursive Strategie schränkt den Suchraum effektiv ein und stellt sicher, dass wir das nächstgelegene Palindrom identifizieren und gleichzeitig die Einschränkungen des Problems einhalten.

sub is_palindrome {
    my ($num) = @_;
    return $num eq reverse($num);
}

sub find_closest {
    my ($lower, $upper, $original) = @_;
    return $lower if is_palindrome($lower) && $lower != $original;
    return $upper if is_palindrome($upper) && $upper != $original;
    return find_closest($lower - 1, $upper + 1, $original) if $lower > 0;
    return $upper + 1;
}

sub closest_palindrome {
    my ($str) = @_;
    my $num = int($str);
    return find_closest($num - 1, $num + 1, $num);
}

Gehen Sie zur Implementierung

Die Go-Implementierung folgt einer ähnlichen rekursiven Strategie. Es überprüft auch die Kandidaten um die ursprüngliche Zahl herum und verwendet Rekursion, um die Grenzen anzupassen, bis ein gültiges Palindrom gefunden wird.

package main

import (
    "strconv"
)

func isPalindrome(num int) bool {
    reversed := 0
    original := num

    for num > 0 {
        digit := num % 10
        reversed = reversed*10 + digit
        num /= 10
    }

    return original == reversed
}

func findClosest(lower, upper, original int) string {
    switch {
        case isPalindrome(lower) && lower != original:
            return strconv.Itoa(lower)
        case isPalindrome(upper) && upper != original:
            return strconv.Itoa(upper)
        case lower > 0:
            return findClosest(lower-1, upper+1, original)
        default:
            return strconv.Itoa(upper + 1)
    }
}

func closestPalindrome(str string) string {
    num, _ := strconv.Atoi(str)
    return findClosest(num-1, num+1, num)
}

Hier ist die erweiterte Definition für den Contiguous Block:

Angrenzender Block

Die zweite Aufgabe besteht darin, die Größe des größten zusammenhängenden Blocks in einer bestimmten Matrix zu bestimmen, in der alle Zellen entweder x oder o enthalten.

Ein zusammenhängender Block besteht aus Elementen, die dasselbe Symbol enthalten und eine Kante (nicht nur eine Ecke) mit anderen Elementen im Block teilen, wodurch ein verbundener Bereich entsteht.

Aufgabenbeschreibung

Eingabe: Eine rechteckige Matrix, die x und o enthält.

Ausgabe: Die Größe des größten zusammenhängenden Blocks.

Beispiele

• Eingabe:
  

  [
      ['x', 'x', 'x', 'x', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'x', 'x', 'o', 'o'],
  ]
  

Ausgabe: 11
Es gibt einen Block aus 9 zusammenhängenden Zellen mit x und einen Block aus 11 zusammenhängenden Zellen mit o.

• Eingabe:
  

  [
      ['x', 'x', 'x', 'x', 'x'],
      ['x', 'o', 'o', 'o', 'o'],
      ['x', 'x', 'x', 'x', 'o'],
      ['x', 'o', 'o', 'o', 'o'],
  ]
  

Ausgabe: 11
Es gibt einen Block aus 11 zusammenhängenden Zellen mit x und einen Block aus 9 zusammenhängenden Zellen mit o.

• Eingabe:
  

  [
      ['x', 'x', 'x', 'o', 'o'],
      ['o', 'o', 'o', 'x', 'x'],
      ['o', 'x', 'x', 'o', 'o'],
      ['o', 'o', 'o', 'x', 'x'],
  ]
  

Ausgabe: 7
Es gibt einen Block aus 7 zusammenhängenden Zellen, die o enthalten, zwei weitere 2-Zellen-Blöcke von o, drei 2-Zellen-Blöcke von x und einen 3-Zellen-Block von x.

Lösung

Perl-Implementierung

In dieser Implementierung verwenden wir einen rekursiven Tiefensuchansatz (DFS), um die Größe des größten zusammenhängenden Blocks in einer Matrix zu bestimmen. Die Hauptfunktion initialisiert eine besuchte Matrix, um zu verfolgen, welche Zellen untersucht wurden. Es durchläuft jede Zelle und ruft die rekursive DFS-Funktion auf, wann immer es auf eine nicht besuchte Zelle trifft.

Die DFS-Funktion untersucht alle vier möglichen Richtungen (oben, unten, links, rechts) von der aktuellen Zelle aus. Es zählt die Größe des zusammenhängenden Blocks, indem es sich rekursiv auf benachbarte Zellen aufruft, die dasselbe Symbol haben und nicht besucht wurden. Diese rekursive Methode aggregiert effektiv die Größe des Blocks und stellt gleichzeitig sicher, dass jede Zelle nur einmal gezählt wird.

sub largest_contiguous_block {
    my ($matrix) = @_;
    my $rows = @$matrix;
    my $cols = @{$matrix->[0]};
    my @visited = map { [(0) x $cols] } 1..$rows;

    my $max_size = 0;

    for my $r (0 .. $rows - 1) {
        for my $c (0 .. $cols - 1) {
            my $symbol = $matrix->[$r][$c];
            my $size = dfs($matrix, \@visited, $r, $c, $symbol);
            $max_size = $size if $size > $max_size;
        }
    }

    return $max_size;
}

sub dfs {
    my ($matrix, $visited, $row, $col, $symbol) = @_;

    return 0 if $row = @$matrix || $col = @{$matrix->[0]}
                || $visited->[$row][$col] || $matrix->[$row][$col] ne $symbol;

    $visited->[$row][$col] = 1;
    my $count = 1;

    $count += dfs($matrix, $visited, $row + 1, $col, $symbol);
    $count += dfs($matrix, $visited, $row - 1, $col, $symbol);
    $count += dfs($matrix, $visited, $row, $col + 1, $symbol);
    $count += dfs($matrix, $visited, $row, $col - 1, $symbol);

    return $count;
}

Gehen Sie zur Implementierung

Die Go-Implementierung spiegelt diese rekursive DFS-Strategie wider. Es durchläuft auf ähnliche Weise die Matrix und verwendet Rekursion, um zusammenhängende Zellen mit demselben Symbol zu untersuchen.

package main

func largestContiguousBlock(matrix [][]rune) int {
    rows := len(matrix)
    if rows == 0 {
        return 0
    }
    cols := len(matrix[0])
    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    maxSize := 0

    for r := 0; r  maxSize {
                maxSize = size
            }
        }
    }

    return maxSize
}

func dfs(matrix [][]rune, visited [][]bool, row, col int, symbol rune) int {
    if row = len(matrix) || col = len(matrix[0]) ||
        visited[row][col] || matrix[row][col] != symbol {
        return 0
    }

    visited[row][col] = true
    count := 1

    count += dfs(matrix, visited, row+1, col, symbol)
    count += dfs(matrix, visited, row-1, col, symbol)
    count += dfs(matrix, visited, row, col+1, symbol)
    count += dfs(matrix, visited, row, col-1, symbol)

    return count
}

Conclusion

In this article, we explored two intriguing challenges from the Perl Weekly Challenge #288: finding the closest palindrome and determining the size of the largest contiguous block in a matrix.

For the first task, both the Perl and Go implementations effectively utilized recursion to navigate around the original number, ensuring the closest palindrome was found efficiently.

In the second task, the recursive depth-first search approach in both languages allowed for a thorough exploration of the matrix, resulting in an accurate count of the largest contiguous block of identical symbols.

These challenges highlight the versatility of recursion as a powerful tool in solving algorithmic problems, showcasing its effectiveness in both Perl and Go. If you're interested in further exploration or have any questions, feel free to reach out!

You can find the complete code, including tests, on GitHub.

Das obige ist der detaillierte Inhalt vonTief tauchen: Rekursive Lösungen für Palindrome und zusammenhängende Blöcke. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!