Merge pull request algorithm001#719 from zsndev/master

GeekUniversity · web-flow · commit 0f9670196eb0 · 2019-05-13T17:18:15.000+08:00
week4-129
diff --git a/Week_04/id_129/LeetCode_169_129.java b/Week_04/id_129/LeetCode_169_129.java
@@ -0,0 +1,17 @@
+import java.util.*;
+
+public class LeetCode_169_129 {
+    public int majorityElement(int[] num) {
+        int major = num[0], count = 1;
+        for (int i = 1; i < num.length; i++) {
+            if (count == 0) {
+                count++;
+                major = num[i];
+            } else if (major == num[i]) {
+                count++;
+            } else count--;
+
+        }
+        return major;
+    }
+}
diff --git a/Week_04/id_129/LeetCode_241_129.java b/Week_04/id_129/LeetCode_241_129.java
@@ -0,0 +1,57 @@
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+public class LeetCode_241_129 {
+    private Map<String, List<Integer>> memo = new HashMap<>();
+
+    public List<Integer> diffWaysToCompute(String input) {
+        int len = input.length();
+        // check history
+        List<Integer> result = memo.get(input);
+        if (result != null) {
+            return result;
+        }
+        result = new ArrayList<>();
+        // base case
+        if (isDigit(input)) {
+            result.add(Integer.parseInt(input));
+            memo.put(input, result);
+            return result;
+        }
+        for (int i = 0; i < len; i++) {
+            char c = input.charAt(i);
+            if (c == '+' || c == '-' || c == '*') {
+                List<Integer> left = diffWaysToCompute(input.substring(0, i));
+                List<Integer> right = diffWaysToCompute(input.substring(i + 1, len));
+                for (Integer il : left) {
+                    for (Integer ir : right) {
+                        switch (c) {
+                            case '+':
+                                result.add(il + ir);
+                                break;
+                            case '-':
+                                result.add(il - ir);
+                                break;
+                            case '*':
+                                result.add(il * ir);
+                                break;
+                        }
+                    }
+                }
+            }
+        }
+        memo.put(input, result);
+        return result;
+    }
+
+    private boolean isDigit(String s) {
+        for (Character c : s.toCharArray()) {
+            if (!Character.isDigit(c)) {
+                return false;
+            }
+        }
+        return true;
+    }
+}
