腾讯算法面试题解答

才在JavaEye论坛看一个帖子求助腾讯一道面试题的解法。

题目是这样的：给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数
要求下排每个数都是先前上排对应那个数在下排十个数中出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】

 

JavaEye论坛里面有人给出了一个java实现的算法。

public class Test
{
  public static void main(String[] args)
  {
    NumberTB nTB = new NumberTB(10);
    
    int[] result = nTB.getBottom();
    for(int i=0;i<result.length;i++)
    {
      System.out.print(result[i] + " ");
    }
  }
}

class NumberTB
{
  private int[] top;
  private int[] bottom;
  private int len;
  private boolean success;
  
  //please into len >= 4
  public NumberTB(int len)
  {
    this.len = len <= 4 ? 4 : len;
    this.success = false;
    
    this.top = new int[this.len];
    this.bottom = new int[this.len];
    
    //format top
    for(int i=0;i<this.len;i++)
    {
      this.top[i] = i;
    }
  }
  
  public int[] getBottom()
  {
    int i = 0;
    
    while(!this.success)
    {
      i++;
      setNextBottom();
    }
    
    System.out.println("执行了: " + i + "次循环得到结果");
    
    return this.bottom;
  }
  
  //set next bottom
  private void setNextBottom()
  {
    boolean reB = true;
    
    for(int i=0;i<this.len;i++)
    {
      int frequecy = getFrequecy(i);
      
      if(this.bottom[i] != frequecy)
      {
        this.bottom[i] = frequecy;
        reB = false;
      }
    }
    
    this.success = reB;
  }
  
  //get frequency in bottom
  private int getFrequecy(int num)
  {
    int count = 0;
    
    for(int i=0;i<this.len;i++)
    {
      if(this.bottom[i] == num)
        count++;
    }
    
    return count;
  }
}

 下面给出一个更具一般性的结论：

这个是有规律可循的，不仅0~9有唯一解，0~n都只有唯一解。关键是最后面一个1它可以左右移动，1和2下面的数永远是2和1，0下面对应的数为n-3（n>=3），上排数n-3下面对应的数为1，其它上排数下面对应为0就ok了。有了这个一般性的结论再大的数都可以马上给出答案。
比如 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    12 2 1 0 0 0 0 0 0 0 0 0 1 0 0 0

请大家验证，这个算法可以用到数据压缩领域。

评论

5 楼 soul_fly 2009-06-18  

forgetOneself 写道

这个是有规律可循的，不仅0~9有唯一解，0~n都只有唯一解。? 这个好像在n<6就会有问题吧

0 1 2 3
1 2 1 0

4 楼 forgetOneself 2009-06-18  

这个是有规律可循的，不仅0~9有唯一解，0~n都只有唯一解。?


这个好像在n<6就会有问题吧

3 楼 soul_fly 2009-06-17  

Java控 写道

为什么总是有人自大而自卑······ 自卑的总是认为自己没有能力去做这个没有能力去做那个，认为难题都是大牛去解决的。 而又很自大认为他不会，我就也不会，总是爱教育别人的姿态。 他不了解算法 就认为算法问题都很难···就认为和他一起工作的我 必然没可能比他更了解算法 他不了解验证码 当初只是遇到个最初级的弱智验证码，我们之前都没接触过图形，所以他就认为我是在自不量力。可最后的事实是他不敢做的验证码破解，我用了一天时间破解成功 莫非一定要教育别人 要把别人的能力看低 才能把自己的能力凸显出来？ 莫非只是因为他比我到得早？比我干的早？拿钱是我两倍，所以就可以这样做么？ 本来对这个题很兴奋的 可现在完全没心情了··

继续努力吧别太悲观。

2 楼 Java控 2009-06-17  

为什么总是有人自大而自卑······
自卑的总是认为自己没有能力去做这个没有能力去做那个，认为难题都是大牛去解决的。
而又很自大认为他不会，我就也不会，总是爱教育别人的姿态。
他不了解算法 就认为算法问题都很难···就认为和他一起工作的我 必然没可能比他更了解算法
他不了解验证码 当初只是遇到个最初级的弱智验证码，我们之前都没接触过图形，所以他就认为我是在自不量力。可最后的事实是他不敢做的验证码破解，我用了一天时间破解成功

莫非一定要教育别人 要把别人的能力看低 才能把自己的能力凸显出来？
莫非只是因为他比我到得早？比我干的早？拿钱是我两倍，所以就可以这样做么？

本来对这个题很兴奋的 可现在完全没心情了··

1 楼 Java控 2009-06-17  

本来想说你那错着呢 ··因为我看到上面有16个数字 而下面12+2+1=15 ····正准备点提交的时候 才发现一堆0里面藏了一个1···郁闷····
这个题很强嘛···