|
锁定老帖子 主题：深圳一家公司面试问题,很囧
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-12-11
public class PaintNumberImage {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int source = scanner.nextInt();
int[][] images = new int[source][source];
images[0][0] = 1;
// 北
boolean isNorth = false;
// 东
boolean isEast = false;
// 南
boolean isSouth = false;
// 西
boolean isWest = true;
// 最大下标
int maxIndex = source - 1;
for (int i = 0; i < source;) {
if (isWest) {
for (int j = 1; j < source; j++) {
if (images[i][j] == 0) {
images[i][j] = images[i][j - 1] + 1;
}
}
isWest = false;
isEast = true;
}
else if (isEast) {
for (int j = 1; j < source; j++) {
if (images[j][maxIndex - i] == 0) {
images[j][maxIndex - i] = images[j - 1][maxIndex - i] + 1;
}
}
isEast = false;
isSouth = true;
}
else if (isSouth) {
for (int j = maxIndex; j >= 0; j--) {
if (images[maxIndex - i][j] == 0) {
images[maxIndex - i][j] = images[maxIndex - i][j + 1] + 1;
}
}
isSouth = false;
isNorth = true;
}
else if (isNorth) {
for (int j = maxIndex; j >= 0; j--) {
if (images[j][0 + i] == 0) {
images[j][0 + i] = images[j + 1][0 + i] + 1;
}
}
isNorth = false;
isWest = true;
i++;
}
}
for (int i = 0; i < images.length; i++) {
System.out.println(Arrays.toString(images[i]));
}
}
}
也附上实现代码 |
| 返回顶楼 | |
|
发表时间：2009-12-11
#include <stdio.h>
main() { int a[10][10]={0},i=1,j=0,value=1,n,stauts=1,k;//i:行号,j:列号 printf("Input the number n(n<9):\n"); scanf("%d",&n); for(k=0;k<=n+1;k++) a[0][k]=a[n+1][k]=a[k][0]=a[k][n+1]= 8; //设定边界 while(value<=n*n) { j+=stauts; while(a[i][j]<1) { a[i][j]=value++; j+=stauts; } j-=stauts; i+=stauts; while(a[i][j]<1) { a[i][j]=value++; i+=stauts; } i-=stauts; stauts*= -1; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%4d",a[i][j]); printf("\n"); } } 用c语言写了一个,通过使用边界设定,合理使用状态变化量(stauts),减少判定语句,精简代码; |
| 返回顶楼 | |
|
发表时间：2009-12-11
遇到过比这更囧的，行列不等的二维数组，数字，字母都有。
当时的算法也是递归调用外层的方框。 |
| 返回顶楼 | |
|
发表时间：2009-12-11
/**
* @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();
}
}
}
}
|
| 返回顶楼 | |
|
发表时间：2009-12-11
jenlp110 写道 一个画图程序 要求打印出
哥们 这拉丁矩阵是算法基础吧。无可厚非 |
| 返回顶楼 | |
|
发表时间：2009-12-11
用数组做，应该不难
|
| 返回顶楼 | |
|
发表时间：2009-12-11
我用递归算法做的
public class Xl { public static void main(String[] args) { int i = 8; Integer[][] disp = new Integer[i][i]; disp = core(disp,1,i,1,i*i); for (int m = 0;m < i;m++) { for (int n = 0;n < i;n++) { System.out.print(disp[m][n]+" "); } System.out.println(); } } public static Integer[][] core(Integer[][] result,int seq,int in,int gradation,int end) { Integer[][] temp = result; if (seq == end || seq == end-3) { if (seq == end) { temp[gradation-1][gradation-1] = new Integer(seq); } else { temp[gradation-1][gradation-1] = new Integer(seq); temp[gradation-1][gradation] = new Integer(seq+1); temp[gradation][gradation] = new Integer(seq+2); temp[gradation][gradation-1] = new Integer(seq+3); } return temp; } temp = core(temp,seq+((in-(gradation-1)*2-1)*4),in,gradation+1,end); for (int i = 0;i < (in-(gradation-1)*2)-1; i++) { temp[gradation-1][i+gradation-1] = new Integer(seq+i); temp[i+gradation-1][in-gradation] = new Integer(seq+(in-(gradation-1)*2)-1+i); temp[in-gradation][in-gradation-i] = new Integer(seq+((in-(gradation-1)*2)-1)*2+i); temp[in-gradation-i][gradation-1] = new Integer(seq+((in-(gradation-1)*2)-1)*3+i); } return temp; } } |
| 返回顶楼 | |
|
发表时间：2009-12-11
5x5 (5,4;4,3;3,2;2,1;1,0)
6x6 (6,5;5,4;4,3;3,2;2,1;1,0) |
| 返回顶楼 | |
|
发表时间：2009-12-11
最后修改：2009-12-11
花半个小时写的，比较粗糙
public class Print {
int startNumber = 1;
public Print() {
}
// public void
public void doPrint(int number) {
String[][] row = null;
row = init(row, number);
printMatrix(row, number);
int size=number;
System.out.println("new Matirx");
int x=0;
for (;number>2;number=number-1){
row = setValue(row, number,x);
x++;
}
printMatrix(row, size);
}
public String[][] setValue(String[][] row, int number, int x) {
for (int q = 0; q < 4; q++) {
for (int i = 0; i < number; i++) {
if (q == 0)
if (row[x][i].equals("x"))
row[x][i] = String.valueOf(startNumber);
else
startNumber--;
if (q == 1)
if (row[i][number - 1].equals("x"))
row[i][number - 1] = String.valueOf(startNumber);
else
startNumber--;
if (q == 2)
if (row[number - 1][number - 1 - i].equals("x"))
row[number - 1][number - 1 - i] = String
.valueOf(startNumber);
else
startNumber--;
if (q == 3)
if (row[number - 1 - i][x].equals("x"))
row[number - 1 - i][x] = String.valueOf(startNumber);
else
startNumber--;
startNumber++;
}
}
return row;
}
public String[][] init(String[][] row, int size) {
row = new String[size][size];
for (int i = 0; i < size; i++) {
for (int q = 0; q < size; q++)
row[i][q] = "x";
}
return row;
}
public void printMatrix(String[][] row, int size) {
for (int i = 0; i < size; i++) {
for (int q = 0; q < size; q++)
System.out.print(row[i][q] + ",");
System.out.println("\n");
}
}
}
|
| 返回顶楼 | |
|
发表时间：2009-12-12
最后修改：2009-12-12
在下从物理学角度出发，贴个代码：
package movement;
/**
*
* @author PS
*
*/
public class Point {
private int x;
private int y;
private int value;
public Point(){}
public Point(int x,int y,int value){
this.x=x;
this.y=y;
this.value=value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
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;
}
}
-----------------------------------------------------------
package movement;
public class Direct {
public static final int RIGHT=1;
public static final int DOWN=2;
public static final int LEFT=3;
public static final int UP=4;
}
-----------------------------------------------------------
package movement;
import java.util.ArrayList;
import java.util.List;
public class Track {
public static final int[] sequence={Direct.RIGHT,Direct.DOWN,Direct.LEFT,Direct.UP};
private int currentDirect=sequence[0];
private int size;
private Point currentPoint=new Point(0,0,1);
private List<Point> pointList=new ArrayList<Point>();
private int getNextDirect(){
int i=0;
for(;i<sequence.length;i++){
if(currentDirect==sequence[i]) break;
}
if(i!=sequence.length-1){
return sequence[++i];
}else{
return sequence[0];
}
}
private boolean isExist(Point p){
for(Point o:pointList){
if(p.getX()==o.getX()&&p.getY()==o.getY()){
return true;
}
}
return false;
}
private Point countNextPoint(Point p,int direct){
Point o=new Point();
switch(direct){
case Direct.RIGHT:
o.setX(p.getX()+1);
o.setY(p.getY());
break;
case Direct.DOWN:
o.setX(p.getX());
o.setY(p.getY()+1);
break;
case Direct.LEFT:
o.setX(p.getX()-1);
o.setY(p.getY());
break;
case Direct.UP:
o.setX(p.getX());
o.setY(p.getY()-1);
break;
}
o.setValue(p.getValue()+1);
return o;
}
private void createPointList(){
while(this.currentPoint.getValue()<=size*size){
pointList.add(this.currentPoint);
//计算下一个currentPoint
Point nextPoint=countNextPoint(currentPoint, currentDirect);
//下一个点越界或者位置已经被占据，则变向，并重新计算下一个点
if(nextPoint.getX()<0||nextPoint.getX()>=size
||nextPoint.getY()<0||nextPoint.getY()>=size
||isExist(nextPoint)){
currentDirect=getNextDirect();
nextPoint=countNextPoint(currentPoint, currentDirect);
}
currentPoint=nextPoint;
}
}
public Point[][] getPointArray(){
createPointList();
Point[][] valueArray=new Point[size][size];
for(Point p:pointList){
valueArray[p.getY()][p.getX()]=p;
}
return valueArray;
}
public void setSize(int size) {
this.size = size;
}
public static void main(String[] args) {
long beginTime=System.currentTimeMillis();
int size=10;
Track t=new Track();
t.setSize(size);
Point[][] valueArray=t.getPointArray();
int len=(size*size+"").length();
int blankLen=0;
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
blankLen=len-(valueArray[i][j].getValue()+"").length();
for(int k=0;k<blankLen;k++){
System.out.print(" ");
}
System.out.print(valueArray[i][j].getValue()+" ");
}
System.out.println();
}
System.out.println("用时："+(System.currentTimeMillis()-beginTime)+"ms");
}
}
|
| 返回顶楼 | |
