|
发表时间：2009-12-15
既然是java题，个人觉得用面向对象的方式来实现比较好，比如这里可以看做是贪吃蛇游戏的简化版。
这个蛇的操作有游走、打印足迹，另外还可以记录足迹、碰到墙壁和走过的地方会掉头。 其他的对象就是点Point和方向Direction。其中方向Direction 有四个子类分别是：上下左右。 因为方向是固定的，先右-》下-》左-》上，可以通过next方法获得掉头后的Direction class Point {//坐标上的点
int x; int y; String value; Direction dir;//这个点的方向 } abstract Direction {
int size; abstract Direction next();//下一个方向 abstract nextPoint(Point point,Map map);//如果在本方向上越界或者已经走过就调头，否则本方向上取下一个点 } class Snake{
int size;//=6 Map map;//走过的点 public void run() {}//初始化起始点和起始方向，遍历size*size次，把走过的点放在map中。 public void print(){}//根据矩阵遍历map对象
public void main(String[]args) {
Snake sn = new Snake(6); sn.run();
sn.print();
}
}
chinpom 写道
看一下我的，思路应该更清晰一点： public class SnakePrint {
private int orient = 0, length = 0, x = 0, y = 0;
// orients为顺时针90°旋转方向，前进步长为1
private int[][] orients = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
private int[][] arrays;
public SnakePrint(int length) {
this.length = length;
arrays = new int[length][length];
}
// 根据当前方向返回下一个前进方向
private int[] nextOrient(int[] curOrient) {
int nextX = x + curOrient[0], nextY = y + curOrient[1];
// 前进方向需要顺时针旋转90°了
if (nextX < 0 || nextX >= length || nextY < 0 || nextY >= length
|| arrays[nextX][nextY] != 0) {
orient = ++orient % 4;
return orients[orient];
}
return curOrient; // 不需要掉头，返回原前进方向
}
public void print() {
int[] curOrient = orients[orient]; // 初始前进方向
for (int i = 1; i <= length * length; i++) { // 依次填充数组
arrays[x][y] = i;
curOrient = nextOrient(curOrient);
x += curOrient[0];
y += curOrient[1];
}
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
System.out.printf("%4d", arrays[i][j]); // 按固定4个字符宽度的格式输出
}
System.out.println();
}
}
public static void main(String[] args) {
SnakePrint snakePrint = new SnakePrint(6);
snakePrint.print();
}
}
|
|
发表时间：2009-12-15
真的是想研究模的 只是失败了
@Test
public void snake() {
assertEquals(1, mod(0, 0, 6));
assertEquals(7, mod(5, 1, 6));
assertEquals(20, mod(0, 1, 6));
assertEquals(16, mod(0, 5, 6));
assertEquals(11, mod(5, 5, 6));
assertEquals(33, mod(2, 2, 6));
assertEquals(26, mod(4, 3, 6));
//after all test passed!
int printSize = 7;
for(int i=0;i<printSize;i++){
for(int j=0;j<printSize;j++)
System.out.printf("%4d",mod(j,i,printSize));
System.out.println();
}
}
private int[][] bufData;
private int mylength;
private int mod(int x, int y, int n) {
if (bufData == null || mylength != n) {
int dilength = n / 2 + n % 2;
bufData = new int[n][n];
int di = 0;
int number = 0;
while (di < dilength) {
//单一维度的打印
int j = 0;
int k = 0;
//-> y=di x [ di -> n-di ]
k = di;
for (j = di; j < n - di; j++) {
bufData[j][k] = ++number;
}
//| x = n-di y [di+1 -> n-di]
j = n - di -1;
for (k = di + 1; k < n - di; k++) {
bufData[j][k] = ++number;
}
//<- y=n-di x [n-di-1 -> di]
k = n - di -1;
for (j = n - di - 1 - 1; j >= di; j--) {
bufData[j][k] = ++number;
}
//| x = di y [ n-di-1 -> di ]
j = di;
for (k = n - di - 1 - 1; k > di; k--) {
bufData[j][k] = ++number;
}
//END
di++;
}
}
return bufData[x][y];
}
|
|
发表时间：2009-12-15
本来在问答里答的，居然发现已经有讨论了。我帖上我的，花了一个小时的。
思路就是从0开始，判断其下一个数字的位置，依次判断周围四个数字然后选择正确的数字。 public class Test {
static int n = 10;
static int[][] arr = new int[n][n];
public static void main(String[] args) {
int x = 0, y = 0;
for (int i = 1; i <= n * n; i++) {
arr[x][y] = i;
if (canSet(x + 1, y) && !canSet(x, y - 1)) {
x = x + 1;
} else if (canSet(x, y + 1) && !canSet(x + 1, y)) {
y = y + 1;
} else if (canSet(x - 1, y) && !canSet(x, y + 1)) {
x = x - 1;
} else if (canSet(x, y - 1) && !canSet(x - 1, y)) {
y = y - 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arr[j][i] + " ");
}
System.out.println("");
}
}
private static boolean canSet(int x, int y) {
if (x < 0 || y < 0 || x >= n || y >= n)
return false;
if (arr[x][y] != 0)
return false;
return true;
}
}
|
|
发表时间：2009-12-15
就是递归打印个正方形嘛...
搞的这么麻烦 |
|
发表时间：2009-12-15
import java.util.HashMap;
import java.util.Map;
class Point {
private int x;
private int y;
private String val;
public Point (int x,int y) {
this.x = x;
this.y = y;
}
public Point (int x, int y, String val) {
this(x, y);
this.val = val;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public String getVal() {
return val;
}
public void setVal(String val) {
this.val = val;
}
}
abstract class Direction {
int size;
abstract public Point nextPoint(Point p);//下个点
abstract public Direction next();//下一个方向
abstract public boolean isOut(Point point);//是否在本方向上出界
}
class Right extends Direction {
public Right(int size){
this.size = size;
}
public Direction next() {
return new Down(size);
}
public Point nextPoint(Point p) {
return new Point(p.getX() + 1,p.getY());
}
public boolean isOut(Point point) {
return point.getX() > size;
}
}
class Down extends Direction {
public Down(int size){
this.size = size;
}
public Direction next() {
return new Left(size);
}
public Point nextPoint(Point p) {
return new Point(p.getX(),p.getY() + 1);
}
public boolean isOut(Point point) {
return point.getY() > size;
}
}
class Left extends Direction {
public Left(int size){
this.size = size;
}
public Direction next() {
return new Up(size);
}
public Point nextPoint(Point p) {
return new Point(p.getX() - 1,p.getY());
}
public boolean isOut(Point point) {
return point.getX() < 1;
}
}
class Up extends Direction {
public Up(int size){
this.size = size;
}
public Direction next() {
return new Right(size);
}
public Point nextPoint(Point p) {
return new Point(p.getX(),p.getY()-1);
}
public boolean isOut(Point point) {
return point.getY() < 1;
}
}
public class Snake {
int size;
Map<String ,Point> map = new HashMap<String, Point>();//记录走过的点
public Snake(int size) {
this.size = size;
}
public void run() {
Point next = new Point(1, 1,"1");
Direction dirct = new Right(size);
map.put(key(1,1), next);
for(int i = 2; i < size * size + 1; i++) {
Point tempNext = dirct.nextPoint(next);
//如果在一个方向上出界或者已经走过的点要掉头
if(dirct.isOut(tempNext) || null != map.get(key(tempNext.getX(),tempNext.getY()))) {
dirct = dirct.next();
next = dirct.nextPoint(next);
}
else {
next = tempNext;
}
next.setVal(String.valueOf(i));
map.put(key(next.getX(),next.getY()), next);//记录走过的点
}
}
//生成key
private String key(int x,int y) {
String xVal = "00000" + x;
String yVal = "00000" + y;
return xVal.substring(xVal.length()-3) + yVal.substring(yVal.length() - 3);
}
public void print() {
for (int y = 1; y < size + 1 ; y++) {
for(int x = 1; x < size + 1; x++) {
String temp = " " + map.get(key(x,y)).getVal();
System.out.print(temp.substring(temp.length() - 5));
}
System.out.println("");
}
}
public static void main(String[] args) {
Snake sn = new Snake(25);
sn.run();
sn.print();
}
}
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 |
|
发表时间：2009-12-16
mod获得位置输出的么
|
|
发表时间：2009-12-16
谈点体会，也碰过这类面试题，也许人家想考察我们对面向对象的分析和设计而
不是具体的算法实现，当我画出类图或者类定义等，面试官总很不屑，很受打击。 我想具体的实现工作做可以参考资料就OK了。但也有些面试官水平（思维）有限只看你是否写出算法。 其实，如果给出具体的算法，像有些网友贴出来的都能实现，但面试官真的有时间有心情还要仔细读才能看懂。 我也当过面试官，我一般问在工作中对面向对象有什么体会，如何应用到具体的工作中和工作态度。一般对具体的技术不会深入 提问，我觉得一个人如果能理解面向对象思想了，对于具体的技术只要有机会用到，用心去学，没有学不会的！ |
|
发表时间：2009-12-16
ilove2009 写道 谈点体会，也碰过这类面试题，也许人家想考察我们对面向对象的分析和设计而
不是具体的算法实现，当我画出类图或者类定义等，面试官总很不屑，很受打击。 我想具体的实现工作做可以参考资料就OK了。但也有些面试官水平（思维）有限只看你是否写出算法。 其实，如果给出具体的算法，像有些网友贴出来的都能实现，但面试官真的有时间有心情还要仔细读才能看懂。 我也当过面试官，我一般问在工作中对面向对象有什么体会，如何应用到具体的工作中和工作态度。一般对具体的技术不会深入 提问，我觉得一个人如果能理解面向对象思想了，对于具体的技术只要有机会用到，用心去学，没有学不会的！ 很是同意，有的时候只要有想法和思路就OK了，学的再多，再精通，工作上没有用到，还是没有多大用处！ 当然对你分析代码和看问题有帮助！ |
|
发表时间：2009-12-16
我写的算法实现：
public class HelixAlgo {
public void print(int len){
if(len<=0){
System.out.println("请输入大于0的整数！");
return;
}
int[][] helix=calculate(len);
for(int i=0;i<helix.length;i++){
for(int j=0;j<helix[i].length;j++){
System.out.print(helix[i][j]+"\t");
}
System.out.println("");
}
}
private int[][] calculate(int len){
int[][] helix=new int[len][len];
int min=0,max=len-1;//行列的最大最小值
int row=0,col=0;
for(int i=0;i<len*len;i++){
helix[row][col]=i+1;
if(row==min&&col<max){
col++;
}else if(row<max&&col==max){
row++;
}else if(row==max&&col>min){
col--;
}else if(row>min&&col==min){
row--;
}
if(row-1==min&&col==min){ //在一个周期结束时修改最大最小值
min++;
max--;
}
}
return helix;
}
public static void main(String[] args){
HelixAlgo algo=new HelixAlgo();
algo.print(6);
}
}
我在blog(http://shuishou119800.iteye.com/blog/549592)中对这个算法写了些分析，希望能一起探讨 |
|
发表时间：2009-12-16
Heis 写道
/**
* @author Heis
* @date Dec 11, 2009
*/
public class SnakeNum {
public static void main(String[] args){
int n=7;
SnakeNum.print(SnakeNum.fill(n));
}
/**
*
* 算法复杂度为n
* 测试结果n=1000时，大概用时70ms
* 以下的算法，在for循环内的一些计算是不必要的，可以用变量保存，但是为了代码更加直观，就不做优化了。
*
* @param n 矩阵边长
*/
public static int[][] fill(int n){
Long startTime=System.currentTimeMillis();
//第几圈
int count=0;
//转弯步数
int step;
//总圈数
int all;
//某圈开始累加的基数
int startNum=0;
//用于数组下标计算
int startIndex;
int k;
int[][] array=null;
if(n>0){
array=new int[n][n];
all=n/2+n%2;
while(all>=count){
step=n-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++][n-count]=startNum+k+step;
}
for(startIndex=n-count,k=1;k<step+1;k++){
array[n-count][startIndex--]=startNum+k+2*step;
}
for(startIndex=n-count,k=1;k<step+1;k++){
array[startIndex--][count-1]=startNum+k+3*step;
}
startNum=4*step+startNum;
}
if(n%2>0){
int mid=all-1;
array[mid][mid]=n*n;
}
}
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[i][j]);
}
System.out.println();
}
}
}
}
我把这个算法的分析写在博客上,有兴趣的可以去看看http://heis.iteye.com/blog/546981 |
