切梦
qiemengdao · 共 66 篇文章
也谈走台阶问题
问题 刚才在首页看到一篇 博客 ,说的是腾讯的一道面试题:一个楼梯有50个台阶,每一步可以走一个台阶,也可以走两个台阶,请问走完这个楼梯共有多少种方法?博主把这题分析的很麻烦。引来很多人围观。我以前也碰到过这个问题。写出来和大家分享一下。 举个例子,假设有3个台阶,则有三种走法:分别是,1-1-1, 1-2, 2-1。 分析 很简单的一道题,学过组合数学的人很快就能想到,这是一个递推关系。假设走完k个台阶有f(k)种走法。 k = 1时,f(k) = 1 k = 2时,f(k) = 2 k = n时,第一步走一个台阶,剩n-1个台阶,有f(n - 1)种走法。第一步走两个台阶,剩n-2个台阶…
2012-08-22 10:59 · 评论(0)
最大公约数(Gcd)两种算法(Euclid && Stein)
转载自: http://www.cnblogs.com/drizzlecrj/archive/2007/09/14/892340.html 很老的东东了,其实也没啥好整理的,网上很多资料了,就当备用把:-) 1. 欧几里德算法和扩展欧几里德算法 欧几里德算法 欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理: 定理:gcd(a,b) = gcd(b,a mod b) 证明:a可以表示成a = kb + r,则r = a mod b 假设d是a,b的一个公约数,则有 d|a, d|b,而r = a - kb,因此d|r 因此d是(b,a mod b)的…
2012-08-20 10:30 · 评论(0)
排序算法大赏(未完待续)
一、前言 排序算法也是面试中常常提及的内容,问的最多的应该是快速排序、堆排序。这些排序算法很基础,但是如果平时不怎么写代码的话,面试的时候总会出现各种bug。虽然思想都知道,但是就是写不出来。本文打算对各种排序算法进行一个汇总,像插入排序、冒泡排序、选择排序等就简单的介绍,重点关注快速排序和堆排序。需要提到的一点就是:插入排序,冒泡排序,归并排序,计数排序都是稳定的排序,而其他排序则都是不稳定的。 二、简单排序 1)插入排序 插入排序是很基本的排序,特别是在数据基本有序的情况下,插入排序的性能很高,基本可以达到O(N)。当然其最坏情况和平均情况时间复杂度都是O(N^2)。代码如下: void…
2012-08-19 22:18 · 评论(0)
链表合并算法
题目 已知两个有序链表,试合并这两个链表,使得合并后的链表仍然有序(注:这两个链表没有公共结点,即不交叉)。 分析 既然两个链表都是有序的,所以合并它们跟合并两个有序数组没有多少区别,只是链表操作涉及到指针,不能大意。 方法一:非递归方法 使用2个指针list1和list2分别遍历两个链表,将较小值结点归并到结果链表中。如果有一个链表归并结束后另一个链表还有结点,则把另一个链表剩下部分加入到结果链表的尾部。代码如下所示: struct node *sorted_merge(struct node *a, struct node *b) { struct node result; //使用一个…
2012-08-19 20:26 · 评论(0)
二分查找之谜题
一、前言 二分查找本身是个简单的算法,但是正是因为其简单,更容易写错。甚至于在二分查找算法刚出现的时候,也是存在bug的(溢出的bug),这个bug直到几十年后才修复(见《编程珠玑》)。本文打算对二分查找算法进行总结,并对由二分查找引申出来的问题进行分析和汇总。若有错误,请不吝赐教。 二、二分查找是这样的 相信大家都知道二分查找的基本算法,如下所示,这就是二分查找算法: int bisearch(int a[], int n, int t) //数组a有序,长度为n, 待查找的值为t { int l = 0, u = n - 1; while (l <= u) { int m = l + (…
2012-08-19 16:19 · 评论(0)
有序的循环链表中插入结点
题目 给定一个有序的循环链表,在其中插入一个值,保持该循环链表依然有序。 分析 首先看下循环链表的结构,如下图所示为一个循环链表,其尾结点指向头结点,从而形成一个循环。给定的链表结点可以是链表任意一个结点,这个结点不一定是链表头结点,从而这也增加了该题的难度。 此时若是要在链表中插入4,则插入后的链表如下所示: 可以看到插入4后,链表依然有序。 **在解决这个问题前,先来看一个简化的问题,就是在一个有序单链表中插入结点,仍然保证其有序。**这个问题的代码相信多数人都很熟悉,一般都是分两种情况考虑: 1)如果原来链表为空或者插入的结点值最小,则直接插入该结点并设置为头结点。 2)如果原来链表非…
2012-08-17 21:43 · 评论(0)
链表相交问题
题目: 给定两个单向链表的头结点指针,比如为h1和h2,判断这两个链表是否相交。 分析: 一、先来分析链表不存在环的情况 。 编程之美和JULY的博文 闲话链表追赶问题 上对该题都有详述,拿来用了。 1.直接循环判断第一个链表的每个节点是否在第二个链表中。但,这种方法的时间复杂度为O(Length(h1) * Length(h2))。显然,我们得找到一种更为有效的方法,至少不能是O(N^2)的复杂度。 2.针对第一个链表直接构造hash表,然后查询hash表,判断第二个链表的每个结点是否在hash表出现,如果所有的第二个链表的结点都能在hash表中找到,即说明第二个链表与第一个链表有相同的结…
2012-08-17 20:09 · 评论(0)
输出链表倒数第K个结点
题目描述: 输入一个单向链表,输出该链表中倒数第k个结点。 分析: 方法1:要输出链表中的倒数第K个结点,最自然的想法是先求出链表的长度N,然后从头遍历链表输出链表的第N-K+1个结点即可。注意本题数字从1计数,也就是说倒数第1个节点是链表最后一个结点。例如链表长度为4,需要输出倒数第2个结点,则我们只需要从头开始输出链表第3个结点即可。该思路代码如下: struct node { int data; struct node* next; }; struct node *getK1(struct node *list, int k) { int n = length(list); //求出链…
2012-08-17 15:26 · 评论(0)
字符串函数汇总
面试中常常会要求写一些基本的库函数,尤其以字符串库函数考的最多,所以本文汇总了一些常见的字符串库函数的实现。此外,把与内存相关的操作函数也汇总到了一起。 //求字符串长度 int strlen(const char *s) { int n = 0; while (*s++ != '\0') n++; return n; } //字符串拷贝,返回指针是为了实现链式操作,如strlen(strcpy(dst, src)),dst需要保证有足够空间 char *strcpy(char *dst, const char *src) { assert(dst != NULL && src != NUL…
2012-08-15 10:56 · 评论(0)
将有序单链表转换为平衡的二叉搜索树
题目: 给定一个升序排列的有序单链表,将其转换为一棵平衡的二叉搜索树。 分析: 单链表的结点结构如下。 struct node { int data; struct node *next; }; 由于单链表升序排列,可以参照前面的文章 将有序数组转换为平衡二叉搜索树 , 先求的链表中的结点的值保存在数组中,然后采用相同的方法实现,时间复杂度为O(N)。当然也可以不额外采用数组保存结点值,只是在每次递归的时候需要找出链表的中间元素,由于每次查找中间元素需要O(N/2)的时间,一共需要O(lgN)查找,所以总的时间为O(NlgN)。 更好的解法 我们可以采用自底向上的方法,在这里我们不再需要每次…
2012-08-15 08:51 · 评论(0)
整数分解使得积最大
题目: 给一个数n,你可以将这个数拆成任意个整数之和。找出在所有的拆分方式中,拆出来的所有的数的积的最大值(也包括只拆成一个数,如2拆成2最大)。 如 n = 6, 可以拆成 3 * 3 = 9 2 * 4 = 8 2 * 2 * 2 = 8 1 * 1 * 4 = 4 1 * 1 * 2 * 2 = 4 ... 最大值为9。 分析: 比较容易想到的是使用动态规划来解该题。首先找出状态方程,可以设f(n)为n拆分后积最大的值,则f(n)=max{i*f(n-i)}, i=1,2...n-1。其中f(1)=1, f(2)=2。使用递归效率上可能会有点问题,不过也很容易改成非递归。 动态规划法代…
2012-08-14 19:16 · 评论(0)
java多线程环境单例模式实现详解
Abstract 在开发中,如果某个实例的创建需要消耗很多系统资源,那么我们通常会使用惰性加载机制,也就是说只有当使用到这个实例的时候才会创建这个实例,这个好处在单例模式中得到了广泛应用。这个机制在single-threaded环境下的实现非常简单,然而在multi-threaded环境下却存在隐患。本文重点介绍惰性加载机制以及其在多线程环境下的使用方法。(作者numberzero,参考IBM文章《Double-checked locking and the Singleton pattern》,欢迎转载与讨论) 1 单例模式的惰性加载 通常当我们设计一个单例类的时候,会在类的内部构造这个类…
2012-08-14 11:41 · 评论(0)
素数算法
题目: 写一个程序,找出前N个素数。比如N为100,则找出前100个素数。 分析 最基本的想法就是对1到N得每个数进行判断,如果是素数则输出。一种改进的方法是不需要对1到N所有的数都进行判断,因为偶数肯定不是素数,而奇数可能是素数,可能不是。2,3,5都是素数,这可以直接得到。然后我们可以跳过2与3的倍数,即对于6n,6n+1, 6n+2, 6n+3, 6n+4, 6n+5,我们只需要判断6n+1与6n+5是否是素数即可。 判断某个数m是否是素数,最基本的方法就是对2到m-1之间的数整除m,如果有一个数能够整除m,则m就不是素数。判断m是否是素数还可以进一步改进,不需要对2到m-1之间的数全…
2012-08-13 15:15 · 评论(0)
腾讯的一道面试题—不用除法求数字乘积
题目: 已知一个包含N个元素的数组A[N],试求出这样一个数组OUTPUT[N],其中OUTPUT[I]的值为数组A中除了A[i]的其他所有元素的乘积。 注意,不能使用除法。时间复杂度必须为O(N)。 例如OUTPUT[0]的值为A[1]*A[2]...A[N], OUTPUT[1]的值为A[0]*A[2]...A[N]。 假定数组A={4, 3, 2, 1, 2},则OUTPUT={12, 16, 24, 48, 24}。 分析: 初看此题,觉得很无聊,这个题目貌似没有什么意义。要是可以用除法,直接OUTPUT[I]=A[0]*A[1]...A[N]/A[i]。 但是不能用除法,而且时间复…
2012-07-31 21:26 · 评论(0)
经典shell面试题整理
一、取出/etc/passwd文件中shell出现的次数 问题 :下面是一个/etc/passwd文件的部分内容。题目要求取出shell并统计次数,shell是指后面的/bin/bash,/sbin/nologin等,如下面/bin/bash出现12次,/sbin/nologin出现3次。 hyn:x:525:500::/home/hyn:/bin/bash ljlxx:x:526:500::/home/ljlxx:/bin/bash lzj:x:527:500::/home/lzj:/bin/bash wfly:x:528:500::/home/wfly:/bin/bash squid:x…
2012-07-31 16:03 · 评论(0)