在本文中，我们将解决 perl weekly challenge #288 中的两项任务：找到最接近的回文并确定矩阵中最大连续块的大小。这两种解决方案都将在 perl 和 go 中递归实现。
目录
- 最近的回文
- 连续块
- 结论
最近的回文
第一个任务是找到最接近的不包含自身的回文。
最接近的回文被定义为最小化两个整数之间的绝对差的回文。
如果有多个候选者，则应返回最小的一个。
任务描述
输入： 字符串 $str，代表整数。
输出： 最接近的回文字符串。
示例
输入：“123”
输出：“121”输入： "2"
输出：“1”
有两个最接近的回文：“1”和“3”。因此，我们返回最小的“1”。输入：“1400”
输出：“1441”输入：“1001”
输出：“999”
解决方案
perl 实现
在此实现中，我们利用递归方法来查找不等于原始数字的最接近的回文。递归函数探索原始数字的下限和上限：
- 它检查当前候选（下级和上级）是否是有效的回文（并且不等于原始）。
- 如果两个候选都无效，该函数会递归地递减较低的候选并递增较高的候选，直到找到有效的回文。
这种递归策略有效地缩小了搜索空间，确保我们在遵守问题约束的同时识别最接近的回文。
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);
}
实施
go 实现遵循类似的递归策略。它还检查原始数字周围的候选数，使用递归来调整边界，直到找到有效的回文数。
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 连续块:
连续块
第二个任务是确定给定矩阵中最大连续块的大小，其中所有单元格都包含 x 或 o。
连续块由包含相同符号的元素组成，这些元素与块中的其他元素共享边缘（而不仅仅是角），从而创建一个连接区域。
任务描述
输入： 包含 x 和 o 的矩形矩阵。
输出：最大连续块的大小。
示例
-
输入：
[ ['x', 'x', 'x', 'x', 'o'], ['x', 'o', 'o', 'o', 'o'], ['x', 'o', 'o', 'o', 'o'], ['x', 'x', 'x', 'o', 'o'], ]
输出： 11
有一个包含 x 的 9 个连续单元格的块和一个包含 o 的 11 个连续单元格的块。
-
输入：
[ ['x', 'x', 'x', 'x', 'x'], ['x', 'o', 'o', 'o', 'o'], ['x', 'x', 'x', 'x', 'o'], ['x', 'o', 'o', 'o', 'o'], ]
输出： 11
有一个包含 x 的 11 个连续单元格的块和一个包含 o 的 9 个连续单元格的块。
-
输入：
[ ['x', 'x', 'x', 'o', 'o'], ['o', 'o', 'o', 'x', 'x'], ['o', 'x', 'x', 'o', 'o'], ['o', 'o', 'o', 'x', 'x'], ]
输出： 7
有一个包含 o 的 7 个连续单元格块、另外两个包含 o 的 2 单元格块、三个包含 x 的 2 单元格块和一个包含 x 的 3 单元格块。
解决方案
perl 实现
在此实现中，我们利用递归深度优先搜索（dfs）方法来确定矩阵中最大连续块的大小。主函数初始化一个访问矩阵来跟踪哪些单元已被探索。它迭代每个单元格，每当遇到未访问的单元格时调用递归 dfs 函数。
dfs 函数探索当前单元格的所有四个可能的方向（上、下、左、右）。它通过在共享相同符号且尚未被访问的相邻单元上递归地调用自身来计算连续块的大小。这种递归方法有效地聚合了块的大小，同时确保每个单元仅被计数一次。
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;
}
实施
go 实现反映了这种递归 dfs 策略。它类似地遍历矩阵并使用递归来探索具有相同符号的连续单元格。
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
}
结论
在本文中，我们探讨了 perl weekly challenge #288 中的两个有趣的挑战：找到最接近的回文并确定矩阵中最大连续块的大小。
对于第一个任务，perl 和 go 实现都有效地利用递归来导航原始数字，确保有效地找到最接近的回文。
在第二个任务中，两种语言的递归深度优先搜索方法可以对矩阵进行彻底探索，从而准确计数最大连续的相同符号块。
这些挑战凸显了递归作为解决算法问题的强大工具的多功能性，展示了它在 perl 和 go 中的有效性。如果您有兴趣进一步探索或有任何疑问，请随时联系！
您可以在 github 上找到完整的代码，包括测试。
