Samsung机试题分析

摘要：之前介绍，机试题主要考察分析和逻辑能力，不会用到复杂的算法，而且现场也不能使用除了输入输出流之外的其他的库或包。判断条件为，实际调试时出错，这块分析不严谨。

3月1日，三星电子研究所公司机试。
之前HR介绍，机试题主要考察分析和逻辑能力，不会用到复杂的算法，而且现场也不能使用除了输入输出流之外的其他的库或包。

在公司的一间机试屋子考试，有VisualStudio和Eclipse两种编译器可选。机试有专门的系统，可以查看题目，并且在下方编程（没有提示，得全程手打，而且不提醒语法错误，建议用编译器），该页面同时可以进行测试案例调试，运行后可得编译结果（会提示语法错误和异常）提供参考。调试次数不限，提交（submit）次数为三次，提交后，屏幕会弹出本地10个case的通过情况，通过为pass，后台还有其他case，所以最终结果还得等总部过几天的反馈。机试总共3小时，系统界面和题目都是英语，手机得飞行模式，现场提供纸笔。

原题记不太清了，大致意思如下：
给一个10×10的表格（grid），其中放置有2×1的方块（blocks），方块和横竖放置。让表格中的方块自由下落（类似俄罗斯方块），堆积在底部。表格中有方块占有的格子用1表示，没有的用0表示。用数字0-10表示下落后，每列的方块高度。

图1：方块降落前

图2：方块降落后

注：题目要求方块不能全部靠在左侧、右侧、上侧或下侧，而且下边这种连续放置方块的情况也不允许（题目中英文没全看懂，个人理解）。这个条件尤其要注意，中途写完程序，就是忽略了这个约束，结果老是不对。

1、Input

0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0
0  0  0  1  0  0  0  1  1  0   
0  0  0  1  0  0  0  0  0  0  
1  1  0  0  0  0  0  0  0  0  
0  0  0  0  1  1  0  0  0  0  
0  1  1  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  1  0  0  
0  0  0  0  0  0  0  1  0  0  
0  0  0  0  0  0  0  0  0  0
…… 
共10个case

2、Output

*1 2212110330 
…… 
10个case，每个case的结果都按行输出(*1表示case1）

首先，本题是计算落下方块的高度。从下往上，方块是堆叠起来的，也就是说，上层的方块降落点取决于下层的方块位置。因此，思路是从下向上，按行迭代分析。再将问题拆解，每行迭代的时候，可以从左向右分析。

设输入表格元素数组为A11，输出的高度数组为height[11]，两者都从1迭代（输入从索引1开始赋值）。

比如：图1第一行，从A10到A10，遍历后，数值都为0，则当前的每列高度都为0，height[k]=0;从第二行开始，A9的元素就变为1，height[8]=1,实际的输入case情况复杂，因此需要定义遍历计算的规则。

按照上诉思路，构建两层for循环，外层i：10~1，内层j：1-10。对于2×1的方块，有两种下落姿态，水平和竖直放置下落。对于竖直下落而言，无论下方多么复杂，该方块永远都是直接落在过程中第一个看到的方块。在迭代时，对于竖直下落方块，每行直接对height加1即可。

对于水平放置方块，情况比较复杂。首先方块横向是一个整体，下落位置受两个子块下方堆叠情况影响。作图分析：

当前迭代列为j，首先考虑当前为1的方格（黑色），其构成的方块的另一半，在其左侧还是右侧。如果在右侧，右侧的方块子块降落会由当前子块决定，不用分析。如果在左侧，那么当前子块的落点取决于左侧兄弟子块的下方和当前列下方情况。自然的，如果左高右低，那么横块将搭在左侧，右侧子块落点同左侧。判断条件为：if(height[j-1]>height[j])，实际调试时出错，这块分析不严谨。
实际情况如下：

由于当前子块与左侧子块相连，迭代到当前列i时，左侧子块对应的height[j]已进行自加，实际条件应为：height[j-1]-1 > height[j]。也就是说，左侧height减1后，与右侧height大小，若左侧大，height[j]=height[j-1]。否则height[j]自加。

由于对第i列迭代时，直接操作左右两侧的Ai和height[j-1]，调试时发生数组索引越界异常。因此在循环内部，首先处理两种特殊情形：

简化案例输入过程，直接在主函数定义一个case数组，方法也直接写在主函数中。

public class ExamSamsun {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[][] A={{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,1,0,0,0,1,1,0},{0,0,0,0,1,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,1,1,0,0,0,0},{0,0,1,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,1,0,0},
            {0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,0,0,0,0}};
        
                
        int[] height=new int[11];  //测试例结果应为1 1 2 2 1 2 1 1 0 3 0 0 
        for(int i=10;i>=1;i--) {
            for(int j=1;j<=10;j++) {
                if(A[i][j]==1) {
                    //特殊情况
                    if(j==1&&A[i][j+1]==1) {
                        if(height[j+1]>height[j])
                            height[j]=height[j+1]+1;
                        else
                            height[j]++;
                        continue; //当前列已迭代完，执行下列
                    }                        
                    if(j==10&&A[i][j]==1) {
                        if(height[j-1]-1>height[j])
                            height[j]=height[j-1];
                        else
                            height[j]++;
                        continue;
                    }
                    //一般情形
                    if(j>=2&&j<=9) {
                        if(A[i][j-1]==1) {
                            if(height[j-1]-1>height[j])
                                height[j]=height[j-1];
                            else
                                height[j]++;
                            continue;
                        }
                        
                        if(A[i][j+1]==1) {
                            if(height[j+1]>height[j])
                                height[j]=height[j+1]+1;
                            else
                                height[j]++;
                            continue;
                        }
                        height[j]++;
                    }
                    
                }
                
            }//inner
        }//outer
            
        
        //output
        for(int i=1;i<=10;i++)
            System.out.print(height[i]+" ");
        }

}

写完后，又想了一遍，觉得对当前Ai=1的格子向前判断似乎重复了，后续有空再简化下程序。