lintcode19

https://www.lintcode.com/contest/34

1416. The Previous Number
      从后往前遍历的单调栈

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]))   

1414. Eat The Beans
      题目意思没说清楚，应该是只要是只剩下一个white就结束，无论在Step1还是在Step2
      如果分2个Step的话，还不好DP，得用个3为数组（额外开一个维度为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))

1413. Tree
      BFS找到所有node的father，但是感觉Contest的时候数据有问题，一直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下来了