金蝶笔试题

Question

昨天去金蝶做笔试，下面是其中的两个，望大人们能给个不错的答案，大家都学习学习。
1 优化下面这段代码，并说明原因
 for(int i =0; i < 1000; i++)
    for (int j=0; j < 100; j++)
       for (int k = 0; k < 10; k++)
           fun(i, j, k);
2:怎样判断一个单向链表是一个闭环（链表的最后一个节点指向链表其中的一个节点），考虑最优方案。
    

Answer 1

  for (int k = 0; k < 10; k++) 
  for (int j=0; j < 100; j++)
  for(int i =0; i < 1000; i++)
  fun(i, j, k);这样  ，，，，

Answer 2

for (int k = 0; k < 10; k++)  
  for (int j=0; j < 100; j++)
  for(int i =0; i < 1000; i++)
  fun(i, j, k);
 这样是有优化，主要是节省了栈的切换频率

Answer 3

问题1： 节省的是 大小比较和++的次数 ，所以性能要高点问题2 ： 对这个列表进行遍历，每次遍历都把节点放到HashSet里，再判断该节点的next节点是否在HashSet里，如果在，就说明是闭环。遍历结束后，如果都不在，则说明不是闭环。

Answer 4

只适用于这种情况吧: A-->B--->C--->B
A-->B--->C--->D--->E--->F--->B这种情况就不适用了吧还是我理解错了？请指教

Answer 5

这个算法很经典
楼主可能没看清楚，单向链表，都想一个方向走，只是步长不同而已看看这里：
http://www.chinaunix.net/jh/23/410637.html

Answer 6

for(int i =0; i < 1000; i++)               1001
  for (int j=0; j < 100; j++)              1000*101
  for (int k = 0; k < 10; k++)             1000*101*11
 fun(i, j, k);                             1000*100*10for (int k = 0; k < 10; k++)               11
  for (int j=0; j < 100; j++)              10*101
  for(int i =0; i < 1000; i++)             10*101*1001
 fun(i, j, k);                             10*100*1000

Answer 7

第一个：
for (int k = 0; k < 10; k++){
    for (int j=0; j < 100; j++){
        for(int i =0; i < 1000; i++){
           fun(i, j, k);
        }
   }
}
虽然循环次数相同，但是层与层之间的切换次数减少，可以提升效率。第二个问题：
我有个思路，可能效率不是最高的。我的思路是按照顺序读取链表，然后没读取一个就记录下当前位置和当前位置指向的下一个位置，然后判断当前位置的下一个位置是否前面已读取过。当然，要自己写一个辅助结果去记录。

Answer 8

补充一下~http://topic.csdn.net/u/20090713/19/780e5a72-caa2-4392-ba60-f93dc1a98c02.html