HTC One的前盖的间隙问题好像被重视了 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PDA - 掌中宝

HTC One的前盖的间隙问题好像被重视了

HTC One的前盖的间隙问题好像被重视了# PDA - 掌中宝

j*e2013-05-01 07:05

1 楼

问题如下。搞了个linear的算法，两个指针往后扫那种，实现起来太
复杂了，费了太多时间调试。有简单的O(n)算法么？
Minimum Window Substring
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".
Note:
If there is no such window in S that covers all characters in T, return the
emtpy string "".
If there are multiple such windows, you are guaranteed that there will
always be only one unique minimum window in S.

f*d2013-05-01 07:05

2 楼

http://www.hardwarezone.com.sg/tech-news-htc-one-suffers-build-
A high level executive of HTC Asia reportedly admitted that the One suffers
from these build issues, and that the company is ready to repair these
devices and replace them. However, HTC made no mention on the reason behind
the build issues.
还有耳机和充电空的毛刺问题。希望尽快能解决。

p*22013-05-01 07:05

3 楼

今天有时间写一个。

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

: 问题如下。搞了个linear的算法，两个指针往后扫那种，实现起来太
: 复杂了，费了太多时间调试。有简单的O(n)算法么？
: Minimum Window Substring
: 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".
: Note:

p*22013-05-01 07:05

4 楼

def min(S,T):
d1={}
d2={}

for c in T:
if not d1.has_key(c):
d1[c]=0
d1[c]+=1

dq=deque()

count=len(d1)
ans=S
for i in xrange(len(S)):
c=S[i]
if d1.has_key(c):
dq.append(i)
if not d2.has_key(c):
d2[c]=0
d2[c]+=1

if d2[c]==d1[c]:
count-=1

if count==0:
while len(dq)>0 and d2[S[dq[0]]]>d1[S[dq[0]]]:
d2[S[dq[0]]]-=1
dq.popleft()
if dq[-1]-dq[0]+1ans=S[dq[0]:dq[-1]+1]

return ans

C*U2013-05-01 07:05

5 楼

你的O(n)时间的算法空间也是O(n)吧？

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

j*e2013-05-01 07:05

6 楼

你想简单了，如果T是AAB，那么要求S对应的substring里包含两个A。
你的算法只适合T没有duplicate字符的情况。
而且memory usage是O(T.size()).

def min(S,T):
d1={}
d2={}

for c in T:
if not d1.has_key(c):
d1[c]=0
d1[c]+=1

dq=deque()

count=len(d1)
ans=S
for i in xrange(len(S)):
c=S[i]
if d1.has_key(c):
dq.append(i)
if not d2.has_key(c):
d2[c]=0
d2[c]+=1

if d2[c]==d1[c]:
count-=1

if count==0:
while len(dq)>0 and d2[S[dq[0]]]>d1[S[dq[0]]]:
d2[S[dq[0]]]-=1
dq.popleft()
if dq[-1]-dq[0]+1ans=S[dq[0]:dq[-1]+1]

return ans

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

: def min(S,T):
: d1={}
: d2={}
:
: for c in T:
: if not d1.has_key(c):
: d1[c]=0
: d1[c]+=1
:
: dq=deque()

j*e2013-05-01 07:05

7 楼

空间上，我用了一个bitmap，256个int，所以应该算O(1)吧。
（btw，如果不算返回的字符串的话).
我的做法类似peking2的，但是用了bitmap替代queue

【在 C***U 的大作中提到】

: 你的O(n)时间的算法空间也是O(n)吧？

p*22013-05-01 07:05

8 楼

are you sure?

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

: 你想简单了，如果T是AAB，那么要求S对应的substring里包含两个A。
: 你的算法只适合T没有duplicate字符的情况。
: 而且memory usage是O(T.size()).
:
: def min(S,T):
: d1={}
: d2={}
:
: for c in T:
: if not d1.has_key(c):

j*e2013-05-01 07:05

9 楼

不好意思，我看错了，python我读起来还是比较费劲。

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

:
: are you sure?