黑马程序员技术交流社区

标题: 今天同学问了一个面试题，大家共同想想解决方法 [打印本页]
作者: 孟伟娟    时间: 2012-12-3 19:11
标题: 今天同学问了一个面试题，大家共同想想解决方法
腾讯面试题：   
给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数   
要求下排每个数都是先前上排那十个数在下排出现的次数。   
上排的十个数如下：   
【0，1，2，3，4，5，6，7，8，9】

初看此题，貌似很难，10分钟过去了，可能有的人，题目都还没看懂。   

举一个例子，   
数值: 0,1,2,3,4,5,6,7,8,9   
分配: 6,2,1,0,0,0,1,0,0,0   
0在下排出现了6次，1在下排出现了2次，   
2在下排出现了1次，3在下排出现了0次....   
以此类推..   
作者: 黑马_张伟    时间: 2012-12-3 20:34
我只能得出一个解，就是你这个，方法很简单，排除法。7,8,9是不能有的，所以不管怎么排不能有7，8,9，即7,8,9之下是0；然后看6，假设6下是1，0又有3以上个，所以0下面是大于等于3的数，但是1下面至少有个1，所以不能是4,5。但是如果是3，就溢出了。所以0下面只能是6。5和4下面肯定是0。这样找出来了5个0，还差一个，但是如果3下面是1,1下面最小就是2了，又溢出，所以3下面是0.结果就显而易见了，6,2,1,0,0,0,1,0,0,0。
作者: 黑马_张伟    时间: 2012-12-3 20:34
同理可以推出其他数字的，我没有找出来合适的。应该就这一个解吧
作者: 孟伟娟    时间: 2012-12-4 09:55
黑马_张伟 发表于 2012-12-3 20:34
同理可以推出其他数字的，我没有找出来合适的。应该就这一个解吧

嗯，是只有一个解，面试题要写出程序，把该解求出来。
作者: 孟伟娟    时间: 2012-12-4 10:02
昨天想了一晚上，我同学给了我点思路，终于把代码想出来了。
  1. public class InterviewTest {

  3.      public static void main(String[] args) {
  4.          //上面的一行数组
  5.         int[] arr = {0,1,2,3,4,5,6,7,8,9};
  6.         //计算下一行数组
  7.         computeArr(arr);
  8.     }

  10.    private static void computeArr(int[] arr) {
  11.        //先把下一行数组任意初始化，循环不断更正，知道符合规则为止
  12.        int[] cou = {1,0,2,0,6,4,1,3,2,0};
  13.       //存储对应数字出现的次数
  14.      int sum = 0;
  15.      //大循环标记，初始为true
  16.     boolean flag = true;
  17.    //大循环
  18.   while(flag){
  19.        //记录检查是否符合规则时，下一行数组首次不符合规则的下标
  20.        int index = 0;
  21.       for(int i=0; i<arr.length; i++){
  22.           sum = count(arr[i],cou);
  23.           cou[i]=sum;
  24.      }
  25.      //检查下一行数组是否符合规则，如果符合，退出大循环
  26.      for(int i=0;i<arr.length;i++){
  27.          sum = count(arr[i],cou);
  28.         if(cou[i]!=sum){
  29.              index = i;
  30.              break;
  31.         }
  32.         index = i;
  33.     }
  34.     //如果检查到最后，所有的都正确，即符合规则，把大循环标记置为false，跳出大循环。
  35.    if(index == arr.length-1)
  36.        flag = false;
  37.    print(arr);
  38.    print(cou);
  39.   }
  40. }
  41. //打印数组
  42. private static void print(int[] cou) {
  43.     for(int c : cou){
  44.        System.out.print(c +", ");
  45.     }
  46.     System.out.println();
  47. }

  49. //数对应数字出现的次数
  50. private static int count( int x,int[] cou) {
  51.     int count=0;
  52.     for(int i=0; i<cou.length;i++){
  53.         if(cou[i] == x){
  54.            count++;
  55.          }
  56.      }
  57.     return count;
  58. }

  60. }
复制代码
打印结果为：
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
3, 1, 2, 2, 1, 0, 0, 0, 0, 0,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
5, 2, 3, 1, 0, 1, 0, 0, 0, 0,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
5, 2, 1, 0, 0, 1, 0, 0, 0, 0,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
6, 2, 1, 0, 0, 0, 1, 0, 0, 0,
为了检验大循环每次更改下一行数组的情况，我把每次的结果打印了出来，最后一组为正确结果。当然，正式程序，要把这些打印中间的内容去掉。直接显示最后正确结果就可以了。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2