N***m
发帖数: 4460 | 1 看到c/c++笔试问题一道，估计是经典问题了。
=======================================
编程输出以下格式的数据。（趣味题）
a) When i=0
1
b) When i=1
7 8 9
6 1 2
5 4 3
c) When i=2
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
=============================
我用java写了一段程序，试了前几个i=1,2,3,4,能工作，但是感觉写的很罗嗦。
有没有更好的Idea?
======================
附：我的臃肿的java code.
[Main.java]
public class Main {
public static void main(String[] args) throws Exception {
FormatOutput.fill();
}
}
[FormatOutput.java]
public class FormatOutput {
static int n = 2;
static int[][] arr = new int[2*n+1][2*n+1];
public static Position findNext(Position current) throws Exception {
Position next = null;
int x = current.row;
int y = current.col;
double minDistance = (2*n+1)*(2*n+1);
char minDirection = 'e';
// along row first
for(int i=-1,j=0;i<=1;i+=2) {
if(!validate(x+i,y+j) || arr[x+i][y+j]>0)
continue;
Position temp = new Position(x+i,y+j);
if(temp.getDistance()
minDistance = temp.getDistance();
minDirection = getDirection(i,j);
next = temp;
}
if(temp.getDistance()==minDistance) {
if(getDirection(i,j)=='d') {
minDistance = temp.getDistance();
minDirection = getDirection(i,j);
next = temp;
}
}
}
// then along column
for(int j=-1, i=0;j<=1;j+=2) {
if(!validate(x+i,y+j) || arr[x+i][y+j]>0)
continue;
Position temp = new Position(x+i,y+j);
if(temp.getDistance()
minDistance = temp.getDistance();
minDirection = getDirection(i,j);
next = temp;
}
if(temp.getDistance()==minDistance) {
if(getDirection(i,j)=='r') {
minDistance = temp.getDistance();
minDirection = getDirection(i,j);
next = temp;
}
}
}
/*if(next==null)
System.out.println("not found @ "+ current.row+","+current.col);
*/
return next;
}
//validate array index not out of bound
public static boolean validate(int x,int y) {
if(x>=0 && x<2*n+1 && y>=0 && y<2*n+1)
return true;
else
return false;
}
public static char getDirection(int i,int j) throws Exception {
if(i!=0&&j!=0) {
throw new Exception("format error");
}
else {
if(i==-1)
return 'u';
if(i==1)
return 'd';
if(j==-1)
return 'l';
if(j==1)
return 'r';
}
return 'e';
}
public static void fill() throws Exception {
int i,j;
if(n==0) {
System.out.println(n+1);
return;
}
for(i=0;i<2*n+1;i++)
for(j=0;j<2*n+1;j++)
arr[i][j] = -1;
arr[n][n] = 1;
arr[n][n+1] = 2;
int filled = 2;
Position old = new Position(n,n+1);
Position next;
boolean done = false;
while(filled<=(2*n+1)*(2*n+1)&&!done) {
try {
if((next=findNext(old))!=null) {
filled++;
int y = next.col;
int x = next.row;
arr[x][y] = filled;
old = next;
}
else
done = true;
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
for(i=0;i<2*n+1;i++) {
for(j=0;j<2*n+1;j++)
System.out.format("%3d ",arr[i][j]);
System.out.println();
}
}
}
[Position.java]
public class Position {
int row, col;
private int n = FormatOutput.n;
public Position(int x,int y) {
row = x;
col = y;
}
public int getDistance() {
return (row-n)*(row-n)+(col-n)*(col-n);
}
} |
t****t
发帖数: 6806 | 2 经典题google一下就好了..
【在 N***m 的大作中提到】
: 看到c/c++笔试问题一道，估计是经典问题了。
: =======================================
: 编程输出以下格式的数据。（趣味题）
: a) When i=0
: 1
: b) When i=1
: 7 8 9
: 6 1 2
: 5 4 3
: c) When i=2
|
t****t
发帖数: 6806 | 3 顺便说一下, 这个题是不需要先存一个二维数组的.
【在 N***m 的大作中提到】
: 看到c/c++笔试问题一道，估计是经典问题了。
: =======================================
: 编程输出以下格式的数据。（趣味题）
: a) When i=0
: 1
: b) When i=1
: 7 8 9
: 6 1 2
: 5 4 3
: c) When i=2
|
N***m
发帖数: 4460 | 4 google过一下，有个用c++二叉数的，没看懂。
所以希望有兴趣的铜锈能给个实现的思路。
【在 t****t 的大作中提到】
: 经典题google一下就好了..
|
N***m
发帖数: 4460 | 5 这个我同意。我的代码段里面是可以去掉这个二唯数组的，
只要改成记录前面一布的信息直接打印出来就可以了。
现在放在哪里只要是为了调试方便：）
【在 t****t 的大作中提到】
: 顺便说一下, 这个题是不需要先存一个二维数组的.
|
t****t
发帖数: 6806 | 6 我的意思是, 你根本不需要什么方向, 前一步的信息. 给定坐标, 尺寸, 就直接可以算
是多少. 换句话你不需要螺旋, 你可以一行一行打印. 相反, 如果你螺旋, 就一定需要
数组, 因为cout不能后退.
【在 N***m 的大作中提到】
: 这个我同意。我的代码段里面是可以去掉这个二唯数组的，
: 只要改成记录前面一布的信息直接打印出来就可以了。
: 现在放在哪里只要是为了调试方便：）
|
N***m
发帖数: 4460 | 7 sigh，没看明白你是怎么实现的。
【在 t****t 的大作中提到】
: 我的意思是, 你根本不需要什么方向, 前一步的信息. 给定坐标, 尺寸, 就直接可以算
: 是多少. 换句话你不需要螺旋, 你可以一行一行打印. 相反, 如果你螺旋, 就一定需要
: 数组, 因为cout不能后退.
|
t****t
发帖数: 6806 | 8 这有什么难理解的, 你给定尺寸每个数字都是已知的. 你直接算就行了.
【在 N***m 的大作中提到】
: sigh，没看明白你是怎么实现的。
|
t****t
发帖数: 6806 | 9 花10分钟做一下好了, 因为我google到的也都是二维数组.
#include
#include
#include
#include
#include
using namespace std;
int calc(int y, int x, int sz)
{
y=y-sz; x=x-sz;
int level = max(abs(y), abs(x));
if (level==0) return 1;
int levelend = (level*2+1)*(level*2+1);
/* which side? */
if (y==-level) {
/* top */
return levelend+x-level;
}
levelend-=2*level;
if (x==-level) {
/* left */
return levelend-y-level;
}
levelend-=2*level;
if (y==level) {
/* bottom */
return levelend-x-level;
}
levelend-=2*level;
return levelend+y-level;
}
int main()
{
int size;
cin>>size;
int s1=2*size+1;
for (int i=0; i
for (int j=0; j
cout<
}
cout<<"\n";
}
return 0;
}
【在 t****t 的大作中提到】
: 这有什么难理解的, 你给定尺寸每个数字都是已知的. 你直接算就行了.
|
N***m
发帖数: 4460 | 10 admire,我啥时候研究一下。
【在 t****t 的大作中提到】
: 花10分钟做一下好了, 因为我google到的也都是二维数组.
: #include
: #include
: #include
: #include
: #include
: using namespace std;
: int calc(int y, int x, int sz)
: {
: y=y-sz; x=x-sz;
|
|
|
g**e
发帖数: 6127 | 11 每一层四个角的数字从左到有从上到下分别是(2i+1)^2-2i, (2i+1)^2, (2i+1)^2-4i,
(2i+1)^2-6i
剩下的就好办了。
【在 t****t 的大作中提到】
: 我的意思是, 你根本不需要什么方向, 前一步的信息. 给定坐标, 尺寸, 就直接可以算
: 是多少. 换句话你不需要螺旋, 你可以一行一行打印. 相反, 如果你螺旋, 就一定需要
: 数组, 因为cout不能后退.
|
g*****g
发帖数: 34805 | 12 这个题有嘛好做的？动态生成一个2维数组，算出坐标转着圈打过去就是了。
再牛逼的数据结构也是O(N^2)的计算复杂度。除非对空间复杂度有要求，不折腾。 |
N***m
发帖数: 4460 | 13 我也不想做啊，可是毕竟是面试题。哎，不说了。
【在 g*****g 的大作中提到】
: 这个题有嘛好做的？动态生成一个2维数组，算出坐标转着圈打过去就是了。
: 再牛逼的数据结构也是O(N^2)的计算复杂度。除非对空间复杂度有要求，不折腾。
|
t****t
发帖数: 6806 | 14 什么数据结构啊, 要的就是省掉那个数组.
【在 g*****g 的大作中提到】
: 这个题有嘛好做的？动态生成一个2维数组，算出坐标转着圈打过去就是了。
: 再牛逼的数据结构也是O(N^2)的计算复杂度。除非对空间复杂度有要求，不折腾。
|
g*****g
发帖数: 34805 | 15 这年头内存白菜价，绝大多数情况下写个好读的程序
比省那个数组有意义多了。
【在 t****t 的大作中提到】
: 什么数据结构啊, 要的就是省掉那个数组.
|
N***m
发帖数: 4460 | 16 CSDN上讨论得很热烈，据说java要完蛋了。
不知道刚自学了java有没有用。枣子道学c#了。
【在 g*****g 的大作中提到】
: 这年头内存白菜价，绝大多数情况下写个好读的程序
: 比省那个数组有意义多了。
|
t****t
发帖数: 6806 | 17 可是明显我的程序也比他的好读啊!
【在 g*****g 的大作中提到】
: 这年头内存白菜价，绝大多数情况下写个好读的程序
: 比省那个数组有意义多了。
|
g*****g
发帖数: 34805 | 18 等你学好了C#，C#就完蛋了。
【在 N***m 的大作中提到】
: CSDN上讨论得很热烈，据说java要完蛋了。
: 不知道刚自学了java有没有用。枣子道学c#了。
|
N***m
发帖数: 4460 | 19 你这打击面太深了，5555555555555555
【在 g*****g 的大作中提到】
: 等你学好了C#，C#就完蛋了。
|
g*********s
发帖数: 1782 | 20 O(N^2) in space is much worse than O(1).
mem is not cheap for large programs.
【在 g*****g 的大作中提到】
: 这年头内存白菜价，绝大多数情况下写个好读的程序
: 比省那个数组有意义多了。
|
|
|
g*****g
发帖数: 34805 | 21 When was the last time you need one time printout of a huge
two dimension array and not have the need to reuse it in
practice?
Premature optimization is evil.
【在 g*********s 的大作中提到】
: O(N^2) in space is much worse than O(1).
: mem is not cheap for large programs.
|
g**e
发帖数: 6127 | 22 面试就喜欢搞这些
【在 g*****g 的大作中提到】
: When was the last time you need one time printout of a huge
: two dimension array and not have the need to reuse it in
: practice?
: Premature optimization is evil.
|
t****t
发帖数: 6806 | 23 premature optimization?
if you already have a NxN matrix and you take effort to remove it, it's
optimization. if you know you could do it without it, and you add it just to
waste memory and write longer program, this is called 脱裤子放屁.
Especially in this case, adding a NxN matrix doesn't buy you anything since
the spiral logic is always there. you don't save time, you don't make
program shorter or easier to understand, you just waste memory.
【在 g*****g 的大作中提到】
: When was the last time you need one time printout of a huge
: two dimension array and not have the need to reuse it in
: practice?
: Premature optimization is evil.
|
g*****g
发帖数: 34805 | 24
to
since
It may not be shorter, but it's easier to figure out the logic. Without
google
it probably takes less time to develop.
In real world, the common 2D array printout is image, and you pass the
entire array, not to paint one pixel at a time. Buffering is always
necessary
for big N, even for simple std out you want to concatenate using a string
buffer first. I can guarrantee 10 times better performance for a real
big N, is that really a waste of memory?
In any sense, if you want to
optimize the generation of a huge 2D array, multi-thread processing and grid
processing using framework like hadoop will
be the first thing I consider, the space requirement is very secondary,
more than likely you'll hit computing power issue first if N is really big.
【在 t****t 的大作中提到】
: premature optimization?
: if you already have a NxN matrix and you take effort to remove it, it's
: optimization. if you know you could do it without it, and you add it just to
: waste memory and write longer program, this is called 脱裤子放屁.
: Especially in this case, adding a NxN matrix doesn't buy you anything since
: the spiral logic is always there. you don't save time, you don't make
: program shorter or easier to understand, you just waste memory.
|
t****t
发帖数: 6806 | 25 easier to figure out logic? tell me Natom's program is "easier" to figure
out logic than mine. BTW i didn't use google to write my program; i took
about 10 mins to wrote it when i was having breakfast this morning. i can
use matrix (spiral filling) too, but i doubt i can finish it with less time.
now you mentioned multithread processing. for MT, independent calculation (
pixel by pixel) is even more important. thanks for supporting me and beat
yourself.
to
【在 g*****g 的大作中提到】
:
: to
: since
: It may not be shorter, but it's easier to figure out the logic. Without
: google
: it probably takes less time to develop.
: In real world, the common 2D array printout is image, and you pass the
: entire array, not to paint one pixel at a time. Buffering is always
: necessary
: for big N, even for simple std out you want to concatenate using a string
|
g*****g
发帖数: 34805 | 26 OK, you have some good point here. But how don't you just conflict
your claim the array is a waste of memory?
time.
【在 t****t 的大作中提到】
: easier to figure out logic? tell me Natom's program is "easier" to figure
: out logic than mine. BTW i didn't use google to write my program; i took
: about 10 mins to wrote it when i was having breakfast this morning. i can
: use matrix (spiral filling) too, but i doubt i can finish it with less time.
: now you mentioned multithread processing. for MT, independent calculation (
: pixel by pixel) is even more important. thanks for supporting me and beat
: yourself.
:
: to
|
t****t
发帖数: 6806 | 27 now show some sense, would you? obviously it all depends on requirement. but
what's the requirement here?
e.g. most sort algorithms are in-place, then we say adding another array is
a waste. but you may need to keep the original, or use some large scale
thing (merge sort, etc), then you use extra space, which is not a waste.
back to our original problem, even if you use MT, you probably still don't
need the whole array.
【在 g*****g 的大作中提到】
: OK, you have some good point here. But how don't you just conflict
: your claim the array is a waste of memory?
:
: time.
|
g*****g
发帖数: 34805 | 28
but
there's no requirement, but common sense is you'll need some buffering for
huge array printout. So I don't buy the waste of memory thing.
sorting is obviously different.
is
【在 t****t 的大作中提到】
: now show some sense, would you? obviously it all depends on requirement. but
: what's the requirement here?
: e.g. most sort algorithms are in-place, then we say adding another array is
: a waste. but you may need to keep the original, or use some large scale
: thing (merge sort, etc), then you use extra space, which is not a waste.
: back to our original problem, even if you use MT, you probably still don't
: need the whole array.
|
N***m
发帖数: 4460 | 29 Compared to your code, my code is easier to understand, at least for me:)
(I still don't understand your code, sorry.)
My logic is simple and the method can be extended to any pattern,not
just this spiral one. With some moderate change, the code is
supposed to be capable of handling irregular format as well.
(sounds like a commercial,hehe, but that's what I thought from the beginning)
time.
【在 t****t 的大作中提到】
: easier to figure out logic? tell me Natom's program is "easier" to figure
: out logic than mine. BTW i didn't use google to write my program; i took
: about 10 mins to wrote it when i was having breakfast this morning. i can
: use matrix (spiral filling) too, but i doubt i can finish it with less time.
: now you mentioned multithread processing. for MT, independent calculation (
: pixel by pixel) is even more important. thanks for supporting me and beat
: yourself.
:
: to
|
S*********g
发帖数: 5298 | 30 首先，这是一道面试题。
脱离背景来谈哪个解法是最好的都是虚无的。
出这种题，真的只是看你会不会写程序？
我觉得未必，更重要的部分看你解决问题的方法和能力。
如果是google出的题，以google的背景来看，他们需要处理海量的数据和请求。
很显然，他们的工作中需要你对程序的效率（时间和空间上的效率）做优化
如果google的人出这道题了，
那么我预期是google的面试官人看thrust的解法是更容易懂的，而且是更优的。
thrust的code如果你没看懂，那不是code本身写的隐晦。
而是你没看懂他背后的数学逻辑，
这部分我想应该也是google出这道面试题要考的一部分吧。
说实在的，他的解法，数学很难吗？不难，我觉得你没用心去想而已。
另外，个人建议你，这些题，听完别人讲了，自己花点时间弄弄明白。
对你找工作也好，真的写程序也好，都有很大的好处。
写程序这东西，没有捷径。就是要多些多想,多上手。
beginning)
【在 N***m 的大作中提到】
: Compared to your code, my code is easier to understand, at least for me:)
: (I still don't understand your code, sorry.)
: My logic is simple and the method can be extended to any pattern,not
: just this spiral one. With some moderate change, the code is
: supposed to be capable of handling irregular format as well.
: (sounds like a commercial,hehe, but that's what I thought from the beginning)
:
: time.
|
|
|
S*********g
发帖数: 5298 | 31 另外，这个数学解法很简单，
两条对角线上的数字都可以很容易算出来。
剩下其他的你就和这四个角的距离推就是了。
beginning)
【在 N***m 的大作中提到】
: Compared to your code, my code is easier to understand, at least for me:)
: (I still don't understand your code, sorry.)
: My logic is simple and the method can be extended to any pattern,not
: just this spiral one. With some moderate change, the code is
: supposed to be capable of handling irregular format as well.
: (sounds like a commercial,hehe, but that's what I thought from the beginning)
:
: time.
|
N***m
发帖数: 4460 | 32 right, in this particular case, you can always derive it.
I just start to make it more flexible and thus inevitably result in
complicacy.
【在 S*********g 的大作中提到】
: 另外，这个数学解法很简单，
: 两条对角线上的数字都可以很容易算出来。
: 剩下其他的你就和这四个角的距离推就是了。
:
: beginning)
|
N***m
发帖数: 4460 | 33 原来是google面试题，呵呵。你说得在理，收下了。
anyway,继续编程去了，日编三百行，直到拿到offer.
【在 S*********g 的大作中提到】
: 首先，这是一道面试题。
: 脱离背景来谈哪个解法是最好的都是虚无的。
: 出这种题，真的只是看你会不会写程序？
: 我觉得未必，更重要的部分看你解决问题的方法和能力。
: 如果是google出的题，以google的背景来看，他们需要处理海量的数据和请求。
: 很显然，他们的工作中需要你对程序的效率（时间和空间上的效率）做优化
: 如果google的人出这道题了，
: 那么我预期是google的面试官人看thrust的解法是更容易懂的，而且是更优的。
: thrust的code如果你没看懂，那不是code本身写的隐晦。
: 而是你没看懂他背后的数学逻辑，
|
S*********g
发帖数: 5298 | 34 我是举个例子，如果这是google出的题，那么肯定希望你考虑优化。
其实不管是哪个公司出的题，都会希望看到你这个思考怎么优化的过程。
【在 N***m 的大作中提到】
: 原来是google面试题，呵呵。你说得在理，收下了。
: anyway,继续编程去了，日编三百行，直到拿到offer.
|
N***m
发帖数: 4460 | 35 我现在有个坏习惯，一上来直接写程序，基本编写边思考，都不怎么考虑优化，
所以写出来的又臭又长。这个坏习惯其实一直都有，主要是以前编程序的时候习惯了。
更要命的是，自从看了设计模式以后，感觉落下病根了，
啥玩艺都想往设计模式上套。其实年纪大了是不是都这样，不喜欢做具体的题目，
喜欢搞个general的东西，一次搞定。
【在 S*********g 的大作中提到】
: 我是举个例子，如果这是google出的题，那么肯定希望你考虑优化。
: 其实不管是哪个公司出的题，都会希望看到你这个思考怎么优化的过程。
|
N***m
发帖数: 4460 | 36 sigh,我知道我不是去这些公司的料。我只希望能拿到一个搞应用的j2ee的offer，
那就谢天谢地了。我要去翻翻算命的书，最近几只股票大跌，损失惨重，
希望股场失意，职场得意！
/ —— \ |
S*********g
发帖数: 5298 | 37 一个人单枪匹马写程序的话，就容易这样吧。
我没有设计大程序的经验。唯一一点写大一点程序的经验也是10几年前的。
那时候在国内兼职写ERP做的时候，什么东西都是有文档有很清楚的要求。
就是把那些功能按照要求实现就行了。
再往后，写过最大的还是10几年自己没事写着玩的一个Latex编辑器。
一开始有设计稿。写着写着就开始做改动，就懒得更新了设计文稿了。
最后写完了，基本上和最开始设计的完全不一样。
用了几年之后想动手改点东西，根本无从下手了。
我没有什么设计的经验，不过我想设计和写代码做实现或者做debug都是一样的，
都是靠经验积累的。根据实际问题，实际情况，要做一些实际的调整。
不同的问题，都会有不同的侧重点。有的要求效率高，有的要求实现快。
【在 N***m 的大作中提到】
: 我现在有个坏习惯，一上来直接写程序，基本编写边思考，都不怎么考虑优化，
: 所以写出来的又臭又长。这个坏习惯其实一直都有，主要是以前编程序的时候习惯了。
: 更要命的是，自从看了设计模式以后，感觉落下病根了，
: 啥玩艺都想往设计模式上套。其实年纪大了是不是都这样，不喜欢做具体的题目，
: 喜欢搞个general的东西，一次搞定。
|
S*********g
发帖数: 5298 | 38 问问goodbug有没有招人名额
【在 N***m 的大作中提到】
: sigh,我知道我不是去这些公司的料。我只希望能拿到一个搞应用的j2ee的offer，
: 那就谢天谢地了。我要去翻翻算命的书，最近几只股票大跌，损失惨重，
: 希望股场失意，职场得意！
: / —— \
|
N***m
发帖数: 4460 | 39 right,我还没和别人合作写过程序。其实我连有趣的程序也没编过，
精力都花在解方程上面了。解方程比较routine，虽说模型变来变去，但是
基本思路都差不多，只要仔细，一般一两天就能搞定个2千行的程序。
而且写程序中根本不需要考虑给其他人用，只要程序能跑就成。
但是写商用程序的话肯定不能这样，正如书上讲的，写出来的程序是要给别人读的，
是要给别人重用的。这个不具体实践恐怕也是纸上谈兵。
所以我要力争拿到第一个offer，逐步积累经验，立志做一个合格的程序员！
【在 S*********g 的大作中提到】
: 一个人单枪匹马写程序的话，就容易这样吧。
: 我没有设计大程序的经验。唯一一点写大一点程序的经验也是10几年前的。
: 那时候在国内兼职写ERP做的时候，什么东西都是有文档有很清楚的要求。
: 就是把那些功能按照要求实现就行了。
: 再往后，写过最大的还是10几年自己没事写着玩的一个Latex编辑器。
: 一开始有设计稿。写着写着就开始做改动，就懒得更新了设计文稿了。
: 最后写完了，基本上和最开始设计的完全不一样。
: 用了几年之后想动手改点东西，根本无从下手了。
: 我没有什么设计的经验，不过我想设计和写代码做实现或者做debug都是一样的，
: 都是靠经验积累的。根据实际问题，实际情况，要做一些实际的调整。
|
N***m
发帖数: 4460 | 40 收到：）
【在 S*********g 的大作中提到】
: 问问goodbug有没有招人名额
|
|
|
c****n
发帖数: 21367 | 41 偶觉着这题做之前问一句“what's the value range of n"就可以了
面试官不会无聊到让人做这么简单的printf题目吧。估计就是考察一下有没有
关于问题规模的sense，只要想到这个点，问完了人都未必要你写这个程序。
如果n小，当然不要考虑运算复杂度，用最不容易错，最好验证的方法写
这是用来做算法原型时候的写法
如果n可能很大，再考虑数学规律啥的，毕竟n给定以后所有数字位置都
完全确定，这也太简单了。
【在 t****t 的大作中提到】
: 花10分钟做一下好了, 因为我google到的也都是二维数组.
: #include
: #include
: #include
: #include
: #include
: using namespace std;
: int calc(int y, int x, int sz)
: {
: y=y-sz; x=x-sz;
|
a****l
发帖数: 8211 | 42 我觉得这说的非常有道理。很多问题并没有一定的最优解决方案，关键是限制条件，条
件不一样，解决方法也不一样。这就是学校考试和实际工作的区别.
【在 c****n 的大作中提到】
: 偶觉着这题做之前问一句“what's the value range of n"就可以了
: 面试官不会无聊到让人做这么简单的printf题目吧。估计就是考察一下有没有
: 关于问题规模的sense，只要想到这个点，问完了人都未必要你写这个程序。
: 如果n小，当然不要考虑运算复杂度，用最不容易错，最好验证的方法写
: 这是用来做算法原型时候的写法
: 如果n可能很大，再考虑数学规律啥的，毕竟n给定以后所有数字位置都
: 完全确定，这也太简单了。
|
N***m
发帖数: 4460 | 43 顾客是上帝，顾客的需求永远是对的。
【在 a****l 的大作中提到】
: 我觉得这说的非常有道理。很多问题并没有一定的最优解决方案，关键是限制条件，条
: 件不一样，解决方法也不一样。这就是学校考试和实际工作的区别.
|
i**********e
发帖数: 1145 | 44 Thanks LZ for sharing this interesting question.
Nice solution!
I agree with thrust that there's no need to store a 2d-array, but I think it
doesn't hurt to ask the interviewer which approach he/she wants.
Basically, you need to make an observation that the grid can be divided into
four areas: upper, lower, left, and right.
The equation for the number in the grid's corner is easy to derived.
Then, you can obtain the actual number by adding the difference either in x
or y coordinate relative to the grid's corner.
My solution, although shorter but slightly more complicated, is as below:
#include
#include
using namespace std;
int get(int row, int col) {
int m, s, a;
if (row > col) {
m = max(abs(row), abs(col));
s = 1 + (2*m) * (2*m-1);
a = (m-row) + (m-col);
} else {
m = max(abs(row-1), abs(col));
s = 1 + (2*m-2) * (2*m-1);
a = (m+row-1) + (m+col) - 1;
}
return s+a;
}
int main() {
int n = 3;
for (int row = -n; row <= n; row++) {
for (int col = -n; col <= n; col++) {
cout << setw(3) << get(row, col) << " ";
}
cout << endl;
}
}
【在 t****t 的大作中提到】
: 花10分钟做一下好了, 因为我google到的也都是二维数组.
: #include
: #include
: #include
: #include
: #include
: using namespace std;
: int calc(int y, int x, int sz)
: {
: y=y-sz; x=x-sz;
|
