2023-11-15：用 go 语言，如果一个正方形矩阵上下对称并且左右对称，对称的意思是互为镜像，那么称这个正方形矩阵叫做神奇矩阵，比如 : 1 5 5 1 6 3 3 6 6 3 3 6 1 5

作者：福大大架构师每日一题

2023-11-15
北京
本文字数：1834 字
阅读完需：约 6 分钟

2023-11-15：用 go 语言，如果一个正方形矩阵上下对称并且左右对称，对称的意思是互为镜像，

那么称这个正方形矩阵叫做神奇矩阵，

比如 :

1 5 5 1

6 3 3 6

1 5 5 1

这个正方形矩阵就是神奇矩阵。

给定一个大矩阵 n*m，返回其中神奇矩阵的数目。

1 <= n,m <= 1000。

来自左程云。

答案 2023-11-15：

go 代码用灵捷 3.5 编写。

大体过程如下：

1.定义常量 MAXN 为 1001，定义常量 baser 为 491，定义常量 basec 为 499。

2.定义数组 powr 和 powc，分别计算 baser 和 basec 的幂次，用于后续计算哈希值。

3.定义数组 arr1、arr2、arr3，分别存储原数组、上下对称数组、左右对称数组。

4.定义数组 sum1、sum2、sum3，分别存储三个数组的前缀哈希和。

5.通过循环读取输入的 n、m 和矩阵元素，并顺便把元素存入 arr1、arr2、arr3 对应位置。

6.构建 arr1、arr2、arr3 的前缀哈希和，存入 sum1、sum2、sum3 中。

7.定义函数 hash，用于计算矩阵中(a,b)到(c,d)范围内的哈希值。

8.定义函数 ok，用于判断以(a,b)到(c,d)范围内的正方形是否为神奇矩阵。

9.定义函数 number，用于统计大矩阵中神奇矩阵的数量。分别计算奇数长度和偶数长度的正方形数量，返回总数量。

10.在主函数中调用上述各个函数，输出最终结果。

11.总时间复杂度为 $O (n^{2} * l o g n)$ ，总额外空间复杂度为 $O (n^{2})$ 。

go 完整代码如下：

package main
import (  "fmt")
const MAXN int = 1001const baser int = 491const basec int = 499
var powr [MAXN]int64var powc [MAXN]int64var arr1 [MAXN][MAXN]intvar arr2 [MAXN][MAXN]intvar arr3 [MAXN][MAXN]intvar sum1 [MAXN][MAXN]int64var sum2 [MAXN][MAXN]int64var sum3 [MAXN][MAXN]int64var n intvar m int
func init() {  powr[0] = 1  powc[0] = 1  for i := 1; i < MAXN; i++ {    powr[i] = powr[i-1] * int64(baser)  }  for i := 1; i < MAXN; i++ {    powc[i] = powc[i-1] * int64(basec)  }}
func buildHash(arr *[MAXN][MAXN]int, sum *[MAXN][MAXN]int64) {  for i := 1; i <= n; i++ {    for j := 1; j <= m; j++ {      sum[i][j] = sum[i][j-1]*int64(basec) + int64(arr[i][j])    }  }  for i := 1; i <= n; i++ {    for j := 1; j <= m; j++ {      sum[i][j] += sum[i-1][j] * int64(baser)    }  }}
func hash(sum *[MAXN][MAXN]int64, a int, b int, c int, d int) int64 {  ans := sum[c][d] - sum[a-1][d]*powr[c-a+1] - sum[c][b-1]*powc[d-b+1] + sum[a-1][b-1]*powr[d-b+1]*powc[c-a+1]  return ans}
func number() int {  ans := 0  // 奇数长度，实点做中心  for i := 1; i <= n; i++ {    for j := 1; j <= m; j++ {      l := 1      r := min(min(i, n-i+1), min(j, m-j+1))      find := 1      var m int      for l <= r {        m = (l + r) / 2        if ok(i-m+1, j-m+1, i+m-1, j+m-1) {          find = m          l = m + 1        } else {          r = m - 1        }      }      ans += find    }  }  // 偶数长度  // 虚点做中心  for i := 1; i < n; i++ {    for j := 1; j < m; j++ {      // 左上角点为代表      l := 1      r := min(min(i, j), min(n-i, m-j))      find := 0      var m int      for l <= r {        m = (l + r) / 2        if ok(i-m+1, j-m+1, i+m, j+m) {          find = m          l = m + 1        } else {          r = m - 1        }      }      ans += find    }  }  return ans}
func ok(a int, b int, c int, d int) bool {  if a == c {    return true  }  h1 := hash(&sum1, a, b, c, d)  h2 := hash(&sum2, n-c+1, b, n-a+1, d)  h3 := hash(&sum3, a, m-d+1, c, m-b+1)  return h1 == h2 && h1 == h3}
func min(x int, y int) int {  if x < y {    return x  }  return y}
func main() {  inputs := []int{5, 5,    4, 2, 4, 4, 4,    3, 1, 4, 4, 3,    3, 5, 3, 3, 3,    3, 1, 5, 3, 3,    4, 2, 1, 2, 4}  ii := 0
  n = inputs[ii]  ii++  m = inputs[ii]  ii++  for i := 1; i <= n; i++ {    for j := 1; j <= m; j++ {      arr1[i][j] = inputs[ii]      ii++      arr2[n-i+1][j] = arr1[i][j]      arr3[i][m-j+1] = arr1[i][j]    }  }  buildHash(&arr1, &sum1)  buildHash(&arr2, &sum2)  buildHash(&arr3, &sum3)  fmt.Println(number())
}