Zade's Weblog
程序人生
Monthly Archives: 11月 2010
找到最小的元素
int findFirst(const vector<int>& A)
{
int size = static_cast<int>(A.size());
if (size == 0){
return -1;
}else if (size == 1){
return 0;
}
int firstMin = A.front();
int secondMax = A.back();
if (firstMin <= secondMax){
return 0;
}
int start = 0;
int end = size – 1;
while(start <= end){
int mid = (start + end) / 2;
if (A[mid] > firstMin){
start = mid + 1;
}else if (A[mid] < firstMin){
end = mid – 1;
}else{
if (A[mid] > secondMax){
start = mid + 1;
}else if (A[mid] < secondMax){
end = mid – 1;
}else{
return mid;
}
}
}
return start;
}
算法小结
这几天因为参加了一些公司的面试和笔试,总的感觉是包括微软,google和IBM都是比较重视算法的.当我们遇到一个具体的算法问题的时候,我们该如何的考虑呢?
我总结了几点经验:
1.
变无序为有序,减少时间开销
一般程序给出的都是无序的序列,我们转换为有序之后,就可以减少时间的开销.
例如google的一道笔试题,求得字符串中第一个只是出现一次的字符,例如abaccd,那和输出是b.
使用最简单的算法,如下:
int firstChar(const string& str)
{
if(str.empty())
return -1;
for(string::const_iterator itr= str.begin();itr != str.end(); ++ itr){
if(count(str.begin(),str.end(),*itr) == 1){
return *str;
}
}
return -1;
}
非常简洁的一段代码,但是时间复杂度是N^2。把str排序以后就可以减少这个复杂度了:
int firstChar(const string& str)
{
if(str.empty())
return -1;
string sorted(str);
sort(sorted.begin(),sorted.end());
typedef string::const_iterator
itr_t;
for(itr_t itr = str.begin(); itr !=str.end();++ itr) {
itr_t pos = lower_bound(sorted.begin(),sorted.end(),*itr);
assert(pos != sorted.end());
itr_t next = pos + 1;
if(next == sorted.end() || *itr != *next){
return *itr;
}
}
return -1;
}
这段代码的复杂度就是N*logN.
2.
模型转换
一个问题初始看起来很复杂,但是经过模型转换以后就会很简单.
上面无序变有序的例子也是一个模型转换的例子,我们看一个更加直观的例子,求得两个字符串的最大公共子串,例如abcdefg abdefg的最大子串是defg.
最简单的想法是求得所有的子串,然后求得长度最大的一个,时间复杂度是N*M+K,K是所有子串的长度之和.这不仅似的算法实现比较复杂,时间复杂度也很大.
我见到了一个把这个问题转换的很好的例子,通过矩阵求解.
首先构造一个N*M的矩阵,初始化全部为0，如果A的第i个字符和B的第j个字符相等,则置1，否则保持不变.这样的一个矩阵,所谓的最长的子串,就是这个矩阵中左对角为1的最长的一个序列.
再进一步,除了边缘的元素,如果A的第i个字符和B的第j个字符相等,则使得矩阵V的 v[i][j] =
v[i-1][j-1]+1,这样最大的子串,就是这个矩阵中数值最大的那个所在的左对角.
程序如下:
string LCS(const string& first,const string& second)
{
int row_count = static_cast<int>(first.length());
int col_count = static_cast<int>(second.length());
if (row_count == 0 || col_count == 0){
return string();
}
vector<int> arr(row_count * col_count);
int max = 0;
int row = 0;
int index = 0;
for (int i= 0 ; i < row_count;++ i)
for (int j = 0 ; j < col_count; ++ j)
{
if (second[j] == first[i]){
if (i > 0 && j > 0){
int idx = index – col_count – 1;
arr[index] = arr[idx] + 1;
}else{
arr[index] = 1;
}
if (arr[index] > max){
max = arr[index];
row = i;
}
}
++
index;
}
if (max != 0){
return first.substr(row – max + 1,max);
}
return string();
}
Zade's Weblog 