Category: Study

C++面试题集合

只熟悉C,对C++不甚了解啊,但是面试又基本只有C++和Java的。于是乎,整理一下自己遇到的C++面试/笔试题吧 ———————————————–我是背景——————————————————————— 题目一:一个C++空类建立以后,会产生哪些成员函数? 分析:当时我就只想到了构造和析构函数啊。答案是6个。 [cpp] class Empty { public: Empty(); // 缺省构造函数 Empty( const Empty&); // 拷贝构造函数 ~Empty(); // 析构函数 Empty& operator=( const Empty&); // 赋值运算符 Empty* operator&(); // 取址运算符 const Empty* operator&() const; // 取址运算符 const }; [/cpp] 但并不一定是6个,如果编译器发现我们只是申明了Empty,并没有发现创建Empty的实例,那么编译器是什么函数都不会生成的。 所有这些只有当被需要才会产生。比如, Empty e; 编译器就会根据上面的实例,给类Empty生成构造函数和析构函数。 当使用 Empty  e2(e); 编译器就会生成类Empty的拷贝构造函数。 Empty   e3; e3 = e; 编译器生成赋值运算符函数 Empty    &ee = e; […]

编程之美3.3 计算字符串的相似度 (编辑距离)

Part 1: 题目描述 许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为: 1.修改一个字符(如把“a”替换为“b”); 2.增加一个字符(如把“abdd”变为“aebdd”); 3.删除一个字符(如把“travelling”变为“traveling”); 比如,对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一 次 。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于“距离+1”的倒数。也就是说,“abcdefg”和“abcdef”的距离为1,相似度 为1/2=0.5。 给定任意两个字符串,你是否能写出一个算法来计算它们的相似度呢? Part 2:分析 书中给出的解法是通过递归来做的。其实有更快更简便的方法——动态规划。 此题其实就是算法中的求“最短编辑距离”。 编辑距离定义:计算两个字符串的距离,完全相同的字符串距离为0,可以通过修改一个字符、增加一个字符或删除一个字符三种方式来使两个字符串相同,但这些方式会使得距离加1。 假设现在有两个字符串A和B A:David B:Taisy 用二维数组d[i][j]表示A中取前i个字符到B中取前j个字符的最短编辑距离。比如d[2][1]就代表从”Da”到”T”的最短编辑距离。这里为2(即把D换成T,去掉A 或者去掉D,把a换成T)。 首先我们作出初始化d[0][j] = j(字符串A子串长度为0,字符串B子串有多少个字符,就作多少次增加操作;于是同理,作删除操作,可得d[i][0] = i) 其中d[i][j]只有3个来源: 1). 来自d[i – i][j – 1],即 “A的前i-1个字符组成的子串” 到 “B的前j-1个字符组成的子串” 的编辑距离,此时如果A[i] = B[j],则最短编辑距离不变,否则最短编辑距离加1(即把A[i]变为B[j] ),所以d[i][j] = d[i – 1][j – 1] + (A[i] == B[j] ?  0 : 1) […]

Ubuntu下Lucene环境搭配

最近想着用一下lucene,就过来简单的写一写,后续还会有。 网上有很多lucene学习资料,例如,lucene源码解析,大家可以去搜一下。这里只是简单介绍怎样搭建lucene所需的环境。 lucene是Apache开源基金会其中一个开源全文检索引擎工具包,是一个全文检索引擎的架构,提供了完整的查询引擎和索引引擎,部分文本分析引擎。是用Java实现的,所以要想运行lucene就需要搭建JDK环境。 Ubuntu中有自带一个openjdk功能貌似不是很强大,所以果断sun jdk走起~ 下面就介绍sun jdk在ubuntu中的安装。其实安装过程是很简单的,错误都是出在环境变量的设置上。 1. 到oracle官网下载linux版本jdk:http://www.oracle.com/technetwork/java/javase/downloads/jdk7-downloads-1880260.html 我的ubuntu是32位的~ 下载的包,名字如下:jdk-7u25-linux-i586.tar.gz 2. 下载完么,就要解压安装,首先在/usr/lib下建一个文件夹名为jvm。然后将压缩包解压至jvm,安装就算完成了~(就是喜欢linux这种不用点来点去的安装,还没有进度条让你抓狂~吼吼~)命令如下: sudo mkdir -p /usr/lib/jvm/ sudo tar zxvf ~/Downloads/jdk-7u25-linux-i586.tar.gz -C /usr/lib/jvm jdk1.7.0_25就是我们要用的~ 3. 然后就是设置jdk的环境变量,终于来到容易出错的地方了。 网上有很多设置环境变量的方法,让我们来总结一下有哪几种,不过要提醒大家,修改需谨慎有可能什么命令都用不了了呢。最好复制一份出来改。。 3.1 修改/etc/profile文件: 事实证明用这个方法修改之后会对所有的用户生效,如果修改错了,所有的用户在图形界面下都进不去。。 用以下命令修改: vim /etc/profile 在profile文件中使用:/CLASSPATH命令找到环境变量设置的地方,其实文件就一页那么点,只是想练习一下快捷键。 修改CLASSPATH如下:  29 JAVA_HOME=/usr/lib/jvm/jdk1.7.0_25  30 PATH=$JAVA_HOME/bin:$PATH  31 CLASSPATH=.:$JAVA_HOME/lib/dt.jar:$JAVA_HOME/lib/tools.jar  32 export JAVA_HOME  33 export PATH 34 export CLASSPATH 效果如下图: 要注意一个跟windows设置十分不一样的地方,就是CLASSPATH是以“:”冒号来分割的,冒号啊,不要习惯性写成分号~~~ 修改之后使用:wq!命令保存退出,不过当然要进行某种操作来让修改生效,这时候就需要source命令了,命令如下: soure /etc/profile […]

C语言新手入门——从下载IDE开始

最近,高三的弟弟马上要去大学了。于是乎,打算教一教他C语言。 让我们从下载IDE( Integrated Develop Environment,即集成开发环境)开始。 Step Zero:买书 首先你需要的是一本完美的书,能够随时在你身边指引你的书。 《C程序设计语言》——if not you, then who? 本书原著即为C语言的设计者之一Dennis M.Ritchie和著名计算机科学家Brian W.Kernighan合著的一本介绍C语言的权威经典著作。我想,没有人比他更了解自己的设计。 摒弃你们的“谭浩强”吧~不是说谭先生不好,只是还不够。 Step One:下载最smart的IDE——CodeBlocks 1. 下载 地址:http://www.codeblocks.org/downloads/26 win7系统,选择这个版本就好了codeblocks-12.11mingw-setup.exe,可以从两个站点下载,一般是从这里Sourceforge这里下,如图 点击连接以后,会跳到Sourceforge网站,等几秒钟就开始自动下载。 2. 安装 点击Next,如上图。 点击I Agree, 如上图。 这一步是装运行所必须的各种软件,不用修改,默认点击Next就行。如上图。 这一步是选择安装路径,可以点击“Browse”然后在弹出的地方选择,或者直接在“Destination Folder”下面的输入框里填写。不建议安装在C盘,工具软件安装在其他盘比较好。比如我就是安装在E盘的Tools文件夹下。然后点击Install进行安装即可。如上图。 如果安装途中出现以下错误,请以管理员身份重新执行安装步骤。即右键“codeblocks-12.11mingw-setup.exe”安装文件,然后选择以管理员身份运行。 安装完成后,会问你是否现在运行Codeblocks,如下图。 可爱的Codeblocks就出来啦!!!! 3. 编写第一个程序之前的小配置 初次启动CodeBlocks的时候,会让你选择是否所有的 C和C++文件都以CodeBlocks打开,如图红色方框所示。点击它,然后点击OK。 现在我们需要新建一个项目,如下图所示。点击界面中间的”Create a new project” 在弹出的窗口里选择“Console application“,即控制台程序,如下图所示。 点击go,跳到下一个页面。选择使用的语言,这里选C。如下图所示。 点击Next以后进入下一个页面。 在”Project title“,即项目名称这里填写项目的名称,这里我们用填入”Test“举例。填好以后,下面的Project fileName以及Resulting fileName会自动帮你填好。 然后就是选择你代码所在的目录,即”Folder to create […]

POJ 2453 解题报告

题目意思:给定正整数x,求出在二进制表示中与他有相同个数的‘1’,且比他大的最小的数。 可以把此题当成求二进制中1的个数来做。而该算法在我的其他帖子(点击这里)中已经有详细说明。 代码: [cpp] #include <iostream> using namespace std; int Count (int); int main() { int x, num; while(cin >> x) { if(!x) break; num = Count(x); while(x++) if(Count(x) == num) { cout << x << endl; break; } } return 0; } int Count(int x) { x = (x & 0x55555555) + ((x >> […]

寻找发帖“水王”

编程之美第2.3题————寻找发帖“水王” 题目描述: Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说,Tango有一大“水王”,他不但喜欢发贴,还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子(包括回帖)的列表,其中帖子作者的ID也在表中,你能快速找出这个传说中的Tango水王吗? 首先,我们可以假设有这样一个数据结构来表示帖子 [cpp] type struct post { char* title; char* content; int uid; }post_t; [/cpp] 题目告诉我们已知所有帖子的列表,也就是说我们知道了所有帖子的链表 post_t* post_list,或者是所有帖子的数组post_array[num]。然后让我们找到出现次数最多的uid是多少,并且该uid一定超过了总和的一半。为了叙述方便,下面用数组举例。最容易就想到的方法,就是遍历整个数组,记录每一个uid出现的次数,然后再比较一下,求出最大的。 其实,这个问题就可以等价于:求数组中出现次数大于一半的那个数 解法一 对数组排序,然后遍历排好序的数组,统计各ID出现的次数,找到超过一半的那个即可。代码如下: [cpp] int Find (int* post, int len) { sort(post, post + len); int num = 1; for(int i = 0; i < len; i++) { if(post[i] == post[i + 1]) num++; else num […]

求二进制数中1的个数

编程之美第2.1题————求二进制数中1的个数 题目描述:对于一个字节(8bit)的无符号整形变量,求其中的二进制表示中“1”的个数,要求算法的执行效率尽可能的高。 书中由浅入深地给出了几种解法。 解法一 也是最容易想到的,因为对于无符号整数,若采取对2取余操作,结果只有两种,奇数余1,偶数余0,而奇数的二进制最后一位为1,偶数的二进制最后一位为0。这样我们就可以通过奇偶判断来得到结果,以二进制数1011和1100举例: 1011 对2取余,余数为1,二进制末尾为1,即含有一个1 1100 对2取余,余数为0,二进制末尾为0,即含有一个0 不管这个二进制数的高位有多少个0或者多少个1,对2取余的操作只与最低位相关。所以,如果能够把所有的位都作为最低位,对2取余一次,然后将结果相加,即可得到该题答案。而二进制数中,右移操作,就相当于除以2,所以有了以下解法。 [c] unsigned int Count (unsigned int x) { unsigned int num = 0; // the result while(x) // end of loop when x is 0 { if(x % 2 == 1) // to judge whether the last bit is ‘1’ { num++; } x = […]