第四十九天

算法: 最长回文子串?

在Go语言中，可以使用多种方法实现查找字符串中的最长回文子串。这里提供两种常见的算法实现，分别是动态规划法和Manacher’s Algorithm（马拉车算法）。

1. 动态规划法：

   package main
   
   import (
       "fmt"
   )
   
   func longestPalindrome(s string) string {
       if len(s) < 2 {
           return s
       }
   
       maxLen := 1
       start := 0
       dp := make([][]bool, len(s))
       for i := range dp {
           dp[i] = make([]bool, len(s))
       }
   
       // 初始化边界
       for i := range dp {
           dp[i][i] = true
       }
   
       // 动态规划填充二维数组dp
       for l := 2; l <= len(s); l++ {
           for i := 0; i+l-1 < len(s); i++ {
               j := i + l - 1
               if s[i] == s[j] {
                   if l == 2 {
                       dp[i][j] = true
                   } else {
                       dp[i][j] = dp[i+1][j-1]
                   }
                   if dp[i][j] && l > maxLen {
                       start = i
                       maxLen = l
                   }
               } else {
                   dp[i][j] = false
               }
           }
       }
   
       return s[start : start+maxLen]
   }
   
   func main() {
       input := "babad"
       fmt.Println(longestPalindrome(input)) // 输出: "bab"
   }

2. Manacher’s Algorithm：
   Manacher’s Algorithm可以在线性时间内找到最长回文子串，适用于处理较长的字符串，但实现较为复杂。以下是简化版的Manacher’s Algorithm的Go实现：

   package main
   
   import (
       "fmt"
   )
   
   func preprocess(s string) string {
       t := "$#"
       for _, c := range s {
           t += string(c) + "#"
       }
       return t
   }
   
   func longestPalindromicSubstring(s string) string {
       t := preprocess(s)
       P := make([]int, len(t))
       C, R, MaxLen, Center := 0, -1, 0, -1
       for i := 0; i < len(t); i++ {
           mirror := 2*C - i
           if i < R {
               P[i] = min(R - i, P[mirror])
           }
           left, right := i - P[i], i + P[i] + 1
           for left >= 0 && right < len(t) && t[left] == t[right] {
               P[i]++
               left--
               right++
           }
           if i + P[i] > R {
               C, R = i, i + P[i]
           }
           if MaxLen < P[i] {
               MaxLen = P[i]
               Center = i
           }
       }
       start := (Center - MaxLen) / 2
       return s[start : start+MaxLen]
   }
   
   func min(a, b int) int {
       if a < b {
           return a
       }
       return b
   }
   
   func main() {
       input := "babad"
       fmt.Println(longestPalindromicSubstring(input)) // 输出: "bab"
   }

协程池的作用?

Go语言中的协程池（goroutine pool）是用来管理和复用协程（goroutine）的一种设计模式，其作用主要包括以下几个方面：

1. 资源控制：
   协程池可以限制并发执行的协程数量，避免在处理大量并发任务时创建过多的协程，从而消耗过多的系统资源，如内存和CPU。通过设置池的最大容量，可以避免因频繁创建和销毁协程而导致的系统开销过大。

2. 任务调度：
   协程池可以对提交的任务进行排队和调度，确保资源被有效利用。当池中有空闲的协程时，它可以立即执行新的任务；反之，当池满时，新任务将会等待，直到有协程完成工作并返回到池中。

3. 并发效率：
   通过复用已经创建好的协程，协程池可以显著提高系统的并发执行效率，特别是在处理大量IO-bound任务（如网络请求、文件读写等）时，协程池能够更好地利用系统的并发能力，提高系统的吞吐量。

4. 系统稳定性：
   通过约束并发协程的数量，可以避免因过多并发导致系统不稳定，如资源耗尽、系统负载过高等问题。

5. 易于管理和监控：
   协程池提供了统一的任务管理和控制接口，方便开发者跟踪任务执行状态、设置超时、限制并发数、优雅地关闭协程池等功能，有助于提升程序的可控性和健壮性。