深入研究：回文和連續區塊的遞歸解決方案

在本文中，我們將解決 Perl 每週挑戰 #288 中的兩個任務：找到最接近的回文並確定矩陣中最大連續區塊的大小。這兩種解決方案都將在 Perl 和 Go 中遞歸實作。

目錄

1. 最近的回文
2. 連續塊
3. 結論

最近的回文

第一個任務是找到最接近的不包含自身的回文。

最接近的回文定義為最小化兩個整數之間的絕對差的回文。

如果有多個候選者，則應傳回最小的一個。

任務說明

輸入： 字串 $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 = @$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;
}

實施

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  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.

以上是深入研究：回文和連續區塊的遞歸解決方案的詳細內容。更多資訊請關注PHP中文網其他相關文章！