-
曼哈顿距离与曼哈顿矩形-打印回字型矩阵
食用指南：
Leetcode专栏开启了，由于博主闭关期末，所以每日只能一题
尽量做到一题多解，先说思路，之后代码实现，会添加必要注释
语法或STL内容会在注意点中点出，新手友好
欢迎关注博主神机百炼专栏，内涵算法基础详细讲解和代码模板题目描述：
-
输入整数 N，输出一个 N 阶的回字形二维数组。
数组的最外层为 1，次外层为 2，以此类推。
输入格式
输入包含多行，每行包含一个整数 N。
当输入行为 N=0 时，表示输入结束，且该行无需作任何处理。输出格式
对于每个输入整数 N，输出一个满足要求的 N 阶二维数组。
每个数组占 N 行，每行包含 N 个用空格隔开的整数。
每个数组输出完毕后，输出一个空行。数据范围
0≤N≤100
输入样例：
1
2
3
4
5
0
输出样例：
11 1
1 11 1 1
1 2 1
1 1 11 1 1 1
1 2 2 1
1 2 2 1
1 1 1 11 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1 -
题目来源：https://www.acwing.com/problem/content/755/
题目分析：
法一：曼哈顿距离
-
曼哈顿距离是两点在垂直坐标系中，x & y方向投影距离最大值
-
应用在数组/矩阵中，曼哈顿距离相同的点集合成为围绕矩阵中心的一圈矩形，
在计算曼哈顿距离时，需要区分行数/列数的奇偶：
法二：数组下标与值的关系
-
曼哈顿距离其实就是数组下标和值关系研究所得的结论
当你不知道曼哈顿距离时，不妨试试手动探究一下，可能得到非曼哈顿距离的其他结论
方向1：用距离推导关系
- 该图关于中心对称
未越过中线的点用i计算，越过中线的点用n-1-i计算，
则对于所有点，要么 i 和 n-1-i/n-i 各计算一次，两者取最大/小值， 要么采用绝对值
2. 对于未过中线的点，采用举例探究
n = 5时，n/2 = 2，中点为(2, 2)
第一个点arr[0][0] = 1，距离中点Δx = Δy =2
第二个点arr[1][0] = 1，距离终点Δx = 2， Δy =1
第三个点arr[0][1] = 1，距离终点Δx = 1， Δy =2
确定计算公式：n/2 - max(abs(x-n/2) , abs(y-n/2)) + 1
3. 对于过了中线的点，采用举例探究
n = 5时，n/2 = 2，中点为(2, 2)
第一个点arr[4][4] = 1，距离中点Δx = Δy =2
第二个点arr[3][4] = 1，距离终点Δx = 1， Δy =2
第三个点arr[4][3] = 1，距离终点Δx = 2， Δy =1
确定计算公式：n/2 - max(abs(x-n/2) , abs(y-n/2)) + 1
- 完成用距离推导后，你会发现你其实推得的就是曼哈顿距离，
方向2：只看下标和值关系
- n = 5时：
- 对于未过中线的点，采用举例探究：
第一个点arr[0][0] = 1，1 = max/min(x + 1, y + 1)
第二个点arr[1][0] = 1，1 = min(x + 1, y + 1)
第三个点arr[0][1] = 1，1 = min(x + 1, y + 1)
石锤采用min(x + 1, y + 1) - 对于过了中线的点，采用举例探究：
第一个点arr[4][4] = 1，1 = max/min(n-x, n-y)
第二个点arr[3][4] = 1，1 = min(n-x, n-y)
第三个点arr[4][3] = 1，1 = min(n-x, n-y)
石锤采用min(n-x, n-y)
3.整体来看所有点：
现在有两种方案：min(x + 1, y + 1) & min(n-x, n-y)
查看是否同时采用/舍弃哪一种？
对于点arr[3][4]，min(x + 1, y + 1) = 4， min(n-x, n-y) = 1
对于点arr[0][0]，min(x + 1, y + 1) = 1， min(n-x, n-y) = 5
发现对于每个点都取两种方案的最小值，所以得出结论：
- 对于未过中线的点，采用举例探究：
- 所以对于所有点：arr[i][j] = min(min(x + 1, y + 1) , min(n-x, n-y));
法三：对称化简（严格说属于技巧而非方法）
-
中心对称图像，填写一点相当于填写了4点。
以n = 5的矩形为例，查看对称的4点下标关系：
-
在填写一个象限的值时，可以采用曼哈顿矩阵法 / 下标与值关系规律
这个技巧提升了时间复杂度，将时间缩减到原本的四分之一
也可以在之后题目中作为一个化简找规律时的思考出发点
算法模板:
- 曼哈顿距离 + 中心对称规律 本身就是基础算法，无模板
代码实现：
法一：
import java.util.Scanner; import java.lang.Math; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if (n == 0) return; //读取终止出口 for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(n % 2 == 1) //曼哈顿距离近者，值大，距离为0者值为(n+1)/2 System.out.print((n+1)/2 - Math.max(Math.abs(n/2-i), Math.abs(n/2-j)) +" "); else //曼哈顿距离近者，值大，距离为0者值为n/2 System.out.print((n/2) - Math.max((int)Math.abs((n-1)/2.0-i), (int)Math.abs((n-1)/2.0-j)) +" "); } System.out.println(); } System.out.println(); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
法二：
- 下标和值关系：Math.min(Math.min(i+1, j+1), Math.min(n-i, n-j))
import java.util.Scanner; import java.lang.Math; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if (n == 0) return; //读取终止出口 for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ System.out.print(Math.min(Math.min(i+1, j+1), Math.min(n-i, n-j))+" "); } System.out.println(); } System.out.println(); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
法三：
- 曼哈顿距离填法：
import java.util.Scanner; import java.lang.Math; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if (n == 0) return; //读取终止出口 int[][] arr = new int[n][n]; //偶数行列，如4行4列，只需填0~1行 & 0~1列 if(n % 2 == 0){ for(int i=0; i<n/2; i++){ for(int j=0; j<n/2; j++){ arr[i][j] = arr[n-1-i][n-1-j] = arr[n-1-i][j] = arr[i][n-1-j] = n/2 - Math.max(Math.abs((int)((n-1)/2.0 - i)), Math.abs((int)((n-1)/2.0 - j))); } } } //奇数行列，如5行5列，需要填0~2行 & 0~2列 else{ for(int i=0; i<=n/2; i++){ for(int j=0; j<=n/2; j++){ arr[i][j] = arr[n-1-i][n-1-j] = arr[n-1-i][j] = arr[i][n-1-j] = (n+1)/2 - Math.max(Math.abs(n/2 - i), Math.abs(n/2 - j)); } } } for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ System.out.print(arr[i][j]+" "); } System.out.println(); } System.out.println(); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 下标和值关系填法：
import java.util.Scanner; import java.lang.Math; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if (n == 0) return; //读取终止出口 int[][] arr = new int[n][n]; //偶数行列，如4行4列，只需填0~1行 & 0~1列 if(n % 2 == 0){ for(int i=0; i<n/2; i++){ for(int j=0; j<n/2; j++){ arr[i][j] = arr[n-1-i][n-1-j] = arr[n-1-i][j] = arr[i][n-1-j] = Math.min(Math.min(i+1, j+1), Math.min(n-i, n-j)); } } } //奇数行列，如5行5列，需要填0~2行 & 0~2列 else{ for(int i=0; i<=n/2; i++){ for(int j=0; j<=n/2; j++){ arr[i][j] = arr[n-1-i][n-1-j] = arr[n-1-i][j] = arr[i][n-1-j] = Math.min(Math.min(i+1, j+1), Math.min(n-i, n-j)); } } } for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ System.out.print(arr[i][j]+" "); } System.out.println(); } System.out.println(); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
注意点：
-
曼哈顿距离计算公式：
- 行/列数为奇：
manhattan = max(abs(x - n/2), abs(y - n/2));
即中点 n/2 向下取整，而结果本身是整数 - 行/列数为偶：
manhattan = max((int)abs(x - (n-1)/2.0), (int)abs(y-(n-1)/2.0));
即中点为小数不取整，而 x - (n-1)/2.0的结果向下取整 - 可以简记为，奇数中点直接除2，偶数中点-1除以2.0
- 行/列数为奇：
-
对于安全性要求较高的Java
double 和 int 运算，也是先Int整型提升到double再与double运算
将Double用(int)显式类型转化为int，也是默认向下取整
-
-
相关阅读:
RFID电力资产全周期智能化管理应用解决方案
字节跳动面试官：请你实现一个大文件上传和断点续传
Docker游戏Dos小游戏，一个web版的dos游戏库
正则表达式
【jvm】虚拟机之本地方法栈
PMI-ACP练习题(30)
【K8S】集群中部署nginx应用 运行手写yaml文件报错排查过程
全内反射棱镜(TIR)的建模
【无标题】
jwt以及加密完善博客系统
- 原文地址：https://blog.csdn.net/buptsd/article/details/125623887