Dans cet article, nous aborderons deux tâches du Perl Weekly Challenge #288 : trouver le palindrome le plus proche et déterminer la taille du plus grand bloc contigu dans une matrice. Les deux solutions seront implémentées de manière récursive en Perl et Go.
La première tâche est de trouver le palindrome le plus proche qui ne s'inclut pas.
Le palindrome le plus proche est défini comme celui qui minimise la différence absolue entre deux entiers.
S'il y a plusieurs candidats, le plus petit doit être renvoyé.
Entrée : Une chaîne, $str, qui représente un entier.
Sortie : Le palindrome le plus proche sous forme de chaîne.
Entrée : "123"
Sortie : "121"
Entrée : "2"
Sortie : "1"
Il existe deux palindromes les plus proches : « 1 » et « 3 ». Par conséquent, nous renvoyons le plus petit "1".
Entrée : "1400"
Sortie : "1441"
Entrée : "1001"
Sortie : "999"
Dans cette implémentation, nous utilisons une approche récursive pour trouver le palindrome le plus proche qui n'est pas égal au nombre d'origine. La fonction récursive explore à la fois les limites inférieures et supérieures autour du nombre d'origine :
Cette stratégie récursive réduit efficacement l'espace de recherche, garantissant que nous identifions le palindrome le plus proche tout en respectant les contraintes du problème.
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);
}
L'implémentation Go suit une stratégie récursive similaire. Il vérifie également les candidats autour du numéro d'origine, en utilisant la récursivité pour ajuster les limites jusqu'à ce qu'un palindrome valide soit trouvé.
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 Bloc contigu :
La deuxième tâche consiste à déterminer la taille du plus grand bloc contigu dans une matrice donnée, où toutes les cellules contiennent x ou o.
Un bloc contigu se compose d'éléments contenant le même symbole qui partagent un bord (pas seulement un coin) avec d'autres éléments du bloc, créant ainsi une zone connectée.
Entrée : Une matrice rectangulaire contenant x et o.
Sortie : La taille du plus grand bloc contigu.
Entrée :
[
['x', 'x', 'x', 'x', 'o'],
['x', 'o', 'o', 'o', 'o'],
['x', 'o', 'o', 'o', 'o'],
['x', 'x', 'x', 'o', 'o'],
]
Sortie : 11
Il existe un bloc de 9 cellules contiguës contenant x et un bloc de 11 cellules contiguës contenant o.
Entrée :
[
['x', 'x', 'x', 'x', 'x'],
['x', 'o', 'o', 'o', 'o'],
['x', 'x', 'x', 'x', 'o'],
['x', 'o', 'o', 'o', 'o'],
]
Sortie : 11
Il existe un bloc de 11 cellules contiguës contenant x et un bloc de 9 cellules contiguës contenant o.
Entrée :
[
['x', 'x', 'x', 'o', 'o'],
['o', 'o', 'o', 'x', 'x'],
['o', 'x', 'x', 'o', 'o'],
['o', 'o', 'o', 'x', 'x'],
]
Sortie :7
Il y a un bloc de 7 cellules contiguës contenant o, deux autres blocs de 2 cellules de o, trois blocs de 2 cellules de x et un bloc de 3 cellules de x.
Dans cette implémentation, nous utilisons une approche de recherche récursive en profondeur d'abord (DFS) pour déterminer la taille du plus grand bloc contigu dans une matrice. La fonction principale initialise une matrice visitée pour suivre quelles cellules ont été explorées. Il parcourt chaque cellule, appelant la fonction récursive DFS chaque fois qu'il rencontre une cellule non visitée.
La fonction DFS explore les quatre directions possibles (haut, bas, gauche, droite) à partir de la cellule actuelle. Il compte la taille du bloc contigu en s'appelant récursivement les cellules voisines partageant le même symbole et n'ayant pas été visitées. Cette méthode récursive agrège efficacement la taille du bloc tout en garantissant que chaque cellule n'est comptée qu'une seule fois.
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 < 0 || $row >= @$matrix || $col < 0 || $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;
}
L'implémentation Go reflète cette stratégie DFS récursive. De la même manière, il parcourt la matrice et utilise la récursivité pour explorer les cellules contiguës portant le même symbole.
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 < rows; r++ {
for c := 0; c < cols; c++ {
symbol := matrix[r][c]
size := dfs(matrix, visited, r, c, symbol)
if size > maxSize {
maxSize = size
}
}
}
return maxSize
}
func dfs(matrix [][]rune, visited [][]bool, row, col int, symbol rune) int {
if row < 0 || row >= len(matrix) || col < 0 || 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
}
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.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Comment utiliser la fonction de tri
Qu'est-ce que CONNECTION_REFUSED ?
Huobi.com
Introduction aux touches de raccourci de capture d'écran dans Win10
Le jeton de connexion n'est pas valide
Introduction au code d'effets spéciaux javascript
Solution à l'échec de la mise à jour WIN10
Commandes communes OGG
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
