add some greedy

JasonHub5 · JasonHub5 · commit 5f3b753470c7 · 2019-12-27T17:28:34.000+08:00
diff --git a/src/main/java/greedy/ActivityProblem.java b/src/main/java/greedy/ActivityProblem.java
@@ -0,0 +1,37 @@
+/*
+设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。
+每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。
+若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。
+
+活动安排问题： 要在所给的活动集合中选出最大的相容活动子集合。
+
+活动安排问题的关键是如何按照一定的顺序安排活动，使得选出的活动间相容并能安排尽量多的活动。
+
+例：
+设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：
+
+ */
+
+package greedy;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class ActivityProblem {
+    public static List<int[]> activityProblem(List<int[]> activities) {
+        List<int[]> result = new ArrayList<>();
+        activities.sort((x, y) -> {
+            return x[1] - y[1];
+        });
+        result.add(activities.get(0));
+        int[] pre = activities.get(0);
+        for (int i = 1; i < activities.size(); i++) {
+            int[] act = activities.get(i);
+            if (act[0] > pre[1]) {
+                result.add(act);
+                pre = act;
+            }
+        }
+        return result;
+    }
+}
diff --git a/src/main/java/greedy/AssignCookies.java b/src/main/java/greedy/AssignCookies.java
@@ -0,0 +1,49 @@
+/*
+455. 分发饼干
+假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
+对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。
+如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
+
+注意：
+你可以假设胃口值为正。
+一个小朋友最多只能拥有一块饼干。
+
+示例 1:
+输入: [1,2,3], [1,1]
+输出: 1
+
+解释:
+你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
+虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
+所以你应该输出1。
+示例 2:
+
+输入: [1,2], [1,2,3]
+输出: 2
+解释:
+你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
+你拥有的饼干数量和尺寸都足以让所有孩子满足。
+所以你应该输出2.
+ */
+package greedy;
+
+import java.util.Arrays;
+
+public class AssignCookies {
+    public int findContentChildren(int[] grid, int[] size) {
+        if (grid == null || size == null) {
+            return 0;
+        }
+        Arrays.sort(grid);
+        Arrays.sort(size);
+        int gi = 0;
+        int si = 0;
+        while (gi < grid.length && si < size.length) {
+            if (size[si] >= grid[gi]) {
+                gi++;
+            }
+            si++;
+        }
+        return gi;
+    }
+}
diff --git a/src/main/java/greedy/FindPlatForm.java b/src/main/java/greedy/FindPlatForm.java
@@ -0,0 +1,59 @@
+/*
+火车站台数量问题
+假设已知某个火车站的所有过往列车的到达arrival和离开departure时间（同一天），如果要求所有列车都不等待直接进站，问至少需要多少个站台。
+无需考虑晚点等特殊情况。
+
+例如，
+Input：
+到达时间： arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
+离开时间： dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
+
+Output：
+3 （最多有3辆列车同时进站（在11:00到11:20之间））
+ */
+package greedy;
+
+import java.util.Arrays;
+
+public class FindPlatForm {
+    public static int findPlatform(int arr[], int dep[], int n) {
+        Arrays.sort(arr);
+        Arrays.sort(dep);
+
+        int result = 1;
+        int currNeed = 1;
+        int j = 0;
+        for (int i = 1; i < arr.length; i++) {
+            currNeed++;
+            if (arr[i] > dep[j]) {
+                while (j <= i && dep[j] < arr[i]) {
+                    currNeed--;
+                    j++;
+                }
+            }
+            result = Math.max(currNeed, result);
+        }
+        return result;
+    }
+
+    public static int findPlatform2(int arr[], int dep[], int n) {
+        Arrays.sort(arr);
+        Arrays.sort(dep);
+
+        int result = 0;
+        int currNeed = 0;
+        int i = 0;
+        int j = 0;
+        while (i < n && j < n) {
+            if (arr[i] < dep[j]) {
+                currNeed++;
+                i++;
+                result = Math.max(result, currNeed);
+            } else {
+                currNeed--;
+                j++;
+            }
+        }
+        return result;
+    }
+}
diff --git a/src/main/java/greedy/FindSmallest.java b/src/main/java/greedy/FindSmallest.java
@@ -0,0 +1,64 @@
+/*
+How to find the smallest number with given digit sum s and number of digits d?
+Examples :
+
+Input  : s = 9, d = 2
+Output : 18
+There are many other possible numbers
+like 45, 54, 90, etc with sum of digits
+as 9 and number of digits as 2. The
+smallest of them is 18.
+
+Input  : s = 20, d = 3
+Output : 299
+ */
+package greedy;
+
+public class FindSmallest {
+    public static int findSmallest(int sum, int m) {
+        int result = 0;
+        int curr = 1;
+        while (sum > 0 && curr <= m) {
+            for (int i = 1; i <= 9; i++) {
+                if (sum - i <= (m - curr) * 9) {
+                    result += i * (int) Math.pow(10, (m - curr));
+                    sum -= i;
+                    break;
+                }
+            }
+            curr++;
+        }
+        return result;
+    }
+
+    /**
+     * 贪心算法
+     * @param sum
+     * @param m
+     * @return
+     */
+    public static int findSmallest2(int sum, int m) {
+        if (m <= 0) {
+            return -1;
+        }
+
+        if (sum > m * 9) {
+            return -1;
+        }
+
+        //预留1 给最高位
+        int result = 0;
+        sum -= 1;
+        for (int i = m - 1; i > 0; i--) {
+            if (sum >= 9) {
+                result += 9 * (int) Math.pow(10, (m - i - 1));
+                sum -= 9;
+            } else {
+                result += sum * (int) Math.pow(10, (m - i - 1));
+                sum = 0;
+            }
+        }
+        result += (1 + sum) * (int) Math.pow(10, m - 1);
+        return result;
+    }
+}
diff --git a/src/main/java/greedy/GasStation.java b/src/main/java/greedy/GasStation.java
@@ -0,0 +1,64 @@
+/*
+134. 加油站
+在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
+
+你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
+
+如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
+
+说明: 
+
+如果题目有解，该答案即为唯一答案。
+输入数组均为非空数组，且长度相同。
+输入数组中的元素均为非负数。
+示例 1:
+
+输入:
+gas  = [1,2,3,4,5]
+cost = [3,4,5,1,2]
+
+输出: 3
+
+解释:
+从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
+开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
+开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
+开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
+开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
+开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
+因此，3 可为起始索引。
+示例 2:
+
+输入:
+gas  = [2,3,4]
+cost = [3,4,3]
+
+输出: -1
+
+解释:
+你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
+我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
+开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
+开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
+你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
+因此，无论怎样，你都不可能绕环路行驶一周。
+
+ */
+package greedy;
+
+public class GasStation {
+    public int canCompleteCircuit(int[] gas, int[] cost) {
+        int total = 0;
+        int curr = 0;
+        int start = 0;
+        for (int i = 0; i < gas.length; i++) {
+            total += gas[i] - cost[i];
+            curr += gas[i] - cost[i];
+            if (curr < 0) {
+                curr = 0;
+                start = i + 1;
+            }
+        }
+        return total >= 0 ? start : -1;
+    }
+}
diff --git a/src/main/java/greedy/JumpGame.java b/src/main/java/greedy/JumpGame.java
@@ -0,0 +1,34 @@
+/*
+55. 跳跃游戏
+给定一个非负整数数组，你最初位于数组的第一个位置。
+
+数组中的每个元素代表你在该位置可以跳跃的最大长度。
+
+判断你是否能够到达最后一个位置。
+
+示例 1:
+
+输入: [2,3,1,1,4]
+输出: true
+解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
+示例 2:
+
+输入: [3,2,1,0,4]
+输出: false
+解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
+ */
+package greedy;
+
+public class JumpGame {
+    public static boolean canJump(int[] nums) {
+        int need = 1;
+        for (int i = nums.length - 2; i > 0; i--) {
+            if (nums[i] >= need) {
+                need = 1;
+            } else {
+                need++;
+            }
+        }
+        return nums[0] >= need;
+    }
+}
diff --git a/src/main/java/greedy/MinCoins.java b/src/main/java/greedy/MinCoins.java
@@ -0,0 +1,30 @@
+/*
+用给定的几种钱币凑成某个钱数
+例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑  15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。
+显然，最少需要2个钱币才能凑成15元
+
+ */
+
+package greedy;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+public class MinCoins {
+    private static int[] coins = {1, 2, 5, 10, 20, 50, 100};
+
+    public static List<Integer> minCoins(int target) {
+        List<Integer> result = new ArrayList<>();
+        int index = coins.length - 1;
+        while (target != 0) {
+            if (target - coins[index] >= 0) {
+                result.add(coins[index]);
+                target = target - coins[index];
+            } else {
+                index--;
+            }
+        }
+        return result;
+    }
+}
diff --git a/src/main/java/greedy/MinimumSum.java b/src/main/java/greedy/MinimumSum.java
@@ -0,0 +1,25 @@
+package greedy;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+public class MinimumSum {
+    public static int minimumSum(int[] nums) {
+        if (nums == null || nums.length == 0) {
+            return 0;
+        }
+        int num1 = 0;
+        int num2 = 0;
+        //排序 ---> 这步可以用堆来做 O(n)
+        Arrays.sort(nums);
+        for (int i = 0; i < nums.length; i++) {
+            if (i % 2 == 0) {
+                num1 = num1 * 10 + nums[i];
+            } else {
+                num2 = num2 * 10 + nums[i];
+            }
+        }
+        return num1 + num2;
+    }
+}
diff --git a/src/main/java/greedy/README.md b/src/main/java/greedy/README.md
@@ -0,0 +1,15 @@
+# 贪心算法
+
+### 练习题
+* [找硬币](MinCoins.java)
+* [活动问题](ActivityProblem.java)
+* [最小的数字问题](FindSmallest.java)
+* [两个数字的最小和](MinimumSum.java)
+* [以最低的成本连接绳索](RopeCost.java)
+* [最小平台数](FindPlatForm.java)
+* [部分背包问题、分蛋糕](AssignCookies.java)
+* 将板子切割成正方形的最小成本
+* 字典中最小的数组
+* [加油站](GasStation.java)
+* [跳跃游戏](JumpGame.java)
+* [摆动序列](WiggleSubsequence.java)
diff --git a/src/main/java/greedy/RopeCost.java b/src/main/java/greedy/RopeCost.java
diff --git a/src/main/java/greedy/WiggleSubsequence.java b/src/main/java/greedy/WiggleSubsequence.java
diff --git a/src/test/java/greedy/CommonTest.java b/src/test/java/greedy/CommonTest.java
