常见算法总结(1)

大约两个月前一位朋友问我一道他同事的面试题目：一个含有无重复元素的集合，找出它所有的子集。例如{1,2}的所有集合是{}, {1}, {2}, {1, 2}.

当时我预料到了这道题目的算法时间复杂度为O(2^n), 但是并没有写出代码来。前两天无意间又试着做了一下这道题目，然后接受查找的资料，原来这是一个专门的算法问题。学名为powerset.

代码如下：

 View Code

这个算法采用了泛型的方式，可以求整型、字符串和字符数组的子组合问题。

然后自己还写了个判断一个数字是否是素数的程序，之所以再写了一个是因为自己以前写的算法时间表复杂度为O(n^1/2),这个还是有可以优化的地方，比如下面这种算法：

 View Code

这种算法使用了判断诸如2, 3, 5, 7, 11, 13…这些比较小的素数是否是n的因子来判断n是否是素数，明显地提升了算法的时间复杂度。

还有一道题目是求数组的最大和的问题。常见的解法是采用动态规划跟记忆算法，采用O(n^2)的时间来循环求解，但是这里有一个复杂度为O(n)的解法，代码如下：

 View Code

的确，这种解法真的非常巧妙。

还有一个算法题目是：自己实现一个power函数。在java的Math库的，有pow(double base, double exp)方法，返回base的exp次方。一般有两种算法，先看一下只对int进行处理的循环和递归算法：

 View Code

以上的两种方法都是在base和exp不小于0的情况下进行的讨论。

后者是递归的实现方式：分成了exp是奇数还是偶数两种情况进行讨论。关于递归，有一个经典名言：“In order to understand recursion, you must first understand recursion.”。就像GNU的定义一样，自己去理解吧。

下面看一下对base和exp可以是任意数值(exp是int)的情况下循环方式的实现：

 View Code

 这里增加了对base和exp为负数时的讨论，以及base=0而exp<0的异常抛出。

暂时只想到了这么多，以后再想到了会及时的添加上去。

 
标签: 算法, 面试, algorithm