initial commit

kamyu104 · kamyu104 · commit d6067bb5170c · 2014-09-05T00:17:56.000+08:00
diff --git a/Python/candy.py b/Python/candy.py
@@ -0,0 +1,31 @@
+# Time:  O(n)
+# Space: O(n)
+#
+# There are N children standing in a line. Each child is assigned a rating value.
+# 
+# You are giving candies to these children subjected to the following requirements:
+# 
+# Each child must have at least one candy.
+# Children with a higher rating get more candies than their neighbors.
+# What is the minimum candies you must give?
+#
+import operator
+
+class Solution:
+    # @param ratings, a list of integer
+    # @return an integer
+    def candy(self, ratings):
+        candies = [1 for i in range(len(ratings))]
+        for i in range(1, len(ratings)):
+            if ratings[i] > ratings[i - 1]:
+                candies[i] = candies[i - 1] + 1
+        
+        for i in reversed(range(1, len(ratings))):
+            if ratings[i - 1] > ratings[i] and candies[i - 1] <= candies[i]:
+                candies[i - 1] = candies[i] + 1
+        
+        return reduce(operator.add, candies)
+        
+if __name__ == "__main__":
+    result = Solution().candy([1, 2, 3, 2, 3, 5, 2, 5])
+    print result
diff --git a/Python/climbStairs.py b/Python/climbStairs.py
@@ -0,0 +1,20 @@
+# Time:  O(n)
+# Space: O(1)
+#
+# You are climbing a stair case. It takes n steps to reach to the top.
+# 
+# Each time you can either climb 1 or 2 steps. 
+# In how many distinct ways can you climb to the top?
+#
+class Solution:
+    # @param n, an integer
+    # @return an integer
+    def climbStairs(self, n):
+        prev, current = 0, 1
+        for i in range(n):
+            prev, current = current, prev + current, 
+        return current
+
+if __name__ == "__main__":
+    result = Solution().climbStairs(2)
+    print result
