才在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
请大家验证,这个算法可以用到数据压缩领域。
分享到:
相关推荐
腾讯算法面试题算法与代码 十分经典的算法 面试必背
数据结构与算法的重要性已不言而喻,这里有更多大厂的各种算法面试题,希望能帮助大家拿到高级offer!
(腾讯)后台开发面试题解答
最新腾讯PHP面试题1. php 的垃圾回收机制 PHP 可以自动进行内存管理,清除不需要的对象。 PHP 使用了引用计数 (reference counting) GC 机制。 每个对象都内含一个引用计数器 refcount,每个 reference 连接到对象,...
最快的排序算法 腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹(详解)?,排序算法数据结构
腾讯Java面试题
腾讯php面试题解析
腾讯面试题 前端面试题 腾讯的前端面试题。
百度,腾讯,阿里等等大公司的算法面试题精心总结,需要的朋友可以下载下来提前研究一下
各大名企常见面试题,在网上搜集整理的,很不错的资源。希望要去面试的人下下来看看
在这里汇总了腾讯历年的笔试面试题,希望对和我一样正在找工作的朋友一点帮助
腾讯面试题解析,android面试题,2020年面试题,网络基础,常用三方库,算法基础等等的。腾讯面试题解析,android面试题,2020年面试题,网络基础,常用三方库,算法基础等等的
企业-腾讯校招面试题真题(20题)-新增
java 腾讯 阿里 华为 平安面试题 112道
10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题
汇总的腾讯的笔试面试题,还包括了实习招聘等。
腾讯Java面试题(内容概要): 这份腾讯Java面试题汇总了腾讯一线技术面试中经常出现的题目,涵盖了Java基础、多线程、集合类、网络编程、JVM调优、Spring框架、分布式系统等多个方面。通过这份面试题,可以帮助...
主要是华为 腾讯的面试题 和一些面试技巧
腾讯算法大赛2018年题目腾讯算法大赛2018年题目腾讯算法大赛2018年题目腾讯算法大赛2018年题目腾讯算法大赛2018年题目腾讯算法大赛2018年题目腾讯算法大赛2018年题目
腾讯面试算法,体验设计高效算法重要性,当数据量很大时,效果更为明显,有图!