h*g
2 楼
Given a list of words, L, that are all the same length, and a string, S,
find the starting position of the substring of S that is a concatenation of
each word in L exactly once and without any intervening characters. This
substring will occur exactly once in S..
.
Example:.
L: "fooo", "barr", "wing", "ding", "wing".
S: "lingmindraboofooowingdingbarrwingmonkeypoundcake".
fooowingdingbarrwing.
trie的话，现场写程序不方便吧？
find the starting position of the substring of S that is a concatenation of
each word in L exactly once and without any intervening characters. This
substring will occur exactly once in S..
.
Example:.
L: "fooo", "barr", "wing", "ding", "wing".
S: "lingmindraboofooowingdingbarrwingmonkeypoundcake".
fooowingdingbarrwing.
trie的话，现场写程序不方便吧？
c*h
3 楼
想搞个7寸板自己玩安卓。。。
Nexus 7还是Nook HD？这屏幕比Nook HD如何？
Nexus 7还是Nook HD？这屏幕比Nook HD如何？
s*y
4 楼
在做一个皮肤病模型，腹腔注射Tamoxifen诱导K14-ERT2-cre表达。连续注射5天，每次
0.3mg。停止注射两周后开始实验，持续2周。
1. Tamoxifen半衰期只有48小时，和玉米油混合后不知道能延长多少。4周后是不是已
经完全代谢没了？
2. 皮肤的turnover比较快，是不是很快就修复了。
谢谢！
0.3mg。停止注射两周后开始实验，持续2周。
1. Tamoxifen半衰期只有48小时，和玉米油混合后不知道能延长多少。4周后是不是已
经完全代谢没了？
2. 皮肤的turnover比较快，是不是很快就修复了。
谢谢！
i*e
5 楼
为啥不要利浦的那个？
【在 F*****y 的大作中提到】
: 不要飞利浦的那个
: 谢谢！
【在 F*****y 的大作中提到】
: 不要飞利浦的那个
: 谢谢！
p*2
6 楼
trie的话写起来也还好。实现add, find两个函数应该就可以了。
这样就是N*L的复杂度了。
这样就是N*L的复杂度了。
S*e
8 楼
tam只要和ert2结合就可以马上带领cre去咬loxp，其实都是一次搞定，不要太久不要太
多，否则副作用大，5天其实偏多。
还有tam必须通过肝脏变成4oh-tam才有效果，所以通过皮肤必须用4oh-tam
【在 s*********y 的大作中提到】
: 在做一个皮肤病模型，腹腔注射Tamoxifen诱导K14-ERT2-cre表达。连续注射5天，每次
: 0.3mg。停止注射两周后开始实验，持续2周。
: 1. Tamoxifen半衰期只有48小时，和玉米油混合后不知道能延长多少。4周后是不是已
: 经完全代谢没了？
: 2. 皮肤的turnover比较快，是不是很快就修复了。
: 谢谢！
多，否则副作用大，5天其实偏多。
还有tam必须通过肝脏变成4oh-tam才有效果，所以通过皮肤必须用4oh-tam
【在 s*********y 的大作中提到】
: 在做一个皮肤病模型，腹腔注射Tamoxifen诱导K14-ERT2-cre表达。连续注射5天，每次
: 0.3mg。停止注射两周后开始实验，持续2周。
: 1. Tamoxifen半衰期只有48小时，和玉米油混合后不知道能延长多少。4周后是不是已
: 经完全代谢没了？
: 2. 皮肤的turnover比较快，是不是很快就修复了。
: 谢谢！
F*y
9 楼
up
p*2
10 楼
写了一个练练手。
import java.util.*;
class Node
{
Node[] children=new Node[26];
public Node Set(char c)
{
Node node=new Node();
children[c-'a']=node;
return node;
}
public Node Get(char c)
{
return children[c-'a'];
}
}
class Trie
{
Node root=new Node();
public void Add(String word)
{
int i=0;
Node node=root;
while(i
char c=word.charAt(i);
if(node.Get(c)==null)
node=node.Set(c);
else
node=node.Get(c);
i++;
}
}
public boolean Find(String word)
{
boolean ret=true;
int i=0;
Node node=root;
while(i
char c=word.charAt(i);
if(node.Get(c)!=null)
node=node.Get(c);
else
{
ret=false;
break;
}
i++;
}
return ret;
}
}
public class Solution
{
static String[] L;
static int len;
static Trie trie=new Trie();
static HashMap hm=new HashMap();
public static boolean Check(String str)
{
HashMap ht=new HashMap();
for(int i=0;i
String sub=str.substring(i*len,i*len+len);
if(trie.Find(sub))
{
if(ht.containsKey(sub))
ht.put(sub, ht.get(sub)+1);
else
ht.put(sub, 1);
}
else
return false;
}
if(hm.size()!=ht.size())
return false;
for(String s: hm.keySet())
{
if(hm.get(s)!=ht.get(s))
return false;
}
return true;
}
public static void main(String[] args)
{
L=new String[]{ "fooo", "barr", "wing", "ding", "wing"};
len=4;
for(String s:L)
{
trie.Add(s);
if(hm.containsKey(s))
hm.put(s, hm.get(s)+1);
else
hm.put(s, 1);
}
int totalLen=len*L.length;
String S="lingmindraboofooowingdingbarrwingmonkeypoundcake";
for(int i=0;i<=S.length()-totalLen;i++)
{
if(Check(S.substring(i,i+totalLen)))
{
System.out.println(S.substring(i,i+totalLen));
break;
}
}
}
}
import java.util.*;
class Node
{
Node[] children=new Node[26];
public Node Set(char c)
{
Node node=new Node();
children[c-'a']=node;
return node;
}
public Node Get(char c)
{
return children[c-'a'];
}
}
class Trie
{
Node root=new Node();
public void Add(String word)
{
int i=0;
Node node=root;
while(i
char c=word.charAt(i);
if(node.Get(c)==null)
node=node.Set(c);
else
node=node.Get(c);
i++;
}
}
public boolean Find(String word)
{
boolean ret=true;
int i=0;
Node node=root;
while(i
char c=word.charAt(i);
if(node.Get(c)!=null)
node=node.Get(c);
else
{
ret=false;
break;
}
i++;
}
return ret;
}
}
public class Solution
{
static String[] L;
static int len;
static Trie trie=new Trie();
static HashMap
public static boolean Check(String str)
{
HashMap
for(int i=0;i
String sub=str.substring(i*len,i*len+len);
if(trie.Find(sub))
{
if(ht.containsKey(sub))
ht.put(sub, ht.get(sub)+1);
else
ht.put(sub, 1);
}
else
return false;
}
if(hm.size()!=ht.size())
return false;
for(String s: hm.keySet())
{
if(hm.get(s)!=ht.get(s))
return false;
}
return true;
}
public static void main(String[] args)
{
L=new String[]{ "fooo", "barr", "wing", "ding", "wing"};
len=4;
for(String s:L)
{
trie.Add(s);
if(hm.containsKey(s))
hm.put(s, hm.get(s)+1);
else
hm.put(s, 1);
}
int totalLen=len*L.length;
String S="lingmindraboofooowingdingbarrwingmonkeypoundcake";
for(int i=0;i<=S.length()-totalLen;i++)
{
if(Check(S.substring(i,i+totalLen)))
{
System.out.println(S.substring(i,i+totalLen));
break;
}
}
}
}
a*m
11 楼
不折腾的话n7还不错。1280*800比1440x900低点，最好自己去商店看看再说。
S*e
12 楼
turnover有一个周期，修复的问题取决于KO在哪里发生，这方面的干细胞很多研究，有
得follow
【在 s*********y 的大作中提到】
: 在做一个皮肤病模型，腹腔注射Tamoxifen诱导K14-ERT2-cre表达。连续注射5天，每次
: 0.3mg。停止注射两周后开始实验，持续2周。
: 1. Tamoxifen半衰期只有48小时，和玉米油混合后不知道能延长多少。4周后是不是已
: 经完全代谢没了？
: 2. 皮肤的turnover比较快，是不是很快就修复了。
: 谢谢！
得follow
【在 s*********y 的大作中提到】
: 在做一个皮肤病模型，腹腔注射Tamoxifen诱导K14-ERT2-cre表达。连续注射5天，每次
: 0.3mg。停止注射两周后开始实验，持续2周。
: 1. Tamoxifen半衰期只有48小时，和玉米油混合后不知道能延长多少。4周后是不是已
: 经完全代谢没了？
: 2. 皮肤的turnover比较快，是不是很快就修复了。
: 谢谢！
c*e
13 楼
不觉得你需要trie, hashtable is enough..
【在 p*****2 的大作中提到】
: 写了一个练练手。
: import java.util.*;
: class Node
: {
: Node[] children=new Node[26];
:
: public Node Set(char c)
: {
: Node node=new Node();
: children[c-'a']=node;
【在 p*****2 的大作中提到】
: 写了一个练练手。
: import java.util.*;
: class Node
: {
: Node[] children=new Node[26];
:
: public Node Set(char c)
: {
: Node node=new Node();
: children[c-'a']=node;
c*h
14 楼
那还是等Nook HD下一波deal吧。
我眼睛要求比较高，看文字比较多。。。。
ipad mini那种是绝对不能忍受的。
【在 p*******m 的大作中提到】
: http://www.mitbbs.com/article_t/PDA/32037579.html
我眼睛要求比较高，看文字比较多。。。。
ipad mini那种是绝对不能忍受的。
【在 p*******m 的大作中提到】
: http://www.mitbbs.com/article_t/PDA/32037579.html
s*y
15 楼
诱导后多久又成为wt野生型了？实验要在几天内完成？
有的模型周期长，难道中间还要再注射几次？
有的模型周期长，难道中间还要再注射几次？
p*2
16 楼
没错。
【在 c*****e 的大作中提到】
: 不觉得你需要trie, hashtable is enough..
c*h
17 楼
我可以折腾的。
【在 a********m 的大作中提到】
: 不折腾的话n7还不错。1280*800比1440x900低点，最好自己去商店看看再说。
【在 a********m 的大作中提到】
: 不折腾的话n7还不错。1280*800比1440x900低点，最好自己去商店看看再说。
s*y
18 楼
找到一篇
(1) administration of high Tm doses leads to extended CreER nuclear
localization; (2) Tm administration induces reporter gene recombination for
several days or weeks after Tm treatment is completed, depending on the
original dose administered; and (3) Tm treatment induces side effects that
may have physiologic consequences in Tm-inducible models.
: 诱导后多久又成为wt野生型了？实验要在几天内完成？
: 有的模型周期长，难道中间还要再注射几次？
【在 s*********y 的大作中提到】
: 诱导后多久又成为wt野生型了？实验要在几天内完成？
: 有的模型周期长，难道中间还要再注射几次？
(1) administration of high Tm doses leads to extended CreER nuclear
localization; (2) Tm administration induces reporter gene recombination for
several days or weeks after Tm treatment is completed, depending on the
original dose administered; and (3) Tm treatment induces side effects that
may have physiologic consequences in Tm-inducible models.
: 诱导后多久又成为wt野生型了？实验要在几天内完成？
: 有的模型周期长，难道中间还要再注射几次？
【在 s*********y 的大作中提到】
: 诱导后多久又成为wt野生型了？实验要在几天内完成？
: 有的模型周期长，难道中间还要再注射几次？
H*e
19 楼
这个find是不是有点问题？只要是前缀就return true了吧？
【在 p*****2 的大作中提到】
: 写了一个练练手。
: import java.util.*;
: class Node
: {
: Node[] children=new Node[26];
:
: public Node Set(char c)
: {
: Node node=new Node();
: children[c-'a']=node;
【在 p*****2 的大作中提到】
: 写了一个练练手。
: import java.util.*;
: class Node
: {
: Node[] children=new Node[26];
:
: public Node Set(char c)
: {
: Node node=new Node();
: children[c-'a']=node;
a*m
20 楼
那选择多不少。现在看nook hd的cm好像耗电太厉害，不解决的话实用性下降很多。
【在 c*****h 的大作中提到】
: 我可以折腾的。
【在 c*****h 的大作中提到】
: 我可以折腾的。
t*p
21 楼
K14是表达在基底细胞，也即通常说的皮肤干细胞，一旦发生敲除就永久敲除，皮肤干
细胞理论上不会丢失，所以不存在4周以后就没有了的问题。
K14-CreERT2的效率不是很高，假设你诱导敲除一半的细胞，那么另一半的细胞足以掩
盖敲除细胞的缺陷。除非你的基因特别强大。我觉的K14-CreERT2作为tracing的工具鼠
就好，要用它研究基因在成体小鼠中的功能并不是很好用，主要就是诱导效率还不够高。
【在 s*********y 的大作中提到】
: 在做一个皮肤病模型，腹腔注射Tamoxifen诱导K14-ERT2-cre表达。连续注射5天，每次
: 0.3mg。停止注射两周后开始实验，持续2周。
: 1. Tamoxifen半衰期只有48小时，和玉米油混合后不知道能延长多少。4周后是不是已
: 经完全代谢没了？
: 2. 皮肤的turnover比较快，是不是很快就修复了。
: 谢谢！
细胞理论上不会丢失，所以不存在4周以后就没有了的问题。
K14-CreERT2的效率不是很高，假设你诱导敲除一半的细胞，那么另一半的细胞足以掩
盖敲除细胞的缺陷。除非你的基因特别强大。我觉的K14-CreERT2作为tracing的工具鼠
就好，要用它研究基因在成体小鼠中的功能并不是很好用，主要就是诱导效率还不够高。
【在 s*********y 的大作中提到】
: 在做一个皮肤病模型，腹腔注射Tamoxifen诱导K14-ERT2-cre表达。连续注射5天，每次
: 0.3mg。停止注射两周后开始实验，持续2周。
: 1. Tamoxifen半衰期只有48小时，和玉米油混合后不知道能延长多少。4周后是不是已
: 经完全代谢没了？
: 2. 皮肤的turnover比较快，是不是很快就修复了。
: 谢谢！
p*2
22 楼
他的题目说的是单词的长度一致，所以应该一定match.
【在 H***e 的大作中提到】
: 这个find是不是有点问题？只要是前缀就return true了吧？
c*h
23 楼
有nook hd+，我是原生系统root+go launcher，很省电，够用了。cm10等以后稳定省电
了再用就是。
所以如果7寸板上nook hd，我比较熟悉折腾，可以如法炮制。
【在 a********m 的大作中提到】
: 那选择多不少。现在看nook hd的cm好像耗电太厉害，不解决的话实用性下降很多。
了再用就是。
所以如果7寸板上nook hd，我比较熟悉折腾，可以如法炮制。
【在 a********m 的大作中提到】
: 那选择多不少。现在看nook hd的cm好像耗电太厉害，不解决的话实用性下降很多。
s*y
24 楼
K14是表达在基底细胞，也即通常说的皮肤干细胞，一旦发生敲除就永久敲除，皮肤干
细胞理论上不会丢失，所以不存在4周以后就没有了的问题。
请问 toptip 这个有文献支持吗？
细胞理论上不会丢失，所以不存在4周以后就没有了的问题。
请问 toptip 这个有文献支持吗？
b*u
25 楼
嗯，trie的特性没什么帮助。
【在 c*****e 的大作中提到】
: 不觉得你需要trie, hashtable is enough..
【在 c*****e 的大作中提到】
: 不觉得你需要trie, hashtable is enough..
a*m
26 楼
哦。那还成，nook hd相对比较适合你。
【在 c*****h 的大作中提到】
: 有nook hd+，我是原生系统root+go launcher，很省电，够用了。cm10等以后稳定省电
: 了再用就是。
: 所以如果7寸板上nook hd，我比较熟悉折腾，可以如法炮制。
【在 c*****h 的大作中提到】
: 有nook hd+，我是原生系统root+go launcher，很省电，够用了。cm10等以后稳定省电
: 了再用就是。
: 所以如果7寸板上nook hd，我比较熟悉折腾，可以如法炮制。
S*e
27 楼
看fuchs的文章，她做的非常全面，当然也有听说造假的传闻。
你的KO如果不是致死，应该不会消失
如果致死，那表型可能会很明显
【在 s*********y 的大作中提到】
: K14是表达在基底细胞，也即通常说的皮肤干细胞，一旦发生敲除就永久敲除，皮肤干
: 细胞理论上不会丢失，所以不存在4周以后就没有了的问题。
: 请问 toptip 这个有文献支持吗？
a*n
28 楼
直接用HASHMAP/RABIN-KARP测试就行了吧，，，加上长度都是４就更简单了。。。每次
产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。
产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。
b*z
29 楼
both garbage
s*y
30 楼
我用的就是fuchs的小鼠。在她1999年的PNAS里写道
This promoter is strongly active in dividing cells of epidermis and some
other stratified squamous epithelia。
Finally, we show that epidermal cells harboring a Cre-dependent rearranged
genome persist for many months after tamoxifen application, indicating that
the epidermal stem cell population has been targeted efficiently.
但是法国的Chambon Lab认为只能维持几天的时间
Curr Protoc Mouse Biol. 2011 Mar 1;1(1):55-70. doi: 10.1002/9780470942390.
mo100128.
Generation of Spatio-Temporally Controlled Targeted Somatic Mutations in the
Mouse.
Metzger D1, Chambon P1.
This promoter is strongly active in dividing cells of epidermis and some
other stratified squamous epithelia。
Finally, we show that epidermal cells harboring a Cre-dependent rearranged
genome persist for many months after tamoxifen application, indicating that
the epidermal stem cell population has been targeted efficiently.
但是法国的Chambon Lab认为只能维持几天的时间
Curr Protoc Mouse Biol. 2011 Mar 1;1(1):55-70. doi: 10.1002/9780470942390.
mo100128.
Generation of Spatio-Temporally Controlled Targeted Somatic Mutations in the
Mouse.
Metzger D1, Chambon P1.
q*c
31 楼
Isn't it similar to strstr? Is it a phone or onsite question?
c*h
32 楼
。。。。。。。。。。。。
那你推荐个。
【在 b****z 的大作中提到】
: both garbage
那你推荐个。
【在 b****z 的大作中提到】
: both garbage
S*e
33 楼
that
the
fuchs是美国的一座大山，想在这行混的美国实验室基本上不甘指出来她的漏洞，我倾
向于法国实验室的结论。不过你还是多看看这方面的文章，或者自己做看看。这个不在
于你ko什么基因，基本上是干细胞marker是不是k15的争议。好像另外一个ru486诱导的
也很多人用。
【在 s*********y 的大作中提到】
: 我用的就是fuchs的小鼠。在她1999年的PNAS里写道
: This promoter is strongly active in dividing cells of epidermis and some
: other stratified squamous epithelia。
: Finally, we show that epidermal cells harboring a Cre-dependent rearranged
: genome persist for many months after tamoxifen application, indicating that
: the epidermal stem cell population has been targeted efficiently.
: 但是法国的Chambon Lab认为只能维持几天的时间
: Curr Protoc Mouse Biol. 2011 Mar 1;1(1):55-70. doi: 10.1002/9780470942390.
: mo100128.
: Generation of Spatio-Temporally Controlled Targeted Somatic Mutations in the
a*g
34 楼
c++ practice (use multiset):
#include
#include
using std::multiset;
using std::string;
int len_p = 4;
bool check_substr(string s, const multiset &L) {
multiset dup_L = L;
for (unsigned i=0; i
multiset::iterator itor = dup_L.find(token);
if (itor == dup_L.end()) {
return false;
}
dup_L.erase(itor);
}
return dup_L.empty();
}
int main(int argc, char* argv[])
{
multiset L;
L.insert("fooo");
L.insert("barr");
L.insert("wing");
L.insert("ding");
L.insert("wing");
const string S = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
int size_L = L.size();
int len_substr = len_p * size_L;
for (unsigned i=0; i < S.length() - len_substr; i++) {
if (check_substr(S.substr(i, len_substr), L)) {
printf("found. pos:%d\n", i);
return 0;
}
}
printf("not found.\n");
return 0;
}
It's not trivial to me how to apply RK algorithm to this problem but I guess
defining a hash function using histogram of characters might work.
#include
#include
using std::multiset;
using std::string;
int len_p = 4;
bool check_substr(string s, const multiset
multiset
for (unsigned i=0; i
multiset
if (itor == dup_L.end()) {
return false;
}
dup_L.erase(itor);
}
return dup_L.empty();
}
int main(int argc, char* argv[])
{
multiset
L.insert("fooo");
L.insert("barr");
L.insert("wing");
L.insert("ding");
L.insert("wing");
const string S = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
int size_L = L.size();
int len_substr = len_p * size_L;
for (unsigned i=0; i < S.length() - len_substr; i++) {
if (check_substr(S.substr(i, len_substr), L)) {
printf("found. pos:%d\n", i);
return 0;
}
}
printf("not found.\n");
return 0;
}
It's not trivial to me how to apply RK algorithm to this problem but I guess
defining a hash function using histogram of characters might work.
p*m
35 楼
ipad mini gen 2 lol
【在 c*****h 的大作中提到】
: 。。。。。。。。。。。。
: 那你推荐个。
D*a
36 楼
多不多要看一次剂量，其实单次剂量小点，还是五天效果好于短点大剂量
tam注射进去就进肝脏代谢了，皮肤敲除还是通过血管到皮肤的，并不是抹在皮肤的，
不需要用4oh-tam
【在 S**********e 的大作中提到】
: tam只要和ert2结合就可以马上带领cre去咬loxp，其实都是一次搞定，不要太久不要太
: 多，否则副作用大，5天其实偏多。
: 还有tam必须通过肝脏变成4oh-tam才有效果，所以通过皮肤必须用4oh-tam
tam注射进去就进肝脏代谢了，皮肤敲除还是通过血管到皮肤的，并不是抹在皮肤的，
不需要用4oh-tam
【在 S**********e 的大作中提到】
: tam只要和ert2结合就可以马上带领cre去咬loxp，其实都是一次搞定，不要太久不要太
: 多，否则副作用大，5天其实偏多。
: 还有tam必须通过肝脏变成4oh-tam才有效果，所以通过皮肤必须用4oh-tam
g*e
37 楼
如果某个字符串在table 里找到了重复的，但这时其他串还没全找到，怎么办？
【在 a*****n 的大作中提到】
: 直接用HASHMAP/RABIN-KARP测试就行了吧，，，加上长度都是４就更简单了。。。每次
: 产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。
【在 a*****n 的大作中提到】
: 直接用HASHMAP/RABIN-KARP测试就行了吧，，，加上长度都是４就更简单了。。。每次
: 产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。
w*g
38 楼
it's a piece of crap. No deal.
【在 c*****h 的大作中提到】
: 想搞个7寸板自己玩安卓。。。
: Nexus 7还是Nook HD？这屏幕比Nook HD如何？
【在 c*****h 的大作中提到】
: 想搞个7寸板自己玩安卓。。。
: Nexus 7还是Nook HD？这屏幕比Nook HD如何？
h*9
39 楼
本人在做骨骼肌基因诱导敲出。Tam 灌胃和腹腔注射哪种方式更有效？似乎灌胃剂量可
以给更大一些（4mg per time)
以给更大一些（4mg per time)
A*u
40 楼
你这不对
差多了
【在 a*****g 的大作中提到】
: c++ practice (use multiset):
: #include
: #include
: using std::multiset;
: using std::string;
: int len_p = 4;
: bool check_substr(string s, const multiset &L) {
: multiset dup_L = L;
: for (unsigned i=0; i
差多了
【在 a*****g 的大作中提到】
: c++ practice (use multiset):
: #include
: #include
: using std::multiset;
: using std::string;
: int len_p = 4;
: bool check_substr(string s, const multiset
: multiset
: for (unsigned i=0; i
c*h
41 楼
嗯，我就是等这个当随身带的大奶机。
安卓板子目前来说只能当二奶机玩玩。
【在 p*******m 的大作中提到】
:
: ipad mini gen 2 lol
安卓板子目前来说只能当二奶机玩玩。
【在 p*******m 的大作中提到】
:
: ipad mini gen 2 lol
j*b
42 楼
没想到什么特别巧的办法，brute force ＋ hashmap？
public static void main(String[] args) {
String l[] = { "fooo", "barr", "wing", "ding", "wing" };
Map map = new HashMap();
for (int i = 0; i < l.length; i++){
if(map.containsKey(l[i]))
map.put(l[i], map.get(l[i]) +1);
else
map.put(l[i], 1);
}
String s = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
int len = l[0].length();
for (int j = 0; j < len; j++) {
Map map2 = new HashMap();
for (int i = j; i <= s.length() - len; i+=len) {
String ss = s.substring(i, i + len);
if (map.containsKey(ss)) {
if(!map2.containsKey(ss) || map2.get(ss) < map.get(ss)){
if(map2.containsKey(ss))
map2.put(ss, map2.get(ss)+1);
else
map2.put(ss, 1);
if(map2.entrySet().equals(map.entrySet())){
String r =s.substring(i+len-l.length*len,i+len);
System.out.println(r);
return;
}
}else{
map2.clear();
}
}else{
map2.clear();
}
}
}
}
public static void main(String[] args) {
String l[] = { "fooo", "barr", "wing", "ding", "wing" };
Map
for (int i = 0; i < l.length; i++){
if(map.containsKey(l[i]))
map.put(l[i], map.get(l[i]) +1);
else
map.put(l[i], 1);
}
String s = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
int len = l[0].length();
for (int j = 0; j < len; j++) {
Map
for (int i = j; i <= s.length() - len; i+=len) {
String ss = s.substring(i, i + len);
if (map.containsKey(ss)) {
if(!map2.containsKey(ss) || map2.get(ss) < map.get(ss)){
if(map2.containsKey(ss))
map2.put(ss, map2.get(ss)+1);
else
map2.put(ss, 1);
if(map2.entrySet().equals(map.entrySet())){
String r =s.substring(i+len-l.length*len,i+len);
System.out.println(r);
return;
}
}else{
map2.clear();
}
}else{
map2.clear();
}
}
}
}
w*g
43 楼
it's definitely fuzzier than ipad3 and nook HD+
【在 c*****h 的大作中提到】
: 那还是等Nook HD下一波deal吧。
: 我眼睛要求比较高，看文字比较多。。。。
: ipad mini那种是绝对不能忍受的。
【在 c*****h 的大作中提到】
: 那还是等Nook HD下一波deal吧。
: 我眼睛要求比较高，看文字比较多。。。。
: ipad mini那种是绝对不能忍受的。
h*w
44 楼
mark
p*m
45 楼
你造的比较好？
【在 b****z 的大作中提到】
: both garbage
s*e
46 楼
用HASHMAP 找出每个WORD 所在的位置 occurrence map，在做一个反向的由所在位置(
position)到WORD 的reverse occurrence map。 吧这些position 排序，然后递归搜索。
package smartnose;
import java.util.Arrays;
import java.util.*;
public class SubWordSeq {
public static void main(String [] args){
List L = new LinkedList();
L.add("fooo");L.add("barr");L.add("wing");L.add("ding");L.add("wing"
);
String S= "lingmindraboofooowingdingbarrwingmonkeypoundcake";
HashMap> occurMap = new HashMap
for(String word:L){
occurMap.put(word, new ArrayList());
}
int wordLen = L.get(0).length();
for(int i=0;i+wordLen
if(occurMap.containsKey(sub))//add the occurrance
occurMap.get(sub).add(i);
}
HashMap> rOccurMap = new HashMap>();
for(String w: occurMap.keySet()){
List occ = occurMap.get(w);
for(Integer pos: occ){
if(rOccurMap.containsKey(pos)){
rOccurMap.get(pos).add(w);
}
else{
rOccurMap.put(pos, Arrays.asList(w));
}
}
}
List distinctPos = new ArrayList();
distinctPos.addAll(rOccurMap.keySet());
Collections.sort(distinctPos);
//now search the f*ck out of it.
for(Integer start:distinctPos)
if(recurSearch(L,rOccurMap,start,wordLen)){
System.out.println("found one instance starting at:"+start);
break;
}
}
public static boolean recurSearch(List L, HashMap
if(L.isEmpty())
return true;
List cWords = rMap.get(curPos);
for(String w: cWords){
if(L.contains(w)){
//L.remove(w);
int idx=L.indexOf(w);
L.remove(idx);//can be more efficient
if(recurSearch(L, rMap, curPos+wLen, wLen))
return true;
L.add(w);
}
}
return false;
}
}
position)到WORD 的reverse occurrence map。 吧这些position 排序，然后递归搜索。
package smartnose;
import java.util.Arrays;
import java.util.*;
public class SubWordSeq {
public static void main(String [] args){
List
L.add("fooo");L.add("barr");L.add("wing");L.add("ding");L.add("wing"
);
String S= "lingmindraboofooowingdingbarrwingmonkeypoundcake";
HashMap
for(String word:L){
occurMap.put(word, new ArrayList
}
int wordLen = L.get(0).length();
for(int i=0;i+wordLen
if(occurMap.containsKey(sub))//add the occurrance
occurMap.get(sub).add(i);
}
HashMap
for(String w: occurMap.keySet()){
List
for(Integer pos: occ){
if(rOccurMap.containsKey(pos)){
rOccurMap.get(pos).add(w);
}
else{
rOccurMap.put(pos, Arrays.asList(w));
}
}
}
List
distinctPos.addAll(rOccurMap.keySet());
Collections.sort(distinctPos);
//now search the f*ck out of it.
for(Integer start:distinctPos)
if(recurSearch(L,rOccurMap,start,wordLen)){
System.out.println("found one instance starting at:"+start);
break;
}
}
public static boolean recurSearch(List
if(L.isEmpty())
return true;
List
for(String w: cWords){
if(L.contains(w)){
//L.remove(w);
int idx=L.indexOf(w);
L.remove(idx);//can be more efficient
if(recurSearch(L, rMap, curPos+wLen, wLen))
return true;
L.add(w);
}
}
return false;
}
}
w*g
47 楼
连二奶都算不上, 暖床丫头而已.
【在 c*****h 的大作中提到】
: 嗯，我就是等这个当随身带的大奶机。
: 安卓板子目前来说只能当二奶机玩玩。
【在 c*****h 的大作中提到】
: 嗯，我就是等这个当随身带的大奶机。
: 安卓板子目前来说只能当二奶机玩玩。
a*s
48 楼
mark
c*h
49 楼
那是你太花心了。我比较专一。
【在 w*****g 的大作中提到】
: 连二奶都算不上, 暖床丫头而已.
【在 w*****g 的大作中提到】
: 连二奶都算不上, 暖床丫头而已.
l*e
50 楼
mark
h*e
51 楼
如果你看文字比较多，那我觉得你可能还是等等吧
去店里看看16:9的屏幕能否接受，反正我是不能
我觉得呢阅读就用eink好了
平板用你现在的nook hd+就行了，
如果4:3只有坑爹的iPad Mini的话至少等等看有没有3:2的安卓吧。
去店里看看16:9的屏幕能否接受，反正我是不能
我觉得呢阅读就用eink好了
平板用你现在的nook hd+就行了，
如果4:3只有坑爹的iPad Mini的话至少等等看有没有3:2的安卓吧。
a*g
52 楼
I will really appreciate if you could elaborate more.
【在 A**u 的大作中提到】
: 你这不对
: 差多了
【在 A**u 的大作中提到】
: 你这不对
: 差多了
p*m
53 楼
hd+太大
【在 h****e 的大作中提到】
: 如果你看文字比较多，那我觉得你可能还是等等吧
: 去店里看看16:9的屏幕能否接受，反正我是不能
: 我觉得呢阅读就用eink好了
: 平板用你现在的nook hd+就行了，
: 如果4:3只有坑爹的iPad Mini的话至少等等看有没有3:2的安卓吧。
k*y
54 楼
Python写了一个，练练手
L = ['fooo', 'barr', 'wing', 'ding', 'wing']
S = 'lingmindraboofooowingdingbarrwingmonkeypoundcake'
# L1 stores distinct stings in L
# multiples counts the corresponding multiples
L1 = []
multiples = []
for str in L:
if str not in L1:
L1.append(str)
multiples.append(L.count(str))
# k is the lenght of each substring
k = len(L[0])
match = [0]*len(S)
checklist = []
for i in range(0, len(L1)):
mul = multiples[i]
list_pos = []
# find all possible positions matching L1[i]
pos = 0; pos = S.find(L1[i], pos, len(S))
while pos != -1:
list_pos.append(pos)
pos = S.find(L1[i], pos+1, len(S))
for j in range(0, len(list_pos)):
# only count those without too many occurrence
if (j+mul >= len(list_pos)
or list_pos[j] + k*len(L) < list_pos[j+mul]):
match[list_pos[j]] = 1
checklist.append(list_pos[j])
for i in range(0, len(checklist)):
pos = checklist[i]
j = 0
while j < len(L):
if match[pos+j*k] == 0:
break
j += 1
if j == len(L):
print S[checklist[i]:checklist[i]+k*len(L)]
break
L = ['fooo', 'barr', 'wing', 'ding', 'wing']
S = 'lingmindraboofooowingdingbarrwingmonkeypoundcake'
# L1 stores distinct stings in L
# multiples counts the corresponding multiples
L1 = []
multiples = []
for str in L:
if str not in L1:
L1.append(str)
multiples.append(L.count(str))
# k is the lenght of each substring
k = len(L[0])
match = [0]*len(S)
checklist = []
for i in range(0, len(L1)):
mul = multiples[i]
list_pos = []
# find all possible positions matching L1[i]
pos = 0; pos = S.find(L1[i], pos, len(S))
while pos != -1:
list_pos.append(pos)
pos = S.find(L1[i], pos+1, len(S))
for j in range(0, len(list_pos)):
# only count those without too many occurrence
if (j+mul >= len(list_pos)
or list_pos[j] + k*len(L) < list_pos[j+mul]):
match[list_pos[j]] = 1
checklist.append(list_pos[j])
for i in range(0, len(checklist)):
pos = checklist[i]
j = 0
while j < len(L):
if match[pos+j*k] == 0:
break
j += 1
if j == len(L):
print S[checklist[i]:checklist[i]+k*len(L)]
break
D*r
55 楼
仍然推荐Nexus 7. 屏幕足够了。
【在 c*****h 的大作中提到】
: 我可以折腾的。
【在 c*****h 的大作中提到】
: 我可以折腾的。
h*g
56 楼
Given a list of words, L, that are all the same length, and a string, S,
find the starting position of the substring of S that is a concatenation of
each word in L exactly once and without any intervening characters. This
substring will occur exactly once in S..
.
Example:.
L: "fooo", "barr", "wing", "ding", "wing".
S: "lingmindraboofooowingdingbarrwingmonkeypoundcake".
fooowingdingbarrwing.
trie的话，现场写程序不方便吧？
find the starting position of the substring of S that is a concatenation of
each word in L exactly once and without any intervening characters. This
substring will occur exactly once in S..
.
Example:.
L: "fooo", "barr", "wing", "ding", "wing".
S: "lingmindraboofooowingdingbarrwingmonkeypoundcake".
fooowingdingbarrwing.
trie的话，现场写程序不方便吧？
c*y
57 楼
如果要随身带，应该给它配网络吧。
如果真想折腾，N7 3G + tmobile + 翻墙
【在 c*****h 的大作中提到】
: 我可以折腾的。
如果真想折腾，N7 3G + tmobile + 翻墙
【在 c*****h 的大作中提到】
: 我可以折腾的。
p*2
58 楼
trie的话写起来也还好。实现add, find两个函数应该就可以了。
这样就是N*L的复杂度了。
这样就是N*L的复杂度了。
c*h
59 楼
我现在随身的是ipad 3 4g，太重了。。。可惜mini不是高清屏，否则一早就跳了。
【在 c*******y 的大作中提到】
: 如果要随身带，应该给它配网络吧。
: 如果真想折腾，N7 3G + tmobile + 翻墙
【在 c*******y 的大作中提到】
: 如果要随身带，应该给它配网络吧。
: 如果真想折腾，N7 3G + tmobile + 翻墙
p*2
60 楼
写了一个练练手。
import java.util.*;
class Node
{
Node[] children=new Node[26];
public Node Set(char c)
{
Node node=new Node();
children[c-'a']=node;
return node;
}
public Node Get(char c)
{
return children[c-'a'];
}
}
class Trie
{
Node root=new Node();
public void Add(String word)
{
int i=0;
Node node=root;
while(i
char c=word.charAt(i);
if(node.Get(c)==null)
node=node.Set(c);
else
node=node.Get(c);
i++;
}
}
public boolean Find(String word)
{
boolean ret=true;
int i=0;
Node node=root;
while(i
char c=word.charAt(i);
if(node.Get(c)!=null)
node=node.Get(c);
else
{
ret=false;
break;
}
i++;
}
return ret;
}
}
public class Solution
{
static String[] L;
static int len;
static Trie trie=new Trie();
static HashMap hm=new HashMap();
public static boolean Check(String str)
{
HashMap ht=new HashMap();
for(int i=0;i
String sub=str.substring(i*len,i*len+len);
if(trie.Find(sub))
{
if(ht.containsKey(sub))
ht.put(sub, ht.get(sub)+1);
else
ht.put(sub, 1);
}
else
return false;
}
if(hm.size()!=ht.size())
return false;
for(String s: hm.keySet())
{
if(hm.get(s)!=ht.get(s))
return false;
}
return true;
}
public static void main(String[] args)
{
L=new String[]{ "fooo", "barr", "wing", "ding", "wing"};
len=4;
for(String s:L)
{
trie.Add(s);
if(hm.containsKey(s))
hm.put(s, hm.get(s)+1);
else
hm.put(s, 1);
}
int totalLen=len*L.length;
String S="lingmindraboofooowingdingbarrwingmonkeypoundcake";
for(int i=0;i<=S.length()-totalLen;i++)
{
if(Check(S.substring(i,i+totalLen)))
{
System.out.println(S.substring(i,i+totalLen));
break;
}
}
}
}
import java.util.*;
class Node
{
Node[] children=new Node[26];
public Node Set(char c)
{
Node node=new Node();
children[c-'a']=node;
return node;
}
public Node Get(char c)
{
return children[c-'a'];
}
}
class Trie
{
Node root=new Node();
public void Add(String word)
{
int i=0;
Node node=root;
while(i
char c=word.charAt(i);
if(node.Get(c)==null)
node=node.Set(c);
else
node=node.Get(c);
i++;
}
}
public boolean Find(String word)
{
boolean ret=true;
int i=0;
Node node=root;
while(i
char c=word.charAt(i);
if(node.Get(c)!=null)
node=node.Get(c);
else
{
ret=false;
break;
}
i++;
}
return ret;
}
}
public class Solution
{
static String[] L;
static int len;
static Trie trie=new Trie();
static HashMap
public static boolean Check(String str)
{
HashMap
for(int i=0;i
String sub=str.substring(i*len,i*len+len);
if(trie.Find(sub))
{
if(ht.containsKey(sub))
ht.put(sub, ht.get(sub)+1);
else
ht.put(sub, 1);
}
else
return false;
}
if(hm.size()!=ht.size())
return false;
for(String s: hm.keySet())
{
if(hm.get(s)!=ht.get(s))
return false;
}
return true;
}
public static void main(String[] args)
{
L=new String[]{ "fooo", "barr", "wing", "ding", "wing"};
len=4;
for(String s:L)
{
trie.Add(s);
if(hm.containsKey(s))
hm.put(s, hm.get(s)+1);
else
hm.put(s, 1);
}
int totalLen=len*L.length;
String S="lingmindraboofooowingdingbarrwingmonkeypoundcake";
for(int i=0;i<=S.length()-totalLen;i++)
{
if(Check(S.substring(i,i+totalLen)))
{
System.out.println(S.substring(i,i+totalLen));
break;
}
}
}
}
c*h
61 楼
HD+ 是LD的。。。。我自己只有ipad 3 4g。
【在 h****e 的大作中提到】
: 如果你看文字比较多，那我觉得你可能还是等等吧
: 去店里看看16:9的屏幕能否接受，反正我是不能
: 我觉得呢阅读就用eink好了
: 平板用你现在的nook hd+就行了，
: 如果4:3只有坑爹的iPad Mini的话至少等等看有没有3:2的安卓吧。
【在 h****e 的大作中提到】
: 如果你看文字比较多，那我觉得你可能还是等等吧
: 去店里看看16:9的屏幕能否接受，反正我是不能
: 我觉得呢阅读就用eink好了
: 平板用你现在的nook hd+就行了，
: 如果4:3只有坑爹的iPad Mini的话至少等等看有没有3:2的安卓吧。
c*e
62 楼
不觉得你需要trie, hashtable is enough..
【在 p*****2 的大作中提到】
: 写了一个练练手。
: import java.util.*;
: class Node
: {
: Node[] children=new Node[26];
:
: public Node Set(char c)
: {
: Node node=new Node();
: children[c-'a']=node;
【在 p*****2 的大作中提到】
: 写了一个练练手。
: import java.util.*;
: class Node
: {
: Node[] children=new Node[26];
:
: public Node Set(char c)
: {
: Node node=new Node();
: children[c-'a']=node;
w*g
63 楼
继续当高富帅吧. N7是萎缩男的标配.
【在 c*****h 的大作中提到】
: HD+ 是LD的。。。。我自己只有ipad 3 4g。
【在 c*****h 的大作中提到】
: HD+ 是LD的。。。。我自己只有ipad 3 4g。
p*2
64 楼
没错。
【在 c*****e 的大作中提到】
: 不觉得你需要trie, hashtable is enough..
c*y
65 楼
我想找一个随身带的7寸，找了好几个月了，最后买了ipad mini。
n7的问题是带鱼屏。分辨率是不差，不过我猜，用过高分之后，
这个分辨率也不能入眼。
既然各方面都很平庸，那我就选mini吧，它毕竟有两个第一，
外观第一好，屏幕第一差
n7的问题是带鱼屏。分辨率是不差，不过我猜，用过高分之后，
这个分辨率也不能入眼。
既然各方面都很平庸，那我就选mini吧，它毕竟有两个第一，
外观第一好，屏幕第一差
H*e
66 楼
这个find是不是有点问题？只要是前缀就return true了吧？
【在 p*****2 的大作中提到】
: 写了一个练练手。
: import java.util.*;
: class Node
: {
: Node[] children=new Node[26];
:
: public Node Set(char c)
: {
: Node node=new Node();
: children[c-'a']=node;
【在 p*****2 的大作中提到】
: 写了一个练练手。
: import java.util.*;
: class Node
: {
: Node[] children=new Node[26];
:
: public Node Set(char c)
: {
: Node node=new Node();
: children[c-'a']=node;
w*g
67 楼
轻薄你就不说了?
【在 c*******y 的大作中提到】
: 我想找一个随身带的7寸，找了好几个月了，最后买了ipad mini。
: n7的问题是带鱼屏。分辨率是不差，不过我猜，用过高分之后，
: 这个分辨率也不能入眼。
: 既然各方面都很平庸，那我就选mini吧，它毕竟有两个第一，
: 外观第一好，屏幕第一差
【在 c*******y 的大作中提到】
: 我想找一个随身带的7寸，找了好几个月了，最后买了ipad mini。
: n7的问题是带鱼屏。分辨率是不差，不过我猜，用过高分之后，
: 这个分辨率也不能入眼。
: 既然各方面都很平庸，那我就选mini吧，它毕竟有两个第一，
: 外观第一好，屏幕第一差
p*2
68 楼
他的题目说的是单词的长度一致，所以应该一定match.
【在 H***e 的大作中提到】
: 这个find是不是有点问题？只要是前缀就return true了吧？
c*y
69 楼
外观包括了轻薄
【在 w*****g 的大作中提到】
: 轻薄你就不说了?
【在 w*****g 的大作中提到】
: 轻薄你就不说了?
b*u
70 楼
嗯，trie的特性没什么帮助。
【在 c*****e 的大作中提到】
: 不觉得你需要trie, hashtable is enough..
【在 c*****e 的大作中提到】
: 不觉得你需要trie, hashtable is enough..
c*h
71 楼
所以我等mini二代高清屏阿。。。
【在 c*******y 的大作中提到】
: 我想找一个随身带的7寸，找了好几个月了，最后买了ipad mini。
: n7的问题是带鱼屏。分辨率是不差，不过我猜，用过高分之后，
: 这个分辨率也不能入眼。
: 既然各方面都很平庸，那我就选mini吧，它毕竟有两个第一，
: 外观第一好，屏幕第一差
【在 c*******y 的大作中提到】
: 我想找一个随身带的7寸，找了好几个月了，最后买了ipad mini。
: n7的问题是带鱼屏。分辨率是不差，不过我猜，用过高分之后，
: 这个分辨率也不能入眼。
: 既然各方面都很平庸，那我就选mini吧，它毕竟有两个第一，
: 外观第一好，屏幕第一差
a*n
72 楼
直接用HASHMAP/RABIN-KARP测试就行了吧，，，加上长度都是４就更简单了。。。每次
产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。
产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。
g*g
73 楼
随时带个板子一般什么时候用？有公交可坐？
【在 c*****h 的大作中提到】
: 我现在随身的是ipad 3 4g，太重了。。。可惜mini不是高清屏，否则一早就跳了。
【在 c*****h 的大作中提到】
: 我现在随身的是ipad 3 4g，太重了。。。可惜mini不是高清屏，否则一早就跳了。
q*c
74 楼
Isn't it similar to strstr? Is it a phone or onsite question?
c*h
75 楼
在公司上qq、上mitbbs、上yahoo mail、gmail，上各种被公司block掉的网。
每个人情况不同么，你用不着，不等于别人就用不着阿。
【在 g*g 的大作中提到】
: 随时带个板子一般什么时候用？有公交可坐？
每个人情况不同么，你用不着，不等于别人就用不着阿。
【在 g*g 的大作中提到】
: 随时带个板子一般什么时候用？有公交可坐？
a*g
76 楼
c++ practice (use multiset):
#include
#include
using std::multiset;
using std::string;
int len_p = 4;
bool check_substr(string s, const multiset &L) {
multiset dup_L = L;
for (unsigned i=0; i
multiset::iterator itor = dup_L.find(token);
if (itor == dup_L.end()) {
return false;
}
dup_L.erase(itor);
}
return dup_L.empty();
}
int main(int argc, char* argv[])
{
multiset L;
L.insert("fooo");
L.insert("barr");
L.insert("wing");
L.insert("ding");
L.insert("wing");
const string S = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
int size_L = L.size();
int len_substr = len_p * size_L;
for (unsigned i=0; i < S.length() - len_substr; i++) {
if (check_substr(S.substr(i, len_substr), L)) {
printf("found. pos:%d\n", i);
return 0;
}
}
printf("not found.\n");
return 0;
}
It's not trivial to me how to apply RK algorithm to this problem but I guess
defining a hash function using histogram of characters might work.
#include
#include
using std::multiset;
using std::string;
int len_p = 4;
bool check_substr(string s, const multiset
multiset
for (unsigned i=0; i
multiset
if (itor == dup_L.end()) {
return false;
}
dup_L.erase(itor);
}
return dup_L.empty();
}
int main(int argc, char* argv[])
{
multiset
L.insert("fooo");
L.insert("barr");
L.insert("wing");
L.insert("ding");
L.insert("wing");
const string S = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
int size_L = L.size();
int len_substr = len_p * size_L;
for (unsigned i=0; i < S.length() - len_substr; i++) {
if (check_substr(S.substr(i, len_substr), L)) {
printf("found. pos:%d\n", i);
return 0;
}
}
printf("not found.\n");
return 0;
}
It's not trivial to me how to apply RK algorithm to this problem but I guess
defining a hash function using histogram of characters might work.
g*g
77 楼
明白了，就是问问而已，呵呵，
你们上班生活很丰富嘛，不过拿个板子有点显眼啊
【在 c*****h 的大作中提到】
: 在公司上qq、上mitbbs、上yahoo mail、gmail，上各种被公司block掉的网。
: 每个人情况不同么，你用不着，不等于别人就用不着阿。
你们上班生活很丰富嘛，不过拿个板子有点显眼啊
【在 c*****h 的大作中提到】
: 在公司上qq、上mitbbs、上yahoo mail、gmail，上各种被公司block掉的网。
: 每个人情况不同么，你用不着，不等于别人就用不着阿。
g*e
78 楼
如果某个字符串在table 里找到了重复的，但这时其他串还没全找到，怎么办？
【在 a*****n 的大作中提到】
: 直接用HASHMAP/RABIN-KARP测试就行了吧，，，加上长度都是４就更简单了。。。每次
: 产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。
【在 a*****n 的大作中提到】
: 直接用HASHMAP/RABIN-KARP测试就行了吧，，，加上长度都是４就更简单了。。。每次
: 产生４个字符的字符串到HASH-MAP里面匹配。全找到就结束，没找到就继续。。
c*h
79 楼
架在几个显示屏的中间，还配个蓝牙键盘。不是分分钟都扑在上面就行，干活干好了，
老板也不管的。
【在 g*g 的大作中提到】
: 明白了，就是问问而已，呵呵，
: 你们上班生活很丰富嘛，不过拿个板子有点显眼啊
老板也不管的。
【在 g*g 的大作中提到】
: 明白了，就是问问而已，呵呵，
: 你们上班生活很丰富嘛，不过拿个板子有点显眼啊
A*u
80 楼
你这不对
差多了
【在 a*****g 的大作中提到】
: c++ practice (use multiset):
: #include
: #include
: using std::multiset;
: using std::string;
: int len_p = 4;
: bool check_substr(string s, const multiset &L) {
: multiset dup_L = L;
: for (unsigned i=0; i
差多了
【在 a*****g 的大作中提到】
: c++ practice (use multiset):
: #include
: #include
: using std::multiset;
: using std::string;
: int len_p = 4;
: bool check_substr(string s, const multiset
: multiset
: for (unsigned i=0; i
g*g
81 楼
那你是买带sim的板子？$230这个是wifi版的吧
还是用手机tether?
【在 c*****h 的大作中提到】
: 架在几个显示屏的中间，还配个蓝牙键盘。不是分分钟都扑在上面就行，干活干好了，
: 老板也不管的。
还是用手机tether?
【在 c*****h 的大作中提到】
: 架在几个显示屏的中间，还配个蓝牙键盘。不是分分钟都扑在上面就行，干活干好了，
: 老板也不管的。
j*b
82 楼
没想到什么特别巧的办法，brute force ＋ hashmap？
public static void main(String[] args) {
String l[] = { "fooo", "barr", "wing", "ding", "wing" };
Map map = new HashMap();
for (int i = 0; i < l.length; i++){
if(map.containsKey(l[i]))
map.put(l[i], map.get(l[i]) +1);
else
map.put(l[i], 1);
}
String s = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
int len = l[0].length();
for (int j = 0; j < len; j++) {
Map map2 = new HashMap();
for (int i = j; i <= s.length() - len; i+=len) {
String ss = s.substring(i, i + len);
if (map.containsKey(ss)) {
if(!map2.containsKey(ss) || map2.get(ss) < map.get(ss)){
if(map2.containsKey(ss))
map2.put(ss, map2.get(ss)+1);
else
map2.put(ss, 1);
if(map2.entrySet().equals(map.entrySet())){
String r =s.substring(i+len-l.length*len,i+len);
System.out.println(r);
return;
}
}else{
map2.clear();
}
}else{
map2.clear();
}
}
}
}
public static void main(String[] args) {
String l[] = { "fooo", "barr", "wing", "ding", "wing" };
Map
for (int i = 0; i < l.length; i++){
if(map.containsKey(l[i]))
map.put(l[i], map.get(l[i]) +1);
else
map.put(l[i], 1);
}
String s = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
int len = l[0].length();
for (int j = 0; j < len; j++) {
Map
for (int i = j; i <= s.length() - len; i+=len) {
String ss = s.substring(i, i + len);
if (map.containsKey(ss)) {
if(!map2.containsKey(ss) || map2.get(ss) < map.get(ss)){
if(map2.containsKey(ss))
map2.put(ss, map2.get(ss)+1);
else
map2.put(ss, 1);
if(map2.entrySet().equals(map.entrySet())){
String r =s.substring(i+len-l.length*len,i+len);
System.out.println(r);
return;
}
}else{
map2.clear();
}
}else{
map2.clear();
}
}
}
}
c*h
83 楼
我现在的ipad 3是 wifi+4g的阿，有数据plan的。
只是想再搞个7寸安卓二奶机玩玩而已。。。
【在 g*g 的大作中提到】
: 那你是买带sim的板子？$230这个是wifi版的吧
: 还是用手机tether?
只是想再搞个7寸安卓二奶机玩玩而已。。。
【在 g*g 的大作中提到】
: 那你是买带sim的板子？$230这个是wifi版的吧
: 还是用手机tether?
h*w
84 楼
mark
d*0
85 楼
看惯了HD+，看N7不太行
s*e
86 楼
用HASHMAP 找出每个WORD 所在的位置 occurrence map，在做一个反向的由所在位置(
position)到WORD 的reverse occurrence map。 吧这些position 排序，然后递归搜索。
package smartnose;
import java.util.Arrays;
import java.util.*;
public class SubWordSeq {
public static void main(String [] args){
List L = new LinkedList();
L.add("fooo");L.add("barr");L.add("wing");L.add("ding");L.add("wing"
);
String S= "lingmindraboofooowingdingbarrwingmonkeypoundcake";
HashMap> occurMap = new HashMap
for(String word:L){
occurMap.put(word, new ArrayList());
}
int wordLen = L.get(0).length();
for(int i=0;i+wordLen
if(occurMap.containsKey(sub))//add the occurrance
occurMap.get(sub).add(i);
}
HashMap> rOccurMap = new HashMap>();
for(String w: occurMap.keySet()){
List occ = occurMap.get(w);
for(Integer pos: occ){
if(rOccurMap.containsKey(pos)){
rOccurMap.get(pos).add(w);
}
else{
rOccurMap.put(pos, Arrays.asList(w));
}
}
}
List distinctPos = new ArrayList();
distinctPos.addAll(rOccurMap.keySet());
Collections.sort(distinctPos);
//now search the f*ck out of it.
for(Integer start:distinctPos)
if(recurSearch(L,rOccurMap,start,wordLen)){
System.out.println("found one instance starting at:"+start);
break;
}
}
public static boolean recurSearch(List L, HashMap
if(L.isEmpty())
return true;
List cWords = rMap.get(curPos);
for(String w: cWords){
if(L.contains(w)){
//L.remove(w);
int idx=L.indexOf(w);
L.remove(idx);//can be more efficient
if(recurSearch(L, rMap, curPos+wLen, wLen))
return true;
L.add(w);
}
}
return false;
}
}
position)到WORD 的reverse occurrence map。 吧这些position 排序，然后递归搜索。
package smartnose;
import java.util.Arrays;
import java.util.*;
public class SubWordSeq {
public static void main(String [] args){
List
L.add("fooo");L.add("barr");L.add("wing");L.add("ding");L.add("wing"
);
String S= "lingmindraboofooowingdingbarrwingmonkeypoundcake";
HashMap
for(String word:L){
occurMap.put(word, new ArrayList
}
int wordLen = L.get(0).length();
for(int i=0;i+wordLen
if(occurMap.containsKey(sub))//add the occurrance
occurMap.get(sub).add(i);
}
HashMap
for(String w: occurMap.keySet()){
List
for(Integer pos: occ){
if(rOccurMap.containsKey(pos)){
rOccurMap.get(pos).add(w);
}
else{
rOccurMap.put(pos, Arrays.asList(w));
}
}
}
List
distinctPos.addAll(rOccurMap.keySet());
Collections.sort(distinctPos);
//now search the f*ck out of it.
for(Integer start:distinctPos)
if(recurSearch(L,rOccurMap,start,wordLen)){
System.out.println("found one instance starting at:"+start);
break;
}
}
public static boolean recurSearch(List
if(L.isEmpty())
return true;
List
for(String w: cWords){
if(L.contains(w)){
//L.remove(w);
int idx=L.indexOf(w);
L.remove(idx);//can be more efficient
if(recurSearch(L, rMap, curPos+wLen, wLen))
return true;
L.add(w);
}
}
return false;
}
}
a*s
87 楼
mark
l*e
88 楼
mark
a*g
89 楼
I will really appreciate if you could elaborate more.
【在 A**u 的大作中提到】
: 你这不对
: 差多了
【在 A**u 的大作中提到】
: 你这不对
: 差多了
k*y
90 楼
Python写了一个，练练手
L = ['fooo', 'barr', 'wing', 'ding', 'wing']
S = 'lingmindraboofooowingdingbarrwingmonkeypoundcake'
# L1 stores distinct stings in L
# multiples counts the corresponding multiples
L1 = []
multiples = []
for str in L:
if str not in L1:
L1.append(str)
multiples.append(L.count(str))
# k is the lenght of each substring
k = len(L[0])
match = [0]*len(S)
checklist = []
for i in range(0, len(L1)):
mul = multiples[i]
list_pos = []
# find all possible positions matching L1[i]
pos = 0; pos = S.find(L1[i], pos, len(S))
while pos != -1:
list_pos.append(pos)
pos = S.find(L1[i], pos+1, len(S))
for j in range(0, len(list_pos)):
# only count those without too many occurrence
if (j+mul >= len(list_pos)
or list_pos[j] + k*len(L) < list_pos[j+mul]):
match[list_pos[j]] = 1
checklist.append(list_pos[j])
for i in range(0, len(checklist)):
pos = checklist[i]
j = 0
while j < len(L):
if match[pos+j*k] == 0:
break
j += 1
if j == len(L):
print S[checklist[i]:checklist[i]+k*len(L)]
break
L = ['fooo', 'barr', 'wing', 'ding', 'wing']
S = 'lingmindraboofooowingdingbarrwingmonkeypoundcake'
# L1 stores distinct stings in L
# multiples counts the corresponding multiples
L1 = []
multiples = []
for str in L:
if str not in L1:
L1.append(str)
multiples.append(L.count(str))
# k is the lenght of each substring
k = len(L[0])
match = [0]*len(S)
checklist = []
for i in range(0, len(L1)):
mul = multiples[i]
list_pos = []
# find all possible positions matching L1[i]
pos = 0; pos = S.find(L1[i], pos, len(S))
while pos != -1:
list_pos.append(pos)
pos = S.find(L1[i], pos+1, len(S))
for j in range(0, len(list_pos)):
# only count those without too many occurrence
if (j+mul >= len(list_pos)
or list_pos[j] + k*len(L) < list_pos[j+mul]):
match[list_pos[j]] = 1
checklist.append(list_pos[j])
for i in range(0, len(checklist)):
pos = checklist[i]
j = 0
while j < len(L):
if match[pos+j*k] == 0:
break
j += 1
if j == len(L):
print S[checklist[i]:checklist[i]+k*len(L)]
break
s*f
91 楼
//码遍本版
//inside for LOOP:
//1st round: check (ling)(mind)(rabo)(ofooowingdingbarrwingmonkeypoundcake
//2nd round: check l(ingm)(indr)(aboo)(fooowingdingbarrwingmonkeypoundcake
//...
//this can avoid double check, and, O(n) time, for slice window
string SubStrWordsGreat(const char *str, const vector &vs){
map ms;
int len = strlen(str);
const char *end = str + len;
int lensub = 0;
if (vs.size() == 0)
return "";
int sz = vs[0].size();
for (vector::const_iterator it = vs.begin(); it != vs.end(); ++
it){
++ms[*it];
lensub += it->size();
}
for (int i = 0; i < sz; ++i){
const char *left = str + i;
const char *right = left;
int count = 0;
while (end - left >= lensub){
string s = string(right, right + sz);
if (ms.find(s) == ms.end()){
//recover map
for (; left < right; left += sz){
string ss = string(left, left + sz);
++ms[ss];
--count;
}
left += sz;
right = left;
} else if (ms[s] == 0){
for (; left < right; left += sz){
string ss = string(left, left + sz);
if (ss == s){
left += sz;
break;
} else {
++ms[ss];
--count;
}
}
} else {
--ms[s];
if (++count == vs.size()){
return string(left, right + sz);
}
right += sz;
}
}
}
return "";
}
void TestSubStrWords(){
vector vs;
vs.push_back("fooo");
vs.push_back("barr");
vs.push_back("wing");
vs.push_back("ding");
vs.push_back("wing");
string a = SubStrWordsGreat("
lingmindraboofooowingdingbarrwingmonkeypoundcake", vs);
}
of
【在 h*****g 的大作中提到】
: Given a list of words, L, that are all the same length, and a string, S,
: find the starting position of the substring of S that is a concatenation of
: each word in L exactly once and without any intervening characters. This
: substring will occur exactly once in S..
: .
: Example:.
: L: "fooo", "barr", "wing", "ding", "wing".
: S: "lingmindraboofooowingdingbarrwingmonkeypoundcake".
: fooowingdingbarrwing.
: trie的话，现场写程序不方便吧？
//inside for LOOP:
//1st round: check (ling)(mind)(rabo)(ofooowingdingbarrwingmonkeypoundcake
//2nd round: check l(ingm)(indr)(aboo)(fooowingdingbarrwingmonkeypoundcake
//...
//this can avoid double check, and, O(n) time, for slice window
string SubStrWordsGreat(const char *str, const vector
map
int len = strlen(str);
const char *end = str + len;
int lensub = 0;
if (vs.size() == 0)
return "";
int sz = vs[0].size();
for (vector
it){
++ms[*it];
lensub += it->size();
}
for (int i = 0; i < sz; ++i){
const char *left = str + i;
const char *right = left;
int count = 0;
while (end - left >= lensub){
string s = string(right, right + sz);
if (ms.find(s) == ms.end()){
//recover map
for (; left < right; left += sz){
string ss = string(left, left + sz);
++ms[ss];
--count;
}
left += sz;
right = left;
} else if (ms[s] == 0){
for (; left < right; left += sz){
string ss = string(left, left + sz);
if (ss == s){
left += sz;
break;
} else {
++ms[ss];
--count;
}
}
} else {
--ms[s];
if (++count == vs.size()){
return string(left, right + sz);
}
right += sz;
}
}
}
return "";
}
void TestSubStrWords(){
vector
vs.push_back("fooo");
vs.push_back("barr");
vs.push_back("wing");
vs.push_back("ding");
vs.push_back("wing");
string a = SubStrWordsGreat("
lingmindraboofooowingdingbarrwingmonkeypoundcake", vs);
}
of
【在 h*****g 的大作中提到】
: Given a list of words, L, that are all the same length, and a string, S,
: find the starting position of the substring of S that is a concatenation of
: each word in L exactly once and without any intervening characters. This
: substring will occur exactly once in S..
: .
: Example:.
: L: "fooo", "barr", "wing", "ding", "wing".
: S: "lingmindraboofooowingdingbarrwingmonkeypoundcake".
: fooowingdingbarrwing.
: trie的话，现场写程序不方便吧？
d*u
92 楼
这题用hashtable的话算是比较平庸的解法，应该达不到facebook或google的要求。正
确的做法是用单词树作为查找容器。
确的做法是用单词树作为查找容器。
S*t
93 楼
It is easy to come up with an $O(SL)$ algorithm for this problem but what is
good about this problem is that it actually has a linear time solution:
Let’s first make some notations clear:
1) |S| -> The length of S.
2) |L| -> The number of words in the list $L$.
3) $len_L$ -> The length of each string in $L$.
First we use an Aho-Corasick automaton to find out the occurrences of all
patterns. The time complexity of this step is $O(|S| + |L| * len_L + z)$
where $z$ is the number of output matches. However, since in this problem,
each index in the text string can correspond to at most one match. Therefore
, z < |S| and the complexity is therefore bounded by $O(|S| + |L| * len_L)$.
In the second step, we’ve now had an array $f$, where f[i] indicates
whether we can match a string in $L$ with substring $S[i..i+len_L-1]$. If
there is a match, f[i] = #the index of matched string in L$, otherwise f[i]
= -1.
Next, we divide this array into $len_L$ subarrays, where each subarray is of
the form: {f[i], f[i+len_L], f[i+2*len_L], …, f[i+k*len_L]}. So in each
array, what we are looking for is in fact a contiguous subarray of length |L
| which is in fact a permutation of numbers from 1 to L. We can use a deque
to achieve this aim. We first push_back the elements in each array till we
find a conflict. (i.e. the element we are going to push has already existed
in the deque). When this happens, we pop_front until the conflicted element
has been popped out of the deque. This algorithm continues till the number
of elements in the deque reaches |L|. (Yes, we do have to handle -1 cases
separately but that is quite easy.) The complexity to handle each subarray
is linear and the overall complexity is still linear.
Therefore the time complexity of the algorithm is dominated by the first
step, which is $O(|S| + |L| * len_L)$ and since |L| * len_L < |S|, the
algorithm is indeed $O(S)$.
Now let’s consider the case where there might be repetitive strings in L.
We first count the numbers of unique strings in $L$ and for each unique
string, we count the actual appearance of that string in $L$.
Then the Aho-Corasick part is still the same and we can guarantee the time
complexity is still bounded linearly.
The only difference is in the deque part where we change the conflicting
part a bit from whether that $f[i]$ already exists in deque to whether $f[i]
< cnt[f[i]]$ in deque.
And that still makes our algorithm linear. Problem solved.
good about this problem is that it actually has a linear time solution:
Let’s first make some notations clear:
1) |S| -> The length of S.
2) |L| -> The number of words in the list $L$.
3) $len_L$ -> The length of each string in $L$.
First we use an Aho-Corasick automaton to find out the occurrences of all
patterns. The time complexity of this step is $O(|S| + |L| * len_L + z)$
where $z$ is the number of output matches. However, since in this problem,
each index in the text string can correspond to at most one match. Therefore
, z < |S| and the complexity is therefore bounded by $O(|S| + |L| * len_L)$.
In the second step, we’ve now had an array $f$, where f[i] indicates
whether we can match a string in $L$ with substring $S[i..i+len_L-1]$. If
there is a match, f[i] = #the index of matched string in L$, otherwise f[i]
= -1.
Next, we divide this array into $len_L$ subarrays, where each subarray is of
the form: {f[i], f[i+len_L], f[i+2*len_L], …, f[i+k*len_L]}. So in each
array, what we are looking for is in fact a contiguous subarray of length |L
| which is in fact a permutation of numbers from 1 to L. We can use a deque
to achieve this aim. We first push_back the elements in each array till we
find a conflict. (i.e. the element we are going to push has already existed
in the deque). When this happens, we pop_front until the conflicted element
has been popped out of the deque. This algorithm continues till the number
of elements in the deque reaches |L|. (Yes, we do have to handle -1 cases
separately but that is quite easy.) The complexity to handle each subarray
is linear and the overall complexity is still linear.
Therefore the time complexity of the algorithm is dominated by the first
step, which is $O(|S| + |L| * len_L)$ and since |L| * len_L < |S|, the
algorithm is indeed $O(S)$.
Now let’s consider the case where there might be repetitive strings in L.
We first count the numbers of unique strings in $L$ and for each unique
string, we count the actual appearance of that string in $L$.
Then the Aho-Corasick part is still the same and we can guarantee the time
complexity is still bounded linearly.
The only difference is in the deque part where we change the conflicting
part a bit from whether that $f[i]$ already exists in deque to whether $f[i]
< cnt[f[i]]$ in deque.
And that still makes our algorithm linear. Problem solved.
h*8
94 楼
Can you elaborate it? Thanks!
is
Therefore
【在 S******t 的大作中提到】
: It is easy to come up with an $O(SL)$ algorithm for this problem but what is
: good about this problem is that it actually has a linear time solution:
: Let’s first make some notations clear:
: 1) |S| -> The length of S.
: 2) |L| -> The number of words in the list $L$.
: 3) $len_L$ -> The length of each string in $L$.
: First we use an Aho-Corasick automaton to find out the occurrences of all
: patterns. The time complexity of this step is $O(|S| + |L| * len_L + z)$
: where $z$ is the number of output matches. However, since in this problem,
: each index in the text string can correspond to at most one match. Therefore
is
Therefore
【在 S******t 的大作中提到】
: It is easy to come up with an $O(SL)$ algorithm for this problem but what is
: good about this problem is that it actually has a linear time solution:
: Let’s first make some notations clear:
: 1) |S| -> The length of S.
: 2) |L| -> The number of words in the list $L$.
: 3) $len_L$ -> The length of each string in $L$.
: First we use an Aho-Corasick automaton to find out the occurrences of all
: patterns. The time complexity of this step is $O(|S| + |L| * len_L + z)$
: where $z$ is the number of output matches. However, since in this problem,
: each index in the text string can correspond to at most one match. Therefore
相关阅读
300bp的DNA怎么测序结果500bp为什么没有大牛站出来3 way anova转：韩春雨“诺奖级”争议升级 方舟子指其博士论文造假大龄单身女博士求发展建议人民日报：诺贝尔奖级实验结果遭质疑 ，《自然》杂志：将调查寻求ＭＩＭＩＣＳ软件高手, 最好在匹兹堡韩春雨是党员吗，还是信佛道基督？2014年11月份Gao Feng还在做CasE的课题韩春雨回应质疑：对重复实验充满信心大刘的科幻小说球状闪电诚聘神经、骨科、肿瘤、干细胞、内分泌、妇科等兼职韩春雨可能跟当年的金凤汉一样，没有造假 (转载)韩春雨提供给300个实验室的质粒同论文里的质粒不一致？小保，韩两次事件说明nature系比science low要害问题不是韩春雨可以重复，而是20个实验室可以重复NBT已经启动调查了，韩黑能不能消停几天韩春雨论文的假就在论文里记得2000年时候拿到海外读博士offer韩爷必定过关，老千终将悲愤