algorithm001 · GeekUniversity · May 13, 2019 · May 12, 2019
diff --git a/Week_04/id_108/LeetCode_169_108.java b/Week_04/id_108/LeetCode_169_108.java
@@ -0,0 +1,91 @@
+package com.algorithm;
+
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * @author zhangruihao.zhang
+ * @version v1.0.0
+ * @since 2019/05/12
+ */
+public class LeetCode_169_108 {
+
+    // 遍历一遍，相同则加1，不相同则减1，最后剩余的item就是众数
+    class Solution1 {
+        public int majorityElement(int[] nums) {
+            int count = 1;
+            int item = nums[0];
+
+            for (int i = 1; i < nums.length; i++) {
+                if (count == 0) {
+                    item = nums[i];
+                    count = 1;
+                } else if (nums[i] == item) {
+                    count++;
+                } else {
+                    count--;
+                }
+            }
+
+            return item;
+        }
+    }
+
+    // 统计每个数字的词频，统计出现次数大于n/2的
+    class Solution2 {
+        public int majorityElement(int[] nums) {
+            Map<Integer, Integer> map = new HashMap<>();
+            int maxCount = 0;
+            int maxItem = 0;
+            for (int num : nums) {
+                int count = map.getOrDefault(num, 0) + 1;
+                if (map.keySet().isEmpty()) {
+                    maxCount = 1;
+                    maxItem = num;
+                }
+                if (map.keySet().contains(num)) {
+                    if (count > maxCount) {
+                        maxCount = count;
+                        maxItem = num;
+                    }
+
+                }
+                map.put(num, map.getOrDefault(num, 0) + 1);
+            }
+
+            return maxItem;
+        }
+    }
+
+    //分治方法
+    class Solution3 {
+        public int majorityElement(int[] nums) {
+
+            if (nums.length == 1) {
+                return nums[0];
+            }
+            int mid = nums.length / 2;
+
+            int[] left = Arrays.copyOfRange(nums, 0, mid);
+            int[] right = Arrays.copyOfRange(nums, mid, nums.length);
+            int a = majorityElement(left);
+            int b = majorityElement(right);
+
+            if (a == b) {
+                return a;
+            }
+            return count(a, nums) > (nums.length / 2) ? a : b;
+        }
+
+        private int count(int num, int[] nums) {
+            int count = 0;
+            for (int i : nums) {
+                if (num == i) {
+                    count++;
+                }
+            }
+            return count;
+        }
+    }
+}
diff --git a/Week_04/id_108/LeetCode_720_108.java b/Week_04/id_108/LeetCode_720_108.java
@@ -0,0 +1,113 @@
+
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * @author zhangruihao.zhang
+ * @version v1.0.0
+ * @since 2019/05/12
+ */
+public class LeetCode_720_108 {
+
+
+    class Solution1 {
+        // 方法一：比较次数较多
+        public String longestWord(String[] words) {
+            Arrays.sort(words);
+            Set<String> set = new HashSet<>();
+            String longest = "";
+            for (String word : words) {
+                if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
+                    set.add(word);
+                    if (word.length() > longest.length()) {
+                        longest = word;
+                    }
+                }
+            }
+            return longest;
+        }
+    }
+
+    class Solution2 {
+        //方法二：trie树，比较耗内存
+        private TreeNode root;
+        private char startChar = 'a';
+        private String longest = "";
+
+        public String longestWord(String[] words) {
+            for (String word : words) {
+                insert(word);
+            }
+            findLongest(root, "");
+            return longest;
+        }
+
+        private void insert(String word) {
+            if (root == null) {
+                root = new TreeNode();
+            }
+            TreeNode tmp = root;
+
+            for (int i = 0; i < word.length(); i++) {
+                int index = word.charAt(i) - startChar;
+                TreeNode child = tmp.getChildren()[index];
+                if (child == null) {
+                    TreeNode node = new TreeNode();
+                    node.setTimes(1).setWord(i == word.length() - 1);
+                    tmp.getChildren()[index] = node;
+                } else {
+                    boolean isWord = child.isWord;
+                    child.setTimes(child.getTimes() + 1).setWord(isWord || i == word.length() - 1);
+                }
+                tmp = tmp.getChildren()[index];
+            }
+        }
+
+        private void findLongest(TreeNode node, String word) {
+            for (int index = 0; index < 26; index++) {
+                if (node.getChildren()[index] != null && node.getChildren()[index].isWord) {
+                    String newWord = word + (char) ('a' + index);
+                    if (newWord.length() > longest.length()) {
+                        longest = newWord;
+                    }
+                    findLongest(node.getChildren()[index], newWord);
+                }
+            }
+        }
+
+        private class TreeNode {
+            private boolean isWord;
+            private TreeNode[] children = new TreeNode[26];
+            private int times;
+
+            public boolean isWord() {
+                return isWord;
+            }
+
+            public TreeNode setWord(boolean word) {
+                isWord = word;
+                return this;
+            }
+
+            public TreeNode[] getChildren() {
+                return children;
+            }
+
+            public TreeNode setChildren(TreeNode[] children) {
+                this.children = children;
+                return this;
+            }
+
+            public int getTimes() {
+                return times;
+            }
+
+            public TreeNode setTimes(int times) {
+                this.times = times;
+                return this;
+            }
+        }
+    }
+
+}
diff --git a/Week_04/id_108/LeetCode_746_108.java b/Week_04/id_108/LeetCode_746_108.java
@@ -0,0 +1,27 @@
+import java.util.Arrays;
+
+/**
+ * @author zhangruihao.zhang
+ * @version v1.0.0
+ * @since 2019/05/12
+ */
+public class LeetCode_746_108 {
+
+    class Solution {
+        public int minCostClimbingStairs(int[] cost) {
+            if (cost.length < 2) {
+                return 0;
+            }
+            if (cost.length == 2) {
+                return Math.min(cost[0], cost[1]);
+            }
+
+            int sum[] = Arrays.copyOfRange(cost, 0, cost.length);
+
+            for (int i = 2; i < sum.length; i++) {
+                sum[i] = sum[i] + Math.min(sum[i - 1], sum[i - 2]);
+            }
+            return Math.min(sum[sum.length - 1], sum[sum.length - 2]);
+        }
+    }
+}