2020-08-15

JiayangWu · JiayangWu · commit 8031e7130ee6 · 2020-08-15T23:43:41.000-04:00
diff --git a/1518.换酒问题/1518-换酒问题.py b/1518.换酒问题/1518-换酒问题.py
@@ -0,0 +1,13 @@
+class Solution(object):
+    def numWaterBottles(self, numBottles, numExchange):
+        """
+        :type numBottles: int
+        :type numExchange: int
+        :rtype: int
+        """
+        empty = res = numBottles
+        while empty >= numExchange:
+            res += empty / numExchange 
+            empty = empty / numExchange + empty % numExchange
+        return res
+        
diff --git a/1519.子树中标签相同的节点数/1519-子树中标签相同的节点数.py b/1519.子树中标签相同的节点数/1519-子树中标签相同的节点数.py
@@ -0,0 +1,30 @@
+class Solution(object):
+    def countSubTrees(self, n, edges, labels):
+        """
+        :type n: int
+        :type edges: List[List[int]]
+        :type labels: str
+        :rtype: List[int]
+        """
+        from collections import defaultdict
+        par2child = defaultdict(set)
+        for s, d in edges:
+            par2child[d].add(s)
+            par2child[s].add(d)
+
+        self.res = [0 for _ in labels]
+        def dfs(node, visited):
+            dic = defaultdict(int)
+            for child in par2child[node]:
+                if child not in visited:
+                    visited.add(child)
+                    child_dic = dfs(child, visited)
+                    for key, val in child_dic.items():
+                        dic[key] = dic[key] + val
+            # print(node, dic)
+            self.res[node] = 1 + dic[labels[node]]
+            dic[labels[node]] += 1
+            return dic
+        dfs(0, set([0]))
+        return self.res
+
