电视病毒 zz# Joke - 肚皮舞运动
f*r
1 楼
一个字符数组a[1]...a[n]. 给一个字符集合{c1,...ck}， 找出包含c1,...ck的最短的
这个题目是dp？
有知道的大侠给个思路，非常感谢！
这个题目是dp？
有知道的大侠给个思路，非常感谢！
J*n
2 楼
一哥们儿隔壁新搬来个老外，一天晚上老外敲门求助，说：“我的电视坏了，不能换台
。”这哥们儿低头看了眼表，很镇定的说： “全国的电视在晚上七点到七点
半都会发作这种病毒的。
。”这哥们儿低头看了眼表，很镇定的说： “全国的电视在晚上七点到七点
半都会发作这种病毒的。
r*o
3 楼
这个是不是返回包含c1...ck的最大范围?
m*i
4 楼
北韩？
【在 J*****n 的大作中提到】
: 一哥们儿隔壁新搬来个老外，一天晚上老外敲门求助，说：“我的电视坏了，不能换台
: 。”这哥们儿低头看了眼表，很镇定的说： “全国的电视在晚上七点到七点
: 半都会发作这种病毒的。
【在 J*****n 的大作中提到】
: 一哥们儿隔壁新搬来个老外，一天晚上老外敲门求助，说：“我的电视坏了，不能换台
: 。”这哥们儿低头看了眼表，很镇定的说： “全国的电视在晚上七点到七点
: 半都会发作这种病毒的。
y*c
5 楼
DP is one approach. But it should take O(n^2)
opt(j) = maximum number of chars in C from a[0] to [j]
start(j) = largest i, st. a[i] to a[j] contains opt(j) chars in C
Then try to compute opt(j) from opt(j-1) and start(j-1).
You only need to start from start(j-1). If opt(j) is a new char, opt(j)=opt(
j-1)+1 (a hash or map needs to be maintained to store all chars in C that
have been seen), otherwise, update start(j) (e.g. if a[start(j-1)] = a[j],
etc.) This would take up to j. So at the end it ta
opt(j) = maximum number of chars in C from a[0] to [j]
start(j) = largest i, st. a[i] to a[j] contains opt(j) chars in C
Then try to compute opt(j) from opt(j-1) and start(j-1).
You only need to start from start(j-1). If opt(j) is a new char, opt(j)=opt(
j-1)+1 (a hash or map needs to be maintained to store all chars in C that
have been seen), otherwise, update start(j) (e.g. if a[start(j-1)] = a[j],
etc.) This would take up to j. So at the end it ta
s*s
6 楼
假
s*t
7 楼
汗，看走眼了
【在 r****o 的大作中提到】
: 这个是不是返回包含c1...ck的最大范围?
【在 r****o 的大作中提到】
: 这个是不是返回包含c1...ck的最大范围?
k*e
8 楼
true. 《新闻联播》时间。
【在 s***s 的大作中提到】
: 假
【在 s***s 的大作中提到】
: 假
s*l
9 楼
我也觉得是~~
【在 r****o 的大作中提到】
: 这个是不是返回包含c1...ck的最大范围?
【在 r****o 的大作中提到】
: 这个是不是返回包含c1...ck的最大范围?
c*o
10 楼
像是天朝，但是天朝现在不是每个台都转新闻联播的了。
【在 m****i 的大作中提到】
: 北韩？
【在 m****i 的大作中提到】
: 北韩？
g*u
11 楼
这个复杂度我觉得不能做到O(n)，因为还要看k
我觉得是O(nlogk)
【在 f*******r 的大作中提到】
: 一个字符数组a[1]...a[n]. 给一个字符集合{c1,...ck}， 找出包含c1,...ck的最短的
: 这个题目是dp？
: 有知道的大侠给个思路，非常感谢！
我觉得是O(nlogk)
【在 f*******r 的大作中提到】
: 一个字符数组a[1]...a[n]. 给一个字符集合{c1,...ck}， 找出包含c1,...ck的最短的
: 这个题目是dp？
: 有知道的大侠给个思路，非常感谢！
d*n
12 楼
Use hashtable, we can achieve O(n)
【在 g*****u 的大作中提到】
: 这个复杂度我觉得不能做到O(n)，因为还要看k
: 我觉得是O(nlogk)
【在 g*****u 的大作中提到】
: 这个复杂度我觉得不能做到O(n)，因为还要看k
: 我觉得是O(nlogk)
f*r
13 楼
能解释的详细点吗？谢谢了:)
【在 d****n 的大作中提到】
: Use hashtable, we can achieve O(n)
【在 d****n 的大作中提到】
: Use hashtable, we can achieve O(n)
l*a
14 楼
这个题昨天就讨论过
http://www.mitbbs.com/article_t/JobHunting/31586251.html
【在 f*******r 的大作中提到】
: 一个字符数组a[1]...a[n]. 给一个字符集合{c1,...ck}， 找出包含c1,...ck的最短的
: 这个题目是dp？
: 有知道的大侠给个思路，非常感谢！
http://www.mitbbs.com/article_t/JobHunting/31586251.html
【在 f*******r 的大作中提到】
: 一个字符数组a[1]...a[n]. 给一个字符集合{c1,...ck}， 找出包含c1,...ck的最短的
: 这个题目是dp？
: 有知道的大侠给个思路，非常感谢！
d*n
15 楼
Here is the code in C#, please do let me know if you find any bug
// This program returns the shortest substring is src
// which contains all charactors in dest
// INT_MAX returned if no coverage found
static int MinimumCover(string src, string dst)
{
int minDist = int.MaxValue;
Hashtable ht = new Hashtable();
ArrayList al = new ArrayList();
foreach (char c in dst)
{
ht.Add(c,1);
【在 f*******r 的大作中提到】
: 能解释的详细点吗？谢谢了:)
// This program returns the shortest substring is src
// which contains all charactors in dest
// INT_MAX returned if no coverage found
static int MinimumCover(string src, string dst)
{
int minDist = int.MaxValue;
Hashtable ht = new Hashtable();
ArrayList al = new ArrayList();
foreach (char c in dst)
{
ht.Add(c,1);
【在 f*******r 的大作中提到】
: 能解释的详细点吗？谢谢了:)
d*n
16 楼
Forgot one small class:
class charPos {
public charPos(int pos, char ch)
{
m_ch=ch;
m_pos=pos;
}
public char m_ch;
public int m_pos;
};
【在 d****n 的大作中提到】
: Here is the code in C#, please do let me know if you find any bug
: // This program returns the shortest substring is src
: // which contains all charactors in dest
: // INT_MAX returned if no coverage found
: static int MinimumCover(string src, string dst)
: {
: int minDist = int.MaxValue;
: Hashtable ht = new Hashtable();
: ArrayList al = new ArrayList();
: foreach (char c in dst)
class charPos {
public charPos(int pos, char ch)
{
m_ch=ch;
m_pos=pos;
}
public char m_ch;
public int m_pos;
};
【在 d****n 的大作中提到】
: Here is the code in C#, please do let me know if you find any bug
: // This program returns the shortest substring is src
: // which contains all charactors in dest
: // INT_MAX returned if no coverage found
: static int MinimumCover(string src, string dst)
: {
: int minDist = int.MaxValue;
: Hashtable ht = new Hashtable();
: ArrayList al = new ArrayList();
: foreach (char c in dst)
r*o
17 楼
能不能讲讲思路啊，这个复杂度好像不是O(n)，for里面还有while.
【在 d****n 的大作中提到】
: Here is the code in C#, please do let me know if you find any bug
: // This program returns the shortest substring is src
: // which contains all charactors in dest
: // INT_MAX returned if no coverage found
: static int MinimumCover(string src, string dst)
: {
: int minDist = int.MaxValue;
: Hashtable ht = new Hashtable();
: ArrayList al = new ArrayList();
: foreach (char c in dst)
【在 d****n 的大作中提到】
: Here is the code in C#, please do let me know if you find any bug
: // This program returns the shortest substring is src
: // which contains all charactors in dest
: // INT_MAX returned if no coverage found
: static int MinimumCover(string src, string dst)
: {
: int minDist = int.MaxValue;
: Hashtable ht = new Hashtable();
: ArrayList al = new ArrayList();
: foreach (char c in dst)
l*a
18 楼
while是针对保存match状态的hashtabl而言。
对于原字符串，就是一个O（n）的扫描
【在 r****o 的大作中提到】
: 能不能讲讲思路啊，这个复杂度好像不是O(n)，for里面还有while.
对于原字符串，就是一个O（n）的扫描
【在 r****o 的大作中提到】
: 能不能讲讲思路啊，这个复杂度好像不是O(n)，for里面还有while.
s*t
19 楼
a = "what the hell is this"
k = ('e','h','s')
def longestSubString(a, k):
n=len(a)
dp = {}
dp[(0,0)] = {}
for j in k:
if a[0]==j:
dp[(0,0)][j] = 1
else:
dp[(0,0)][j] = 0
x=0;y=0;minlength = n+1;
while y
if not (0 in dp[(x,y)].values()):
"""found substr"""
if y-x+1 < minlength:
"""update minlength if necessary"""
minlength =
【在 f*******r 的大作中提到】
: 一个字符数组a[1]...a[n]. 给一个字符集合{c1,...ck}， 找出包含c1,...ck的最短的
: 这个题目是dp？
: 有知道的大侠给个思路，非常感谢！
k = ('e','h','s')
def longestSubString(a, k):
n=len(a)
dp = {}
dp[(0,0)] = {}
for j in k:
if a[0]==j:
dp[(0,0)][j] = 1
else:
dp[(0,0)][j] = 0
x=0;y=0;minlength = n+1;
while y
if not (0 in dp[(x,y)].values()):
"""found substr"""
if y-x+1 < minlength:
"""update minlength if necessary"""
minlength =
【在 f*******r 的大作中提到】
: 一个字符数组a[1]...a[n]. 给一个字符集合{c1,...ck}， 找出包含c1,...ck的最短的
: 这个题目是dp？
: 有知道的大侠给个思路，非常感谢！
s*t
20 楼
思路见注释
【在 s*********t 的大作中提到】
: a = "what the hell is this"
: k = ('e','h','s')
: def longestSubString(a, k):
: n=len(a)
: dp = {}
: dp[(0,0)] = {}
: for j in k:
: if a[0]==j:
: dp[(0,0)][j] = 1
: else:
【在 s*********t 的大作中提到】
: a = "what the hell is this"
: k = ('e','h','s')
: def longestSubString(a, k):
: n=len(a)
: dp = {}
: dp[(0,0)] = {}
: for j in k:
: if a[0]==j:
: dp[(0,0)][j] = 1
: else:
相关阅读
学子们抗暑奇招，校长，你怎么看？Re: 各类反外F的2B男纯粹欺软怕硬,缺屌少蛋. (转载)Re: 求推荐一款行车记录仪，要前后都能录像吧 (转载)中美2国生活水平的量化比较 (转载)以后奔贴声明不让转的大家手下留情猥琐男根本不懂得欣赏大波Re: 高考报志愿！亲戚年头还有人坚持报生物，唉！！过来人表示(转载)Re: 浙大这个太搞笑：校友会公开反对新任校长任命 (转载)张国荣和张国立原来是表兄弟武松日记NSA: 只有将斯诺登绳之以法才能保护美国人民的隐私权 (转载)雪村不是那个唱我们都是活雷锋的么大兄弟你可别再按喇叭了，你每次按过喇叭车里都很臭给在版上奔的mm提个醒 (转载)何俊仁：雪村爱喝百事、不喝红酒，小屁孩一个 (转载)ZT学外语，为什么你总是发不好音？关于球类运动的一个发现女司机把油门当成刹车的真实原因---有关怠速 (转载)超市买醋小技巧ZT 请收下，不要客气