8月 16 2013

BFS和DFS算法温习

广度优先搜索BFS

给定无向图G和源点s，遍历图。
BFS(G,s)
for each vertex u in G
u.color = white //所有点置为未扫描
endif
s.color = black //设置源点s为当前扫描点
Q = new queue //新建空队列
Q.add(s) //加入源点s
while(Q)
u = Q.dequeue //取队列首节点
for each vertex v connect with u
if(v.color == white)
Q.add(v)
v.color = black
endif
endwhile
广度优先遍历演示地址

5月 31 2013

面试题

[编程之美]求数组的连续子数组最大和

求连续子数组的最大和

一个整型数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和，求所有子数组的和的最大值，要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，那么最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18，
说明:
当全是负数的情况时，返回最大的那个负数

5月 22 2013

面试题

POJ上看到一种O(nm)求逆序数的方法

思路其实很简单，直接上代码

int count_inver(char *str, int len)
{
        int i;  
        int cnt = 0;
        int a[4] = {0};
        for(i = len - 1; i >= 0; i--) {
                switch (str[i]) {
                        case 'A':
                                a[1]++; 
                                a[2]++; 
                                a[3]++; 
                                break;  
                        case 'C':
                                a[2]++; 
                                a[3]++; 
                                cnt += a[1];
                                break;  
                        case 'G':
                                a[3]++; 
                                cnt += a[2];
                                break;  
                        case 'T':
                                cnt += a[3];
                }
        }
        return cnt;
}