|
锁定老帖子 主题：关于螺旋矩阵问题的新思路
精华帖 (0) :: 良好帖 (0) :: 新手帖 (2) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-05-04
最后修改：2011-05-10
基本就是画圈圈呗，大圈套小圈，用个递归代码多短啊
void SetMatrix(int **matrix, int x, int y, int start, int n) {
int i, j;
if (n <= 0) return;
if (n == 1) {
matrix[x][y] = start;
return;
}
for (i = x; i < x + n-1; i++) /* 上部 */
matrix[y][i] = start++;
for (j = y; j < y + n-1; j++) /* 右边 */
matrix[j][x+n-1] = start++;
for (i = x+n-1; i > x; i--) /* 底部 */
matrix[y+n-1][i] = start++;
for (j = y+n-1; j > y; j--) /* 左边 */
matrix[j][x] = start++;
SetMatrix(matrix, x+1, y+1, start, n-2); /* 递归 */
}
|
| 返回顶楼 | |
|
发表时间：2011-05-04
我对递归概念一直弄不明白，所以对此螺旋矩阵进行了自然模拟，像小虫爬管道一样，慢慢把所有矩阵位爬满~呵呵
/**
* 螺旋矩阵算法实例，算法思路为：
* 1、将螺旋矩阵分解模拟为：数据小虫按照一定既定方向填充，根据指定条件进行方向调转。
* 2、方向分为：上、下、左、右四个方向
* 3、此算法的填充方向和顺序为：顺时针
* @author yoya 2011.05.04
*
*/
public class Luoxuan {
private int[][] luoxuan;
/**
* 根据参数，生成并打印螺旋矩阵
* @param rowNum - 矩阵行数值
* @param colNum - 矩阵列数值
*/
public void print(int rowNum, int colNum) {
luoxuan = new int[rowNum][colNum];
right(luoxuan, 0, 0, 1);
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
System.out.print(luoxuan[i][j] + "\t");
}
System.out.println();
}
}
/**
* 向上填充螺旋矩阵列
* @param arr - 被填充螺旋矩阵数组
* @param row - 填充起始行
* @param col - 填充起始列
* @param value - 填充起始数值
* (其他方向功能函数参数相同，不再注释)
*/
public void up(int[][] arr, int row, int col, int value) {
while (arr[row][col] == 0) {
arr[row][col] = value++;
row--;
}
//判定向上矩阵位有无数值，如果有，调转方向，向右填充，反之继续填充
if (arr[row + 1][col + 1] == 0) {
right(arr, row + 1, col + 1, value);
}
}
/**
* 向左填充螺旋矩阵行
* @param arr
* @param row
* @param col
* @param value
*/
public void left(int[][] arr, int row, int col, int value) {
while (col > -1) {
arr[row][col] = value++;
if (col != 0) {
if (arr[row][col - 1] != 0)
break;
}
col--;
}
if (col == -1) {//处理矩阵最左边的填充逻辑
col = 0;
}
//判定向左矩阵位有无数值，如果有，调转方向，向上填充，反之继续填充
if (arr[row - 1][col] == 0) {
up(arr, row - 1, col, value);
}
}
/**
* 向右填充螺旋矩阵行
* @param arr
* @param row
* @param col
* @param value
*/
public void right(int[][] arr, int row, int col, int value) {
while (true) {
arr[row][col] = value++;
if (col < arr[row].length) {
if (col + 1 != arr[row].length) {
if (arr[row][col + 1] != 0)
break;
} else {
break;
}
} else {
break;
}
col++;
}
//判定向右矩阵位有无数值，如果有，调转方向，向下填充，反之继续填充
if (arr[row + 1][col] == 0) {
down(arr, row + 1, col, value);
}
}
/**
* 向下填充螺旋矩阵列
* @param arr
* @param row
* @param col
* @param value
*/
public void down(int[][] arr, int row, int col, int value) {
while (true) {
arr[row][col] = value++;
if (row < arr.length) {
if (row + 1 != arr.length) {
if (arr[row + 1][col] != 0)
break;
} else {
break;
}
} else {
break;
}
row++;
}
//判定向下矩阵位有无数值，如果有，调转方向，向左填充，反之继续填充
if (arr[row][col - 1] == 0) {
left(arr, row, col - 1, value);
}
}
public static void main(String[] arg) {
new Luoxuan().print(100, 100);
}
}
|
| 返回顶楼 | |
|
发表时间：2011-05-05
我这个就是用算法在棋盘上爬。。呵呵有点晦涩
import java.io.OutputStream;
public class Martix {
public static void main(String[] args) throws Exception {
int m = 10;
int[][] martix = martix(m);
toString(martix, System.out);
}
public static int[][] martix(int m) {
int[][] martix = new int[m][m];
int d = 0, x = 0, y = 0, loop = 0, k = 0, t = m * m;
for (int i = 0; i < t; i++, k++) {
if (m - 1 - loop * 2 == k) {
if (d == 3) {
x++;
y++;
loop++;
}
k = 0;
d = (d + 1) & 3;
}
martix[x][y] = i + 1;
x += (2 - d) * (d & 1);
y += (1 - d) * ((d + 1) & 1);
}
return martix;
}
private static void toString(int[][] martix, OutputStream os) throws Exception {
for (int i = 0; i < martix.length; i++) {
for (int j = 0; j < martix[i].length; j++) {
os.write((martix[i][j] + "\t").getBytes());
}
os.write("\r\n".getBytes());
}
os.flush();
}
}
|
| 返回顶楼 | |
|
发表时间：2011-05-06
不需要用到数学方法的 ， 从第一个位置一直走，碰边就换方向 、、、
|
| 返回顶楼 | |
|
发表时间：2011-05-06
参与快乐~
|
| 返回顶楼 | |
|
发表时间：2011-05-09
可以使用类似寻路的算法，不同时改变方向是单一顺序的。
|
| 返回顶楼 | |
|
发表时间：2011-05-09
package cn.wingware;
public class ConvoluteNumber {
public static void main(String args[]) {
int a = 10;
int aa[][] = new int[a][a];
int p[];
for (int i = a * a; i >= 1; i--) {
p = getCoordinateByIndex(i, a);
aa[p[0]][p[1]] = i;
}
for (int i = 0; i < a; i++) {
for (int j = 0; j < a; j++) {
System.out.print(aa[j][i] + "\t");
}
System.out.println("");
}
}
/**
* 获取总数
*
* @param count
* @return
*/
private static int getAllCountFor(int count) {
return count * count;
}
/**
* 获取
*
* @param count
* @return
*/
private static int getCount(int count) {
if (count < 1) {
throw new RuntimeException("数字应该在大于0.");
}
if (count == 1) {
return 1;
}
return count * 4 - 4;
}
/**
* 获取坐标轴
*
* @param index
* 第几位数
* @param count
* 输入量
* @return
*/
public static int[] getCoordinateByIndex(int index, int count) {
if (index <= 0 || index > getAllCountFor(count)) {
throw new RuntimeException("数字应该在[0," + (getAllCountFor(count) - 1) + "]");
}
int t = count;
int temp = count;
for (int i = count; i >= 1; i = i - 2) {
int tt = getAllCountFor(i);
t = i;
if (tt >= index && index > tt - getCount(i)) {
break;
}
temp--;
}
int begin = count - temp;
/** 起点坐标 */
// int x = 0, y = 0;
/** 偏移量 */
int a = begin, b = begin;
int _begin = getAllCountFor(t) - getCount(t);
if ((_begin + (t - 1) * 4) >= index && index > (_begin + (t - 1) * 3)) {
a = (_begin + (t - 1) * 4) - index + begin;
} else if ((_begin + (t - 1) * 3) >= index && index > (_begin + (t - 1) * 2)) {
a = count - begin - 1;
b = (_begin + (t - 1) * 3) - index + begin;
} else if ((_begin + (t - 1) * 2) >= index && index > (_begin + (t - 1) * 1)) {
a = count - ((_begin + (t - 1) * 2) - index) - begin - 1;
b = count - begin - 1;
} else if ((_begin + (t - 1) * 1) >= index) {
b = index - (_begin + (t - 1) * 1) + count - begin - 1;
}
return new int[] { a, b };
}
}
这个回旋矩阵，好像是支付宝的面试题，看了楼主写的代码，感觉好像比较长，我也刚刚写了一个算法，晒出来，大家看看，哪种更效率高。。。 |
| 返回顶楼 | |
|
发表时间：2011-05-09
感觉我的代码好像比楼主的少一半。。。
现在也在想，有时候为了写一些高效的算法，用不用搞那么多代码。 |
| 返回顶楼 | |
|
发表时间：2011-05-11
楼上那些代码都好牛逼，有的语言看不懂，小弟写了个简单点的，代码量多了一些，大家有兴趣改善下
public class LuoXuan {
public int n,m;
public int luoxuan[][];
public static void main(String[] args) {
LuoXuan ls = new LuoXuan();
ls.init(4,6);
ls.change(0,0,1,0);
for(int i=0;i<ls.n;i++){
for(int j=0;j<ls.m;j++){
System.out.print(ls.luoxuan[i][j]+" ");
}
System.out.println();
}
}
public void init(int x,int y){
n=x;
m=y;
luoxuan=new int[x][y];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
luoxuan[i][j]=0;
}
}
}
public void change(int x,int y,int num,int b){
int i,j;
if(x==0&&y==0){
luoxuan[x][y]=num;
num++;
}
if(num>=n*m){
return;
}
if(b==0){
for(i=y+1;i<m;i++){
luoxuan[x][i]=num;
num++;
if(i==m-1||luoxuan[x][i+1]!=0)
break;
}
change(x,i,num,1);
}
if(b==1){
for(j=x+1;j<n;j++){
luoxuan[j][y]=num;
num++;
if(j==n-1||luoxuan[j+1][y]!=0)
break;
}
change(j,y,num,2);
}
if(b==2){
for(i=y-1;i>=0;i--){
luoxuan[x][i]=num;
num++;
if(i==0||luoxuan[x][i-1]!=0)
break;
}
change(x,i,num,3);
}
if(b==3){
for(j=x-1;j>=0;j--){
luoxuan[j][y]=num;
num++;
if(j==0||luoxuan[j-1][y]!=0)
break;
}
change(j,y,num,0);
}
}
}
|
| 返回顶楼 | |
|
发表时间：2011-05-11
看看这个吧，数学算法
http://archive.cnblogs.com/a/1912829/ |
| 返回顶楼 | |
