`

interview--- 求下排数

J# 
阅读更多
给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数。要求下排每个数都是先前上排对应那个数在下排十个数中出现的次数。

上排的十个数如下: 
【0,1,2,3,4,5,6,7,8,9】

有点绕口:
   下排的数有两个角色:
   1。对于他头顶的数来说,他代表出现的次数
   2。对于非头顶的数来说,他代表对应的那个数,贡献一次出现次数

我们只关注他一个角色,然后去修正另一个角色,这样不容易晕。。
如果下排都为0, 那么意思是 上面的每个数都出现0次,显然0不是出现0次,而且只有0下面的是错误的。。所以更改。。把0改成9,那么9出现1次,然后改9下面的。。。。依次推下去。。最后知道全部正确为止。。。

思路是: 复杂问题分解,
我们现在要做的事情其一是: 给定上排数一个数,计算它在下排的出现次数

int frequecy = getFrequecy(i);

private int getFrequery(int i){
   int count = 0;
    for(int j=0;j<10;j++)
       if(bottom[j] == i)count++;
  return count;                    
}

其二: 判断这个数下排的数是不是出现次数,如果不是出现次数,那么改正
if(bottom[i]!=getFrequery(top[i]))
 bottom[i] = getFrequery(top[i]);

因为第一次只有一个值错误,所以修正的时候会把一个修正对,但是可能引起另一个错误,不过最多也只会引起一个错误,所以我们直接遍历这个top然后修正可能的值

下面是一个网友做的。。。






public class Test   
{   
  public static void main(String[] args)   
  {   
    NumberTB nTB = new NumberTB(10);//Number Top Bottom  
       
    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++)   // 初始化top,而bottom不需要初始化,会自动初始化为0
    {   
      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;   //如果出现需要修正,则说明还可能存在需要修正的,因为修正可以带来他之前的数字的错误,这个地方命名不是很好,改成 succ比较好
      }   
    }   
       
    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;   
  }   
}






分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics