algorithm001 · GeekUniversity · May 13, 2019 · May 12, 2019
diff --git a/Week_04/id_85/LeetCode_169_085.java b/Week_04/id_85/LeetCode_169_085.java
@@ -0,0 +1,63 @@
+public class LeetCode_169_085 {
+}
+
+/**
+ * @Package:
+ * @ClassName: MajorityElement
+ * @Description: 给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
+ * *************你可以假设数组是非空的，并且给定的数组总是存在众数。
+ * @leetcode_url:https://leetcode-cn.com/problems/majority-element/
+ * @Author: wangzhao
+ * @Date: 2019-05-12 09:49:03
+ * @Version: 1.0.0
+ * @Since: 1.8
+ **/
+class MajorityElement {
+
+
+    public int majorityElement(int[] nums) {
+
+        if (nums == null || nums.length == 0) {
+            return -1;
+        }
+
+        int count = 0;
+        int majority = -1;
+
+        for (int num : nums) {
+            if (count == 0) {
+                majority = num;
+                count++;
+            } else {
+                if (majority == num) {
+                    count++;
+                } else {
+                    count--;
+                }
+            }
+        }
+
+        if (count <= 0) {
+            return -1;
+        }
+        int counter = 0;
+        for (int num : nums) {
+            if (num == majority) {
+                counter++;
+            }
+        }
+        if (counter > nums.length / 2) {
+            return majority;
+        }
+        return -1;
+    }
+
+
+    public static void main(String[] args) {
+
+        int[] nums = {2, 2, 1, 1, 1, 2, 2};
+
+        int num = new MajorityElement().majorityElement(nums);
+        System.out.println(num);
+    }
+}
diff --git a/Week_04/id_85/LeetCode_455_085.java b/Week_04/id_85/LeetCode_455_085.java
@@ -0,0 +1,56 @@
+import java.util.Arrays;
+
+public class LeetCode_455_085 {
+}
+
+/**
+ * @Package:
+ * @ClassName: AssignCookies
+ * @Description: 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
+ * **************对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。
+ * **************如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。
+ * **************你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
+ * **************注意：
+ * **************你可以假设胃口值为正。
+ * **************一个小朋友最多只能拥有一块饼干。
+ * @leetcode_url:https://leetcode-cn.com/problems/assign-cookies/
+ * @Author: wangzhao
+ * @Date: 2019-05-12 10:14:17
+ * @Version: 1.0.0
+ * @Since: 1.8
+ **/
+class AssignCookies {
+
+    public int findContentChildren(int[] g, int[] s) {
+
+        if (g == null || g.length == 0) {
+            return 0;
+        }
+        if (s == null || s.length == 0) {
+            return 0;
+        }
+
+        int child = 0;
+        int cookie = 0;
+        Arrays.sort(g);
+        Arrays.sort(s);
+
+        while (child < g.length && cookie < s.length) {
+            if (g[child] <= s[cookie]) {
+                child++;
+            }
+            cookie++;
+        }
+
+        return child;
+    }
+
+    public static void main(String[] args) {
+
+        int[] g = {1, 2};
+        int[] s = {1, 2, 3};
+        int num = new AssignCookies().findContentChildren(g, s);
+        System.out.println(num);
+    }
+
+}
diff --git a/Week_04/id_85/LeetCode_720_085.java b/Week_04/id_85/LeetCode_720_085.java
@@ -0,0 +1,109 @@
+public class LeetCode_720_085 {
+}
+
+
+/**
+ * @Package:
+ * @ClassName: LongestWordInDictionary
+ * @Description: 给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。
+ * **************若其中有多个可行的答案，则返回答案中字典序最小的单词。
+ * **************若无答案，则返回空字符串。
+ * @leetcode url:https://leetcode-cn.com/problems/longest-word-in-dictionary/
+ * @Author: wangzhao
+ * @Date: 2019-05-11 21:21:44
+ * @Version: 1.0.0
+ * @Since: 1.8
+ **/
+class LongestWordInDictionary {
+
+    private String longestWord="";
+    public String longestWord(String[] words) {
+
+        if (words == null || words.length == 0) {
+            return null;
+        }
+        Trie trie = new Trie();
+        for (String word : words) {
+            trie.insert(word);
+        }
+
+        search(new StringBuffer(),trie.nodes);
+
+        return longestWord;
+    }
+
+    private void search(StringBuffer sb,TreeNode4[] node4s) {
+        if (node4s == null || node4s.length == 0) {
+            return;
+        }
+
+        for (TreeNode4 node4 : node4s) {
+            if (node4 != null && node4.end) {
+                sb.append(node4.val);
+                if (sb.length()>longestWord.length()){
+                    longestWord=sb.toString();
+                }
+                search(sb,node4.children);
+                sb.deleteCharAt(sb.length()-1);
+            }
+        }
+
+    }
+
+
+    public static void main(String[] args) {
+//        String[] words = {"w", "wo", "wor", "worl", "world"};
+        String[] words= {"a", "banana", "app", "appl", "ap", "apply", "apple"};
+        String longestWord = new LongestWordInDictionary().longestWord(words);
+        System.out.println(longestWord);
+    }
+}
+
+class Trie {
+
+    TreeNode4[] nodes;
+
+    public Trie() {
+        this.nodes = new TreeNode4[26];
+    }
+
+    public void insert(String word) {
+        if (word == null || word.length() == 0) {
+            return;
+        }
+
+        insert(0, word.toCharArray(), nodes);
+
+    }
+
+    private void insert(int i, char[] chars, TreeNode4[] children) {
+
+        int idx = chars[i] - 'a';
+
+        if (children[idx] == null) {
+            children[idx] = new TreeNode4(chars[i]);
+        }
+
+        if (i == chars.length - 1) {
+            children[idx].end = true;
+            return;
+        }
+
+        if (children[idx].children == null) {
+            children[idx].children = new TreeNode4[26];
+        }
+
+        insert(i + 1, chars, children[idx].children);
+    }
+}
+
+class TreeNode4 {
+
+    char val;
+    boolean end;
+    TreeNode4[] children;
+
+    public TreeNode4(char val) {
+        this.val = val;
+    }
+}
diff --git a/Week_04/id_85/LeetCode_746_085.java b/Week_04/id_85/LeetCode_746_085.java
@@ -0,0 +1,81 @@
+public class LeetCode_746_085 {
+}
+
+/**
+ * @Package:
+ * @ClassName: MinCostClimbingStairs
+ * @Description: 数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
+ * **************每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
+ * **************您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
+ * @leetcode_url:https://leetcode-cn.com/problems/min-cost-climbing-stairs/
+ * @Author: wangzhao
+ * @Date: 2019-05-12 11:53:46
+ * @Version: 1.0.0
+ * @Since: 1.8
+ **/
+class MinCostClimbingStairs {
+
+    public int minCostClimbingStairs2(int[] cost) {
+
+        if (cost == null || cost.length == 0) {
+            return 0;
+        }
+        if (cost.length == 1) {
+            return cost[0];
+        }
+
+        if (cost.length == 2) {
+            return Math.min(cost[0], cost[1]);
+        }
+
+        int length = cost.length;
+
+        for (int i = 2; i < length; i++) {
+            cost[i] += Math.min(cost[i - 1], cost[i - 2]);
+        }
+
+
+        return Math.min(cost[length - 1], cost[length - 2]);
+    }
+
+    public int minCostClimbingStairs(int[] cost) {
+
+        if (cost == null || cost.length == 0) {
+            return 0;
+        }
+
+        return minStep(cost, -1);
+    }
+
+    private int minStep(int[] cost, int step) {
+
+        if (step >= cost.length) {
+            return 0;
+        }
+        int val1 = 0;
+        if (step + 1 < cost.length) {
+            val1 = cost[step + 1];
+        }
+
+        int val2 = 0;
+        if (step + 2 < cost.length) {
+            val2 = cost[step + 2];
+        }
+
+        int res1 = val1 + minStep(cost, step + 1);
+        int res2 = val2 + minStep(cost, step + 2);
+
+        return Math.min(res1, res2);
+    }
+
+
+    public static void main(String[] args) {
+//        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
+//        int[] cost = {0, 1, 2, 2};
+        int[] cost = {0, 2, 2, 1};
+
+
+        int num = new MinCostClimbingStairs().minCostClimbingStairs2(cost);
+        System.out.println(num);
+    }
+}
diff --git a/Week_04/id_85/LeetCode_784_085.java b/Week_04/id_85/LeetCode_784_085.java
@@ -0,0 +1,70 @@
+import java.util.ArrayList;
+import java.util.List;
+
+public class LeetCode_784_085 {
+}
+
+/**
+ * @Package:
+ * @ClassName: LetterCasePermutation
+ * @Description: 给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
+ * @leetcode_url:https://leetcode-cn.com/problems/letter-case-permutation/
+ * @Author: wangzhao
+ * @Date: 2019-05-12 10:35:23
+ * @Version: 1.0.0
+ * @Since: 1.8
+ **/
+class LetterCasePermutation {
+
+
+    public List<String> letterCasePermutation(String S) {
+
+        List<String> result = new ArrayList<>();
+        if (S == null || S.length() == 0) {
+            return result;
+        }
+
+        char[] chars = S.toCharArray();
+
+        permutation(chars,0,result);
+
+        return result;
+    }
+
+    private void permutation(char[] chars,int cursor,List<String> result ){
+        if (cursor>=chars.length){
+            return;
+        }
+        int temp= cursor;
+
+        if (!result.contains(new String(chars))){
+            result.add(new String(chars));
+        }
+        if (Character.isDigit(chars[cursor])){
+            permutation(chars,++cursor,result);
+        }else if(chars[cursor]>='a'&& chars[cursor]<='z'){
+            permutation(chars,++cursor,result);
+            chars[temp]=Character.toUpperCase(chars[temp]);
+            if (!result.contains(new String(chars))){
+                result.add(new String(chars));
+            }
+            permutation(chars,++temp,result);
+        }else if (chars[cursor]>='A'&&chars[cursor]<='Z'){
+            permutation(chars,++cursor,result);
+            chars[temp]=Character.toLowerCase(chars[temp]);
+            if (!result.contains(new String(chars))){
+                result.add(new String(chars));
+            }
+            permutation(chars,++temp,result);
+        }
+    }
+
+    public static void main(String[] args) {
+
+        String S = "C";
+        List<String> list = new LetterCasePermutation().letterCasePermutation(S);
+        list.stream().forEach(System.out::println);
+
+    }
+}
+