https://www.lintcode.com/contest/34
- The Previous Number
從后往前遍歷的單調(diào)棧
class Solution:
"""
@param num: The arry you should handle
@return: Return the array
"""
def getPreviousNumber(self, a):
# Write your code here
if not a: return a
res= [i for i in a]
st = []
for i in range(len(a)-1,-1,-1):
while st and a[st[-1]]>a[i]:
res[st.pop()] = a[i]
st.append(i)
return res
s=Solution()
print(s.getPreviousNumber([2,3,6,1,5,5]))
print(s.getPreviousNumber([6,3,1,2,5,10,9,15]))
- Eat The Beans
題目意思沒說清楚平道，應該是只要是只剩下一個white就結(jié)束芳悲，無論在Step1還是在Step2
如果分2個Step的話永罚，還不好DP梢夯，得用個3為數(shù)組（額外開一個維度為2的dimension）
還是recursion+memo好用
class Solution:
"""
@param w: The W
@param r: The R
@return: The answer
"""
def eatTheBeans(self, w, r):
# Write your code here
memo = {}
def helper(w2, r2, flag):
if (w2,r2,flag) in memo: return memo[(w2,r2,flag)]
if w2==1 and r2==0: return 1.00
if w2==0: return 0.00
if r2==0: return 1.00
if flag==1:
res = w2/(w2+r2)*helper(w2-1,r2,2)+r2/(w2+r2)*helper(w2,r2,2)
memo[(w2,r2,flag)] = res
return res
else:
res = w2/(w2+r2)*helper(w2-1,r2,1)+r2/(w2+r2)*helper(w2,r2-1,1)
memo[(w2,r2,flag)] = res
return res
return helper(w,r,1)
s=Solution()
print(s.eatTheBeans(1, 1))
print(s.eatTheBeans(1, 0))
print(s.eatTheBeans(2, 2))
- Tree
BFS找到所有node的father至扰，但是感覺Contest的時候數(shù)據(jù)有問題揩晴，一直AC不了上沐，Contest完了相同的code AC了纤勒，窩草，這比賽真的好無語
from collections import defaultdict
class Solution:
"""
@param x: The x
@param y: The y
@param a: The a
@param b: The b
@return: The Answer
"""
def tree(self, x, y, a, b):
# Write your code here
adj = defaultdict(list)
for i in range(len(x)):
adj[x[i]].append(y[i])
adj[y[i]].append(x[i])
q, qq = [1], []
fa = {1:0}
marked = set()
marked.add(1)
while q:
while q:
t = q.pop()
for tt in adj[t]:
if tt not in marked:
fa[tt] = t
qq.append(tt)
marked.add(tt)
q,qq = qq,q
res = []
for i in range(len(a)):
if a[i] not in fa or b[i] not in fa: res.append(0)
elif fa[a[i]]==b[i] or fa[b[i]]==a[i]: res.append(2)
elif fa[a[i]]==fa[b[i]]: res.append(1)
else: res.append(0)
return res
不過還是感到自己太挫了啊术瓮，別的大神在自己寫第3題的時候就finish了康聂，額，不每天刷胞四，真的思維就down下來了
