标签: greedy

令 X 为实线上 n 个区间的集合。如果 X 中的每个区间至少包含 P 中的一个点，我们就说一组 P 点刺穿 X 。描述并分析一种有效的算法来计算刺穿 X 的最小点集。假设您的输入由两个数组 XL [1 .. n] 和 XR[1..n] 组成，分别代表 X 中区间的左端点和右端点。

有什么建议从哪里开始以及如何解决吗？贪心算法？霍夫曼的？

所以问题是这样的：

我们有 n 个班级（n 个间隔），开始时间和结束时间为 [si , fi]，我们希望找到能够满足所有班级（间隔）且没有任何串通的教室的最小数量

我正在读的书说我们可以在 O(nlogn) 中解决这个问题，但我找不到比 O(n^2) 更好的算法

它说我们应该按开始时间对它们进行排序，但没有说解决方案的其余部分，但这没有任何意义，因为在给每个班级一个房间之前，我们不应该检查所有其他时间间隔，看看是否我们有没有串通？这使得它的复杂度为 O(n^2) 因为对于每个间隔我们需要检查所有其他间隔

我错过了什么吗？

我原来听说它不合情理.然后在网上的引用'我看到它被称为懒惰.这是什么？

我正在尝试编写一个正则表达式,它将完整路径文件名转换为给定文件类型的短文件名,减去文件扩展名.

例如,我试图从字符串中获取.bar文件的名称

re.search('/(.*?)\.bar$', '/def_params/param_1M56/param/foo.bar')

根据Python re docs,*?是不合适的版本*,所以我期待得到

'foo'

返回,match.group(1)但我得到了

'def_params/param_1M56/param/foo'

我在这里想到的贪婪是什么？

如何将Dijkstra算法应用于图形以找到MST,使得结果树必须在两个给定顶点之间具有边？(例如:MST必须包含X和Y之间的边)

谢谢

我有以下Python正则表达式:

xml_parse = re.search(r'^.+?<Hit_accession>(\w+?)</Hit_accession>.+?<Hsp_qseq>(\w+?)</Hsp_qseq>\s+?<Hsp_hseq>(\w+?)</Hsp_hseq>\s+?<Hsp_midline>(.+?)</Hsp_midline>',string,flags=re.DOTALL)

对于以下文字:

<?xml version="1.0"?>
 <Hit_accession> Desired Group #1 </Hit_accession>
<Hsp>
 <Hsp_qseq> Desired Group # 2 </Hsp_qseq>
 <Hsp_hseq> Desired Group # 3 </Hsp_hseq>
 <Hsp_midline> Desired Group # 4 </Hsp_midline>
</Hsp>

... way later in the XML string

 <Hit_accession> Undesired Group #1 </Hit_accession>
<Hsp>
 <Hsp_qseq> Undesired Group # 2 </Hsp_qseq>
 <Hsp_hseq> Undesired Group # 3 </Hsp_hseq>
 <Hsp_midline> Undesired Group # 4 </Hsp_midline>
</Hsp>

返回的组是:
(1)期望的组#1
(2)不期望的组#2
(3)不期望的组#3
(4)不期望的组#4

为什么会这样？因为我得到了Desired Group#1并且使用了非贪婪的.+？使用flags = re.DOTALL,我希望它不会跳过任何我想要的组2-4.

提前致谢.

更新:

使用xml.etree.ElementTree结束如下:

tree = xml.etree.ElementTree.fromstring(string)
iteration …

我只是尝试实现最好的第一次搜索,我不确定该算法是否有任何LIFO或FIFO属性.如果是的话我应该使用哪一个？我需要使用它吗？

我正在阅读wikipeida并发现Kruskal的Pseudocode如下:

KRUSKAL(G):    
    foreach v ? G.V:    
        MAKE_SET(v)    
    G.E = sort(G.E)    
    i = 0    
    while (i != |V|-1):      
        pick the next (u, v) edge from sorted list of edges G.E        
        if (FIND_SET(u) != FIND_SET(v)):          
            UNION(u, v)        
            i = i + 1 

我不确定是什么FIND_SET(),维基百科有以下描述:

如果该边连接两个不同的树,则将其添加到森林中,将两棵树组合成一棵树.

所以我想它会检查是否连接了两棵不同的树,但这究竟意味着什么呢？