algorithm001 · GeekUniversity · May 13, 2019 · May 8, 2019 · May 9, 2019 · May 10, 2019
diff --git a/Week_04/id_6/LeetCode_241_6.java b/Week_04/id_6/LeetCode_241_6.java
@@ -0,0 +1,43 @@
+
+
+    // LeetCode 241
+
+
+	// [ 1. 分治 ]
+
+    // 已运算符为界，  分为left和right，递归的计算
+    public List<Integer> diffWaysToCompute(String input) {
+        List<Integer> rst = new ArrayList<Integer>();
+        Stack<Integer> stack = new Stack<>();
+
+        int i = 0;
+        int val = 0;
+        for (i = 0; i < input.length(); i++) {
+            List<Integer> left = new ArrayList<Integer>();
+            List<Integer> right = new ArrayList<Integer>();
+            char c = input.charAt(i);
+            if (c=='+' || c=='-' || c=='*'){
+                left = diffWaysToCompute(input.substring(0, i));
+                right = diffWaysToCompute(input.substring(i+1, input.length()));
+
+                // 返回的两个集合再根据运算符合并
+                for (int j = 0; j < left.size(); j++) {
+                    for (int k = 0; k < right.size(); k++) {
+                        if (c == '+'){
+                            val = left.get(j) + right.get(k);
+                        }else if (c == '-'){
+                            val = left.get(j) - right.get(k);
+                        }else {
+                            val = left.get(j) * right.get(k);
+                        }
+                        rst.add(val);
+                    }
+                }
+            }
+        }
+        // 纯数字时
+        if (rst.size() == 0){
+            rst.add(Integer.valueOf(input));
+        }
+        return rst;
+    }
diff --git a/Week_04/id_6/LeetCode_455_6.java b/Week_04/id_6/LeetCode_455_6.java
@@ -0,0 +1,31 @@
+
+
+    // LeetCode 455
+
+
+	// [ 1. 贪心算法 ]
+
+
+    // 遍历每个孩子，依次选出适合他的最小饼干
+    public int findContentChildren(int[] g, int[] s) {
+        Arrays.sort(g);
+        Arrays.sort(s);
+
+        int num = 0;
+        int curr = 0;
+        for (int i = 0; i < g.length; i++) {
+            for (int j = curr; j < s.length; j++) {
+                curr++;
+                if (g[i] <= s[j]){
+                    num ++;
+                    break;
+                }
+
+            }
+            if (curr > s.length){
+                break;
+            }
+        }
+
+        return num;
+    }
diff --git a/Week_04/id_6/LeetCode_720_6.java b/Week_04/id_6/LeetCode_720_6.java
@@ -0,0 +1,161 @@
+
+
+    // LeetCode 104
+
+
+	// [ 2. Trie树 ]
+
+    // 从最短的字符串开始建树，后面下一个，如果减1能找到，插入并记录为rst
+    public String longestWord(String[] words) {
+        Set<Integer> set = new TreeSet<>();
+        HashMap<Integer, List<String>> map = new HashMap<>();
+        TrieNode p = root;
+
+        for (int i = 0; i < words.length; i++) {
+            int len = words[i].length();
+            set.add(len);
+            List<String> list = null;
+            if (map.containsKey(len)){
+                list = map.get(len);
+            }else {
+                list = new ArrayList<>();
+            }
+            list.add(words[i]);
+            map.put(len, list);
+        }
+
+        // 去重，排序
+        int[] wordsLen = new int[set.size()];
+        int k = 0;
+        for (Integer n : set) {
+            wordsLen[k++] = n;
+        }
+        Arrays.sort(wordsLen);
+        String rst = "";
+        // 按word长度递增顺序，开始建trie树
+        // 先用word去掉尾字符在trie树中查询，找到rst记录，并插入树
+        for (int i = 0; i < wordsLen.length; i++) {
+            int len = wordsLen[i];
+            List<String> list = map.get(len);
+            for (String word : list){
+                char[] text = word.toCharArray();
+                char[] txt = Arrays.copyOf(text, text.length-1);
+                if (text.length > 1){
+                    if (find(txt)){
+                        insert(text);
+                        if (rst.length() == word.length()){
+                            if (rst.compareTo(word) > 0){
+                                rst = word;
+                            }
+                        }else {
+                            rst = word;
+                        }
+                    }
+                }else {
+                    if (rst.length() == 0){
+                        rst = word;
+                    }else if (rst.compareTo(word) > 0){
+                        rst = word;
+                    }
+                    insert(text);
+                }
+            }
+        }
+
+        return rst;
+    }
+
+    class TrieNode {
+
+        public char data;
+        public TrieNode[] children = new TrieNode[26];
+        public boolean isEndingChar = false;
+        public TrieNode(char data){
+            this.data = data;
+        }
+    }
+
+    // root
+    TrieNode root = new TrieNode('\\');
+
+    // 插入一个字符
+    public void insert(char[] text){
+        TrieNode p = root;
+
+        int len = text.length;
+        for (int i = 0; i < len; i++) {
+            // 字符插入位置索引
+            int index = text[i] - 'a';
+            // 根据索引插入children中。如果已经存在则不处理
+            if (p.children[index] == null){
+                p.children[index] = new TrieNode(text[i]);
+            }
+            // 到下一层遍历
+            p = p.children[index];
+        }
+        p.isEndingChar = true;
+    }
+
+
+    // 查找一个字符串
+    public boolean find(char[] pattern){
+        TrieNode p = root;
+
+        for (int i = 0; i < pattern.length; i++) {
+            int index = pattern[i] - 'a';
+            if (p.children[index] == null){
+                return false;
+            }
+            // 继续向下一层查询
+            p = p.children[index];
+        }
+        if (p.isEndingChar == false){
+            return true;
+        }
+
+        return true;
+    }
+
+
+
+
+
+    // [ 1. 哈希表 ]
+
+
+    // 通过单词长度递减，然后在words中查询，如果能找到，符合题目要求
+    public String longestWord1(String[] words) {
+        int[] wordsLen = new int[words.length];
+        HashMap<String, Integer> map = new HashMap<>();
+        TrieNode p = root;
+
+        for (int i = 0; i < words.length; i++) {
+            int len = words[i].length();
+            wordsLen[i] = len;
+            if (!map.containsKey(words[i])){
+                map.put(words[i], 1);
+            }
+        }
+
+        String rst = "";
+        for (int i = 0; i < words.length; i++) {
+            String wd = words[i];
+            int len = wd.length();
+            int j = 0;
+            for (j = 1; j < len; j++) {
+                wd = wd.substring(0, len - j);
+                // 子串在words中没有
+                if (!map.containsKey(wd)){
+                    break;
+                }
+            }
+            if (j == len){
+                if (rst.length() == 0 || rst.length() < len){
+                    rst = words[i];
+                }else if (rst.length() == len && rst.compareTo(words[i]) > 0){
+                    rst = words[i];
+                }
+            }
+        }
+        return rst;
+    }
diff --git a/Week_04/id_6/LeetCode_746_6.java b/Week_04/id_6/LeetCode_746_6.java
@@ -0,0 +1,35 @@
+
+
+    // LeetCode 746
+
+
+    // [ 1. 动态规划  ]
+
+    // 到达每个点的花费的集合 看成状态集合，然后根据这个集合推导下一个点的花费集合
+    // 因为题目只求花费的最小值，所以集合只保留一个值即可
+    // 动态的向前推进
+    // 推导依据：f(n) = f(n-1) + f(n-2) + val(n)  斐波那契数
+    // 到达第cost.length个点(数组外的点)时，花费值即为所求
+    public int minCostClimbingStairs(int[] cost) {
+        int n = cost.length;
+        if (n == 1){
+            return cost[0];
+        }
+        if (n == 2){
+            return Math.min(cost[0], cost[1]);
+        }
+
+        int[] sum = new int[n+1];
+        sum[0] = cost[0];
+        sum[1] = cost[1];
+        int i = 2;
+        // 计算每个点的花费集合，只保留最小值
+        for (i = 2; i < n; i++) {
+            sum[i] = Math.min(sum[i - 1], sum[i - 2]) + cost[i];
+        }
+
+        return Math.min(sum[i - 1], sum[i - 2]);
+    }
+
+
+
diff --git a/Week_04/id_6/LeetCode_784_6.java b/Week_04/id_6/LeetCode_784_6.java
@@ -0,0 +1,90 @@
+
+
+    // LeetCode 784
+
+
+    // [ 2. 回溯  ]
+
+    // "a1b2"
+    // 每个字符有两种选择
+    // 第一种选择时，计算后面字符的所有组合（递归）
+    // 第二种选择时，同样方式
+    public List<String> letterCasePermutation(String S) {
+        if (S.length() == 0){
+            List<String> lt = new ArrayList<>();
+            lt.add("");
+            return lt;
+        }
+
+        List<String> rst = new ArrayList<>();
+        dfs("", S, S.length(), rst);
+        return rst;
+    }
+
+
+    public void dfs(String curr, String other, int len, List<String> rst){
+        if (curr.length() == len){
+            rst.add(curr);
+            return;
+        }
+
+        for (int i = 0; i < other.length(); i++) {
+            char c = other.charAt(i);
+            if (Character.isAlphabetic(c)){
+                // 每个字符有两种选择
+                dfs(curr + Character.toLowerCase(c), other.substring(i+1, other.length()), len, rst);
+                dfs(curr + Character.toUpperCase(c), other.substring(i+1, other.length()), len, rst);
+                return;
+            }else {
+                curr = curr + c;
+            }
+        }
+
+        // 都是数字 可以用递归，也可以i==length直接加入rst
+        dfs(curr, "", len, rst);
+    }
+
+
+
+	// [ 1. 分治  ]
+
+    // 第一个字符的集合 与 其它剩余字符集合 的组合
+    // 其它剩余字符集合 递归用此方法
+    public List<String> letterCasePermutation(String S) {
+        if (S.length() == 0){
+            List<String> lt = new ArrayList<>();
+            lt.add("");
+            return lt;
+        }
+
+        List<String> rst = new ArrayList<>();
+        String num = "";
+        int i = 0;
+        for (i = 0; i < S.length(); i++) {
+            // 找到字母停止循环
+            char c = S.charAt(i);
+            if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
+                break;
+            }
+        }
+        List<String> left = new ArrayList<>();
+        List<String> right = new ArrayList<>();
+        // 没找到字符
+        if (i == S.length()){
+            left.add(S);
+            right.add("");
+        }else {
+            left.add(S.substring(0, i) + Character.toLowerCase(S.charAt(i)));
+            left.add(S.substring(0, i) + Character.toUpperCase(S.charAt(i)));
+            right = letterCasePermutation(S.substring(i+1, S.length()));
+        }
+
+        // 合并
+        for (String p : left){
+            for (String q : right){
+                rst.add(p + q);
+            }
+        }
+
+        return rst;
+    }