import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
public class ShortestAbstract {
/**
* 编程之美 最短摘要的生成
* 扫描过程始终保持一个[pBegin,pEnd]的range,初始化确保[pBegin,pEnd]的range里包含所有关键字
* 然后每次迭代,尝试调整pBegin和pEnd:
* 1.pBegin递增,直到range无法包含所有关键字
* 2.pEnd递增,直到range重新包含所有关键字
* 计算新的range,与旧的range相比,看是否缩短了,如果是,则更新
* 不考虑关键字的先后顺序
*/
public static void main(String[] args) {
// String description = "w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1";
String description = "w0,w1,w2,q1,w3,q0,w4,w5,q1,q0,w6,w7,w8,,q0,w9,q1";
String[] keywords = {"q1","q0"};
String summery = shortestAbstract(description, keywords);
System.out.println(summery);
}
public static String shortestAbstract(String description, String[] keywords) {
if (description == null || description.length() == 0
|| keywords == null || keywords.length == 0) {
return null;
}
String[] desc = description.split(",");
return extract(desc, keywords);
}
public static String extract(String[] desc, String[] keywords) {
Map<String, Integer> map = new HashMap<String, Integer>(); //key=关键字 value=关键字出现的次数
for (String keyword : keywords) {
if (keyword != null && keyword.length() != 0) { //忽略null和空字符
map.put(keyword, 0);
}
}
if (map.isEmpty()) {
return null;
}
String summery = null;
int descLen = desc.length;
int shortestLen = descLen + 1;
int pBegin = 0;
int pEnd = 0;
int abstractBegin = -1;
int abstractEnd = -1;
while (true) {
//相当于初始化,从desc[0]开始,找到第一个包含所有关键字的摘要:desc[0]~desc[pEnd],此时pBegin=0
while (!isAllVisited(map) && pEnd < descLen) {
if (map.containsKey(desc[pEnd])) {
setVisited(map, desc[pEnd], 1); //出现次数加1
}
pEnd++;
}
//pBegin右移,停止条件为:已经无法包含所有关键字;
//然后回到上面,右移pEnd,重新初始化,使得pBegin~pEnd重新包含所有关键字
while (isAllVisited(map)) {
if (pEnd - pBegin < shortestLen) {
shortestLen = pEnd - pBegin;
abstractBegin = pBegin;
abstractEnd = pEnd -1;
}
if (map.get(desc[pBegin]) != null) {
setVisited(map, desc[pBegin], -1); //出现次数减1
}
pBegin++;
}
if (pEnd >= descLen) {
break;
}
}
//返回找到的最短摘要,没找到则返回null
if (abstractBegin == -1 || abstractEnd == -1) {
System.out.println("one or more keywords not found.");
} else {
StringBuilder sb = new StringBuilder();
for (int i = abstractBegin; i <= abstractEnd; i++) {
sb.append("," + desc[i]);
}
if (sb.length() > 1) {
summery = sb.substring(1);
}
}
return summery;
}
//所有关键字出现次数大于0,则找到了一个摘要
private static boolean isAllVisited(Map<String, Integer> map) {
for (Entry<String, Integer> entry : map.entrySet()) {
int count = entry.getValue();
if (count == 0) {
return false;
}
}
return true;
}
private static void setVisited(Map<String, Integer> map, String key, int add) {
int count = map.get(key);
map.put(key, count + add);
}
}
分享到:
相关推荐
介绍: 最短路径是以下问题:在图中找到两个顶点(或节点)之间的路径,以使其组成边的权重之和最小。 MST是连接的加权无向图的边的子集,该边以最小可能的总边权重连接所有顶点。解决方案: 解决问题1(最短路径)...
CMP302:算法设计和分析摘要 该存储库是本课程的摘要,...动态编程最短路径 Floyd-Warshall算法 全对最短路径上的应用 传递闭包 约翰逊算法 最大流量问题 对流图建模不同的图 流网络定义 残留网络 增强路径 流网削减 最
java生成海报实例源码代码转换器 这是CodeTransformer模型的官方 PyTorch 实现: D. Zügner、T. Kirschstein、M. Catasta、J. Leskovec 和 S. Günnemann, “从结构和上下文中学习源代码的语言不可知表示” 出现在...
7、与网络相结合:配套网站algs4.cs.princeton.edu提供了本书内容的摘要及相关的代码、测试数据、编程练习、教学课件等资源 作者简介 Robert Sedgewick,斯坦福大学博士,导师为Donald E.Knuth,从1985年开始...
算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行了...
Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、保存私钥到文件privateKey.dat、如何用Java对象序列化保存私钥...
Java生成密钥的实例 1个目标文件 摘要:Java源码,算法相关,密钥 Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、...
笔记本摘要我基础1算法在计算中的作用2入门3功能成长4分而治之5概率分析和随机算法II排序和订单统计6堆排序7快速排序8线性时间排序9中位数和订单统计III数据结构10种基本数据结构11哈希表12个二叉搜索树13棵红黑树14...
与网络相结合:配套网站algs4.cs.princeton.edu提供了本书内容的摘要及相关的代码、测试数据、编程练习、教学课件等资源。 作者简介 作者:(美国)塞奇威克(Robert Sedgewick)^韦恩(Kevin Wayne) 译者:谢路云...