首页 > Golang > Go教程

深入研究：回文和连续块的递归解决方案

来源：dev.to

时间：2024-09-29 19:06:58 439浏览收藏

本篇文章向大家介绍《深入研究：回文和连续块的递归解决方案》，主要包括，具有一定的参考价值，需要的朋友可以参考一下。

深入研究：回文和连续块的递归解决方案

在本文中，我们将解决 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
}