qiemengdao
- 浏览: 276477 次
- 性别:
- 来自: 武汉
-
最新评论
-
tuspark：
总结的不错，只是格式太规范。如果说最全面的泛型内容总结，我推荐 ...
Java泛型编程最全总结 -
huihui_0218：
泛型方法go的调用fg.<String>go(&q ...
Java泛型编程最全总结 -
fantaxy025025：
楼主总结的不错~赞一个!
Java泛型编程最全总结 -
rocksword：
<name> hbase.tmp.dir</ ...
Fedora13中安装HBase笔记 -
lijunwyf41：
public static void main(String[ ...
Java泛型编程最全总结
文章列表
问题
刚才在首页看到一篇博客，说的是腾讯的一道面试题：一个楼梯有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)种走法。第一步走两个台阶，剩 ...
- 2012-08-22 10:59
- 浏览 1098
- 评论(0)
转载自：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
因此 ...
- 2012-08-20 10:30
- 浏览 1856
- 评论(0)
一、前言
排序算法也是面试中常常提及的内容，问的最多的应该是快速排序、堆排序。这些排序算法很基础，但是如果平时不怎么写代码的话，面试的时候总会出现各种bug。虽然思想都知道，但是就是写不出来。本文打算对各 ...
- 2012-08-19 22:18
- 浏览 1011
- 评论(0)
题目
已知两个有序链表，试合并这两个链表，使得合并后的链表仍然有序（注：这两个链表没有公共结点，即不交叉）。
分析
既然两个链表都是有序的，所以合并它们跟合并两个有序数组没有多少区别，只是链表操作涉及到指针，不能大意。
方法一：非递归方法
使用2个指针list1和list2分别遍历两个链表，将较小值结点归并到结果链表中。如果有一个链表归并结束后另一个链表还有结点，则把另一个链表剩下部分加入到结果链表的尾部。代码如下所示：
struct node *sorted_merge(struct node *a, struct node *b) {
struct node res ...
- 2012-08-19 20:26
- 浏览 1837
- 评论(0)
一、前言
二分查找本身是个简单的算法，但是正是因为其简单，更容易写错。甚至于在二分查找算法刚出现的时候，也是存在bug的（溢出的bug），这个bug直到几十年后才修复（见《编程珠玑》）。本文打算对二分查找算法进行总结，并对由二分查找引申出来的问题进行分析和汇总。若有错误，请不吝赐教。
二、二分查找是这样的
相信大家都知道二分查找的基本算法，如下所示，这就是二分查找算法：
int bisearch(int a[], int n, int t) //数组a有序，长度为n， 待查找的值为t
{
int l = 0, u = n - 1;
while (l <= u ...
- 2012-08-19 16:19
- 浏览 2882
- 评论(0)
题目
给定一个有序的循环链表，在其中插入一个值，保持该循环链表依然有序。
分析
首先看下循环链表的结构，如下图所示为一个循环链表，其尾结点指向头结点，从而形成一个循环。给定的链表结点可以是链表任意一个结点，这个结点不一定是链表头结点，从而这也增加了该题的难度。
此时若是要在链表中插入4，则插入后的链表如下所示：
可以看到插入4后，链表依然有序。
在解决这个问题前，先来看一个简化的问题，就是在一个有序单链表中插入结点，仍然保证其有序。这个问题的代码相信多数人都很熟悉，一般都是分两种情况考虑：
1）如果原来链表为空或者插入的结点值最小，则直接插入该结点并设置为头结点。
2）如 ...
- 2012-08-17 21:43
- 浏览 4411
- 评论(0)
题目:
给定两个单向链表的头结点指针，比如为h1和h2，判断这两个链表是否相交。
分析：
一、先来分析链表不存在环的情况。
编程之美和JULY的博文闲话链表追赶问题上对该题都有详述，拿来用了。
1.直接循环判断第一个 ...
- 2012-08-17 20:09
- 浏览 1132
- 评论(0)
题目描述：
输入一个单向链表，输出该链表中倒数第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 ...
- 2012-08-17 15:26
- 浏览 1592
- 评论(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 & ...
- 2012-08-15 10:56
- 浏览 1077
- 评论(0)
题目：
给定一个升序排列的有序单链表，将其转换为一棵平衡的二叉搜索树。
分析：
单链表的结点结构如下。
struct node {
int data;
struct node *next；
}；由于单链表升序排列，可以参照前面的文章将有序数组转换为平 ...
- 2012-08-15 08:51
- 浏览 2771
- 评论(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
- 浏览 1709
- 评论(0)
Abstract
在开发中，如果某个实例的创建需要消耗很多系统资源，那么我们通常会使用惰性加载机制，也就是说只有当使用到这个实例的时候才会创建这个实例，这个好处在单例模式中得到了广泛应用。这个机制在single-threaded环境下的实现非常简单，然而在multi-threaded环境下却存在隐患。本文重点介绍惰性加载机制以及其在多线程环境下的使用方法。（作者numberzero，参考IBM文章《Double-checked locking and the Singleton pattern》，欢迎转载与讨论）
1 单例模式的惰性加载
通常当我们设计一个单例类的时候，会 ...
- 2012-08-14 11:41
- 浏览 977
- 评论(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- ...
- 2012-08-13 15:15
- 浏览 1784
- 评论(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
- 浏览 2778
- 评论(0)
一、取出/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
...
- 2012-07-31 16:03
- 浏览 2731
- 评论(0)