第二十八~二十九章 最大连续乘积子串、字符串编辑距离
第二十八章、最大连续乘积子串
-2.5 4 0 3 0.5 8 -1Ans:(3,0.5,8)
template<typenameComparable>
Comparable maxprod(constvector<Comparable>& v)
{
int i;
Comparable maxProduct =1;
Comparable minProduct =1;
Comparable maxCurrent = 1;
Comparable minCurrent =1;
for(inti=0;i<v.size();i++)
{
maxCurrent *= v[i];
minCurrent *= v[i];
if(maxCurrent >maxProduct)
maxProduct =maxCurrent;
if(minCurrent >maxProduct)
maxProduct =minCurrent;
if(maxCurrent <minProduct)
minProduct =maxCurrent;
if(minCurrent <minProduct)
minProduce =minCurrent;
if(minCurrent >maxCurrent)
Swap(maxCurrent,minCurrent);
if(maxCurrent < 1)
maxCurrent = 1;
return maxProduct;
}
}
*直接用动态规划求解
状态转移方程：max表示以a结尾的最大连续子串
Max = max{a,Max[i-1]*a,Min[i-1]*a};
Min =min{a,Max[i-1]*a,Min[i-1]*a};
C++代码：
double func(double* a ,constint n)
{
double* maxA = newdouble[n];
double* minA = newdouble[n];
msxA[0] = min[A] = a[0];
double value = maxA[0];
for(int i=1;i<n;i++)
{
maxA[i] =max(max(a[i],maxA[i-1]*a[i]),minA[i-1]*a[i]);
minA[i] =min(,min(a[i],maxA[i-1]*a[i]),minA[i-1]*a[i]);
vlaue =max(value,maxA[i]);
}
delete [] maxA;
delete [] minA;
return value;
}
第二十九章 字符串编辑距离
给定一个源串和目标串，能够对源串进行如下操作：
1.在给定位置上插入一个字符
2.替换任意字符
3.删除任意字符
要求写一个程序，返回最少操作数，使得对源串操作后等于目标串。
第二十一~第二十二章
出现次数超过一半的数字，最短摘要的生成
《编程之美》寻找Tango水王（100题第74题）
1.hash表：查找时间复杂度O(1) - 事先预处理时间复杂度O(N)
需要O(N)的开销空间，且要设计hash函数
2.最佳方法：每次删除两个不同的数
3.保存两个值：一个是数组中数字，一个是次数
遍历，相同则次数加1，不同则次数减1
如果次数为0，则保存下一个数字
|
阿里巴巴笔试题：给定一段产品的英文描述，包含M个英文字母，每个英文单词以空格分隔，无其他标点符号；再给定N个英文关键词，请说明思路并变成实现方法。 String extractSummary(String description , String[] keyWords) 目标：找出此产品描述中包含N个关键字的长度最短的子串（20分） W0 W1 W2 W3 Q0 W4 W5 Q1 W6 W7 W8 Q0 W9 Q1
P335 《编程之美》上的参考代码： int nTarget = N + 1; int pBegin = 0; int pEnd = 0; int nLen = N; int nAbstractBegin = 0; int nAbstractEnd = 0; while(true) { while(!isAllExisted() && pEnd < nLen) pEnd++; while(isAllExisted()) { if(pEnd - pBegin < nTargetLen) { nTarget = pEnd - pBegin; nAbstractBegin = pBegin; nAbstractEnd = pEnd - 1; } pBegin++; } if(pEnd >= N) break; }
1.将传入的keyWords[]生成哈希表，以便字符串比较 P337 struct keyWords{ int cnt; char key[]; int hash; }
2.struct keyWord{当前扫描到的一个关键词 int start; KeyHash* key; KeyWord* next; KeyWord* prev; }
3.全局变量 KeyWord* head; KeyWord* tail; int minLen; int minStartPos; int needKeyCnt;
4.扫描文章，每扫描到一个关键字时，就建立一个KeyWord，并连入双向链表中。 更新head,tail 对应KeyHash结构中的cnt+1 若cnt 0 - 1,则needKeyCnt - 1;
5.needKeyCnt = 0时，扫描到了全部关键字 链表头优化 若cnt大于1，说明摘要中还有相同； 跳过，cnt-1 直至某个链表头对应KeyHash中的cnt为1，此事该结构不能少了。
6.如果找到更短的minLength,更新minLength和minStartPos;
7.开始新一轮搜索 摘除链表第一个节点 needKeyCnt + 1; 下一节点 - 链表头，开始优化。 *搜索从上一次搜索结束处开始，不用回溯，一直沿文章向下。
7.实际意义：摘要应该包含完整的句子 struct Sentence { int start; int end; KeyWord* StartKey; KeyWord* endKey; Sentence* prev; Sentence* next; } 扫描到一个完整句子的结束 Sentence头结点优化 句子全部key的cnt-1;才去掉句子 更新HashKey 直至句子包含只出现一次的关键字
扩展问题： 如何判断两个页面相似。 |