- 浏览: 606915 次
- 性别:
- 来自: 西安
文章分类
- 全部博客 (365)
- Java 基础知识(笔试面试有用) (35)
- SQL 相关 (11)
- Oracle笔试 (1)
- Java 笔试面试 (11)
- LINUX (12)
- ExtJS (21)
- Javascript (17)
- WebGIS (2)
- 软件工程 (3)
- 数据库 (17)
- 项目管理 (63)
- 工作流 (2)
- 计算机网络 (3)
- ZigBee技术及应用 (24)
- 单片机(AVR Studio) (7)
- 项目人力资源管理 (3)
- 项目管理高级知识 (4)
- JAVA技术 (12)
- 项目管理中的概念 (3)
- SQL SERVER (1)
- C++ (1)
- C/C++编程经验 (12)
- C和C++面试笔试题 (12)
- 其他IT技术笔试面试 (6)
- 名企笔试面试集锦 (16)
- 非技术 (10)
- C#相关 (1)
- Matlab相关 (2)
- 计算机专业课相关 (2)
- Web Service (1)
- Excel 使用 (1)
- PhotoShop相关 (4)
- ASP 相关 (2)
- android (1)
- Java WEB 相关 (1)
- web 安全相关 (7)
- 网络安全 (1)
- IBatis (1)
- web 开发技巧 (2)
- css 相关 (1)
- Ruby相关 (2)
- 生活 (3)
- 操作系统安全相关 (6)
- 操作系统相关 (1)
- PHP相关 (3)
- 开发经验 (12)
- Redis (1)
最新评论
1.给定如下的n*n的数字矩阵,每行从左到右是严格递增, 每列的数据也是严格递增
1 2 3
3 5 6
4 8 9
现在要求设计一个算法, 给定一个数k 判断出k是否在这个矩阵中。 描述算法并且给出时间复杂度(不考虑载入矩阵的消耗)
2.设 一个64位整型n,各个bit位是1的个数为a个. 比如7, 2进制就是 111, 所以a为3。
现在给出m个数, 求各个a的值。要求代码实现。
大多数的读者都会有这样的反应:这个题目也太简单了吧,解法似乎也相当地单一,不会有太多的曲折分析或者峰回路转之处。那么面试者到底能用这个题目考察我们什么呢?事实上,在编写程序的过程中,根据实际应用的不同,对存储空间或效率的要求也不一样。比如在PC上的程序编写与在嵌入式设备上的程序编写就有很大的差别。我们可以仔细思索一下如何才能使效率尽可能地“高”。
【解法一】
可以举一个八位的二进制例子来进行分析。对于二进制操作,我们知道,除以一个2,原来的数字将会减少一个0。如果除的过程中有余,那么就表示当前位置有一个1。
以10 100 010为例;
第一次除以2时,商为1 010 001,余为0。
第二次除以2时,商为101 000,余为1。
因此,可以考虑利用整型数据除法的特点,通过相除和判断余数的值来进行分析。于是有了如下的代码。
代码清单2-1
int Count(int v)
{
int num = 0;
while(v)
{
if(v % 2 == 1)
{
num++;
}
v = v/ 2;
}
return num;
}
【解法二】使用位操作
前面的代码看起来比较复杂。我们知道,向右移位操作同样也可以达到相除的目的。唯一不同之处在于,移位之后如何来判断是否有1存在。对于这个问题,再来看看一个八位的数字:10 100 001。
在向右移位的过程中,我们会把最后一位直接丢弃。因此,需要判断最后一位是否为1,而“与”操作可以达到目的。可以把这个八位的数字与00000001进行“与”操作。如果结果为1,则表示当前八位数的最后一位为1,否则为0。代码如下:
代码清单2-2
int Count(int v)
{
int num = 0;
While(v)
{
num += v &0x01;
v >>= 1;
}
return num;
}
【解法三】
位操作比除、余操作的效率高了很多。但是,即使采用位操作,时间复杂度仍为O(log2v),log2v为二进制数的位数。那么,还能不能再降低一些复杂度呢?如果有办法让算法的复杂度只与“1”的个数有关,复杂度不就能进一步降低了吗?
同样用10 100 001来举例。如果只考虑和1的个数相关,那么,我们是否能够在每次判断中,仅与1来进行判断呢?
为了简化这个问题,我们考虑只有一个1的情况。例如:01 000 000。
如何判断给定的二进制数里面有且仅有一个1呢?可以通过判断这个数是否是2的整数次幂来实现。另外,如果只和这一个“1”进行判断,如何设计操作呢?我们知道的是,如果进行这个操作,结果为0或为1,就可以得到结论。
如果希望操作后的结果为0,01 000 000可以和00 111 111进行“与”操作。
这样,要进行的操作就是 01 000 000 &(01 000 000 – 00 000 001)= 01 000 000 &
00 111 111 = 0。
因此就有了解法三的代码:
代码清单2-3
int Count(int v)
{
int num = 0;
while(v)
{
v &= (v-1);
num++;
}
return num;
}
【解法四】使用分支操作
解法三的复杂度降低到O(M),其中M是v中1的个数,可能会有人已经很满足了,只用计算1的位数,这样应该够快了吧。然而我们说既然只有八位数据,索性直接把0~255的情况都罗列出来,并使用分支操作,可以得到答案,代码如下:
代码清单2-4
int Count(int v)
{
int num = 0;
switch (v)
{
case 0x0:
num = 0;
break;
case 0x1:
case 0x2:
case 0x4:
case 0x8:
case 0x10:
case 0x20:
case 0x40:
case 0x80:
num = 1;
break;
case 0x3:
case 0x6:
case 0xc:
case 0x18:
case 0x30:
case 0x60:
case 0xc0:
num = 2;
break;
//...
}
return num;
}
解法四看似很直接,但实际执行效率可能会低于解法二和解法三,因为分支语句的执行情况要看具体字节的值,如果a =0,那自然在第1个case就得出了答案,但是如果a =255,则要在最后一个case才得出答案,即在进行了255次比较操作之后!
看来,解法四不可取!但是解法四提供了一个思路,就是采用空间换时间的方法,罗列并直接给出值。如果需要快速地得到结果,可以利用空间或利用已知结论。这就好比已经知道计算1+2+ … +N的公式,在程序实现中就可以利用公式得到结论。
最后,得到解法五:算法中不需要进行任何的比较便可直接返回答案,这个解法在时间复杂度上应该能够让人高山仰止了。
【解法五】查表法
代码清单2-5
/* 预定义的结果表 */
int countTable[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3,
4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4,
5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3,
4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4,
4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6,
7, 6, 7, 7, 8
};
int Count(int v)
{
//check parameter
return countTable[v];
}
这是个典型的空间换时间的算法,把0~255中“1”的个数直接存储在数组中,v作为数组的下标,countTable[v]就是v中“1”的个数。算法的时间复杂度仅为O(1)。
在一个需要频繁使用这个算法的应用中,通过“空间换时间”来获取高的时间效率是一个常用的方法,具体的算法还应针对不同应用进行优化。
扩展问题
1. 如果变量是32位的DWORD,你会使用上述的哪一个算法,或者改进哪一个算法?
2. 另一个相关的问题,给定两个正整数(二进制形式表示)A和B,问把A变为B需要改变多少位(bit)?也就是说,整数A 和B 的二进制表示中有多少位是不同的?
发表评论
-
IT工程师面试经验
2013-09-03 10:05 853(1)穿着:IT面试不像销售,不需要西装革履。得体大方,整 ... -
360 笔试题
2012-10-06 08:08 4174360笔试题 一、主观 ... -
华为Java笔试题
2012-10-01 10:36 2261一、 单项选择题 1.Java是从( )语言改进重新设计。 ... -
北京数码视讯,神州软件,华为,用友软件,趋势科技面试心得
2012-09-29 19:27 5019在不到一个月的找工作历程中,感受到了很多,也收获很多 ... -
人人网Java笔试题
2012-09-19 08:49 730从网上找到一份人人网JAVA的笔试题,做了一下,受益匪浅 ... -
华为历年机试题
2012-09-17 21:30 10651.找出一个数组中满足2^N的元素 #include < ... -
百度算法笔试题01
2012-09-17 10:19 13702009百度实习笔试题Zz 一、编程题(30分)输入:N(整数 ... -
名企笔试题
2012-09-12 18:02 984腾讯2011.10.15校园招聘 ... -
Google 技术 面试
2012-09-06 09:23 10781.谷歌面试题:给定能随机生成整数1到5的函数,写出能随 ... -
Google 面试 01
2012-09-06 09:22 948今年年初的时候 申请 ... -
Google 笔试01
2012-09-06 09:20 753题型:9道单选题+3道 ... -
海量数据处理总结
2012-09-06 08:40 713大数据量的问题是很 ... -
2006百度笔试题
2012-09-05 11:10 9202006百度笔试题 ... -
微软笔试-01
2012-09-01 15:40 7131.把二元查找树转变成排序的双向链表 题目: 输入 ... -
百度面试 01
2012-08-28 14:08 831百度技术研发笔试题目 /*百度面试题 ...
相关推荐
百度笔试题常常涉及到算法与数据结构的运用,如排序算法(快速排序、归并排序等)、查找算法(二分查找、哈希查找)以及常用的数据结构(链表、栈、队列、树、图)。这些基础知识是解决问题的基础,熟练掌握能提高...
在准备BAT(百度、阿里巴巴、腾讯)这样的中国顶级互联网公司的...总之,这个“BAT iOS算法笔试题集合”是一个宝贵的资源,它涵盖了面试中可能遇到的各种问题,通过深入学习和实践,你将更有信心面对大厂的面试挑战。
本文档总结了北京-百度计算机视觉算法工程师笔试的回忆版,涵盖了计算机视觉、算法设计、人工智能等方面的知识点。下面将对标题、描述、标签和部分内容进行详细解释和总结。 一、OSI七层模型 OSI七层模型是国际...
【百度笔试题】中的知识点主要涉及三个方面:编程题、算法题和系统设计。下面将分别对这三个方面进行详细的解析。 1. **编程题** 这道编程题要求编写一个函数`is_include(char *a, char *b)`,判断字符串`b`的所有...
大疆公司是一家以生产民用和商用无人飞行器知名的高科技企业,对算法工程师的笔试通常会包含但不限于计算机视觉、机器学习、数据结构、算法设计和分析等领域的知识点。 以下是根据大疆公司背景及算法工程师职位需求...
从给定的百度公司笔试题中,我们可以提炼出多个IT领域的知识点,主要集中在数据结构、算法、编程语言特性以及操作系统原理上。以下是对这些知识点的详细解析: ### 数据结构与算法 1. **排序算法的特性**:题目...
根据给定文件的信息,我们可以提炼出与“百度校园招聘笔试试题—深度学习算法研发工程师”相关的几个核心知识点。下面将详细阐述这些知识点,并结合题目中的具体问题进行深入解析。 ### 1. 当N很大时,降低计算...
【百度笔试题】涵盖的内容广泛,涉及编程、算法、系统设计等多个方面,下面将逐一解析这些题目中的知识点。 1. **编程题 - 字符串判断**: 这道题目要求编写一个函数来判断字符串b的所有字符是否都在字符串a中出现...
【标题】:“百度最全笔试题”所涵盖的IT知识点主要集中在Java编程语言上,这是一份集合了大量关于Java的面试与笔试问题的资源。Java作为广泛应用的面向对象编程语言,其知识点广泛且深入,涵盖了语法基础、数据结构...
百度2010-2011年各部门招聘笔试题及面经总结.doc 百度2014校园招聘笔试试题-产品经理笔试题.doc 百度2014校园招聘笔试试题-北京站未知岗位.docx 百度2014校园招聘笔试试题-南京PC客户端开发笔试题.doc 百度2014校园...
【百度历年笔试试题汇总】是一份集合了百度公司历年技术类笔试题目的资源,涵盖了算法、数据结构等多个核心IT领域。这些题目旨在测试应聘者的编程能力、逻辑思维以及对计算机科学基础知识的理解。 1. **数据库通知...
【标题】:“百度Java笔试题”通常涉及到的Java编程基础及高级概念 在“百度Java笔试题”中,我们可以预见到一系列与Java编程语言相关的测试题目。这些题目旨在评估候选人在Java开发领域的知识水平,包括但不限于...
【百度笔试题】是应聘者在申请百度职位时可能会遇到的测试内容,涵盖了一系列的编程基础知识,主要包括排序算法、多线程同步、内存管理、网络协议、数据结构和操作系统等主题。下面是对这些知识点的详细解释: 1. *...
1. **算法与数据结构**:百度的笔试题通常会测试基础的算法,如排序、查找,以及复杂的数据结构,如链表、树、图和队列等。 2. **编程基础**:应聘者需要熟练掌握至少一种编程语言,如Java、C++或Python,并理解...
这些题目涵盖了计算机科学和软件工程中的多个核心概念,主要涉及数据结构、算法、操作系统、网络协议、编程语言特性和软件开发技术。以下是每个题目及其相关的知识点详解...准备这样的笔试题可以提高在IT行业的竞争力。
**二、算法与程序设计题** 1. **二叉树最近公共父节点** - 算法描述:从两个节点分别向上遍历,直到找到公共父节点为止。可以使用递归或迭代方法实现。 - 代码实现(Python为例): ```python class TreeNode: ...
### 百度网上笔试题及答案解析 #### 题目一:字符串倒序函数实现 **题目描述:** ...以上是针对百度网上笔试题的具体解答和解析,涵盖了编程实现、算法设计等多个方面,希望能帮助到准备参加百度笔试的同学。
【标题解析】:“08百度笔试题(北京)”指的是2008年百度公司在北京市进行的一次技术笔试,主要针对系统开发工程师等职位。题目旨在考察应聘者的编程能力、算法理解和系统设计思维。 【描述解析】:16号的百度北京...
【压缩包子文件的文件名称列表】:百度2008.4.26.doc、baidu.rar、质量部笔试题.rar 1. **百度2008.4.26.doc** - 这可能是一份特定日期(2008年4月26日)的百度笔试题目文档,可能包含了编程题目、逻辑思维题、数据...