标签: greedy

我有以下几行:

"14:48 say;0ed673079715c343281355c2a1fde843;2;laka;hello ;)"

我使用一个简单的正则表达式解析这个:

if($line =~ /(\d+:\d+)\ssay;(.*);(.*);(.*);(.*)/) {
    my($ts, $hash, $pid, $handle, $quote) = ($1, $2, $3, $4, $5);
}

但是; 最后搞砸了,我不知道为什么.贪婪的操作员不应该处理"一切"吗？

我试图找出字符串中有多少正则表达式匹配.我正在使用迭代器迭代匹配,并使用整数来记录有多少.

long int before = GetTickCount();
string text;

boost::regex re("^(\\d{5})\\s(\\d{8})\\s(.*)\\s(.*)\\s(.*)\\s(\\d{8})\\s(.{1})$");
char * buffer;
long length;
long count;
ifstream f;


f.open("c:\\temp\\test.txt", ios::in | ios::ate);
length = f.tellg();
f.seekg(0, ios::beg);

buffer = new char[length];

f.read(buffer, length);
f.close();

text = buffer;
boost::sregex_token_iterator itr(text.begin(), text.end(), re, 0);
boost::sregex_token_iterator end;

count = 0;
for(; itr != end; ++itr)
{
    count++;
}

long int after = GetTickCount();
cout << "Found " << count << " matches in " << (after-before) << " ms." << endl;

在我的例子中,count总是返回1,即使我把代码放在for循环中以显示匹配(并且有很多).这是为什么？我究竟做错了什么？ …

我以为我在合理的范围内理解了Perl RE,但这令我感到困惑:

#!/usr/bin/perl
use strict;
use warnings;

my $test = "'some random string'";

if($test =~ /\'?(.*?)\'?/) {
       print "Captured $1\n";
       print "Matched $&";
}
else {
       print "What?!!";
}

版画

捕获的
匹配'

它似乎与"结局"相匹配,因此没有任何结果.
我本来期望它与整个事物相匹配,或者如果它完全不贪婪,什么都没有(因为一切都有可选匹配).
这种行为让我感到困惑,任何人都可以解释发生了什么？

问题陈述

c是一个给定的n整数数组; 问题是要找到一个增加的n整数数组,a (a[i] <= a[i+1])以便最小化这个总和:

abs(a[0]+c[0]) + abs(a[1]+c[1]) + ... + abs(a[n-1]+c[n-1])
// abs(x) = absolute value of x  

最优a存在只出现在整数中,c因此我们可以使用DP来解决它O(n^2):

dp[i][j]: a[i] >= j'th integer  

但可能应该有一个更快的解决方案O(n lg n).

我有一个整数序列{a1,a2 ... an},我想把它分成最小数量的"递增子序列".例如:让序列为{10,30,20,40},然后答案为2.在这种情况下,第一个增加序列为{10,30,40},第二个增加序列为{20}.我能够使用O(N ^ 2)算法来做到这一点但我对O(N*logN)解决方案特别感兴趣,它可以达到目的.

有人问我这个问题:
给你一个间隔清单.您必须设计一种算法来查找非重叠区间的序列,以便区间范围的总和最大.

例如:
如果给定的间隔是:

["06:00","08:30"],
["09:00","11:00"],
["08:00","09:00"],
["09:00","11:30"],
["10:30","14:00"],
["12:00","14:00"]

三个间隔时范围最大化

[“06:00”, “08:30”],
[“09:00”, “11:30”],
[“12:00”, “14:00”],

被选中.

因此,答案是420(分钟).

我做了搜索并查看了以下链接,但没有帮助.

1. 点覆盖问题
2. 用点戳戳(覆盖)的段 - 任何棘手的测试用例？
3. 需要有效的贪婪来覆盖线段

问题描述:

 You are given a set of segments on a line and your goal is to mark as
 few points on a line as possible so that each segment contains at least
 one marked point

任务.

  Given a set of n segments {[a0,b0],[a1,b1]....[an-1,bn-1]} with integer
  coordinates on a line, find the minimum number 'm' of points such that 
  each segment contains at least one point .That is,  find a set of 
  integers X of …

给定两个输入数组[R1,...,Rn]和[C1,...,Cn].我们想要创建二进制矩阵A(大小为nxn),使得A的列i中的元素之和为Ci,并且A的行j中的元素之和为Rj.

我尝试使用贪婪算法填充:从左到右填充1并递减Ci,并为每行执行此操作.但是,它没有用.(另外,我尝试按递减顺序对行和列进行排序,但仍然无效)

我有一个字符串'CCCC',我想在其中匹配'CCC',重叠.

我的代码:

...
std::string input_seq = "CCCC";
std::regex re("CCC");
std::sregex_iterator next(input_seq.begin(), input_seq.end(), re);
std::sregex_iterator end;
while (next != end) {
    std::smatch match = *next;
    std::cout << match.str() << "\t" << "\t" << match.position() << "\t" << "\n";
    next++;
}
...

然而,这只会返回

CCC 0 

并跳过CCC 1我需要的解决方案.

我读过非贪婪的'？' 匹配,但我无法使它工作

如果我有一个未知的结构字符串:

"stuff I don't care about THING different stuff I don't care about THING ... THING even more stuff I don't care about THING stuff I care about"

我想捕捉"我关心的东西",它总是在最后一次出现之后.有可能出现0次或多次.如果有0次出现则没有我关心的东西.字符串不能以THING开头或结尾.

一些可能的字符串

"stuff I don't care about THING stuff I care about"

"stuff I don't care about"

一些不可能的字符串:

"THING stuff I care about"

"stuff I don't care about THING stuff I don't care about THING"

我目前解决这个问题的方法是使用带有两个贪心量词的正则表达式,如下所示:

if( /.*THING(.*)/ ) {
    $myStuff = $1;
}

它似乎有效,但我的问题是两个贪婪量词如何相互作用.第一个(最左边)贪婪量词总是"比第二个更贪婪"吗？

基本上我保证不会得到如下分割:

"stuff I don't care about THING" …