submit week4 homework

luyunfang · luyunfang · commit 1991b470d12b · 2020-12-13T22:13:50.000+08:00
diff --git a/Week4/easy/__init__.py b/Week4/easy/__init__.py
diff --git a/Week4/easy/assign_cookies.py b/Week4/easy/assign_cookies.py
@@ -0,0 +1,27 @@
+# ============================================
+# 455. Assign Cookies
+# 审题: 1.每个孩子最多只能给一块饼干。2.你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
+# not seen before, not solved alone, idea following the solutions proposed in leetcode
+# 解体思路: 1.贪心思想。
+# time complexity: 1.O(nlongn) + O(n) ≈ O(nlogn)
+# ============================================
+
+
+class Solution(object):
+    def findContentChildren(self, g, s):
+        """
+        :type g: List[int]
+        :type s: List[int]
+        :rtype: int
+        """
+        if (len(g) == 0) or (len(s) == 0):
+            return 0
+        g.sort(reverse=False)
+        s.sort(reverse=False)
+        child = 0
+        bisc = 0
+        while (bisc <= len(s)-1) and (child <= len(g)-1):
+            if (s[bisc] >= g[child]):
+                child += 1
+            bisc += 1
+        return child
diff --git a/Week4/easy/lemon_change.py b/Week4/easy/lemon_change.py
@@ -0,0 +1,39 @@
+# ============================================
+# 860. Lemonade Change
+# 审题: 1. 一开始你手头没有任何零钱; 2. 只有5, 10, 20三种类型。
+# not seen before, not solved alone, idea following the solutions proposed in leetcode
+# 解体思路: 1.枚举所有可能的找零方式; 2.找零时贪心思想。
+# time complexity: 1.O(n)
+# ============================================
+
+
+# TODO, 内存消耗太大
+class Solution(object):
+    def lemonadeChange(self, bills):
+        """
+        :type bills: List[int]
+        :rtype: bool
+        """
+        cash_5 = 0
+        cash_10 = 0
+        ct = 0
+        for ele in bills:
+            if ele == 5:
+                cash_5 += 1
+            elif ele == 10:
+                if cash_5 < 1:
+                    return False
+                cash_10 += 1
+                cash_5 -= 1
+            # ele == 20
+            else:
+                if (cash_10 > 0)  and (cash_5 > 0):
+                    cash_10 -= 1
+                    cash_5 -= 1
+                elif (cash_5 >= 3):
+                    cash_5 -= 3
+                else:
+                    return False
+        return True
+
+
