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

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

时间：2023-11-18 20:55:05浏览次数：38  
标签：int mid 矩阵 ++ enlarge 正方形 对称 col row

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

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

比如 :

1 5 5 1

6 3 3 6

6 3 3 6

1 5 5 1

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

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

1 <= n,m <= 1000。

来自左程云。

答案2023-11-18：

go，c++，c的代码用灵捷3.5编写，go和c++有修改。

具体步骤如下：

1.通过输入获取大矩阵的大小n和m。

2.将输入的数据按行列填充到数组arr中。

3.根据行遍历，对每一行调用manacher函数进行回文串的预处理。该函数会在rp数组中保存每个位置向右的回文长度。

4.根据列遍历，对每一列调用manacher函数进行回文串的预处理。该函数会在cp数组中保存每个位置向下的回文长度。

5.遍历所有内部的行和列，计算每个位置上、下、左、右四个方向上的回文长度，并取其最小值作为当前位置的enlarge值。

6.统计enlarge数组中每个奇数行、奇数列位置的值除以2的结果，作为神奇矩阵的数量。

7.统计enlarge数组中每个偶数行、偶数列位置的值减去1后除以2的结果，再累加到神奇矩阵的数量。

8.返回神奇矩阵的数量作为结果。

总的时间复杂度：O(n * m * log(min(n, m)))，其中n为矩阵的行数，m为矩阵的列数。主要耗时的是manacher函数的预处理过程，而manacher函数的时间复杂度为O(log(min(n, m)))。

总的额外空间复杂度：O(n * m)，需要额外的数组保存回文长度。

go完整代码如下：

package main

import (
	"fmt"
)

const MAXN = 1001

var log2 [(MAXN<<1 | 1) + 1]int

var arr [MAXN<<1 | 1][MAXN<<1 | 1]int
var rp [MAXN<<1 | 1][MAXN<<1 | 1]int
var cp [MAXN<<1 | 1][MAXN<<1 | 1]int
var enlarge [MAXN<<1 | 1][MAXN<<1 | 1]int
var rmq [MAXN<<1 | 1][MAXN<<1 | 1]int
var s [MAXN<<1 | 1]int
var p [MAXN<<1 | 1]int
var n, m int

func init() {
	for k, j := 0, 1; j <= (MAXN<<1 | 1); j++ {
		if 1<<(k+1) <= j {
			k++
		}
		log2[j] = k
	}
}

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, r := 0, 1; i < n; i, r = i+1, r+2 {
		for j, c := 0, 1; j < m; j, c = j+1, c+2 {
			arr[r][c] = inputs[ii]
			ii++
		}
	}
	n = n*2 + 1
	m = m*2 + 1
	fmt.Println(number())

}

func number() int {
	for row := 0; row < n; row++ {
		manacher(row, 0, 0, 1)
	}
	for col := 0; col < m; col++ {
		manacher(0, col, 1, 0)
	}
	for row := 1; row < n-1; row++ {
		rowRmq(row)
		for col := 1; col < m-1; col++ {
			l := 1
			r := min(min(row+1, n-row), min(col+1, m-col))
			find := 1
			for l <= r {
				m := (l + r) / 2
				if query(col-m+1, col+m-1) >= m {
					find = m
					l = m + 1
				} else {
					r = m - 1
				}
			}
			enlarge[row][col] = find
		}
	}
	for col := 1; col < m-1; col++ {
		colRmq(col)
		for row := 1; row < n-1; row++ {
			l := 1
			r := min(min(row+1, n-row), min(col+1, m-col))
			find := 1
			for l <= r {
				m := (l + r) / 2
				if query(row-m+1, row+m-1) >= m {
					find = m
					l = m + 1
				} else {
					r = m - 1
				}
			}
			enlarge[row][col] = min(enlarge[row][col], find)
		}
	}
	ans := 0
	for row := 1; row < n-1; row += 2 {
		for col := 1; col < m-1; col += 2 {
			ans += enlarge[row][col] / 2
		}
	}
	for row := 2; row < n-1; row += 2 {
		for col := 2; col < m-1; col += 2 {
			ans += (enlarge[row][col] - 1) / 2
		}
	}
	return ans
}

func manacher(row int, col int, radd int, cadd int) {
	limit := 0
	for r, c := row, col; r < n && c < m; r, c = r+radd, c+cadd {
		s[limit] = arr[r][c]
		limit++
	}
	C := -1
	R := -1
	for i := 0; i < limit; i++ {
		p[i] = R
		if i < R {
			p[i] = min(p[2*C-i], R-i)
		} else {
			p[i] = 1
		}
		for i+p[i] < limit && i-p[i] > -1 && s[i+p[i]] == s[i-p[i]] {
			p[i]++
		}
		if i+p[i] > R {
			R = i + p[i]
			C = i
		}
	}
	var fill *[2003][2003]int
	if cadd == 1 {
		fill = &rp
	} else {
		fill = &cp
	}
	for i, r, c := 0, row, col; i < limit; i++ {
		fill[r][c] = p[i]
		r += radd
		c += cadd
	}
}

func rowRmq(row int) {
	for i := 0; i < m; i++ {
		rmq[i][0] = cp[row][i]
	}
	for j := 1; (1 << j) <= m; j++ {
		for i := 0; i+(1<<j)-1 < m; i++ {
			rmq[i][j] = min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1])
		}
	}
}

func colRmq(col int) {
	for i := 0; i < n; i++ {
		rmq[i][0] = rp[i][col]
	}
	for j := 1; (1 << j) <= n; j++ {
		for i := 0; i+(1<<j)-1 < n; i++ {
			rmq[i][j] = min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1])
		}
	}
}

func query(l int, r int) int {
	k := log2[r-l+1]
	return min(rmq[l][k], rmq[r-(1<<k)+1][k])
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1001;

int log22[(MAXN << 1 | 1) + 1];
int arr[MAXN << 1 | 1][MAXN << 1 | 1];
int rp[MAXN << 1 | 1][MAXN << 1 | 1];
int cp[MAXN << 1 | 1][MAXN << 1 | 1];
int enlarge[MAXN << 1 | 1][MAXN << 1 | 1];
int rmq[MAXN << 1 | 1][MAXN << 1 | 1];
int s[MAXN << 1 | 1];
int p[MAXN << 1 | 1];
int n, m;

void manacher(int row, int col, int radd, int cadd);

int number();

void rowRmq(int row);

void colRmq(int col);

int query(int l, int r);

int min(int a, int b);

void init() {
    for (int k = 0, j = 1; j <= (MAXN << 1 | 1); j++) {
        if (1 << (k + 1) <= j) {
            k++;
        }
        log22[j] = k;
    }
}

int number() {
    for (int row = 0; row < n; row++) {
        manacher(row, 0, 0, 1);
    }
    for (int col = 0; col < m; col++) {
        manacher(0, col, 1, 0);
    }
    for (int row = 1; row < n - 1; row++) {
        rowRmq(row);
        for (int col = 1; col < m - 1; col++) {
            int l = 1;
            int r = min(min(row + 1, n - row), min(col + 1, m - col));
            int find = 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (query(col - mid + 1, col + mid - 1) >= mid) {
                    find = mid;
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            enlarge[row][col] = find;
        }
    }
    for (int col = 1; col < m - 1; col++) {
        colRmq(col);
        for (int row = 1; row < n - 1; row++) {
            int l = 1;
            int r = min(min(row + 1, n - row), min(col + 1, m - col));
            int find = 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (query(row - mid + 1, row + mid - 1) >= mid) {
                    find = mid;
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            enlarge[row][col] = min(enlarge[row][col], find);
        }
    }
    int ans = 0;
    for (int row = 1; row < n - 1; row += 2) {
        for (int col = 1; col < m - 1; col += 2) {
            ans += enlarge[row][col] / 2;
        }
    }
    for (int row = 2; row < n - 1; row += 2) {
        for (int col = 2; col < m - 1; col += 2) {
            ans += (enlarge[row][col] - 1) / 2;
        }
    }
    return ans;
}

void manacher(int row, int col, int radd, int cadd) {
    int limit = 0;
    for (int r = row, c = col; r < n && c < m; r += radd, c += cadd) {
        s[limit] = arr[r][c];
        limit++;
    }
    int C = -1;
    int R = -1;
    for (int i = 0; i < limit; i++) {
        p[i] = R;
        if (i < R) {
            p[i] = min(p[2 * C - i], R - i);
        }
        else {
            p[i] = 1;
        }
        while (i + p[i] < limit && i - p[i] > -1 && s[i + p[i]] == s[i - p[i]]) {
            p[i]++;
        }
        if (i + p[i] > R) {
            R = i + p[i];
            C = i;
        }
    }
    int(*fill)[2003];
    if (cadd == 1) {
        fill = rp;
    }
    else {
        fill = cp;
    }
    for (int i = 0, r = row, c = col; i < limit; i++) {
        fill[r][c] = p[i];
        r += radd;
        c += cadd;
    }
}

void rowRmq(int row) {
    for (int i = 0; i < m; i++) {
        rmq[i][0] = cp[row][i];
    }
    for (int j = 1; (1 << j) <= m; j++) {
        for (int i = 0; i + (1 << j) - 1 < m; i++) {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}

void colRmq(int col) {
    for (int i = 0; i < n; i++) {
        rmq[i][0] = rp[i][col];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r) {
    int k = log22[r - l + 1];
    return min(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}

int min(int a, int b) {
    if (a < b) {
        return a;
    }
    return b;
}

int main() {
    init();
    int inputs[] = { 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 };
    int ii = 0;
    n = inputs[ii++];
    m = inputs[ii++];
    for (int i = 0, r = 1; i < n; i++, r += 2) {
        for (int j = 0, c = 1; j < m; j++, c += 2) {
            arr[r][c] = inputs[ii++];
        }
    }
    n = n * 2 + 1;
    m = m * 2 + 1;
    cout << number() << endl;
    return 0;
}

在这里插入图片描述

c完整代码如下：

#include <stdio.h>

#define MAXN 1001

int log2Arr[(MAXN << 1 | 1) + 1];
int arr[MAXN << 1 | 1][MAXN << 1 | 1];
int rp[MAXN << 1 | 1][MAXN << 1 | 1];
int cp[MAXN << 1 | 1][MAXN << 1 | 1];
int enlarge[MAXN << 1 | 1][MAXN << 1 | 1];
int rmq[MAXN << 1 | 1][MAXN << 1 | 1];
int s[MAXN << 1 | 1];
int p[MAXN << 1 | 1];
int n, m;

void init() {
    int k = 0;
    for (int j = 1; j <= (MAXN << 1 | 1); j++) {
        if (1 << (k + 1) <= j) {
            k++;
        }
        log2Arr[j] = k;
    }
}

int min(int a, int b) {
    return (a < b) ? a : b;
}

void manacher(int row, int col, int radd, int cadd) {
    int limit = 0;
    for (int r = row, c = col; r < n && c < m; r += radd, c += cadd) {
        s[limit] = arr[r][c];
        limit++;
    }

    int C = -1;
    int R = -1;
    for (int i = 0; i < limit; i++) {
        p[i] = R;
        if (i < R) {
            p[i] = min(p[2 * C - i], R - i);
        }
        else {
            p[i] = 1;
        }

        while (i + p[i] < limit && i - p[i] > -1 && s[i + p[i]] == s[i - p[i]]) {
            p[i]++;
        }

        if (i + p[i] > R) {
            R = i + p[i];
            C = i;
        }
    }

    int(*fill)[2003];
    if (cadd == 1) {
        fill = rp;
    }
    else {
        fill = cp;
    }

    for (int i = 0, r = row, c = col; i < limit; i++) {
        fill[r][c] = p[i];
        r += radd;
        c += cadd;
    }
}

void rowRmq(int row) {
    for (int i = 0; i < m; i++) {
        rmq[i][0] = cp[row][i];
    }

    for (int j = 1; (1 << j) <= m; j++) {
        for (int i = 0; i + (1 << j) - 1 < m; i++) {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}

void colRmq(int col) {
    for (int i = 0; i < n; i++) {
        rmq[i][0] = rp[i][col];
    }

    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r) {
    int k = log2Arr[r - l + 1];
    return min(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}

int number() {
    for (int row = 0; row < n; row++) {
        manacher(row, 0, 0, 1);
    }

    for (int col = 0; col < m; col++) {
        manacher(0, col, 1, 0);
    }

    for (int row = 1; row < n - 1; row++) {
        rowRmq(row);
        for (int col = 1; col < m - 1; col++) {
            int l = 1;
            int r = min(min(row + 1, n - row), min(col + 1, m - col));
            int find = 1;

            while (l <= r) {
                int mid = (l + r) / 2;
                if (query(col - mid + 1, col + mid - 1) >= mid) {
                    find = mid;
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }

            enlarge[row][col] = find;
        }
    }

    for (int col = 1; col < m - 1; col++) {
        colRmq(col);
        for (int row = 1; row < n - 1; row++) {
            int l = 1;
            int r = min(min(row + 1, n - row), min(col + 1, m - col));
            int find = 1;

            while (l <= r) {
                int mid = (l + r) / 2;
                if (query(row - mid + 1, row + mid - 1) >= mid) {
                    find = mid;
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }

            enlarge[row][col] = min(enlarge[row][col], find);
        }
    }

    int ans = 0;

    for (int row = 1; row < n - 1; row += 2) {
        for (int col = 1; col < m - 1; col += 2) {
            ans += enlarge[row][col] / 2;
        }
    }

    for (int row = 2; row < n - 1; row += 2) {
        for (int col = 2; col < m - 1; col += 2) {
            ans += (enlarge[row][col] - 1) / 2;
        }
    }

    return ans;
}

int main() {
    init();

    int inputs[] = { 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 };
    int ii = 0;

    n = inputs[ii];
    ii++;
    m = inputs[ii];
    ii++;

    for (int i = 0, r = 1; i < n; i++, r += 2) {
        for (int j = 0, c = 1; j < m; j++, c += 2) {
            arr[r][c] = inputs[ii];
            ii++;
        }
    }

    n = n * 2 + 1;
    m = m * 2 + 1;
    printf("%d\n", number());

    return 0;
}

在这里插入图片描述

标签：int,mid,矩阵,++,enlarge,正方形,对称,col,row
From： https://www.cnblogs.com/moonfdd/p/17841104.html

相关文章

  • echarts修改图例legend样式：正方形、矩形、圆形、圆角
    ECharts提供的标记类型有'circle','rect','roundRect','triangle','diamond','pin','arrow','none'legend:{icon:'circle'}参考文章echarts图例修改legend中icon的形状及大小......
  • es笔记七之聚合操作之桶聚合和矩阵聚合
    本文首发于公众号：Hunter后端原文链接：es笔记七之聚合操作之桶聚合和矩阵聚合桶(bucket)聚合并不像指标(metric)聚合一样在字段上计算，而是会创建数据的桶，我们可以理解为分组，根据某个字段进行分组，将符合条件的数据分到同一个组里。桶聚合可以有子聚合，意思就是在分组之后，可以在每......
  • 矩阵乘法
    一个神奇的东西矩阵乘法重载符实现代码：nodeoperator*(constnode&a)const{nodesum(0);for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)for(intk=1;k<=n;k++)sum.g[i][j]+=g[i][k]*a.g[k][j];r......
  • oracle SQL 实现对数据库的的脱敏和对称加密
    之前的kettleETL太慢了insertintoselect83w数据220skettle83w数据etl3h26w~功能变更耗时另外如果需要再次对其他字段做脱敏时间又比较耗时需要再次编写环节复制表INSERTINTOXXXXSELECT*FROMXXXX_JM;验证数据--源表总数SELECTCOUNT(*)F......
  • 【动态规划】矩阵连乘问题
    问题描述：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。m[i][j] ：i=j时指矩阵Ai ，i<j时指矩阵Ai到矩阵Aj的若干矩阵连乘的最小次数。pi指维数。例： ......
  • 利用 kettle 对 oracle 实现字符串的脱敏和对称加密
    脱敏要求对身份证进行ASE加密处理对手机号只显示前三位和后四位其余使用****代替对于职业只显示前三个字对于真实姓名只显示展示一位即可kettle建立转换表输入表输出ASE加密选择组件密钥转换密钥必须是16进制且大于16个字节配置字段和加密算法......
  • Java非对称加密RSA算法
    简介：公开密钥密码学（英语：Public-keycryptography）也称非对称式密码学（英语：Asymmetriccryptography）是密码学的一种算法。加密与解密使用不同的密钥,其中一个称之为公钥,对外公开,通常用于数据加密。另一个称之为私钥,是不能对外公布的,通常用于数据解密,这样使用公钥加密的数据即使被......
  • DES对称加密算法Java实现
    DES对称加密算法Java实现源代码AESUtils.java//packageme.muphy.util;importjavax.crypto.*;importjavax.crypto.spec.SecretKeySpec;importjava.nio.charset.StandardCharsets;importjava.security.InvalidKeyException;importjava.security.NoSuchAlgorithmExcept......
  • 算法学习笔记(37): 矩阵
    一切线性操作都可以归为矩阵乘法--bySmallBasic本文是拿来玩耍，而不是学习的！目录线性递推超级矩阵快速幂！矩阵与邻接矩阵矩阵与线段树矩阵与FFT矩阵与期望不知道还能扯啥了矩阵的加法，要求两个矩阵大小相等，于是可以对位单点相加。\[C_{i,j}=A_{i,j}+B_{i,j}\]关于矩......
  • 密钥分配和用户认证——基于对称加密的密钥分配
    基于对称加密的密钥分配(SymmetricKeyDistributionusingsymmetricencryption)对于对称加密，加密双方必须共享同一密钥，且必须保护密钥不被他人窃取需要频繁地改变密钥，以减少攻击者可能知道密钥所带来的数据泄露因此，任何密码系统的强度取决于密钥分配技术(密钥分发技术:传......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99