关于contribution - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Immigration - 落地生根

关于contribution

关于contribution# Immigration - 落地生根

p*o2011-11-11 08:11

1 楼

LeetCode上的题目，我怎么想都是O(kn)，k是T里的unique charater的数目。请问大侠
如何做到O(n)。
附题目：
Given a string S and a string T, find the minimum window in S which will
contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

l*u2011-11-11 08:11

2 楼

我怀疑被天燃气公司Scana Energy 骗了。使用它的天然气取暖，就是空调的加热功能
。空调的制冷用电，不用天燃气。热水用天然气，但是小区统一加热，平滩在水费里了。
从6月开始，天气变暖，不再用了。但还是每个月用 5个 CCF （CCF 好像是天然气的体
积单位）。为什么每个月用的一样多？以往天冷用天然气取暖时，每月30-40 CCF 不等。
5个 CCF 只要$5,但是只要不是 0 CCF,就要交 Customer Service Charge， Atlanta
Gas Light Pass Through Charges，再加上税，一个月就要$30
有没有可能管道或阀门漏气？

l*a2011-11-11 08:11

3 楼

各位灌好.实在孩子课外活动太多.
其实这种投资很值得,HOMESCHOOL的孩子这里非常多.

s*a2011-11-11 08:11

4 楼

以前读书期间在某小公司实习，做的东西申请了个专利还在pending，但是那个东西应
该是被他们用在生产系统里了，这个可以算一个contribution么？
另外，读书期间的课题是和一个大公司合作的，做的东西可能被他们的某些部门拿了在
用或者继续研究，这也可以算一个contribution么？

Z*Z2011-11-11 08:11

5 楼

假设T的长度是k，如果你先把T扫一遍所有字母放到一个hashtable里，然后再扫S，对S
里面的每一个字母，查询hashtable的时间是常数，这样算下来时O(k+n)的。
当然这只是复杂度分析不是算法。你O（kn）的算法是怎样的？

【在 p*****o 的大作中提到】

: LeetCode上的题目，我怎么想都是O(kn)，k是T里的unique charater的数目。请问大侠
: 如何做到O(n)。
: 附题目：
: Given a string S and a string T, find the minimum window in S which will
: contain all the characters in T in complexity O(n).
: For example,
: S = "ADOBECODEBANC"
: T = "ABC"
: Minimum window is "BANC".

s*e2011-11-11 08:11

6 楼

CSS AGLC 这是基本费只要你开了气就跑不了
除非你不用气就不用抱怨了

了。
等。

【在 l***u 的大作中提到】

: 我怀疑被天燃气公司Scana Energy 骗了。使用它的天然气取暖，就是空调的加热功能
: 。空调的制冷用电，不用天燃气。热水用天然气，但是小区统一加热，平滩在水费里了。
: 从6月开始，天气变暖，不再用了。但还是每个月用 5个 CCF （CCF 好像是天然气的体
: 积单位）。为什么每个月用的一样多？以往天冷用天然气取暖时，每月30-40 CCF 不等。
: 5个 CCF 只要$5,但是只要不是 0 CCF,就要交 Customer Service Charge， Atlanta
: Gas Light Pass Through Charges，再加上税，一个月就要$30
: 有没有可能管道或阀门漏气？

x*w2011-11-11 08:11

7 楼

有证据么？

p*o2011-11-11 08:11

8 楼

k 出现在用来找T中哪个字母最靠前。具体的，如果S里下一个字母是当前T中最靠前的
字母，替换以后需要找到T中下一个最靠前的字母。

对S

【在 Z*****Z 的大作中提到】

: 假设T的长度是k，如果你先把T扫一遍所有字母放到一个hashtable里，然后再扫S，对S
: 里面的每一个字母，查询hashtable的时间是常数，这样算下来时O(k+n)的。
: 当然这只是复杂度分析不是算法。你O（kn）的算法是怎样的？

l*u2011-11-11 08:11

9 楼

我就是没用，还是被每个月读表用了5个 CCF.怀疑是不是漏气？这样才会每个月漏的一
样多。或是表坏了。没用它也走？

s*a2011-11-11 08:11

10 楼

就是不知道证据怎么出，让公司写个证明可以么？

Z*Z2011-11-11 08:11

11 楼

嗯，看看这样想行不行：
先扫一遍T，把所有字符出现的次数存到一个hashtable（记做ht）里。
然后再弄另外一个hashtable(ht2)用于计数。
接下来用两个指针head和tail同时扫描S，先寻找初始解，再寻找最优解。
（1）在寻找初始解阶段，不停地advance head，每遇到一个S中的T字符就把ht2的相应
count++，直到ht2中每个key的count都比ht中相应key大（至少不小）。
然后不停地advance tail，每遇到一个S中的T字符就把ht2的相应count--，直到ht2中某
一个key的值恰好等于ht中相应key的值。
这就是初始解，记录之。
（2）寻找最优解。这时tail指向的就是T中最靠前的字符，advance head寻找它，同时
更新ht2，逻辑同（1）。找到之后再更新tail，逻辑也同（1）
不知道说清楚了没有。。。

【在 p*****o 的大作中提到】

: k 出现在用来找T中哪个字母最靠前。具体的，如果S里下一个字母是当前T中最靠前的
: 字母，替换以后需要找到T中下一个最靠前的字母。
:
: 对S

l*u2011-11-11 08:11

12 楼

我的问题是它为什么是5，不是0？因为我没用。
为什么总是5？
我的问题不是它为什么是5，不是2？

T*y2011-11-11 08:11

13 楼

yes, find someone in those two companies to write you letters.

【在 s********a 的大作中提到】

: 就是不知道证据怎么出，让公司写个证明可以么？

t*h2011-11-11 08:11

14 楼

这个是dp吧，然后backtracking？

中某

【在 Z*****Z 的大作中提到】

: 嗯，看看这样想行不行：
: 先扫一遍T，把所有字符出现的次数存到一个hashtable（记做ht）里。
: 然后再弄另外一个hashtable(ht2)用于计数。
: 接下来用两个指针head和tail同时扫描S，先寻找初始解，再寻找最优解。
: （1）在寻找初始解阶段，不停地advance head，每遇到一个S中的T字符就把ht2的相应
: count++，直到ht2中每个key的count都比ht中相应key大（至少不小）。
: 然后不停地advance tail，每遇到一个S中的T字符就把ht2的相应count--，直到ht2中某
: 一个key的值恰好等于ht中相应key的值。
: 这就是初始解，记录之。
: （2）寻找最优解。这时tail指向的就是T中最靠前的字符，advance head寻找它，同时

c*72011-11-11 08:11

15 楼

自己去看看煤气表。

k*e2011-11-11 08:11

16 楼

a letter from the company might work. also try to find some hard evidence,
such as online material showing that they use your research.

Z*Z2011-11-11 08:11

17 楼

我描述的这个方法不是DP也没有BT。要是高富帅知道更好或者更正确的做法请share :)

【在 t**********h 的大作中提到】

: 这个是dp吧，然后backtracking？
:
: 中某

e*i2011-11-11 08:11

18 楼

Maybe....
http://en.wikipedia.org/wiki/Pilot_light

了。
等。

【在 l***u 的大作中提到】

p*o2011-11-11 08:11

19 楼

en,跟我后来想到的差不多。不需要两个hashtable，可以用一个hashtable，节点用
queue，其中放字符出现的位置。

中某

【在 Z*****Z 的大作中提到】

s*e2011-11-11 08:11

20 楼

你开通了气就要交基本费除非你把服务停了
至于为什么是5，如楼上所说 Pilot light
这个火是一直点着的灭了就没热水出来了
而且热水器有温度感应它那炉子里的水低于一定温度就会自动加热以保证你想用热水
马上就能出来

【在 l***u 的大作中提到】

: 我的问题是它为什么是5，不是0？因为我没用。
: 为什么总是5？
: 我的问题不是它为什么是5，不是2？

Z*Z2011-11-11 08:11

21 楼

Queue其实可以取代tail指针。
关于一个hashtable，你是说把ht干掉还是ht2干掉？只用一个hashtable的话怎么给S和
T同时计数？

【在 p*****o 的大作中提到】

: en,跟我后来想到的差不多。不需要两个hashtable，可以用一个hashtable，节点用
: queue，其中放字符出现的位置。
:
: 中某

l*u2011-11-11 08:11

22 楼

多谢各位的回复。我还是没说明白。
热水（厨房里的和卫生间里的）不是用我的热水器加热的。我没有独立的热水器。整个
小区公用热水器。热水器用天然气加热。但是用多少天然气小区统一计算，每户分摊。
每月几块钱，和水费一起收。
通到我家的天然气只用作空调的加热功能，也就是取暖用。我说的是通到我家的个人天
然气。
我试过，刚搬进时，前一个星期还没开通个人天然气服务时，就有热水。家里停电时也
有热水。

t*h2011-11-11 08:11

23 楼

刚才没认真看，sorry。确实没dp，也没bt。明天有面试，不看新题了，复习复习旧题
，完了上来看大牛们的结论。。。

【在 Z*****Z 的大作中提到】

: 我描述的这个方法不是DP也没有BT。要是高富帅知道更好或者更正确的做法请share :)

B*y2011-11-11 08:11

24 楼

你自己打电话去公司问呀。可以就着Bill一项项的问，弄清楚它们是怎么读的表。。。

【在 l***u 的大作中提到】

: 多谢各位的回复。我还是没说明白。
: 热水（厨房里的和卫生间里的）不是用我的热水器加热的。我没有独立的热水器。整个
: 小区公用热水器。热水器用天然气加热。但是用多少天然气小区统一计算，每户分摊。
: 每月几块钱，和水费一起收。
: 通到我家的天然气只用作空调的加热功能，也就是取暖用。我说的是通到我家的个人天
: 然气。
: 我试过，刚搬进时，前一个星期还没开通个人天然气服务时，就有热水。家里停电时也
: 有热水。

Z*Z2011-11-11 08:11

25 楼

bless

【在 t**********h 的大作中提到】

: 刚才没认真看，sorry。确实没dp，也没bt。明天有面试，不看新题了，复习复习旧题
: ，完了上来看大牛们的结论。。。

w*12011-11-11 08:11

26 楼

正解，我夏天的时候也不知道，还去关了，结果没热水用，又重开了，关关开开多花了
70多
气费不贵，主要是开通费贵，固定要十多块吧，七七八八各种费用税的加起来就算夏天
不用热水也基本二十五左右的气费稳稳的

【在 s***e 的大作中提到】

: 你开通了气就要交基本费除非你把服务停了
: 至于为什么是5，如楼上所说 Pilot light
: 这个火是一直点着的灭了就没热水出来了
: 而且热水器有温度感应它那炉子里的水低于一定温度就会自动加热以保证你想用热水
: 马上就能出来

r*g2011-11-11 08:11

27 楼

这个：
直到ht2中每个key的count都比ht中相应key大（至少不小）
是不是要遍历所有的key来保证每个的key都满足？那复杂度就是O(km）吧。。。我记得
leetcode的讨论里面有个巧妙的办法来避免遍历，但是原理稍微复杂一点点

中某

【在 Z*****Z 的大作中提到】

e*i2011-11-11 08:11

28 楼

as long as you use gas for AC heat, the pilot light will be on 365 / 24
Also, if you have gas dryer / baking...

【在 l***u 的大作中提到】

p*o2011-11-11 08:11

29 楼

我的完整的方法是这样的。用两个辅助数据结构，一个hashtable, 每个节点是个固定
长度的queue，长度是该字符在T中的数量，存放T字符在目前序列中的位置。另一个是
queue, 用来存目前序列中属于T的字符的顺序，以方便寻找下一序列起点。不用queue
直接用尾指针也可以，但会增加一些比较。

【在 Z*****Z 的大作中提到】

: Queue其实可以取代tail指针。
: 关于一个hashtable，你是说把ht干掉还是ht2干掉？只用一个hashtable的话怎么给S和
: T同时计数？

b*u2011-11-11 08:11

30 楼

骗几块钱也好？露珠是凤凰南吧。

了。
等。

【在 l***u 的大作中提到】

Z*Z2011-11-11 08:11

31 楼

不用，搞个counter，初始化为T的长度。在（1）阶段，每次增加ht2 key值的时候，和
ht key比一下，要是ht2的key值小，就把counter --。
counter就是当前所找到的有效字符。
counter为0的时候，条件自然就满足了。

【在 r********g 的大作中提到】

: 这个：
: 直到ht2中每个key的count都比ht中相应key大（至少不小）
: 是不是要遍历所有的key来保证每个的key都满足？那复杂度就是O(km）吧。。。我记得
: leetcode的讨论里面有个巧妙的办法来避免遍历，但是原理稍微复杂一点点
:
: 中某

l*u2011-11-11 08:11

32 楼

打电话问了，确实是 Pilot_light 的原因。
多谢各位的回复

Z*Z2011-11-11 08:11

33 楼

那也就是说hashtable里每个节点最多就放那么多元素？不是很明白那个hashtable是怎
么更新的
比如在abbcc 里面找abc，那第二个b只放在queue里？
你要是过了leetcode可以直接贴代码，看起来快些:)

queue

【在 p*****o 的大作中提到】

: 我的完整的方法是这样的。用两个辅助数据结构，一个hashtable, 每个节点是个固定
: 长度的queue，长度是该字符在T中的数量，存放T字符在目前序列中的位置。另一个是
: queue, 用来存目前序列中属于T的字符的顺序，以方便寻找下一序列起点。不用queue
: 直接用尾指针也可以，但会增加一些比较。

l*u2011-11-11 08:11

34 楼

我以为只要不用天然气，也就是0 CCF,我就可以不用交各种基本费。
而事实是，既使我关掉Pilot_light，每月用气0 CCF,只要服务还是开通不取消，就要
交各种基本费。
还是很好奇。为什么用天然气取暖？比用电省钱么？

r*g2011-11-11 08:11

35 楼

嘿嘿俺说的就是这个trick啦，当时看的时候还是觉得很巧妙的。。特别是counter++的
地方

【在 Z*****Z 的大作中提到】

: 不用，搞个counter，初始化为T的长度。在（1）阶段，每次增加ht2 key值的时候，和
: ht key比一下，要是ht2的key值小，就把counter --。
: counter就是当前所找到的有效字符。
: counter为0的时候，条件自然就满足了。

d*y2011-11-11 08:11

36 楼

用得多的大户好像要省一些，小apt再搞个gas，基本就是做贡献。

【在 l***u 的大作中提到】

: 我以为只要不用天然气，也就是0 CCF,我就可以不用交各种基本费。
: 而事实是，既使我关掉Pilot_light，每月用气0 CCF,只要服务还是开通不取消，就要
: 交各种基本费。
: 还是很好奇。为什么用天然气取暖？比用电省钱么？

p*o2011-11-11 08:11

37 楼

T里的元素都放在hashtable的queue里，后面每多加一个前面就拿走一个。这是我最初O
(kn)的code，后来的都没有存。为了方便用的是STL里的map，比hashtable慢一点。
class Solution {
public:
string minWindow(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map > tbl;
int ct = 0; // counter to find the first full set
int lowest; // lowest index of current set
for (int i=0; iif (tbl.find(T[i]) == tbl.end()) tbl[T[i]] = queue();
tbl[T[i]].push(-1);
}
int mlen = S.size(), lo = -1; // min length and start position
map >::iterator p, q; // temp iterators

for (int i=0; i < S.size(); ++i) if ((p = tbl.find(S[i])) != tbl.end
()){

if (p->second.front() == -1) ++ct;
p->second.push(i);
p->second.pop();
if (ct == T.size() && (mlen == S.size() || S[i] == S[lowest])) {

lowest = S.size();
for (q = tbl.begin(); q != tbl.end(); ++q)
if (q->second.front() < lowest) lowest = q->second.front
();
int len = i - lowest + 1;
if (len < mlen || len == S.size()){
lo = lowest;
mlen = len;
}
}

}
if (lo == -1) return "";
else return S.substr(lo, mlen);
}
}

【在 Z*****Z 的大作中提到】

: 那也就是说hashtable里每个节点最多就放那么多元素？不是很明白那个hashtable是怎
: 么更新的
: 比如在abbcc 里面找abc，那第二个b只放在queue里？
: 你要是过了leetcode可以直接贴代码，看起来快些:)
:
: queue

w*12011-11-11 08:11

38 楼

这美国的热水必须用gas吧，没法儿关啊，除非是集体收费包在房租里

【在 d******y 的大作中提到】

:
: 用得多的大户好像要省一些，小apt再搞个gas，基本就是做贡献。

Z*Z2011-11-11 08:11

39 楼

不错，这个O（kn）的code挺好看的。

初O

【在 p*****o 的大作中提到】

: T里的元素都放在hashtable的queue里，后面每多加一个前面就拿走一个。这是我最初O
: (kn)的code，后来的都没有存。为了方便用的是STL里的map，比hashtable慢一点。
: class Solution {
: public:
: string minWindow(string S, string T) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: map > tbl;
: int ct = 0; // counter to find the first full set
: int lowest; // lowest index of current set

d*y2011-11-11 08:11

40 楼

哦。原来这样，难怪现在的房子暖气热水全包，不过这样给租户省了不少钱呢，坏处就
是有些人很浪费。

【在 w*****1 的大作中提到】

: 这美国的热水必须用gas吧，没法儿关啊，除非是集体收费包在房租里

p*o2011-11-11 08:11

41 楼

Thanks. Here is the weird thing: this O(kn) method seems faster than any O(
n) implementation I tried. I have tried to mimic a hash table with an array
of 128 elements since LeetCode's test cases are limited to ASCII characters
. For the large test, the O(kn) method with map takes about 140ms, the fake
hash table method with tail pointer takes about 180ms, and the queue
implementation takes about the same amount time.
My guess is that the factor of "k" part is only run very few times, which
makes it better than the 2n methods. What's your thought?

【在 Z*****Z 的大作中提到】

: 不错，这个O（kn）的code挺好看的。
:
: 初O

a*a2011-11-11 08:11

42 楼

我们这儿热水都是电热水器的，冬天取暖也是空调

【在 w*****1 的大作中提到】

: 这美国的热水必须用gas吧，没法儿关啊，除非是集体收费包在房租里

e*i2011-11-11 08:11

43 楼

some ACs also use natural gas for heating.

【在 a****a 的大作中提到】

: 我们这儿热水都是电热水器的，冬天取暖也是空调