TA的每日心情 | 开心
2021-3-12 23:18 |
|---|
签到天数: 2 天 [LV.1]初来乍到
|
|
题目要求打印一个回旋数字矩阵
int
i
=
5
;
1
2
3
4
5
16
17
18
19
6
15
24
25
20
7
14
23
22
21
8
13
12
11
10
9
int
i
=
6
1
2
3
4
5
6
20
21
22
23
24
7
19
32
33
34
25
8
18
31
36
35
26
9
17
30
29
28
27
10
16
15
14
13
12
11
我的解题思路分析： 1.将此矩阵分解为一个一个的圈，如下图，1-20可以看成一个圈，21-32是一个圈，33-36也是一个圈。 
2.再将圈分解为四个均等的数列 
3.打印的过程中用一个二维数组存储矩阵，记录圈数 ，当前圈的数列长度 和圈开始计数的数字 。如i=6，第1圈时数列长为5，开始计数的数字为0；第2圈数列长为3，开始计数的数字为20；从这些规律总结出,已知变长为i，假设当前圈数为count，则数列长step=i-1-count*2 
程序代码：
package
snakematrix;
/**
*
@author
Heis
* @date Dec 11, 2009
*/
public
class
SnakeNum {
public
static
void
main(String[] args){
int
i
=
6
;
SnakeNum.print(SnakeNum.fill(i));
}
/**
*
* 算法复杂度为n
* 以下的算法，在for循环内的一些计算是不必要的，可以用变量保存，但是为了代码更加直观，就不做优化了。
*
*
@param
i 矩阵边长
*/
public
static
int
[][] fill(
int
i){
Long startTime
=
System.currentTimeMillis();
//
第几圈
int
count
=
0
;
//
数列长度
int
step;
//
总圈数
int
all;
//
某圈开始计数的基数
int
startNum
=
0
;
//
用于数组下标计算
int
startIndex;
int
k;
int
[][] array
=
null
;
if
(i
>
0
){
array
=
new
int
;
all
=
i
/
2
+
i
%
2
;
while
(all
>=
count){
step
=
i
-
1
-
(count
<<
1
);
count
++
;
for
(startIndex
=
count
-
1
,k
=
1
;k
<
step
+
1
;k
++
){
array[count
-
1
][startIndex
++
]
=
startNum
+
k;
}
for
(startIndex
=
count
-
1
,k
=
1
;k
<
step
+
1
;k
++
){
array[startIndex
++
][i
-
count]
=
startNum
+
k
+
step;
}
for
(startIndex
=
i
-
count,k
=
1
;k
<
step
+
1
;k
++
){
array[i
-
count][startIndex
--
]
=
startNum
+
k
+
2
*
step;
}
for
(startIndex
=
i
-
count,k
=
1
;k
<
step
+
1
;k
++
){
array[startIndex
--
][count
-
1
]
=
startNum
+
k
+
3
*
step;
}
startNum
=
4
*
step
+
startNum;
}
//
当矩阵边长为基数时，打印最后一个数字
if
(i
%
2
>
0
){
int
mid
=
all
-
1
;
array[mid][mid]
=
i
*
i;
}
}
Long timeUsed
=
System.currentTimeMillis()
-
startTime;
System.out.println(
"
总用时：
"
+
timeUsed
+
"
ms
"
);
return
array;
}
/**
* 打印数组
*
*
@param
array
*/
public
static
void
print(
int
[][] array){
if
(array
!=
null
){
int
n
=
array.length;
int
i
=
0
,j;
int
count
=
Integer.valueOf(n
*
n).toString().length()
+
1
;
for
(;i
<
n;i
++
){
for
(j
=
0
;j
<
n;j
++
){
System.out.printf(
"
%
"
+
count
+
"
d
"
,array[j]);
}
System.out.println();
}
}
}
}
优化后的代码：
package
snakematrix;
/**
*
@author
Heis
*
*/
public
class
SnakeNum2 {
public
static
void
main(String[] args){
int
i
=
6
;
SnakeNum2
.print(SnakeNum2
.fill(i));
}
/**
*
* 算法复杂度为n
*
@param
i 矩阵边长
*/
public
static
int
[][] fill(
int
i){
Long startTime
=
System.currentTimeMillis();
//
第几圈
int
count
=
0
;
//
转弯步数
int
step;
//
总圈数
int
all;
//
某圈开始累加的基数
int
startNum
=
0
;
//
用于数组下标计算
int
startIndex;
int
k,cache
=
0
;
int
[][] array
=
null
;
if
(i
>
0
){
array
=
new
int
;
all
=
i
/
2
+
i
%
2
;
while
(all
>=
count){
step
=
i
-
1
-
(count
<<
1
);
count
++
;
for
(startIndex
=
count
-
1
,k
=
1
;k
<
step
+
1
;k
++
){
array[count
-
1
][startIndex
++
]
=
startNum
+
k;
}
for
(startIndex
=
count
-
1
,k
=
1
;k
<
step
+
1
;k
++
){
array[startIndex
++
][i
-
count]
=
startNum
+
k
+
step;
}
cache
=
(step
<<
1
)
+
startNum;
for
(startIndex
=
i
-
count,k
=
1
;k
<
step
+
1
;k
++
){
array[i
-
count][startIndex
--
]
=
cache
+
k;
}
cache
=
(step
<<
1
)
+
startNum
+
step;
for
(startIndex
=
i
-
count,k
=
1
;k
<
step
+
1
;k
++
){
array[startIndex
--
][count
-
1
]
=
cache
+
k;
}
startNum
=
(step
<<
2
)
+
startNum;
}
//
当矩阵边长为基数时，打印最后一个数字
if
(i
%
2
>
0
){
int
mid
=
all
-
1
;
array[mid][mid]
=
i
*
i;
}
}
Long timeUsed
=
System.currentTimeMillis()
-
startTime;
System.out.println(
"
总用时：
"
+
timeUsed
+
"
ms
"
);
return
array;
}
/**
* 打印数组
*
*
@param
array
*/
public
static
void
print(
int
[][] array){
if
(array
!=
null
){
int
n
=
array.length;
int
i
=
0
,j;
int
count
=
Integer.valueOf(n
*
n).toString().length()
+
1
;
for
(;i
<
n;i
++
){
for
(j
=
0
;j
<
n;j
++
){
System.out.printf(
"
%
"
+
count
+
"
d
"
,array[j]);
}
System.out.println();
}
}
}
}
回帖还有另外一种思路，也是用一个二维数组存储数组，按照数列顺序输出，在输出过程中判断输出的方向，可以看这里的代码http://www.javaeye.com/topic/545378?page=1#1288013 
源码下载：http://file.javaxxz.com/2014/11/11/000325093.zip |
|
|手机版|Java学习者论坛
( 声明：本站资料整理自互联网，用于Java学习者交流学习使用，对资料版权不负任何法律责任，若有侵权请及时联系客服屏蔽删除 )
发表于 2014-11-11 00:03:25