Merge pull request algorithm001#696 from GUOSF/master

GeekUniversity · web-flow · commit 556e33f73378 · 2019-05-13T17:22:30.000+08:00
gsf 第四周
diff --git a/Week_04/id_30/LeetCode_169_30.java b/Week_04/id_30/LeetCode_169_30.java
@@ -0,0 +1,64 @@
+package com.shufeng.algorithm4.demo;
+
+import java.util.Random;
+
+/**
+ * @author gsf
+ * @date 2019-05-11 22:41
+ */
+public class LeetCode_169_30 {
+    public static void main(String[] args) {
+        int[] arr = {47,47,72,47,72,47,79,47,12,92,13,47,47,83,33,15,18,47,47,47,47,64,47,65,47,47,47,47,70,47,47,55,47,15,60,47,47,47,47,47,46,30,58,59,47,47,47,47,47,90,64,37,20,47,100,84,47,47,47,47,47,89,47,36,47,60,47,18,47,34,47,47,47,47,47,22,47,54,30,11,47,47,86,47,55,40,49,34,19,67,16,47,36,47,41,19,80,47,47,27};
+        int i = majorityElement(arr);
+        System.out.println(i);
+    }
+
+    public static int majorityElement(int[] nums) {
+        quickSort1(nums, 0, nums.length-1);
+        return nums[nums.length / 2];
+    }
+
+    /**
+     * leetcode 执行和提交 结果不一致，提交代码不过。
+     * 三路快排
+     * 数组根据基数分成三份<、=、>
+     */
+    private static void quickSort1(int[] nums, int l, int r) {
+        if (l >= r) {
+            return;
+        }
+        // 随机数基数
+        int s = new Random().nextInt(nums.length);
+        swap1(nums, l, s);
+        int v = nums[l];
+        // 左分点，分割小于和等于，i左边小v，i~k 等于v
+        int i = l;
+        // 循环点
+        int k = l + 1;
+        // 右分点，右边大于v的数
+        int j = r + 1;
+
+        while (k < j) {
+            if (nums[k] < v) {
+                // 循环数和最左边等于V的数交换
+                swap1(nums, k, i + 1);
+                i++;
+                k++;
+            } else if (nums[k] > v) {
+                swap1(nums, k, j - 1);
+                j--;
+            } else {
+                k++;
+            }
+        }
+        swap1(nums, l, i);
+        quickSort1(nums, l, i - 1);
+        quickSort1(nums, j, r);
+    }
+
+    private static void swap1(int[] arr, int i, int j) {
+        int tem = arr[i];
+        arr[i] = arr[j];
+        arr[j] = tem;
+    }
+}
diff --git a/Week_04/id_30/LeetCode_455_30.java b/Week_04/id_30/LeetCode_455_30.java
@@ -0,0 +1,35 @@
+package com.shufeng.algorithm4.demo;
+
+import java.util.Arrays;
+
+/**
+ * @author gsf
+ * @date 2019-05-12 09:34
+ */
+public class LeetCode_455_30 {
+    public static void main(String[] args) {
+        int[] arr = {1, 2};
+        int[] arr1 = {1,2,3};
+        int i = findContentChildren(arr, arr1);
+        System.out.println(i);
+    }
+
+    public static int findContentChildren(int[] g, int[] s) {
+        Arrays.sort(g);
+        Arrays.sort(s);
+        int i = g.length - 1;
+        int j = s.length - 1;
+        int k = 0;
+        while (j >= 0 && i >= 0) {
+            if (g[i] > s[j]) {
+                i--;
+                continue;
+            }
+
+            j--;
+            i--;
+            k++;
+        }
+        return k;
+    }
+}
diff --git a/Week_04/id_30/LeetCode_720_30.java b/Week_04/id_30/LeetCode_720_30.java
@@ -0,0 +1,82 @@
+package com.shufeng.algorithm4.demo;
+
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * @author gsf
+ * @date 2019-05-09 14:16
+ */
+public class LeetCode_720_30 {
+
+    public static void main(String[] args) {
+//        String[] words = {"w", "wo", "wor", "worl", "world"};
+//        String[] words = {"a", "banana", "app", "appl", "ap", "apply", "apple"};
+        String[] words = {"b", "br", "bre", "brea", "break", "breakf", "breakfa", "breakfas", "breakfast", "l", "lu", "lun", "lunc", "lunch", "d",
+                "di", "din", "dinn", "dinne", "dinner"};
+        String s = longestWord(words);
+        System.out.println(s);
+    }
+
+
+    public static String longestWord(String[] words) {
+        Node node = new Node(true);
+        for (int i = 0; i < words.length; i++) {
+            add(node, words[i]);
+        }
+        String str = "";
+        for (String word : words) {
+            if (find(node, word) && (word.length() > str.length() || word.length() == str.length() && word.compareTo(str) < 0)) {
+                str = word;
+            }
+        }
+        return str;
+    }
+
+    private static class Node {
+        // 是单词
+        private boolean isword;
+        // 每个字符有多个子字符
+        private Map<Character, Node> next;
+
+        public Node(boolean isword) {
+            this.isword = isword;
+            this.next = new HashMap<>();
+        }
+
+        public Node() {
+            this(false);
+        }
+    }
+
+    /**
+     * 查询字符串是否每加个字符都有
+     */
+    public static boolean find(Node node, String word) {
+        for (int i = 0; i < word.length(); i++) {
+            char c = word.charAt(i);
+            if (node.next.get(c) == null || !node.isword) {
+                return false;
+            }
+            node = node.next.get(c);
+        }
+
+        return true;
+    }
+
+    public static void add(Node node, String word) {
+
+        for (int i = 0; i < word.length(); i++) {
+            char c = word.charAt(i);
+            if (node.next.get(c) == null) {
+                node.next.put(c, new Node());
+            }
+            node = node.next.get(c);
+        }
+        if (!node.isword) {
+            node.isword = true;
+        }
+    }
+
+}
diff --git a/Week_04/id_30/LeetCode_746_30.java b/Week_04/id_30/LeetCode_746_30.java
@@ -0,0 +1,23 @@
+package com.shufeng.algorithm4.demo;
+
+/**
+ * @author gsf
+ * @date 2019-05-12 11:03
+ */
+public class LeetCode_746_30 {
+    public static void main(String[] args) {
+        int[] cost = {10, 15, 20};
+//        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
+        int i = minCostClimbingStairs(cost);
+        System.out.println(i);
+
+    }
+
+    public static int minCostClimbingStairs(int[] cost) {
+
+        for (int i = 2; i < cost.length; i++) {
+            cost[i] = Math.min(cost[i - 1], cost[i - 2]) + cost[i];
+        }
+        return Math.min(cost[cost.length - 1], cost[cost.length - 2]);
+    }
+}
diff --git a/Week_04/id_30/LeetCode_784_30.java b/Week_04/id_30/LeetCode_784_30.java
@@ -0,0 +1,44 @@
+package com.shufeng.algorithm4.demo;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * @author gsf
+ * @date 2019-05-12 10:04
+ */
+public class LeetCode_784_30 {
+    public static void main(String[] args) {
+
+        String str = "a1b2";
+//        char c = 'A';
+//        System.out.println((int) c);
+//        System.out.println(c);
+        List<String> list = letterCasePermutation(str);
+        System.out.println(list);
+    }
+
+    public static List<String> letterCasePermutation(String S) {
+        List<String> list = new ArrayList<>();
+        char[] chars = S.toCharArray();
+        letterCasePermutation(list, chars, "");
+        return list;
+    }
+
+    public static void letterCasePermutation(List<String> list, char[] chars, String str) {
+        if (chars.length == str.length()) {
+            list.add(str);
+            return;
+        }
+
+        char c = chars[str.length()];
+        String s = String.valueOf(c);
+
+        if (c >= 'A' && c <= 'z') {
+            letterCasePermutation(list, chars, str + s.toLowerCase());
+            letterCasePermutation(list, chars, str + s.toUpperCase());
+        } else {
+            letterCasePermutation(list, chars, str + s);
+        }
+    }
+}
